129 views

Skip to first unread message

Mar 22, 2007, 6:28:02 AM3/22/07

to

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.

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)))))))

Mar 23, 2007, 1:44:38 AM3/23/07

to

> 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)))))))

> (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

Mar 24, 2007, 5:42:20 PM3/24/07

to

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 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

Apr 15, 2007, 1:53:46 PM4/15/07

to

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!

Apr 17, 2007, 2:41:49 AM4/17/07

to

Emilio Lopes:

> Indeed the approach in "The Little Schemer" has a practical advantage:

> it's tail recursive.

> 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

Apr 19, 2007, 6:44:19 PM4/19/07

to

Thanks Emilio that gives me something to think about.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu