[plt-scheme] HTDP 21.1.2

Wooks-

On Jul 14, 2006, at 11:30 PM, wooks . wrote:

>> The names don't matter at all; in fact, we could instead use the   
>> names S and T:
>>
>> ;; fold : forall S, T . S (S T -> T) [Listof S] -> T
>>
>
> Per our agreed correction
> We mean
>
> ;fold : (S T -> T) [Listof S] -> T

Well, no, with the correction I wrote earlier, it should be:

; fold : T (S T -> T) [Listof S] -> T

That is, fold takes three arguments: an initial element from T, a  
combiner that takes an S and T and produces a T, and a list of S's,  
and from these three arguments, fold produces a T.


>> So, what class of data could you plug in for the contract  
>> parameter T  to make fold return the same class of data as map?   
>> When you do this  plugging in, what is the resulting instantiated  
>> contract for fold?
>
>
> T should be [Listof Y] so we get
>
>
> ;fold:  (S [Listof Y]  -> [List of Y])      [Listof S]    ->      
> [Listof Y]

This is consistent with what you wrote above, but incorrect since  
your contract left out the initial T.

>
>> How should S be instantiated?
>>
>
> Presumably you mean how should S be instantiated to produce map -  
> don't know
>
>> (Hint: go back write the instantiation of fold for sum, product,   
>> _and_ append.  Look at the resulting classes of data.)
>>
>
> S instantiates to Y?
>
> So my contract for fold becomes
>
> ;fold : (Y [Listof Y] -> [Listof Y])  [Listof Y] -> [Listof Y].
>
> Subject to my last answer being right I am confident that I  
> understand what I've been told. However with greater understanding  
> comes greater confusion because I'm now sure I don't understand  
> what is expected from the question. I'm also not sure that what I  
> did with append was right. Hmmmm?

I'm going to play around a bit to try to illustrate the kind of  
thinking process I am suggesting.  The answer I'm going to get at the  
end will be flawed (semi-deliberately), so I'm not claiming that this  
is a perfect technique for development.  Its just an illustration.

Let's use append as an example.

----

We are given:

; fold : T (S T -> T) [Listof S] -> T

and we've already established what fold does.

Using the given fold, we want to develop a function append, which  
takes two lists of X's and produces a single list of the X's from  
both lists.

; append : [Listof X] [Listof X] -> [Listof X]
; produces a list of all of the elements of lst-one in front of the  
elements of lst-two
(define (append lst-one lst-two)
     ...)

Now, I'm telling you upfront that I want to use fold to accomplish  
this goal, just to see if I can.

; append : [Listof X] [Listof X] -> [Listof X]
(define (append lst-one lst-two)
     (fold ... ... ...)) ;;; as a reminder, I've put three sets of  
ellipses since fold takes three arguments

I don't know whether the above template will work or not, but I'm  
just experimenting with my options.

Whatever the body of append does, it needs to produce a [Listof X].   
But fold produces a T.  So if I want this to make any sense at all, I  
need to instantiate fold's parametric contract, plugging in [Listof  
X] for T.  Let's write down this more specific contract for fold:

; fold : [Listof X] (S [Listof X] -> [Listof X]) [Listof S] ->  
[Listof X]

So fold is going to take one list of X's, and some sort of combining  
function, and a list of S's.

Consider our skeleton for append again:

; append : [Listof X] [Listof X] -> [Listof X]
(define (append lst-one lst-two)
     (fold ... ... ...))

Our invocation of fold needs a [Listof S] for the third argument,   
But we have no [Listof S].  Ah, but S is a parameter in the  
contract. . . and we do have these two lists of X's floating around  
here.  So perhaps we can plug X in for S, just to satisfy the  
requirements of fold.

So now we have instantiated both the S and the T in our parametric  
contract for fold.  True, we haven't made it a fully concrete  
contract, because the X is floating around, but that's okay, because  
at the point that we are invoking fold within the body of append, it  
will be the responsibility of the client of append to instantiate X  
to something sensible.

; fold : [Listof X] (X [Listof X] -> [Listof X]) [Listof X] ->  
[Listof X]

Okay, so now we know that fold needs to take three arguments: a list  
of X's, some sort of combining function, and another list of X's.   
Hey, we've already got two lists of X's: lst-one and lst-two, the two  
arguments to append.

(define (append lst-one lst-two)
     (fold lst-one ... lst-two))

So we just need to fill in that middle parameter and see if that does  
the job.

Let's see... what's a function that takes an X, and a list of X's,  
and yields a list of X's?

There's a lot of such functions, I suppose:
(define (combine-1 an-x some-xs) some-xs)
(define (combine-2 an-x some-xs) empty)

but I'm betting you can think of something else that uses both an-x  
and some-xs and puts them together in some way to make a new list of  
X's.

----

This last bit is "easy" for append (see caveat below).  The real  
insight comes when you see how to apply the same process for  
developing the map function in terms of fold.

----

As I said at the outset, this was only playing, and the end solution  
is actually flawed.

As in, you're not going to actually come up with a correct  
implementation of append without going back and revising some of the  
arbitrary decisions that I made along the way.

But the contracts gave me guidance; they cut down the search space of  
possible things to plug in, without guesswork on my part trying to  
make sure I come up with something that isn't going to make DrScheme  
pop up with an error message.

-Felix