[plt-scheme] HTDP 21.1.2

On Tue, Jul 11, 2006 at 01:58:09PM +0100, wooks . wrote:

> fold is a reducing function - produces a consolidated value from multiple 
> inputs (eg list).
> 
> map is a one to one function.
> 
> So there is a mismatch at contract level  (hence why methinksh trick 
> question) .

Ah -- this is a common mistake.  Let's look at the contracts for map and
fold:

    map :: (X -> Y) (Listof X) -> (Listof Y)

    fold :: A (B A -> A) (Listof B) -> A

Since these contracts have these weird X and Y things in them, we can
effectively use map with a different contract every time.

    (map square (list 1 2 3))  -->  (list 1 4 9)
    ;; map :: (Num -> Num) (Listof Num) -> (Listof Num)
    ;; that is, X = Num and Y = Num

    (map even? (list 1 2 3))   -->  (list false true false)
    ;; map :: (Num -> Boolean) (Listof Num) -> (Listof Boolean)
    ;; that is, X = Num and Y = Boolean

Now, let's look at an application of map that's a little different from
ones you've seen before.

    ;; how-many :: (Listof Z) -> Nat  (i.e., natural number)
    ;; counts the number of items in a list.
    (define (how-many l)
      (cond 
        [(null? l) 0]
        [(cons? (car l)) (+ 1 (how-many (cdr l)))]))

    (map length (list (list 1 2 3)
                      (list 4 5)
                      (list 6 7 8 9)))

What are X and Y in this application of map?

Once you've figured that out, take another look at the contracts for
fold and map and see if you can't figure out how to fit them together.

Richard