[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