[plt-scheme] HTDP 21.1.2

From: wooks . (wookiz at hotmail.com)
Date: Fri Jul 14 23:30:23 EDT 2006


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?




Posted on the users mailing list.