SICP - 2.28 Plucking Leaves (fringe)
This exercise follows much discussion about how data can be grouped and manipulated using cons, car, cdr, and list. The objective is to take a tree in list form, for example (1 (2 3) 4 5), and return a basic list consisting of all of the leaves of the tree in original order. So the result for (1 (2 3) 4 5) would be (1 2 3 4 5). This is to be done using a function named fringe.
By the time this exercise is reached, we are quite familiar with the idea of breaking lists apart. So for example we know that (car ((1 2) 3)) is (1 2) and (cdr (1 2)) is (2). Note that the last result is a list consisting of only one non-null element. You would have to apply car to that to get the single element 2, and the tail of (2) would be null or ().
I started out on this one with a simple idea. I figured the function would have to recur until null was reached, and that if an inner-list was encountered that would have to recur again. So I ended up with something like this:
(define (fringe x)
(cond ((null? x) x)
((not (list? x)) x)
(cons (fringe (car x)) (fringe (cdr x)))))So the idea is that we cons the result of the function applied to the beginning of the list and the end of the list, recursively. This works well for (1 2 3 4) but fails for ((1 2) 3 4). It's not quite right. For one thing, the last line is going to result in some badly constructed cons calls on processing inner lists. After some trial and error, I decided to simplify the part of the procedure that does the constructing of the return value (the last line).
Instead of trying to apply fringe twice in the result, it should be simpler to deal only with the first element of the list and then move on to the next element. This means we are going to have a final line of (cons (car x) (fringe (cdr x))). The rest of the procedure deals with all of the cases necessary to ensure that (car x) is a non-null, non-list, single element.
(define (fringe x)
(cond ((null? x) x)
((not (list? x)) (list x))
((null? (cdr x)) (fringe (car x)))
((null? (car x)) (fringe (car (cdr x))))
((list? (car x)) (fringe (list (car (car x)) (cdr (car x)) (car (cdr x)) (cdr (cdr x)))))
(else (cons (car x) (fringe (cdr x))))))While cdr'ing down a list it's possible to end up left with null. If we do we'll return that as the final parameter to the last cons. Remember that construction of a flat list using cons has to end with either null or a single element list. For example (cons 1 (cons 2 (cons 3 ()))) returns (1 2 3) as does (cons 1 (cons 2 cons (list 3))). So those are our two ending conditions - null, or a non-list parameter.
If the parameter that is being processed has null as its tail, we don't need the tail at all, so we have a condition there as well to only take the head of the list in that case. Similarly, if the head of the parameter is null, we take only the tail.
In the case of a list as the next element, we want to recur back into the procedure with a newly created list consisting of the next element extracted from the inner-list, followed by the rest of the elements. So a parameter of ((1 2) 3) would be changed to (1 (2) 3 ()). Also, (((1 2) 3) 4) would recur as ((1 2) (3) 4 ()) then processed again as (1 (2) (3) (4 ()). The idea is to keep calling fringe on the parameter until the first element is not a list, without loosing any of the other elements.
(fringe '((1 2) (3 4) 5 () (6) (((7))) ((8) 9) (((10 ((11))))) 12))
(1 2 3 4 5 6 7 8 9 10 11 12)
As always, I've written this out and worded it for myself with hopes that I will understand it if I come back to it later on. If you've found it useful as well, I'd love to hear about it.