Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 2.28

From Drewiki
Jump to: navigation, search

Problem

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)

Output:

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

Output:

(1 2 3 4 1 2 3 4)


Solution

Here's an implementation of fringe. When its input is neither nil nor a pair, it returns a list containing its input:

(define nil (quote ()))
 
(define (fringe x)
  (cond ((null? x) nil)
        ((pair? x) (append (fringe (car x)) (fringe (cdr x))))
        (else (list x))))

Test:

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

Output:

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

Output:

(1 2 3 4 1 2 3 4)
Personal tools