little schemer - multirember&co - reprise for dec 2006

[Geoffrey King]

I am working my way through the little schemer and so far it has been good
exercise but not challenging. Until "Lambda the ultimate" chapter. Which
while not hard is actually teaching me things. I noted that wooks back in
Dec 5 2006 had similar feelings.

In particular about the function (pg. 137-ish) multirember&co. The code in
the book makes sense. I just don't understand why they chose that approach.
Below is the book's code, and mine. In short I would appreciate so some
clues on why the little schemer approach is better.

Little Schemer Book says >>
(define multirember&co
(lambda (a lat col)
(cond
((null? lat)
(col '() '()))
((eq? (car lat) a)
(multirember&co a
(cdr lat)
(lambda (newlat seen)
(col newlat
(cons (car lat) seen)))))
(else
(multirember&co a
(cdr lat)
(lambda (newlat seen)
(col (cons (car lat) newlat)
seen)))))))

My solution >>
(define multirco
(lambda (a lat)
(cond
((null? lat)
(list '() '()))
((eq? (car lat) a)
(let ((result (multirco a (cdr lat))))
(list (car result)
(cons a (cadr result)))))
(else
(let ((result (multirco a (cdr lat))))
(list (cons (car lat) (car result))
(cadr result)))))))

[Marlene Miller]

> Little Schemer Book says >>
> (define multirember&co
> (lambda (a lat col)
> (cond
> ((null? lat)
> (col '() '()))
> ((eq? (car lat) a)
> (multirember&co a
> (cdr lat)
> (lambda (newlat seen)
> (col newlat
> (cons (car lat) seen)))))
> (else
> (multirember&co a
> (cdr lat)
> (lambda (newlat seen)
> (col (cons (car lat) newlat)
> seen)))))))

My guess is this example is explaining something about recursion. A sequence
of functions is constructed (recursively) then the functions are applied
sequentially (without recursion). We might say, the recursion is flattened.

(define sum
(lambda (lat)
(cond ((null? lat) 0)
(else
(+ (car lat) (sum (cdr lat)))))))

(sum '(3 5 9)) ;=> 17

(define m
(lambda (lat col)
(cond ((null? lat) (col 0))
(else (m (cdr lat)
(lambda (sum)
(col (+ (car lat) sum))))))))

(m '(3 5 9) (lambda (x) x)) ;=> 17

(define f1 (lambda (sum) sum))
(define f2 (lambda (sum) (f1 (+ 3 sum))))
(define f3 (lambda (sum) (f2 (+ 5 sum))))
(define f4 (lambda (sum) (f3 (+ 9 sum))))
(f4 0) ;=> 17

[bearoph...@lycos.com]

Geoffrey King:

> In particular about the function (pg. 137-ish) multirember&co.
> The code in
> the book makes sense. I just don't understand why they chose that
> approach.

> In short I would appreciate so some

> clues on why the little schemer approach is better.

If you think that code makes sense then you have understood it enough
already :-)
I have found yet different (purely functional) solutions, that solve
the same problem and they don't require the building of all those
nested lambdas (that makes me feel ick).
I think they chose that approach because they were trying to teach a
new concept, and not because that design has some (practical)
advantages.

Bye,
bearophile

[Emilio Lopes]

Geoffrey King writes:

> In particular about the function (pg. 137-ish) multirember&co. The
> code in the book makes sense. I just don't understand why they chose
> that approach. Below is the book's code, and mine. In short I would
> appreciate so some clues on why the little schemer approach is better.

> [code elided]

Well, they wanted to abstract the collector. At first I thought they
would introduce recursion patterns like "fold" and friends.

Then I thought that they would introduce CPS (continuation passing
style), which they kind of did.

Also bearophileHUGS writes:

> [...]

> I think they chose that approach because they were trying to teach a
> new concept, and not because that design has some (practical)
> advantages.

Indeed the approach in "The Little Schemer" has a practical advantage:
it's tail recursive. Although they did not mentioned this fact, the
tenth commandment is a hint in this direction:

*Build* *functions* to collect more than one value at a time.
[my emphasis]

Explanation of the terms "continuation passing style" and "tail
recursion" are available at WikiPedia. The analysis of "recursive"
and "iterative" processes in the first sections of "Structure and
Interpretation of Computer Programs" [1] might also be of interest.

Footnotes:
[1] http://mitpress.mit.edu/sicp/full-text/book/book.html

--
Emílio C. Lopes Ich leb und weiß nit wie lang,
Munich, Germany ich stirb und weiß nit wann,
ich fahr und weiß nit wohin,
(Martinus von Biberach) mich wundert, dass ich fröhlich bin!

[bearoph...@lycos.com]

Emilio Lopes:

> Indeed the approach in "The Little Schemer" has a practical advantage:
> it's tail recursive.

If you are interested about this function and some of its variants, I
have started a thread on the Python newsgroup too:
http://groups.google.com/group/comp.lang.python/browse_thread/thread/0f1055fcd0ef2503/

Bye,
bearophile

[Geoffrey King]

Thanks Emilio that gives me something to think about.