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

wooks




>From: Chris Warrington <chrisw at rice.edu>
>Reply-To: Chris Warrington on the PLT Scheme List 
><plt-scheme at list.cs.brown.edu>
>To: wooks on the PLT Scheme List <plt-scheme at list.cs.brown.edu>
>Subject: Re: [plt-scheme] HTDP 21.1.2 - trying to put it together
>Date: Sat, 15 Jul 2006 23:00:51 -0400
>
>
>wooks . @ 2006-7-15 7:52:12 PM
>"[plt-scheme] HTDP 21.1.2 - trying to put it together" 
><mid:BAY103-F568FFDE8392B4A82B38C1C06C0 at phx.gbl>
>
><SNIP>
>
> > ;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 empty a-list))
>
> > Now to define someFunc.
>
> > Well its contract must conform to
>
> > ;someFunc: X [listof Y] -> [listof Y]
>
>All of what you've said so far looks good to me.
>
> > 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.
>
>Yes.
>
> > I would have said
>
> > (define (someFunc f aloy)
> >     (cons (f first aloy) (rest aloy)))
>
> > but it's not right - is it.
>
>What's the contract of someFunc now? Does it match (A [listof Y] ->
>[listof Y])?
>
>If you look at someFunc's contract, it is very close, but needs to be
>"flattened" (I'm not sure if that's technically the correct word.). Is
>there some way to flatten it?
>

Yes this is where it went ropey. In somefunc X is a function ... but such an 
instantiation  would make the 3rd parameter of fold a [listof functions] 
.... and of course it is not.

ergo X is a value ... whatever our input is made of .... let me see if 
exemplification is going to help.

If we wish to map a function square to a list of numbers with fold then by 
our earlier incantations

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

hence somefuncs contract is

;somefunc:  number [listof number] [listof number]

et voila

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

n'est pas possible because  f is supposed to be a number.

how do we combine an input number and a list to produce a list ----- with 
cons.

But our first input to somefunc is an X - it's supposed to be turned into a 
Y ...... but somefunc doesn't know what to use to turn the X into a Y 
because we haven't got a slot in the contract for the input 
function............I've "lost" the (X -> Y)  ...the only thing I can think 
of now is making somefunc local to the definition of the map function to 
bring the (X -> Y) from map within the scope of somefunc.