recursionschemelispflattenthe-little-schemer

Scheme: Is it possible to convert a list of S-expressions into a list of atoms?


I am trying to convert a list of S-expressions to a plain list of atoms similar to a problem in the book The Little Schemer.

My code is (as typed in Dr.Racket):

> (define lat '((coffee) cup ((tea) cup) (and (hick)) cup))
> (define f
    (lambda (lat)
      (cond
        ((null? lat) (quote ()))
        ((atom? (car lat)) (cons (car lat) (f (cdr lat))))
        (else (cons (f (car lat)) (f (cdr lat)))))))
> (f lat)
'((coffee) cup ((tea) cup) (and (hick)) cup)

The above code is returning back the list the same as input list. I tried my best, but getting different answers like:

(coffee)
(cup . cup)
( () (()) (()) )

for various modifications in the program.

I would like to know, can we achieve the answer:

'(coffee cup tea cup and hick cup)

given

'((coffee) cup ((tea) cup) (and (hick)) cup)

by using cond cons car and cdr only.


Solution

  • Tweak it:

    (define f
        (lambda (lat)
          (cond
            ((null? lat) (quote ()))
            ;; add this clause
            ((null? (car lat)) (f (cdr lat)))
            ((atom? (car lat)) (cons (car lat) (f (cdr lat))))
            (else ;; (cons (f (car lat)) (f (cdr lat)))
                 (f (cons (car (car lat))       ; rotate the tree to the right
                          (cons (cdr (car lat)) (cdr lat))))))))  ; and repeat
    

    Uses John McCarthy's "gopher" trick, rotating the tree to the right until the leftmost atom is exposed in the top left position, then splitting it off and continuing.