SICP 2.28: Flattening Nested Lists

From SICP section 2.2.2 Hierarchical Structures

Exercise 2.28 asks us to write a procedure fringe that takes a tree as its argument and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example

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

This problem is simpler than the one before it because the return value here is just a flat list. That means we can simply traverse the tree and append each node to the result as we encounter it. Once again, we'll be using the append procedure given in the text to build up the result.

(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

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

If the parameter passed to fringe is not a pair, we simply return its value as a list (this will be the case when we reach a leaf node). Otherwise we append the fringe of the first node of the tree to the fringe of the remaining nodes.

Here are the results using the test case given:

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

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.