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

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

Процедура fringe будет производить обход дерева в глубину слева направо и собирать узлы в порядке обхода в один список. Ее структура очень похожа на структуру count-leaves. При рассмотрении каждого узла также рассматриваются три случая: пустое дерево, листовой элемент и нелистовой элемент (поддерево).

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

Получаем такую процедуру:

(define (fringe tree) 
  (cond ((null? tree) ()) 
        ((pair? tree) (append (fringe (car tree)) 
                      (fringe (cdr tree)))) 
        (else (list tree))))

Она генерирует необходимый результат.

Comments

Comment from meduza
Date: October 25, 2008, 6:50 pm

Блин, так просто, а я намудрил…

(define (fringe lst)
  (define (f lst acc)
    (cond ((null? lst) acc)
          ((not (list? lst)) (cons lst acc))
          (else (append (f (car lst) acc) (f (cdr lst) acc)))))
  (f lst (list)))

но работает :)

Comment from qMax
Date: January 16, 2009, 6:25 am

итеративная версия:

(define (fringe tree)
  (define (fringe-elem elem)
    (cond ((null? elem) '())
          ((pair? elem) (fringe elem))
          (else (list elem))))
  (define (iter src res)
    (if (null? src)
        res
        (iter (cdr src)
              (append res (fringe-elem (car src))))))
  (iter tree '()))

Comment from qMax
Date: January 16, 2009, 6:26 am

пардон…

(define (fringe tree)
  (define (fringe-elem elem)
    (cond ((null? elem) '())
          ((pair? elem) (fringe elem))
          (else (list elem))))
  (define (iter src res)
    (if (null? src)
        res
        (iter (cdr src)
              (append res (fringe-elem (car src))))))
  (iter tree '()))

Comment from JessicaFletcher
Date: March 18, 2009, 10:15 am

(define (fring list)
 (cond (= (list null) null)
       ((notlist? list) list)
 (else (cons (fring (car list) fring (cdr list)))))

Comment from alex
Date: October 21, 2010, 8:55 am

Если не ошибаюсь, процедура append при каждом вызове “проходит” по результирующему списку от начала до текущего “хвоста”. Тогда реализация Сергея не слишком эффективна. У меня такой вариант:

(define (fringe li)
  (define (fringe-leave leave root)
    (if (null? leave)
        (if (null? root)
            '()
            (fringe-leave (car root) (cdr root)))
        (if (pair? (car leave))
            (fringe-leave (car leave) (cons (cdr leave) root))
            (cons (car leave) (fringe-leave (cdr leave) root)))))
(fringe-leave (car li) (cdr li)))

Опыта у меня совсем мало, могу ошибаться относительно append. Если это так, поправьте, пожалуйста.

Comment from Farmer
Date: March 28, 2011, 7:51 pm

Элегантное решение получилось при использовании абстракции thor’a – process-tree:

(define (fringe tree)
    (process-tree append list (list) tree))

Comment from alchimik
Date: September 12, 2013, 9:16 am

А мне мой решение больше нравится, т.к. не используется ни car, ни cdr. Моя функция работает со списками и не опускается до уровня пар.

(define (fringe items)
  (cond ((null? items) (list))
        ((list? items) (foldl append (list) (map fringe items)) )
        (else (list items))))

Comment from Rokker Ruslan
Date: February 8, 2014, 7:44 am

(define (flat x)
  (cond ((null? x) (list))
        ((not (pair? x)) (list x))
        (else (append (flat (car x))
                      (flat (cdr x))))))

Comment from Irv
Date: January 31, 2016, 12:09 pm

Согласен с alex про append (по крайней мере в той реализации, которая приведена в книге).

(define (fringe tree)
  (define (iter source target)
    (if (null? source)
        target
        (iter 
         (cdr source)
         (let ((i (car source)))
           (if (pair? i)
               (iter i target)
               (cons i target))))))
  (reverse (iter tree (list))))

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

Write a comment