Решение упражнения 2.18 из SICP

24 January, 2008 (21:19) | Решения упражнений

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

Этот подход легко реализуется следующей процедурой:

(define (reverse items)
  (define (reverse-iter source result)
    (if (null? source)
        result
        (reverse-iter (cdr source) (cons (car source) result))))
  (reverse-iter items (list)))

Обратите внимание, что вызов (list) в последней строке строит пустой список. Такой же результат можно получить, если заменить в этом месте (list) на null. Возможно, для обозначения null в других диалектах используется другая запись.

Comments

Pingback from SICP по-русски » Blog Archive » Решение упражнения 2.27 из SICP
Date: January 28, 2008, 10:09 pm

[…] Определение процедуры reverse можно посмотреть в решении упражнения 2.18. […]

Comment from tymmym
Date: May 25, 2008, 3:31 pm

Можно использовать процедуру append, описанную до упражнений:

(define (reverse items)
  (if (null? (cdr items))
      items
      (append (reverse (cdr items)) (list (car items)))))

Comment from null-me
Date: February 21, 2009, 11:55 am

Я сделал так. Хотя решение автора, конечно, и изящнее и эффективнее…

(define (reverse items)
  (define (proc items count)
    (if (> 0 count)
        ()
        (cons (list-ref items count) (proc items (dec count)))))
  (proc items (dec (length items))))

Comment from null-me
Date: February 21, 2009, 11:56 am

(dec - декремент)

Comment from JessicaFletcher
Date: March 7, 2009, 1:25 pm

еще один простой способ -

(define (reverse item)
  (if (= (cdr item) nill)
    (item)
    (cons (reverse (cdr item)) (car item))))

Comment from anonymous
Date: November 29, 2010, 10:28 am

простой и неверный:
‘(((((25) . 16) . 9) . 4) . 1) это вовсе не ‘(25 16 9 4 1)

Comment from Kirill
Date: April 24, 2012, 7:23 pm

Будет верный, если чуть подправить:

(define (reverse item)
  (if (null? (cdr item))
      item
      (append (reverse (cdr item)) (list (car item)))))

Хотя таким образом получается более худший способ, чем описанный в 1 комментарии(достаточно передать пустой список). И все равно, у автора решение лучше: итерация и cons(вычислительная сложность — n), а тут рекурсия и append(вычислительная сложность — n**2, который перебирет каждый раз весь список для вставки значения.

Write a comment