Найти все пути от корня к листьям дерева в схеме

Учитывая дерево, я хочу найти пути от корня к каждому листу.

Итак, для этого дерева:

    D
   /
  B
 / \ 
A   E
 \
  C-F-G

имеет следующие пути от корня (A) к листьям (D, E, G):

(A B D), (A B E), (A C F G)

Если я представлю дерево выше как (A (B D E) (C (F G))), тогда функция g сделает свое дело:

(define (paths tree)
  (cond ((empty? tree)
         '())
        ((pair? tree)
         (map (lambda (path)
                (if (pair? path)
                    (cons (car tree) path)
                    (cons (car tree) (list path))))
              (map2 paths (cdr tree))))
        (else
         (list tree))))

(define (map2 fn lst)
  (if (empty? lst)
      '()
      (append (fn (car lst))
              (map2 fn (cdr lst)))))

Но все это выглядит неправильно. Мне не приходилось думать об этом какое-то время, но я чувствую, что должен быть более аккуратный способ сделать это. Любые идеи для лучшего решения (на любом языке) будут оценены.

РЕДАКТИРОВАТЬ. Сопоставление решения Svante со схемой дает:

(define (paths tree)
  (if (pair? tree)
      (append-map (lambda (node)
              (map (lambda (path)
                     (cons (car tree) path))
                   (paths node)))
            (cdr tree))
      (list (list tree))))

который намного аккуратнее, чем мой оригинал.


lisp scheme racket
person grifaton    schedule 10.06.2010    source источник

Ответы (4)


arrow_upward
3
arrow_downward

Я лучше владею Common Lisp.

(defun paths (tree)
  (if (atom tree)
      (list (list tree))
      (mapcan (lambda (node)
                (mapcar (lambda (path)
                          (cons (car tree) path))
                        (paths node)))
              (cdr tree))))

CL-USER> (paths '(A (B D E) (C (F G))))
((A B D) (A B E) (A C F G))
person Svante    schedule 11.06.2010
comment
Это намного аккуратнее и, вероятно, более правильно, учитывая то, как он работает с деревом с одним узлом: (пути 'a) => ((a)), в то время как (g 'a) => (a). Является ли карта CL более или менее эквивалентной моей карте 2 выше? Знаете ли вы о встроенной функции Scheme? - person grifaton; 11.06.2010
comment
Я мало что знаю о Scheme, но я бы предположил, что доступно что-то вроде mapcan. Хотя, возможно, это кажется простым в реализации. Ваш map2 в принципе кажется эквивалентным, но у него неправильный хвостовой вызов, поэтому он взорвет стек, когда список станет слишком длинным. Возможно, вам следует использовать идиому аккумулятор/обратный. - person Svante; 11.06.2010
comment
Эквивалентом схемы mapcan является append-map из СРФИ-1. - person Nathan Shively-Sanders; 11.06.2010

arrow_upward
2
arrow_downward

Перевод R5RS ответа Сванте:

(define (accumulate op init seq)
  (define (iter ans rest)
    (if (null? rest)
        ans
        (iter (op ans (car rest))
              (cdr rest))))
  (iter init seq))

(define (flatten seq)
  (accumulate append '() seq))

(define (flatmap op seq)
  (flatten (map op seq)))

(define (atom? x)
  (not (pair? x)))

(define (paths tree)
  (if (atom? tree)
      (list (list tree))
      (flatmap (lambda (node)
                 (map (lambda (path)
                        (cons (car tree) path))
                      (paths node)))
               (cdr tree))))
person Nietzche-jou    schedule 11.06.2010

arrow_upward
0
arrow_downward

Я думаю, вы могли бы определить дерево примеров как (корневой левый правый) каждый список. Таким образом, ваше примерное дерево будет выглядеть так: (D (B (A () (C () (F () G )) ) ) E) () ) и его легче пройти

person Ismael    schedule 10.06.2010
comment
Я думаю, вы неправильно прочитали мою диаграмму - A - корень дерева. Кроме того (и это, вероятно, не ясно из вопроса), узел может иметь более двух ветвей, поэтому я не думаю, что ваш подход сработает. - person grifaton; 11.06.2010
comment
Я только что понял, что неправильно прочитал вашу схему. Я бы сказал, что если функция g работает, вы должны использовать ее :-) - person Ismael; 11.06.2010

arrow_upward
0
arrow_downward

Вам нужен алгоритм поиска по дереву. Обход в ширину или в глубину будет работать, и в данном случае не имеет значения, какой именно, поскольку вам нужно просканировать все дерево. Всякий раз, когда вы доберетесь до листа, просто сохраните текущий путь в своих результатах.

person G__    schedule 10.06.2010