[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