Scheme - question on exercise from Little Schemer

Author

question on exercise from Little Schemer

dmh2000@gmail.com

2007-02-13, 7:11 pm

>From "Little Schemer" 4th ed" the exercise on page 60 asks you to
write a '+' function using zero?, add1 and sub1. My version looked
like this:

(define plus
(lambda(n m)
(cond
((zero? m) n)
(else (plus (add1 n ) (sub1 m))))))

where the book solution is

(define plus
(lambda(n m)
(cond
((zero? m) n)
(else (add1 (plus n (sub1 m)))))))

both versions work. the difference I see is that my version computes
on the way down the expression and then just pops all the way out,
whereas the book version descends all the way down and then computes
on the way back up.

is there a style or substance reason for the way the book version is
coded?

(it seems to me the book version isn't tail recursive because it
leaves the add1 operation pending after the recursion. am i reading it
right?)

Marlene Miller

2007-02-14, 4:14 am

> >From "Little Schemer" 4th ed" the exercise on page 60 asks you to
> write a '+' function using zero?, add1 and sub1. My version looked
> like this:
>
> (define plus
> (lambda(n m)
> (cond
> ((zero? m) n)
> (else (plus (add1 n ) (sub1 m))))))
>
>
> where the book solution is
>
> (define plus
> (lambda(n m)
> (cond
> ((zero? m) n)
> (else (add1 (plus n (sub1 m)))))))
>
>
> both versions work. the difference I see is that my version computes
> on the way down the expression and then just pops all the way out,
> whereas the book version descends all the way down and then computes
> on the way back up.
>
> is there a style or substance reason for the way the book version is
> coded?

Here is one way to describe n!

F(n) = 0 if n = 1
F(n) = n * F(n-1) if n > 0

Here another way to describe n!

(cond ((= n 0) 1)
(else (* n (F (- n 1)))))

Here is one way to define ++

n ++ 0 = n
n ++ m = n + (k + 1) = (n + k) + 1 if m > 0

Here is another way to define ++

(cond ((= m 0) n)
(else (+ (++ n (- m 1)) 1)))

Two different ways to express recursion equations, math and Lisp.

- - - - - - - - - -
Early Lisp programs were similar to recursion equations, defining functions
on symbolic expressions. They differed from the equations of pure recursive
function theory by introducing the conditional expression construction.

Joe Marshall

2007-02-14, 7:10 pm

On Feb 13, 4:31 pm, dmh2...@gmail.com wrote:
>
> write a '+' function using zero?, add1 and sub1. My version looked
> like this:
>
> (define plus
> (lambda(n m)
> (cond
> ((zero? m) n)
> (else (plus (add1 n ) (sub1 m))))))
>
> where the book solution is
>
> (define plus
> (lambda(n m)
> (cond
> ((zero? m) n)
> (else (add1 (plus n (sub1 m)))))))
>
> both versions work. the difference I see is that my version computes
> on the way down the expression and then just pops all the way out,
> whereas the book version descends all the way down and then computes
> on the way back up.

Actually, your version doesn't go `down' at all. It sits in a loop
with the first argument getting bigger and the second getting smaller
until the second reaches zero.

> is there a style or substance reason for the way the book version is
> coded?
>
> (it seems to me the book version isn't tail recursive because it
> leaves the add1 operation pending after the recursion. am i reading it
> right?)

Yes, you are correct. In fact, your version is better than the book's
version because it uses fewer resources.

Sponsored Links