SICP Exercise 2.28

Question

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)

Answer

For this problem, a recursive algorithm may be used. Here, there are three different base cases for (car l): it may be a single value, a list containing a single value, or an $n$-dimensional list containing multiple values. All these base cases need to be handled appropriately.

If (car l) is just a single value, we can simply append it to the recursive fringe call on (cdr l).

If it’s a list containing one value, something like (1), we need to append the car of that list (which is (caar l)) to the recursive call.

And then in the third case, if (car l) is a list containing multiple values, we need to differentiate the same way again: is the first value a single number, a list with a single number, a list with multiple numbers or sub-lists etc. So in this scenario, we need to recursively call the fringe-procedure on (car l). A cond-clause is the simplest way to handle these different possibilities.

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

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

(fringe x)
(fringe (list x x))

Results:

(1 2 3 4)
(1 2 3 4 1 2 3 4)