LINUX.ORG.RU

Получить список из листьев дерева (scheme)


0

0

Упражнение из SICP:
Написать процедуру fringe, принимающую в качестве аргумента дерево (представленное в виде списка) и возвращает список, элементы которого - все листья дерева, упорядоченные слева направо. Пример:

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

(fringe x)
(1 2 3 4)

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


Моё решение таково:

(define (listed x) (if (pair? x) x (cons x #f)))

(define (listed-all x) (map listed x)) ;;делает все эл-ты списка х списками

(define (merge x) (if (null? x) #f (append (car x) (merge (cdr x))))) ;;объединяет все эл-ты списка в 1 список

(define (tree? x) (cond ((null? x) #f)
                              ((pair? (car x)) #t)
                              (else (tree? (cdr x))))) ;;проверка на дерево

(define (fringe x) (if (not (tree? x)) x (fringe (merge (listed-all x)))))

На каждом шаге короткие ветки дерева "удлиняются" до вел-ны самых длинных, а потом из них "собирается букетик" append-ом. Но что-то мне подсказывает, что этот вариант решения через одно место и слишком громоздкий. Как сделать короче?
★★★★★

Лисп:
(defun fringe (l)
  (if (consp l)
    (if (consp (car l))
        (append (fringe (car l)) (fringe (cdr l)))
        (cons (car l) (fringe (cdr l))))
    nil))

На схему сам переведешь?

yyk ★★★★★
()
Ответ на: комментарий от seiken

t если пара, в противном случае nil

yyk ★★★★★
()
Ответ на: комментарий от grob

Да, так лучше. Соответсвенно на Лиспе:
(defun finger (tree)
  (if (consp tree)
      (apply #'append (mapcar #'finger tree))
      (list tree)))

Только мне связка (apply #'append (mapcar не нравится... Выглядит уж очень банально. Может можно еще короче?

yyk ★★★★★
()
Ответ на: комментарий от grob

foldr? Не знаю, там есть что-то про fold-right и fold-left, но уже после этого упражнения. В любом случае, как я понимаю, в lisp существует множество различных решений одной и той же задачи.

seiken ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.