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

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.

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

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

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)

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)

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)

A simple version use number?

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

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

short code

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

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

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)

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 '()))
```

iterative solution