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)

SICP Exercise 2.27: Deep Reverse

Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,

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

> x
((1 2) (3 4))

> (reverse x)
((3 4) (1 2))

> (deep-reverse x)
((4 3) (2 1))

Here's the reverse procedure we produced for exercise 2.18:

(define (reverse l)
  (define (iter remaining result)
    (if (null? remaining)
        result
        (iter (cdr remaining) (cons (car remaining) result))))
  (iter l nil))

...and we can indeed confirm its behavior matches that given above:

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

reverse is designed to reverse the ordering of elements in the top-level list. It does not touch the contents of the elements themselves.

To implement deep-reverse we need to reverse the list as we do in reverse, but we also need to identify those elements of the list that are pairs themselves and apply the reversal process to those as well. This means at each iteration we now have three cases instead of two to consider:

• If the remaining list is empty then return the result.
• If the head of remaining is not a pair then put it onto the head of the result list and make the iterative call as before.
• If the head of remaining is a pair then put the result of deep reversing that onto the head of the result list and make the iterative call.

We can translate this into a procedure as follows:

(define (deep-reverse l)
  (define (iter remaining result)
    (cond ((null? remaining) result)
          ((pair? (car remaining))
            (iter (cdr remaining) (cons (deep-reverse (car remaining)) result)))
          (else (iter (cdr remaining) (cons (car remaining) result)))))
  (iter l nil))

...and check it works as expected:

> (deep-reverse x)
((4 3) (2 1))
> (deep-reverse (list (list (list 1 2) (list 3 4) 5) (list 6 (list 7 8) 9) (list 10)))
((10) (9 (8 7) 6) (5 (4 3) (2 1)))

SICP Exercise 2.26: Combining Lists

Suppose we define x and y to be two lists:

(define x (list 1 2 3))
(define y (list 4 5 6))

What result is printed by the interpreter in response to evaluating each of the following expressions:

(append x y)

(cons x y)

(list x y)

Let's fire up our interpreter and find out...

> (define x (list 1 2 3))
> (define y (list 4 5 6))
> (append x y)
(1 2 3 4 5 6)
> (cons x y)
((1 2 3) 4 5 6)
> (list x y)
((1 2 3) (4 5 6))

In the first case we're using append which takes two lists and produces a new list containing all of the elements from both lists in order.

In the second case we're using cons, which creates a pair using its two arguments. As the second argument is a list the resulting structure will also be a list... and as the first argument is a list the first element of the list will be that list.

In the final case we're using list, which creates a list containing all of its arguments. We have two arguments, both of which are lists, so the resulting structure is a two-element list, each element of which is a list.