[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