[plt-scheme] HTDP 21.1.2 - trying to put it together

From: wooks . (wookiz at hotmail.com)
Date: Sat Jul 15 19:52:12 EDT 2006

Starting from the top with all the rough working

We have

;map: (X -> Y) [listof X] -> [listof Y]
;fold: (A B -> B) B [listof A] -> B

We want to implement map in terms of fold which means we want fold to 
produce [listof Y]

substituting [listof Y] for B in folds result

;fold (A B -> B) B [listof A] -> [listof Y]

...and all other places within folds contract

;fold (A [listof Y] -> [listof Y])  [listof Y] [listof A] -> [listof Y]

thus far defining map in terms of fold gives us

(define (map f a-list)
   (fold someFunc someValue a-list))

but we know that the result of applying map to an empty list should be an 
empty list

hence we substitute someValue with empty

(define (map f a-list)
   (fold someFunc empty a-list))

Now to define someFunc.

Well its contract must conform to

;someFunc: X [listof Y] -> [listof Y]

If we plug in Y for X and consider that Y is supposed to result from 
applying  (the function we are mapping) to X
then someFunc begins to look like this

(define (someFunc f aloy)
   (..... f ..... (first aloy)  (rest aloy))

where f is a function with a contract

(X -> Y)

To produce a list as required by the contract  we have to use cons 
somewhere.

I would have said

(define (someFunc f aloy)
    (cons (f first aloy) (rest aloy)))

but it's not right - is it.




Posted on the users mailing list.