# [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]