Производя глубокий-обратная процедура


Упражнения 2.27

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

(define x (list (list 1 2) (list 3
4)))

x ((1 2) (3 4))

(reverse x) ((3 4) (1 2))

(deep-reverse x) ((4 3) (2 1))

Я написал следующее:

(define (deep-reverse lis)
  (define (snoc elem lis)
    (if (null? lis) 
        (cons elem lis)
        (cons (car lis) (snoc elem (cdr lis)))))
  (cond ((null? lis) lis)
        ((pair? (car lis)) (snoc (deep-reverse (car lis)) (deep-reverse (cdr lis))))
        (else (snoc (car lis) (deep-reverse (cdr lis))))))

(define a (list 1 2 3 4 5 (list 1 2 3 4) (list 5 6 7 8)))

Что вы думаете?



972
0
задан 7 апреля 2011 в 04:04 Источник Поделиться
Комментарии
1 ответ

Основная проблема с использованием snoc (или добавьте, что ваш snoc эффективны) заключается в том, что каждый вызов является o(n) времени. Это делает вашу функцией o(N2), которая является (каламбур) весьма проблематичным.

Вот мой О(N) реализации, что хвост-рекурсивной по Удус:

(define (deep-reverse l)
(let loop ((x l)
(r '()))
(cond ((null? x) r)
((pair? x) (loop (cdr x) (cons (deep-reverse (car x)) r)))
(else x))))

Вот еще более короткий вариант, используя фолд (также хвост-рекурсивный вдоль цхды):

(define (deep-reverse l)
(define (iter x y)
(cons (if (pair? x) (deep-reverse x) x) y))
(fold iter '() l))

Для еще большего удовольствия, либо разворачиваться-правая версия (также хвост-рекурсивной по Удус); требуется составить , а также:

(define (deep-reverse l)
(define (iter x)
(if (pair? x) (deep-reverse x) x))
(unfold-right null? (compose iter car) cdr l))

2
ответ дан 7 апреля 2011 в 05:04 Источник Поделиться