Разработать процедуру для обратного список


Упражнения SICP 2.18 просит следующее:

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

(reverse (list 1 4 9 16 25))
(25 16 9 4 1)

Я написал эту итерационную функцию:

(define (reverse n)
  (define (iter a b)
    (if (null? a) b
        (iter (cdr a) (cons (car a) b))))
  (iter n null))

Я не мог придумать способ сделать это рекурсивно. Есть ли лучший способ, чтобы написать эту функцию? Можно ли сделать это рекурсивно?



5914
1
задан 5 апреля 2011 в 05:04 Источник Поделиться
Комментарии
2 ответа

Вот рекурсивное определение обратного (по имени Ред.), который использует примитивы (авто/ЦДР/минусы) и внутренний определение snoc (обратный свод):

(define (rev lis)
(define (snoc elem lis)
(if (null? lis)
(cons elem lis)
(cons (car lis) (snoc elem (cdr lis)))))
(if (null? lis)
lis
(snoc (car lis) (rev (cdr lis)))))

Очевидно, это определение не означало, чтобы быть эффективным. =)

1
ответ дан 5 апреля 2011 в 07:04 Источник Поделиться

Не сильно отличается от вашей, и неаккуратный со списком механика (идентификатор, как правило, предпочитают использовать минусы за добавление)

> (define (rev l)
(if (null? (cdr l))
l
(append (rev (cdr l)) (list (car l)))))
> (rev '(1 2 3 4))
(4 3 2 1)

Это, с другой стороны, мне нравится

(define (rev l) (foldr (lambda (a b) (append b (list a))) l '()))

0
ответ дан 5 апреля 2011 в 06:04 Источник Поделиться