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 ?

Gottlieb

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!

Vitriolize

Thanks! It'd be better to use list? instead of pair? though (which can easily be implemented with lambda), to handle the case where the input list to flatten is null (thanks to chrislck on #guile for pointing me both to this example and to this small bug) – Rheumatic

Answer 2

I'm not familiar with the Little Schemer primitives, so you may need to flavor this to suit.

I'm not sure if this is the answer you want, but you can write append using primitives:

(define (append l1 l2)
  (cond
    ((null? l1) l2)
    (else (cons (car l1) (append (cdr l1) l2)))))

The flatten function could then be written in terms of this.

Not sure if this is outside the rules or not :)

Wilcher

Answer 3

Here's an attempt. It gets away with using cons and avoiding append, because it only chips away the first non-pair it can get to and conses that to the flatten of a new tail it has built. Sometimes it rewrites the list then just calls flatten again. Def not the most efficient way.

Fixed code:

(define (flatten x)
  (cond 
    ((null? x) x)
    ((and (pair? x) 
          (not (pair? (car x))))
     (cond 
       ((null? (car x)) (flatten (cdr x)))
       (else (cons (car x) (flatten (cdr x))))))
    ((and (pair? x)
          (pair? (car x)))
     (flatten (cons (caar x) 
                    (cons (cdar x) (cdr x)))))
    (else (cons x '()))))

Billet

BTW this is closely related to John McCarthy's "gopher" device. – Verada