SICP Exercise 2.28: On the Fringe

Write a procedure fringe that takes as argument a tree (represented as a list) 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)

What we want to do here is to iterate through the list we're given and, for each element determine whether or not it's a list itself. If it isn't then we can just cons the current item onto the head of the list we're going to produce by applying fringe to the rest of the list. If it is a list then we want to apply fringe to the element itself to get a list of all the leaf node values under that element. However, we can't just cons this onto the head of the list we're going to produce by applying fringe to the rest of the list, as that will give a nested list. Instead we need to append the lists together so that we get a single non-nested list.

Here's my implementation:

(define (fringe l)
  (cond ((null? l) nil)
        ((pair? (car l)) (append (fringe (car l)) (fringe (cdr l))))
        (else (cons (car l) (fringe (cdr l))))))

...and here it is in action:

> (define x (list (list 1 2) (list 3 4)))
> (define y (list 1 (list 2 (list 3 4) 5) (list 6 7) 8))
> (fringe x)
(1 2 3 4)
> (fringe (list x x))
(1 2 3 4 1 2 3 4)
> (fringe y)
(1 2 3 4 5 6 7 8)
> (fringe (list y y))
(1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8)