sicp-ex-2.28



<< Previous exercise (2.27) | Index | Next exercise (2.29) >>


  
 ;; Fringe.   
  
 (define my-tree (list 1 (list 2 (list 3 4) (list 5 6)) (list 7 (list 8)))) 
  
 ;; First try.  If the current element is a leaf, cons it to the fringe 
 ;; of the rest.  If the current element is a tree, cons the fringe if 
 ;; it to the fringe of the rest.  .... Won't work because the bad line 
 ;; indicated won't build a flat list, it will always end in nested 
 ;; cons. 
 (define (fringe tree) 
   (define nil '()) 
   (if (null? tree)  
       nil 
       (let ((first (car tree))) 
         (if (not (pair? first)) 
             (cons first (fringe (cdr tree))) 
             ;; bad line follows: 
             (cons (fringe first) (fringe (cdr tree))))))) 
  
 (fringe my-tree) 
  
 ;; Second try. 
 ;; Need to store fringe of the cdr, then add the fringe of the car to 
 ;; that. 
 (define (fringe tree) 
   (define nil '()) 
  
   (define (build-fringe x result) 
     (cond ((null? x) result) 
           ((not (pair? x)) (cons x result)) 
           (else (build-fringe (car x)  
                               (build-fringe (cdr x) result))))) 
  
   (build-fringe tree nil)) 
  
 ;; Usage: 
 (fringe my-tree) 
  

Is there a better way to do this? Specifically, is there a way to do this only in terms of fringe, without creating another function?

Yes, there is a better way ... just use append instead of cons in version 1.

  
 (define (fringe tree) 
   (define nil '()) 
   (if (null? tree)  
       nil 
       (let ((first (car tree))) 
         (if (not (pair? first)) 
             (cons first (fringe (cdr tree))) 
             (append (fringe first) (fringe (cdr tree))))))) 
  
 ;; Usage 
 (fringe my-tree) 
 (fringe (list 3)) 
 (fringe 3)  ;; fails, as it should. 
  

This takes an alternate form later in the book (enumerate-tree in a future chapter), and Eli Bendersky's answer was also slightly different than mine. They didn't bother with doing all the (let ((first (car tree)...) nonsense:

  
 (define (fringe tree) 
   (define nil '()) 
   (cond ((null? tree) nil) 
         ((not (pair? tree)) (list tree)) 
         (else (append (fringe (car tree)) (fringe (cdr tree)))))) 
  
 (fringe my-tree) 
  

A much cleaner solution, with the caveat (if it can be called such) that this function works even if passed a non-tree (eg, (fringe 3) => 3), while the previous fails as expected. Again, not really a valid caveat.

A solution which I found that happens to be similar to the one from enumerate-tree, but which fails if passed a non-list.

 (define (fringe x) 
   (define (fringe-recur x result) 
     (cond ((null? x) 
            result) 
           ((not (pair?  (car x))) 
            x) 
            (else 
            (fringe-recur (cdr x) (append result (fringe-recur (car x) (list ))))) )) 
   (fringe-recur x (list ))) 

rnsmit

iterative solution

  
 ;;take all leafs as a list 
 (define (fringe items)  
   (define (fringe-iter items result) 
     (cond ((null? items) 
            result) 
           ((pair? items) 
            (fringe-iter (car items) 
                         (fringe-iter (cdr items) result))) 
           (else (cons items result)))) 
   (fringe-iter items nil)) 
  
  
 (fringe (list (list 1 2) (list 3 4 (list 5 (list 6))))) 

VladimirF

The versions with append fail for lists with n~1000 for me. The version with just cons works nicely up to n~100000 with guile.


holub

my way:

 (define (fringe items) 
   (define (fringe-iter source dist) 
     (if (null? source) 
         dist 
         (fringe-iter (cdr source) 
                      (append dist 
                              (let ((scar (car source))) 
                                (if (pair? scar) 
                                    (fringe scar) 
                                    (list scar))))))) 
   (fringe-iter items (list))) 

Daniel-Amariei

Puts ones mind to work.

 ;; construct the list from the right of the tree, to the left 
 (define (fringe T) 
   (define (iter T R) 
     (cond ((null? T) R) 
           ((not (pair? T)) (cons T R)) 
           (else (iter (car T) 
                       (iter (cdr T) R))))) 
   (iter T '())) 
  
  
 (define x '(1 (2 (3 4)))) 
  
 (fringe x)  ;; (1 2 3 4) 
 (fringe (list x x)) ;; (1 2 3 4 1 2 3 4) 
 (fringe '(2)) ;; 2 

Alex Gunnarson

I did this late at night kind of accidentally. I tried to put the least amount of thought into it possible and I messed around with the code without really thinking, shoved it in a REPL, and voila! the problem solved itself. For comparison's sake, I spent a grand total of 5 minutes on this but a few hours on Problem 2.27. Wish I could have solved 2.27 as easy.

 (define (fringe L) 
         (define (fringe-help L result) 
                 (if (null? L) ; if at end of the branch 
                     result 
                     (if (list? L) ; if the element is a list, not a number 
                         (fringe-help (car L) ; left branch 
                                      (fringe-help (cdr L) result)) ; right branch 
                         (cons L result)))) ; otherwise gather numbers into a list 
         (fringe-help L '())) 
  
 (fringe '((1 2) (3 4) (5 6 7 (8 9)))) 
 ;; (1 2 3 4 5 6 7 8 9) 

Adam Stanton

Here is my solution. I'm eager to find a better solution that performs better!

  
  
 (define (fringe tree) 
   (define (iter x new) 
     (if (null? x) 
         new 
         (let ((first (car x))) 
           (if (list? first) 
               (append (iter first new) (iter (cdr x) new)) 
               (cons first (iter (cdr x) new)))))) 
  
   (iter tree '())) 
  
 ;; Testing 
 (fringe (list (list (list 1 2 3 19 283 38) 2 3 2) (list 2 3 (list 217 382 1827) 2 187 (list 2838)) 2 1 2 (list 2 (list 3 (list 3)) 23 2 1 238))) 
  
 (1 2 3 19 283 38 2 3 2 2 3 217 382 1827 2 187 2838 2 1 2 2 3 3 23 2 1 238) 

Mathieu Bordere

And another one ... (thanks for the testcase Adam!)

  
 (define (fringe tree) 
   (cond ((null? tree) '()) 
         ((list? (car tree)) (append (fringe (car tree)) 
                                     (fringe (cdr tree)))) 
         (else (cons (car tree) (fringe (cdr tree)))))) 
  
 ;; Testing 
 (fringe (list (list (list 1 2 3 19 283 38) 2 3 2) (list 2 3 (list 217 382 1827) 2 187 (list 2838)) 2 1 2 (list 2 (list 3 (list 3)) 23 2 1 238))) 
  
 (1 2 3 19 283 38 2 3 2 2 3 217 382 1827 2 187 2838 2 1 2 2 3 3 23 2 1 238) 

zhenhuaa

A simple version use number?

  
 (define (fringe x) 
   (cond ((null? x) x) 
         ((number? x) (list x)) 
         (else (append (fringe (car x)) 
                       (fringe (cdr x)))))) 

vpraid

This is my iterative solution. It doesn't use append and it doesn't rely on call stack. Instead, it uses its own stack. This should work even for extremely large trees.

  
 (define (reverse x) 
   (define (iter x acc) 
     (if (null? x) 
         acc 
         (iter (cdr x) 
               (cons (car x) acc)))) 
   (iter x nil)) 
  
 (define (fringe x) 
   (define (collect stack acc) 
     (if (null? stack) 
         acc 
         (let ((top (car stack))) 
           (cond ((null? top) (collect (cdr stack) acc)) 
                 ((not (pair? top)) (collect (cdr stack) (cons top acc))) 
                 (else (collect (cons (car top) 
                                      (cons (cdr top) (cdr stack))) 
                                acc)))))) 
   (reverse (collect (list x) nil))) 
  

ly

short code

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

musiXelect

My solution. It doesn't do anything special but why wouldn't I share it?

  
 (define nil '()) 
 (define (fringe ls) 
   (define (helper ls result) 
     (cond ((null? ls) result) 
           ((not (pair? ls)) (cons ls result)) 
           (else (append (helper (car ls) result) (helper (cdr ls) result))))) 
   (helper ls nil)) 

Nico de Vreeze

Not using append and/or helper proc:

  
 (define (fringe items) 
   (cond ((not (pair? items)) items) 
         ((pair? (car items)) (fringe (cons (caar items) (cons (cdar items) (cdr items))))) 
         ((null? (car items)) (fringe (cdr items))) 
         (else (cons (car items) (fringe (cdr items)))))) 
  
 ;; Also works with empty sub-lists: 
 (fringe '(1 2 3 (4 5) 6 () (((7 (8 9) (()) 10) 11) 12))) 
 ;;Value: (1 2 3 4 5 6 7 8 9 10 11 12) 
  

rohitkg98

Completely Iterative solution but it reverses the contents The idea is to maintain three state variables first, rest, res Trace of ((1 2) (3 4)):

| first | rest          | res       |
|-------|---------------|-----------|
| nil   | ((1 2) (3 4)) | nil       |
| (1 2) | ((3 4))       | nil       |
| 1     | (2 (3 4))     | nil       |
| nil   | (2 (3 4))     | (1)       |
| 2     | ((3 4))       | (1)       |
| nil   | ((3 4))       | (2 1)     |
| (3 4) | nil           | (2 1)     |
| 3     | (4)           | (2 1)     |
| nil   | (4)           | (3 2 1)   |
| 4     | nil           | (3 2 1)   |
| nil   | nil           | (4 3 2 1) |

So instead of call stack we maintain info in rest.

  
 (define (fringe-iter-reverse items) 
   (define (iter first rest res) 
     (cond ((and (null? first) (null? rest)) res) 
           ((null? first) (iter (car rest) (cdr rest) res)) 
           ((pair? first) (iter (car first) (cons (cdr first) rest) res)) 
           (else (iter (car rest) (cdr rest) (cons first res))))) 
   (iter '() items '())) 
  

madhur95

Inspired by somarl's solution in 2.22 of using a higher order function to store the leaves to avoid reversing the final answer. Maybe this approach can be combined with rohitkg98's approach to get complete iterative solution.

 (define (fringe lst) 
   ; iter succesively reduces the inputted list by cdr ing it 
   (define (iter lst f is-outer-list?)  
   ; f keeps record of the leaves using cons and succesive application of itself 
   ; list of leaves is formed by applying f to nil when finally original list has  
   ; been cdr ed into empty. 
   ; is-outer-list? ensures nil is applied only once to make final list, is #t for  
   ; outermost list and #f for any sub-lists found within the original list  
     (cond ((null? lst) (if is-outer-list? 
                            (f lst) 
                            f)) 
           ; edge case                  
           ((not (pair? lst)) lst) 
           ; if first element is a leaf, add it to the function   
           ((not (pair? (car lst))) 
              (iter (cdr lst)  
                    (lambda (x) (f (cons (car lst) x)))  
                    is-outer-list?)) 
           ; otherwise add all the leaves of first element to the function 
           (else (iter (cdr lst)  
                       (iter (car lst) f #f)  
                       is-outer-list?)) 
   )) 
   (iter lst (lambda (x) x) #t)) 
  
 (fringe (list 1 (list 1 2) 3 (list 8 9 (list 10 11)))) 
 ; outputs -> '(1 1 2 3 8 9 10 11)