Добавление обратного списка в Схеме

Question

Я изучаю Scheme и хотел написать рекурсивную программу, которая переворачивает заданный список.

Однако в одном тестовом случае я заметил, что a (b c) e -> e (b c) a,

То, что я пытаюсь получить, это a (b c) e -> e (c b) a,

Вот что у меня есть:

(define (deep-reverse lst)
(if (null? lst)
  '()
  (begin
    (display (car lst))
    (display "\n")
    (if (null? (cdr lst))
        '()
        (append (deep-reverse (cdr lst)) (list (reverse (car lst))))
        ) //End of inner if
))) //End of begin, outer if, define  

Когда я пытаюсь запустить код с

(глубокий обратный '(1 (b c) (a b)))

Я получил:

1
(b c)
(a b)
mcdr: contract violation
expected: mpair?
given: 1

Вопрос с (list (reverse (car lst))), хотя в изолированном тестовом случае все работает нормально. Что приводит меня к мысли, что проблема, возможно, связана с дополнением.

Заранее спасибо.

Редактировать: Исходя из (list (reverse (car lst))) в (reverse (list(car lst))) заставляет код работать без ошибок, но не переворачивает (a b) в (b a),

Answer 1

Как объясняется в сообщении об ошибке, ваша проблема в том, что вы пытаетесь изменить номер. Во-первых, давайте удалим некоторые из ненужных условий и средств отладки в вашей программе, придя к этой более простой программе. Давайте пройдемся по этой программе, чтобы увидеть, что происходит:

(define (deep-reverse lst)
  (if (null? lst)
      '()
      (append (deep-reverse (cdr lst)) (list (reverse (car lst))))))

Начнем с

(deep-reverse '(1 (b c) (a b)))

Подставляя аргумент, мы получаем

(if (null? '(1 (b c) (a b)))
    '()
    (append (deep-reverse (cdr '(1 (b c) (a b))))
            (list (reverse (car '(1 (b c) (a b)))))))

Потому что условие #fэто упрощает

(append (deep-reverse (cdr '(1 (b c) (a b))))
                (list (reverse (car '(1 (b c) (a b))))))

Чтобы оценить первый аргумент, сначала найдите cdrи позвоните deep-reverse на что. Я пропущу шаги здесь, но вы легко сможете проверить, что он работает правильно.

(append '((b a) (c b)) (list (reverse (car '(1 (b c) (a b))))))

Далее мы оцениваем car:

(append '((b a) (c b)) (list (reverse 1)))

И здесь мы видим, в чем проблема: мы не можем перевернуть ни одного числа!

Проблема в том, что ваш deep-reverse должно иметь два различных рекурсивных поведения:

• с числом, или символом, или другим объектом, не включенным в список, ничего не делать, потому что нет смысла менять число на обратное
• в списке, глубоко изменить его

Есть две причины, почему ваша текущая программа не делает это должным образом:

• это только делает мелкий реверс на элементах списка; то есть он не будет глубоко повернуть вспять '(((a b) (c d)) ((e f) (g h))) правильно
• это терпит неудачу, если это когда-либо встречает число или другой не список, как символ

Простое решение - добавить условие, чтобы проверить, является ли это pair? сначала, прежде чем пытаться повернуть вспять. Если это не pair?, затем lst должен быть nil (который мы можем оставить как есть) или объект не из списка (который мы также можем оставить как есть)

(define (deep-reverse lst)
  (if (pair? lst)
      (append (deep-reverse (cdr lst)) (list (deep-reverse (car lst))))
      lst))

Наконец, я должен отметить, что шаблон, который мы здесь используем, действительно foldr шаблон. Мы можем абстрагировать эту модель с foldr:

(define (deep-reverse xs)
  (cond ((pair? xs)
         (foldr (lambda (x y) (append y (list (deep-reverse x)))) '() xs))
        (else xs)))

Но отметим также, что это неэффективно, потому что append это дорогая операция. Изменение алгоритма на хвостовой рекурсивный дает понять, что это на самом деле foldl:

(define (deep-reverse xs)
  (cond ((pair? xs)
         (foldl (lambda (x y) (cons (deep-reverse x) y)) '() xs))
        (else xs)))

как такая функция может быть написана в типичной идиоматической схеме, или как указал Уилл Несс,

(define (deep-reverse xs)
  (cond ((pair? xs) (reverse (map deep-reverse xs)))
        (else xs)))