[plt-scheme] HTDP 21.1.2

Wooks-

On Jul 11, 2006, at 8:58 AM, wooks . wrote:

> fold is a reducing function - produces a consolidated value from  
> multiple inputs (eg list).
>
> map is a one to one function.
>
> So there is a mismatch at contract level  (hence why methinksh  
> trick question) .

Its a _tricky_ question, not a trick question.

Richard's suggestion was sound; you haven't shown us the circles you  
drew according to his instructions, so we can't critique your work  
there, and must assume that you made a mistake in the execution of  
his suggestion.

But, since you brought up contracts, lets look at the contracts for  
map and fold, and see if that leads us down a different path for the  
solution.

;; 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

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]

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.

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

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?   
How should S be instantiated?

(Hint: go back write the instantiation of fold for sum, product,  
_and_ append.  Look at the resulting classes of data.)

-Felix