Понимание глубокого обратного

Question

Скажите, у меня есть список '(1 2 3 (4 5 6) 7 8 9). Он должен вернуть (9 8 7 (6 5 4) 3 2 1), используя следующий код ниже. Я пытаюсь понять, как работает этот итеративный процесс. Показывать, как это делается шаг за шагом, было бы очень полезно.

Больше всего я запутался, когда в этот момент дважды вызывается глубокий реверс
(добавить (глубокий обратный (cdr lst)) (список (глубокий обратный (автомобильный lst)))))

Я не знаю, что происходит потом.

(define (deep-reverse lst) 
   (cond ((null? lst) '() ) 
         ((pair? (car lst)) 
          (append 
           (deep-reverse (cdr lst)) 
           (list (deep-reverse (car lst))))) 
         (else 
          (append 
           (deep-reverse (cdr lst)) 
           (list (car lst)))))) 

Answer 1

Ну, я только что ответил что-то вроде этого здесь , но я не особо углублялся в детали глубокого реверса.

Что происходит, когда он переворачивает каждый элемент, который происходит сбыть списком, прежде чем добавлять его в конец списка.Представьте себе, что произойдет, если на машине списка не будет выполнен глубокий реверс: (reverse '(a (b c d) e) is

(list
   'e
   '(b c d)
   'a
)

С глубоким реверсом это будет выглядеть примерно так:

(list
    'e
    (deep-reverse '(b c d))
    'a
)

Это

(list
    'e
    '(d c b)
    'a
)

Вот еще одна версия глубокого реверса, написанная иначе, если это делает ее более понятной.

(define (deep-reverse ls)
  (define (deep-reverse-2 ls acc)
    (if (null? ls)
        acc
        (if (list? (car ls))
            (deep-reverse-2 (cdr ls) (cons (deep-reverse (car ls)) acc));  If adding  a list, reverse it first
            (deep-reverse-2 (cdr ls) (cons (car ls) acc)))))
  (deep-reverse-2 ls '()))

Эта версия глубокого копирования использует аккумулятор иtail recursive.

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

(deep-reverse '(a (b c d) e)) -> '(e (d c b) a)

в обратном алфавитном порядке, несмотря на то, что существует вложенный список.Это оценивается так:

(deep-reverse-2 '(a (b c d) e) '()); Which calls
(deep-reverse-2 '((b c d) e)  '(a)); which is the same as
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(b c d) '()) '(a))); it calls deep-reverse on the list '(b c d) before consing it on.
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(c d)  '(b)) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(d)  '(c b)) '(a)))
(deep-reverse-2 '(e) (cons '(d c b) '(a)))
(deep-reverse-2 '(e)  '((d c b) a))
(deep-reverse-2 '() '(e (d c b) a))
'(e (d c b) a)

Answer 2

Легко, вы не знаете, является ли заголовок целым числом или списком, поэтому вы должны также применить deep-reverse к нему, а затем добавить его к перевернутому хвосту текущего списка.

Итак:

((1 2) 3 4)

должно стать

(4 3 (2 1))

Обратите внимание, как мы должны были повернуть голову И хвост.