sicp-ex-2.28


  
 ;; 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 ))) 

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.



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


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)