Smooth list using only forms in "The Little Schemer"

Question

I go through LIttle Schemer to learn Scheme (as an old C programmer), and as an exercise I tried to write a procedure to smooth out a list using only forms in The Little Schemer; Ie, define , lambda , cond , car , cdr , and , or etc., but not append . I thought it would be easy, but I could not find a solution. How can i do this?

Answer 1

I have a version that uses only the "first principle" operations and is effective (more than one pass through any of the lists is not required, unlike append based solutions) append

He does this by defining two simple building blocks ( fold and reverse ), and then defining flatten (and his assistant, reverse-flatten-into ) on top of these (and notice how each function is one or two long lines):

 ;; Similar to SRFI 1 fold (define (fold1 kons knil lst) (if (null? lst) knil (fold1 kons (kons (car lst) knil) (cdr lst)))) ;; Same as R5RS 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 '()))) 

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

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

Answer 2

Here is an attempt. He walks away with cons and avoids adding because he only cuts off the first non-pair that he can get to, and agrees with this smoothing out of the new tail that he built. Sometimes it rewrites the list, and then simply causes anti-aliasing. Def is 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 '())))) 

Answer 3

I am not familiar with the primitives of Little Schemer, so you may need a taste for this.

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

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

Then the flatten function can be written as this.

Not sure if this is out of the rules or not :)