[plt-scheme] HTDP 21.1.2
Having re-read as threatened I shall have another go at this
>From: Felix Klock's PLT scheme proxy <pltscheme at pnkfx.org>
>To: "wooks ." <wookiz at hotmail.com>
>CC: plt-scheme at list.cs.brown.edu
>Subject: Re: [plt-scheme] HTDP 21.1.2
>Date: Tue, 11 Jul 2006 09:26:19 -0400
>
>Wooks-
>
>On Jul 11, 2006, at 8:58 AM, wooks . wrote:
>;; map : (X -> Y) [Listof X] -> [Listof Y]
>
>;; fold : hmm, you didn't give a contract for fold in the code you posted
>earlier. Shame on you for still failing to follow the design recipe; at
>some point people are going to stop responding.
>
>But since I want to actually put content in this post, and since you could
>find this information from Figure 57, I'll fill in the blank, using the
>argument order you gave in your post.
>
>;; fold : X (X Y -> Y) [Listof X] -> Y
>
combining conventionality with the correction that you supplied
;;fold : (X Y -> Y) Y [Listof X] -> Y
>Now, if you look at these two contracts, they certainly look very
>different. map takes two arguments, fold takes three; plus, map returns a
>[Listof Y], while fold returns a Y. So how could we hope to implement map
>in terms of fold, as you say?
>
>The mistake in the reasoning in the preceding paragraph is the assumption
>that the X's and Y's in the contract for map have anything to do with the
>X's and Y's in the contract for fold. Each pair of parameters is
>independent, implicitly quantified in each contract. If we wanted to be
>really formal about it, we could have written our contracts like so:
>
>;; map : forall X,Y . (X -> Y) [Listof X] -> [Listof Y]
>
The scope of the parametric data types does not extend beyond the specific
contract in which they are used.
>What this is saying is that X and Y are contract parameters that, at each
>invocation of map, you can replace with different classes of data. Thus,
>we can plug in X:=Num, Y:=String to get:
>
>;; map : (Num -> String) [Listof Num] -> [Listof String]
>
>This is often called "instantiation" or "speciailizaton" of the contract;
>we're taking our (very general) contract and deriving a more specific one
>for our particular needs at one point in the program.
>
Memo to self think Prolog from hereonin.
>Likewise,
>;; fold : forall X, Y . X (X Y -> Y) [Listof X] -> Y
>
>Once again, the X's and Y's in the contract for fold are independent from
>the X's and Y's for map, and we could instantiate it like so: X:=Num
>Y:=Num to yield
>
>;; fold : Num (Num Num -> Num) [Listof Num] -> Num
>
>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
>This makes it crystal clear that the parameters for fold are totally
>different from the ones for map.
>
>Now my question for you, wooks, is this:
>
>We have:
>
>;; map : (X -> Y) [Listof X] -> [Listof Y]
>;; fold : S (S T -> T) [Listof S] -> 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]
>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?