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

Question

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

Часть I запутаться больше всего, когда глубоко реверс вызывается дважды в данный момент
(добавить (глубокий-реверс (СРВ 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

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

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

(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 '())) 

В этой версии глубокой копии используется аккумулятор и рекурсивно хвост.

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

(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

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

Итак:

((1 2) 3 4) 

должен стать

(4 3 (2 1)) 

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