Getting the ordered leaves of a tree in scheme

Question

I'm going through an exercise to grab the 'leaves' of a nested list in scheme (from SICP). Here is the exercise input-output:

(define x (list (lis 1 2) (list 3 4)))
(fringe x)
; (1 2 3 4)

(fringe (list x x))
; (1 2 3 4 1 2 3 4)

Now, I've come up with two answers for this: one recursive and one iterative. Here are my two implementations below:

(define (fr lst)
  (cond ((null? lst) '())
        ((not (pair? (car lst))) (cons (car lst) (fr (cdr lst))))
        (else (append (fr (car lst)) (fr (cdr lst))))))

(define (add-element-to-list lst elem)
  (if (null? lst)
      (list elem)
      (cons (car lst) (add-element-to-list (cdr lst) elem))))

(define (fringe lst)
 (define L '())
  (define (iter lst)
    (if (not (pair? (car lst)))
        (set! L (add-element-to-list L (car lst))) ; update the list if it's a leaf
        (iter (car lst)))                          ; otherwise recurse
    (if (not (null? (cdr lst))) (iter (cdr lst)))  ; and if we have a cdr, recurse on that
    L
    )
  (iter lst)
)

(fringe x)
(fr x)
(fr (list x x))
(fringe (list x x))
; (1 2 3 4)
; (1 2 3 4)
; (1 2 3 4 1 2 3 4)
; (1 2 3 4 1 2 3 4)
; OK

The problem for me is, this exercise took me forever to figure out with a ton of head-bashing along the way (and it's still difficult for me to 'get it' as I write this up). Here are a few things I struggled with and seeing if there are any suggestions on ways to deal with these issues in scheme:

1. I thought initially that there are two cases. The normal/scalar case and the nested case. However, it seems like there are actually three! There's the normal case, the nested case, and then the null case -- and inner-lists also have the null case! Is there a good general pattern or something to account for the null case? Is this something that comes up a lot?
2. In the iterative case, why do I have to return L at the end? Why doesn't (iter lst) just return that (i.e., if I removed the standalone-L at the bottom of the iter function).
3. Finally, is there a 'cleaner' way to implement the iterative case? It seems like I have so much code, where it could probably be improved on.

Answer 1

It's about types. Principled development follows types. Then it becomes easy.

Lisp is an untyped language. It's like assembler on steroids. There are no types, no constraints on what you're able to code.

There are no types enforced by the language, but still there are types, conceptually. We code to types, we handle types, we produce values to a given specs i.e. values of some types as needed for the pieces of bigger system to interface properly, for the functions we write to work together properly, etc. etc.

What is it we're building a fringe of? Is it a "list"?

What is a "list"? Is it

(define (list? ls)
  (or (null? ls)
      (and (pair? ls)
           (list? (cdr ls)))))

Is this what we're building a fringe of? How come it says nothing about the car of the thing, are we to ignore anything that's in the car? Why, no, of course not. We're not transforming a list. We're actually transforming a tree:

(define (tree? ls)
  (or (null? ls)
      (and (pair? ls)
           (tree? (car ls))
           (tree? (cdr ls)))))

Is it really enough though to only be able to have ()s in it? Probably not.

Is it

(define (tree? ls)
  (or (null? ls)
      (not (pair? ls))   ;; (atom? ls) is what we mean
      (and ;; (pair? ls)
           (tree? (car ls))
           (tree? (cdr ls)))))

It 1 a tree? Apparently it is, but let's put this aside for now.

What we have here, is a structured, principled way to see a piece of data as belonging to a certain type. Or as some say, data type.

So then we just follow the same skeleton of the data type definition / predicate, to write a function that is to process the values of said type in some specific way (this is the approach promoted by Sterling and Shapiro's "The Art of Prolog").

(define (tree-fringe ls)

So, what is it to produce? A list of atoms in its leaves, that's what.

  (cond 
      ((null? ls)

A () is already a list?.

                   ls)
      ((not (pair? ls))   ;; (atom? ls) is what we mean
           (handle-atom-case ls))

Let's put this off for now. On to the next case,

      (else
           ;; (tree? (car ls))
           ;; (tree? (cdr ls))

both car and cdr of ls are tree?s. How to handle them, we already know. It's

          (let ((a (tree-fringe (car ls)))
                (b (tree-fringe (cdr ls)))

and what do we do with the two pieces? We piece them together. First goes the fringe from the left, then from the right. Simple:

            (append   a   b  )))))

(define (handle-atom-case ls)  
      ;; bad name, inline its code inside 
      ;; the `tree-fringe` later, when we have it

And so, what type of data does append expect in both its arguments? A list?, again.

And this is what we must produce for an atomic "tree". Such "tree" is its own fringe. Except,

    ;;  tree:       1         2
    ;; fringe:    ( 1 )     ( 2 )

it must be a list?. It's actually quite simple to turn an atomic piece of data, any data, into a list? containing that piece of data.

      ........ )

And that was the only non-trivial thing we had to come up with here, to get to the solution.

Recursion is about breaking stuff apart into the sub-parts which are similar to the whole thing, transforming those with that same procedure we are trying to write, then combining the results in some simple and straightforward way.

If a tree? contains two smaller trees?, well, we've hit the jackpot -- we already know how to handle them!

And when we have structural data types, we already have the way to pick them apart. It is how they are defined anyway.

---

Maybe I'll address your second question later.

Answer 2

The reason there are three cases is that you are importing some scalar / vector distinction from some other language: Scheme doesn't have it and it is not helpful. Instead a list is a recursively-defined object: a list is either the empty list, or it is a pair of something and a list. That means there are two distinctions to make, not one: is an object a pair, and is an object the empty list:

(define (lyst? o)
  (or (null? o)
      (and (pair? o) (lyst? (cdr o)))))

That's completely different than a vector / scalar distinction. I don't know what language you're getting this from, but just think about how the maths of this would work: vectors are defined over some scalar field, and there is no vector which is also a scalar. But for lists there is a list which is not a pair. Just stop thinking about vectors and scalars: it is not a helpful way to think about lists, pairs and the empty list.

The iterative version is too horrible to think about: there's a reason why SICP hasn't introduced set! yet.

First of all it's not actually iterative: like most of the 'iterative' solutions to this problem on the net it looks as if it is, but it's not. The reason it's not is that the skeleton of the iter function looks like

1. if blah
   • recurse on the first element of the list
   • otherwise do something else
2. if other blah
   • iterate on the rest of the list

And the critical thing is that both (1) and (2) always happen, so the call into the car of the list is not a tail call: it's a fully-fledged recursive call.

That being said you can make this much better: the absolutely standard way of doing this sort of thing is to use an accumulator:

(define (fringe l)
  (define (fringe-loop thing accum)
    (cond
      ((null? thing)
       ;; we're at the end of the list or an element which is empty list
       accum)
      ((pair? thing)
       ;; we need to look at both the first of the list and the rest of the list
       ;; Note that the order is rest then first which means the accumulator
       ;; comes back in a good order
       (fringe-loop (car thing)
                    (fringe-loop (cdr thing) accum)))
      (else
       ;; not a list at all: collect this "atomic" thing
       (cons thing accum))))
  (fringe-loop l '()))

Note that this builds the fringe (linear) list from the bottom up, which is the natural way of building linear lists with recursion. To achieve this it slightly deviously orders the way it looks at things so the results come out in the right order. Note also that this is also not iterative: it's recursive, because of the (fringe-loop ... (fringe-loop ...)) call. But this time that's much clearer.

The reason it's not iterative is that the process of searching a (tree-like, Lisp) list is not iterative: it's what SICP would call a 'recursive process' because (Lisp's tree-like) lists are recursively defined in both their first and rest field. Nothing you can do will make the process iterative.

But you can make the code to appear iterative at the implementation level by managing the stack explicitly thus turning it into a tail recursive version. The nature of the computational process doesn't change though:

(define (fringe l)
  (define (fringe-loop thing accum stack)
    (cond
      ((null? thing)
       ;; ignore the () sentinel or () element
       (if (null? stack)
           ;; nothing more to do
           accum
           ;; continue with the thing most recently put aside
           (fringe-loop (car stack) accum (cdr stack))))
      ((pair? thing)
       ;; carry on to the right, remembering to look to the left later
       (fringe-loop (cdr thing) accum (cons (car thing) stack)))
      (else
       ;; we're going to collect this atomic thing but we also need 
       ;; to check the stack
       (if (null? stack)
           ;; we're done
           (cons thing accum)
           ;; collect this and continue with what was put aside
           (fringe-loop (car stack) (cons thing accum) (cdr stack))))))
  (fringe-loop l '() '()))

Whether that's worth it depends on how expensive you think recursive calls are and whether there is any recursion limit. However the general trick of explicitly managing what you are going to do next is useful in general as it can make it much easier to control search order.

(Note, of course, that you can do a trick like this for any program at all!)