[plt-scheme] HTDP 21.1.2

>From: Richard Cobbe <cobbe at ccs.neu.edu>
>To: plt-scheme at list.cs.brown.edu
>Subject: Re: [plt-scheme] HTDP 21.1.2
>Date: Tue, 11 Jul 2006 09:31:35 -0400
>
>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?
>

the contract instantiates to

;map : (listof numbers -> number) [listof listof numbers] -> [listof 
numbers]


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

fold: ([listof numbers] [listof numbers] -> [listof numbers]) [listof listof 
Numbers] -> [listof Numbers]