Find all the ways from the root to the leaves of the tree in the pattern

Question

Given the tree, I want to find paths from the root to each leaf.

So for this tree:

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

has the following paths from root (A) to leaves (D, E, G):

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

If I present the tree above as (A (B D E) (C (F G))), then the function gdoes the trick:

(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)))))

But everything looks wrong. I didn’t have to think about it for a while, but I feel that there should be a more accurate way to do this. Any ideas for a better solution (in any language) will be appreciated.

---

EDIT - Mapping a Svante solution to Scheme gives:

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

which is far ahead of my original.

Answer 1

I speak more freely about 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))

Answer 2

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))))

Answer 3

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

Answer 4

. , , , . , , .