[plt-scheme] HtDP Exercise 21.1.2

On Dec 10, 2009, at 8:55 AM, Roman Sykora wrote:

> I should define fold as abstraction of the two given functions:
>
> ;; sum : (listof number) -> number , and
> ;; product : (listof number) -> number.
>
> After that I should define append in term of fold. Eventually I came
> up with:
>
> ;; fold : (X Y -> Z) Z (listof X) -> Z
> (define (fold f base lst)
>   (cond ((empty? lst) base)
>         (else (f (car lst) (fold f base (cdr lst))))))

This doesn't obey its own contract.  It calls "f" with, as its second  
argument, the result of "fold", which is a Z, not a Y.
Fortunately, all you have to do is replace the Y in the contract with  
a Z.

> ;; sum : (listof number) -> number
> (define (sum ln)
>   (fold + 0 ln))
>
> ;; sum tests
> (check-expect (sum '()) 0)
> (check-expect (sum '(1 2 3 4 5)) 15)
>
> ;; product : (listof number) -> number
> (define (product ln)
>   (cond ((empty? ln) 0)
>         (else (fold * 1 ln))))
>
> ;; product tests
> (check-expect (product '()) 0)
> (check-expect (product '(1 2 3 4 5)) 120)

Why is "product" so much more complicated than "sum"?  Because you  
had to take special measures to make sure the answer on the empty  
list was 0.  But why should the answer on the empty list be 0?  Is  
there anything else that could be a reasonable "right answer" for the  
product of an empty list?

For another view on this issue, try writing "any-true?", which takes  
a list of Booleans and tells whether any of them are true, and then  
"all-true?" which takes a list of Booleans and tells whether ALL of  
them are true.  First write these recursively, using the usual  
template for lists; they should both be pretty simple.  Then rewrite  
them using "fold".  (For the "fold" versions, you may need to write a  
very short, simple helper function for each, not for any fundamental  
reason but because of language implementation issues.)

> ;; my-append : list list -> list
> (define (my-append l1 l2)
>   (fold concat '() (list l1 l2)))

which expands to, precisely, (concat l1 (concat l2 '())).  In other  
words, you're not really using the power of "fold", which is about  
calling some function a VARIABLE number of times, once for each  
element of a list.  That's why "my-append" and "concat" seem to do  
the same thing.

However, you CAN write "my-append" by applying "fold" to a much  
simpler (in fact, built in!) function than "concat", and that's what  
the exercise was asking for.


Stephen Bloch
sbloch at adelphi.edu