[plt-scheme] HTDP 21.1.2

From: wooks . (wookiz at hotmail.com)
Date: Sat Jul 15 06:54:59 EDT 2006




>From: "wooks ." <wookiz at hotmail.com>
>To: plt-scheme at list.cs.brown.edu
>Subject: Re: [plt-scheme] HTDP 21.1.2
>Date: Sat, 15 Jul 2006 04:54:41 +0100
>
>
>
>
>>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]
>

My bad as pointed out by Felix.

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




Posted on the users mailing list.