схема расширения функции

Question

Я пытался решить эту проблему часами. Функция расширения, которая берет список элементов и частот и разворачивает их в простой список. Например, результат (развернуть '(a (3 b) (3 a) b (2 c) (3 a)) должен быть (a b b b a a a b c c a a a)

Вот мое решение:

---

вспомогательная функция:

(define (expandHelper n value)
  (if (= 0 n) 
      '()
      (cons (append (cons value '()))(expandHelper (- n 1) value)))) 

---

функция расширения

(define (expand lst) 
  (cond ((null? lst) '())
    (else (expandHelper (car lst) (cadr lst)))))

---

Но это не делает то, что я ожидал. Он ищет целое число, когда список имеет только один элемент, который является значением. Например, (раскрыть '(a (2 b)). Поскольку существует только одна копия a, в выражении отсутствует (1 a). Я новичок в Scheme. Я был бы очень признателен, если бы вы могли помоги мне.

Спасибо

Вот обновленная версия: Но это все еще не правильно. Я был бы очень признателен, если бы кто-нибудь помог мне изменить мой код, чтобы получить правильные результаты.

;; helper function
(define (expandHelper value)
  (if (= 0 value) 
      '()
      (cons (append (cons (car sublist) '()))(expandHelper (- (car sublist) 1) (car sublist)))))  

;; the expand function
(define (expand lst) 
  (cond ((null? lst) '())
        (else (list? (car lst)) (expandHelper (car lst)) (expand (cadr lst)))))

Answer 1

Вы можете выразить это как правую складку и избежать разработки пользовательской рекурсивной функции Если следующий элемент - это список типа (3 a), разверните и добавьте его. Если символ, просто cons это.

(define (expand xs)
  (fold-right
   (lambda (x result)
     (if (list? x)
     (append (apply make-list x) result)
         (cons x result)))
   '()
   xs))

Answer 2

Это было бы мое решение, без какой-либо вспомогательной функции, и повторение в подсписке (т.е. (3 a) становится (cons a (expand '(2 a)))):

#lang racket

(define (expand lst)
  (cond
    ((null? lst) '())
    ((list? (car lst))
     (let ((cnt (caar lst)) (chr (cadar lst)))
       (if (= cnt 0)
           (expand (cdr lst))
           (cons chr (expand (cons (list (- cnt 1) chr) (cdr lst)))))))
    (else (cons (car lst) (expand (cdr lst))))))

Answer 3

(define (term-expander n val partial)
  (if (zero? n)
    partial
    (term-expander (- n 1) val (cons val partial))))

(define (append-expand a b)
  (if (pair? b)
    (append a (term-expander (car b) (cadr b) '()))
    (append a (list b))))

(define (expand l) (foldl append-expand l '() ))

> (expand '(a (3 b) (3 a) b (2 c) (3 a)))
(a b b b a a a b c c a a a)

Итак ... term-expander занимает (5 a) -> '(a a a a a)'.append-expand добавит новый термин (расширенный, если это пара) к нашему ответу в процессе.просто нужно свернуть это по списку.

Я надеюсь, что у вас уже есть foldl, но вот мое на всякий случай.

(define (foldl op seq init)
  (define (iter acc rest)
    (if (null? rest)
      acc
      (iter (op acc (car rest)) (cdr rest))))
  (iter init seq))

---

РЕДАКТИРОВАТЬ

Поняв, что потом это можно сделать немного более естественно с foldr, а не foldl (потребуется append-expand, написанный иначе).Почему вы не видите, можете ли вы найти это?В основном та же идея, но она будет работать со списком «спереди назад» и более естественным образом подойдет для cons структур

---

Вот я делаю это без сгиба, но это работает так же, и я недействительно заботьтесь об этом

(define (term-expander p partial)
  (if (zero? (car p))
    partial
    (term-expander (cons (- (car p) 1) (cdr p)) (cons (cadr p) partial))))

(define (expand l)
  (define (expand-rec l partial)
    (if (null? l)
      partial
      (let ((t 
        (if (pair? (car l))
             (term-expander (car l) '())
             (list (car l)))))
      (expand-rec (cdr l) (append partial t)))))
  (expand-rec l '()))

> (expand '(a (3 b) (3 a) b (2 c) (3 a)))
(a b bb a a a b c c a a a)

Если вы предпочитаете, секция (if (pair?... может вместо этого перейти к term-expander, и тогда вы просто позвоните через доску.Я немного предпочитаю этот способ, но все равно

Answer 4

 (define (expand l)
   (cond ((null? l) '())
         ((not (pair? (car l))) (cons (car a) (expand (cdr l)))
         ((< (caar l) 1) (expand (cdr l)))
         (else (cons (cadar l)) (expand (cons (cons (- (caar l) 1) (cdar l))
                                                (cdr l))))))

Answer 5

Здесь нужно подумать о двух вещах.Первый - тот, который вы упомянули - у вас может быть либо a, либо (1 a), что означает одно и то же.Возможно, вы захотите переместить это в expandHelper, чтобы оно выглядело больше как (expandHelper value), а затем вам нужно включить, является ли он списком или символом.

Второе - то, как вы звоните expandHelper.Если вы добавите в список, например, от '(a (3 b) (3 a) b (2 c) (3 a)) до expand, в данный момент он будет вызывать (expandHelper a (3 b)), что, вероятно, не то, что вы имели в виду.Вместо этого вы должны убедиться, что вы вызываете expandHelper для каждого элемента списка и cons вместе с результатами.Вы можете сделать это, вызвав expandHelper в первом элементе списка, а затем рекурсивно вызвав expand в оставшейся части списка.

Я не проверял, чтобы это компилировалось, простообщая идея:

(define (expandHelper value)
    (if (list? value) ;; means value is something like (2 a)

        (if (= 0 (car value)) ;; then (car value) is 2
            '() ;; if it's zero, we complete the list and return!
            (cons (cadr value) ;;otherwise, we append (cadr value) = a to...
                  (expandHelper (cons (- (car value) 1) (cadr value))))))
                  ;; the result of expand helper on (- (car value) 1) = 1 
                  ;; and (cadr value) = a

         (cons value '()))) ;; if it's not a list, we should just return the value.