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

28 January, 2008 (22:05) | Решения упражнений

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

В определении deep-reverse все остается прежним, кроме того, что при переносе очередного элемента из исходного списка в результирующий мы “реверсируем” этот элемент (процедура reverse-it). Реверсирование элемента для списка означает deep-reverse для него, а реверсирование атомарного значения (не списка) возвращает само это значение.

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

Подход “глубоких” (deep) операций в противовес поверхностным широко применяется в разработке программ. Как правило речь идет именно об операциях над данными древовидной структуры. Поверхностный подход затрагивает лишь данные верхнего уровня иерархии, в то время как глубокий касается всех уровней.

Comments

Comment from tymmym
Date: May 27, 2008, 10:53 am

(define (deep-reverse items)
  (define (rev items res)
    (cond ((null? items) res) 
          ((not (pair? items)) items)
          (else (rev (cdr items) (cons (rev (car items) (list)) res)))))
  (rev items (list)))

Comment from JessicaFletcher
Date: March 17, 2009, 12:37 pm

(define (d-reverse item)
  (cond ((= (cdr item) null) item)
        ((notpair? (car item)) item)
        (else (cons (d-reverse (cdr item)) (d-reverce (car item))))))

Comment from anonymous
Date: November 29, 2010, 4:50 pm

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

Comment from anonymous
Date: November 29, 2010, 4:52 pm

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

Comment from njgfkmnj
Date: January 24, 2011, 9:16 pm

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

(define (deep-reverse x)
  (cond ((null? x) x)
	((not (pair? x)) x)
	(else (append (deep-reverse (cdr x))
		      (list (deep-reverse (car x)))))))

очень хотелось бы избавится от append и list от одного элемента, но все решения какие то не изящные.

Comment from rsp
Date: August 18, 2011, 6:52 pm

(define (deep-reverse l)
  (reverse (map reverse l)))

Comment from alchimik
Date: September 12, 2013, 8:23 am

(define (deep-reverse items)
  (if (or (null? items) (notpair? items)) 
      items
      (reverse (map deep-reverse items))))

Comment from фыав
Date: April 28, 2014, 4:20 pm

(define (deep-reverse li)
  (if (pair? li) 
      (reverse (map deep-reverse li))
      li))

Comment from Irv
Date: January 31, 2016, 10:19 am

(define (deep-reverse items)
  (define (iter source target)
    (if (null? source)
        target
        (iter 
         (cdr source)
         (let ((i (car source)))
           (cons 
            (if (pair? i) 
                (deep-reverse i) 
                i) 
            target)))))
  (iter items (list)))

(reverse (list 1 (list 2 3) 4 5 (list 6 7 (list 8 9))))

Comment from Ilyas
Date: February 1, 2016, 2:33 am

(define (deep-reverse items)
  (define (rec result)
    (cond ((null? result)
           '())
          ((pair? (car result))
           (cons (reverse (car result)) (rec (cdr result))))
          (else
           (cons (car result)) (rec (cdr result)))))
  (rec (reverse items)))

Write a comment