<< 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 '()))
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)
(define (fringe tree)
(cond ((null? tree) '())
((not (pair? (car tree))) (cons (car tree) (fringe (cdr tree))))
(else (append (fringe (car tree)) (fringe (cdr tree))))))
My implementation is similar to "Yes, there is a better way ...".
(define (fringe lst)
(if (pair? lst)
(let* ((first_elem (car lst))
(to_append_first_elem
;; first_elem may be nil hinted by Nico de Vreeze
; (if (pair? first_elem)
(if (list? first_elem)
(fringe first_elem)
(list first_elem))))
(append to_append_first_elem (fringe (cdr lst))))
lst))
But it doesn't use `(cons first (fringe (cdr tree)))`. `(null? tree)` functions same as `(not (pair? lst))` here since `lst` can't be number when recursively calling `fringe`. `(fringe 3) ;; fails, as it should.` is not considered here since we assume the first lst is list.
This is same as holub's but the latter is iterative.
This is also same as zhenhuaa's but the latter is more clear. ly is same as the latter.
musiXelect's is almost same as "Second try". Based on "applicative-order evaluation", the latter will manipulate with (helper (car ls) result) first while the former will manipulate with (build-fringe (cdr x) result) first and then based on that construct result further.
IMHO musiXelect's code is very unreadable since result is just passed verbatimly, i.e. nil here. Then based on induction, base case are nil and number. Then we can show the code works for non-nested lists and then nested lists.
------
Review history comments:
1. "First try" fails since it tries cons one list at the start instead of one single element.
2. "Second try" works since the basic operation is just (cons x result) which won't have the above problem. Then we use induction to prove else works. rnsmit's, Daniel-Amariei's, Alex Gunnarson's, Adam Stanton's (not iter with new unchanged) are same as this.
Alex Gunnarson's, Adam Stanton's use list?. Here L when calling fringe-help can only be non-empty list / number / nil. Then when calling (list? L) it can only be non-empty list / number. So (list? L) functions same as (pair? x) here.
Mathieu Bordere's is same as Adam Stanton's. chessweb's is same as Mathieu Bordere's.
3. "They didn't bother with doing all the (let ((first (car tree)...) nonsense:" This is similar to exercise 2.27 ybsh's comment "Then I realized that car'ing before pair? was unnecessary".
4. "A solution which I found that happens to be similar to the one from enumerate-tree" is a bit wrong. When recursively calling fringe-recur, (cdr x) is ensured to be list but (car x) may be one number. Then the base case (not (pair? (car x)) will return the wrong x when x is something like (list 1 (list 2 3)). We should use:
... ((not (pair? x)) (list x)) ...
Here (append result ...) is due to we manipulate x from left to right and so we should append the new element at the right instead of left.
---
vpraid's is a bit different. Its base operation is (cons top acc), but it uses (cons (car top) (cons (cdr top) (cdr stack))) to recursively extracts the leftmost leaf by splitting top and then do the base operation. So it needs reverse at last. Here (null? top) is to consider (cdr top) may be nil.
"it doesn't rely on call stack" here mean it is one iterative implementation.
Nico de Vreeze is same as vpraid's where (not (pair? items)) is same as (null? stack) since recursive calls imply items to be list (See the above "non-empty list / number / nil"). The former is recursive so it doesn't need reverse.
rohitkg98's shares the same basic idea but is more readable. (pair? first) corresponds to else. else corresponds to (not (pair? top). (null? first) called not at the first time corresponds to (null? top).
---
madhur95's: We need is-outer-list? since we are using cons and x may be nil. (not (pair? lst)) is not needed since (cdr lst) must be list and (car lst) in else must be pair.
We can add the following case before (not (pair? (car lst))) to consider "empty sub-lists":
((null? (car lst))
(iter (cdr lst)
f
is-outer-list?))
iterative solution