Flatten a list using only the forms in "The Little Schemer"

Question

I'm going through The LIttle Schemer to learn Scheme (as an old C programmer) and as an exercise I tried to write a procedure to flatten a list using only the forms in The Little Schemer; I.e., define, lambda, cond, car, cdr, and, or, etc., but not append. I thought it would be easy but I haven't been able to come up with a solution. How can I do this ?

Answer 1

I have a version that uses only "first-principles" operations and is efficient (does not require more than one pass through any of the lists, unlike append-based solutions). :-)

It does this by defining two simple building blocks (fold and reverse), and then defining flatten (and its helper, reverse-flatten-into) atop those (and notice how each function is just one or two lines long):

;; Similar to SRFI 1's fold
(define (fold1 kons knil lst)
  (if (null? lst)
      knil
      (fold1 kons (kons (car lst) knil) (cdr lst))))

;; Same as R5RS's reverse
(define (reverse lst)
  (fold1 cons '() lst))

;; Helper function
(define (reverse-flatten-into x lst)
  (if (pair? x)
      (fold1 reverse-flatten-into lst x)
      (cons x lst)))

(define (flatten . lst)
  (reverse (reverse-flatten-into lst '())))

The only external functions used are: cons, car, cdr, null?, and pair?.

The key insight from this function is that fold is a very powerful operation, and should be part of any Schemer's toolkit. And, as seen in the code above, it's so simple to build from first principles!