Схема: вернуть все элементы выражения, которые могут быть получены с использованием любой комбинации car и cdr.

Question

Я пытаюсь написать процедуру на схеме (R5RS) моего класса CS, которая принимает выражение (либо символ, либо список) в качестве аргумента, и возвращает список (1) всех возможных выражений, которые могут быть формируется с использованием car и cdr в выражении и (2) и выражении, демонстрирующем, как был получен каждый из этих компонентов исходного выражения. Если часть может быть получена более чем одним способом, она должна быть возвращена более одного раза.

Examples

(pieces '()) => ((() x))

(pieces 'apple) =>  ((apple x))

(pieces '(apple)) => (((apple) x) (apple (car x)) (() (cdr x)))

(pieces '(a (b c))) =>
               (((a (b c)) x)
                (a (car x))
                (((b c)) (cdr x))
                ((b c) (car (cdr x)))
                (b (car (car (cdr x))))
                ((c) (cdr (car (cdr x))))
                (c (car (cdr (car (cdr x)))))
                (() (cdr (cdr (car (cdr x)))))
                (() (cdr (cdr x))))

Так как мы только начали со Scheme, мы ограничены довольно базовым синтаксисом для этого назначения. Вот что у меня есть:

(define pieces
  (lambda (exp)
    (cond
      ((symbol? exp)
       (list exp 'x))
      ((null? exp)
       (list '() 'x))
      ((list? exp)
       (let ((b (pieces (car exp))) (c (pieces (cdr exp))))
          (list exp 'x b c))))))

(pieces '()) => (() x)

(pieces 'apple) => (apple x)

(pieces '(apple)) => ((apple) x (apple x) (() x))

(pieces '(a (b c))) => ((a (b c)) x (a x) (((b c)) x ((b c) x (b x) ((c) x (c x) (() x)))
                       (() x)))

Процедура возвращает все нужные элементы, но каждая рекурсия приводит к тому, что компоненты вкладываются в дополнительный список. Есть ли способ предотвратить это?

Кроме того, я понятия не имею, с чего начать для второй части проблемы (показывающей, как каждый элемент был получен из оригинала с использованием car и cdr). Я пробовал миллион разных подходов, и ни один из них даже близко не работал. Если у кого-нибудь есть какие-либо подсказки или предложения о том, как реализовать эту функцию, я был бы очень признателен. Спасибо за тонну.

Answer 1

(pieces 'apple) => (apple x)

Но это должно быть ((apple x)), верно? Вы должны получить список, где первым и единственным элементом является список (apple x).

Предложения cond, завершающие рекурсию (exp - символ или ноль), возвращают элементы, которые должны быть в списке, в то время как предложение, которое повторяется в car и cdr, пытается создать список элементов. Поскольку pieces может возвращать как элементы, так и списки элементов, довольно сложно составить список элементов из значений, которые возвращаются из него: когда вы делаете (list exp 'x b c), вы не знаете, b и c являются элементами, которые должны войти в список или списки элементов.

Если вы убедитесь, что pieces всегда возвращает список элементов (например, (list (list exp 'x))), это становится намного проще. Когда вы возвращаетесь к car и cdr, вы хотите сделать что-то вроде append списков a и b и добавить в этот список «текущий» ((list exp 'x)) элемент (возможно, с cons или что-то).

Для второй части, pieces должен знать, как он попал к текущему предмету. Вы можете сделать pieces указанием «пути» к текущему элементу в качестве (возможно, необязательного) параметра. Если путь является списком, то при вызове pieces на (car exp) вы можете добавить символ car к пути, который вы отправляете в качестве аргумента, а для (cdr exp) вы можете добавить символ cdr. И затем вы используете путь, чтобы создать что-то хорошее, чтобы заменить 'x в (list exp 'x).

Answer 2

Я знаю, что это не Схема, но, возможно, поможет поиск аналогичного языка. Я сделал это больше, чтобы практиковать себя, так что принимайте это с каплей соли, но кажется, что вы делаете именно то, что вам нужно:

(defun parse-list (whatever)
  (labels ((pieces (expression &optional path)
         (cond
           ((null expression)
        `((,path . nil)))
           ((listp expression)
        (append (list
             `(,path . ,expression))
            (pieces (car expression)
                (cons 'car path))
            (pieces (cdr expression)
                (cons 'cdr path))))
           (t `((,path . ,expression))))))
    (dolist (output (pieces whatever))
      (format t "path ~a => result ~a~&"
          (car output) (cdr output)))))

(parse-list '(a (b c)))

Который затем производит этот вывод:

path NIL => result (A (B C))
path (CAR) => result A
path (CDR) => result ((B C))
path (CAR CDR) => result (B C)
path (CAR CAR CDR) => result B
path (CDR CAR CDR) => result (C)
path (CAR CDR CAR CDR) => result C
path (CDR CDR CAR CDR) => result NIL
path (CDR CDR) => result NIL

Извините, я не могу получить форматирование кода SO лучше, чем это:)