[plt-scheme] Was HTDP 21.1.2 - Why I "don't" use the design recipe

Wooks-

On Jul 13, 2006, at 5:31 AM, wooks . wrote:

> I am extremely appreciative of all the help I have gotten here but  
> I wish to say something that  I think applies generally to people  
> of my background.
> [[snip]]

I feel the design recipe is targeted at teaching new programmers how  
to write maintainable code, not to teach them how to maintain code  
that has been developed in the wild.

I agree that being able to maintain undomesticated code is a very  
useful skill.  However, I have encountered very few ways to actually  
teach such skills, because undomesticated code is often by its nature  
unmaintainable by any pre-established method.


>> 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?
>>
>
> Maybe I should ask the question that struck me immediately I saw  
> this problem. Why would I want to do this anyway. Map and fold are  
> clearly intuitive one is a translation the other is a  
> summarisation. I cannot intuitively see why I would want to  
> implement a translation in terms of a summarisation.

Its an exercise.  But its also something that comes up in practice,  
this act of building a simple function like map on top of a general  
function like fold.

My feeling about this particular exercise is that its meant to test  
your ability to use tools like fold to their full power.  Once you  
see how to implement map (and how incredibly simple it actually  
*is*), hopefully you'll see this "summarizing" power of fold is much  
more general than you might have realized.

>> ...
>>
>> Likewise,
>>
>> ;; fold : forall X, Y . Y (X Y -> Y) [Listof X] -> Y
>>
>
> Well I had a more conservative
> ;; fold : X (X X -> X) (listof X)  ->  X

This is *too* conservative.  If this were the contract for fold, you  
would not be able to implement map using it.

Not only that, but you would not be able to implement append either,  
if this were the most general contract for fold.

This makes me very curious to see how you chose to implement append,  
and how you decided to instantiate the parameter X to accomplish that  
goal.

>> 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 . T (S T -> T) [Listof S] -> T
>
> I would more readily accept this with an example of a case where we  
> summarised 2 different types of data - but lets see.
>
>>
>> This makes it crystal clear that the parameters for fold are  
>> totally  different from the ones for map.
>>
>
> Hmmm well all the instantation and matching stuff  looks a lot like  
> prolog - but no its not crystal clear because the reason why I  
> would want to do this is not intuitive.

I'm not sure what "this" is in the above sentence, so I'll take some  
guesses and answer each one.

* You want to implement map in terms of fold.  Why?  (1) Because its  
a good pedagogical exercise to help you see the power of functions  
like fold.  (2) Because oftentimes you will need to implement  
function A and you really have to layer it on top of function B, for  
whatever reason, and understanding how to adapt B to fit the needs of  
A is important. (3) Because we're testing to see if you understand  
how to work with parametric contracts such as those for map and fold.

* You want to instantiate the parameters in contracts.  Why?  Well,  
this is just my view on things, not official HtDP philosophy, but my  
attitude is that the parameters in these contracts exist solely to be  
instantiated to more specific types of data.  We have no class of  
data named X or S or T; we have things like String and Number and  
[Listof Symbol].  So if you want to use functions like map or fold,  
you need to first take their general contracts and make them more  
specific by plugging in the class of data that you happen to care  
about at the point of invocation (of map or fold).  You don't always  
have to plug in a completely concrete class; you could plug in  
[Listof X] for S, or even just X for S.  The idea is to adapt the  
function you're given (fold) to the needs of the function you are  
trying to write (map).

>> Now my question for you, wooks, is this:
>>
>> We have:
>>
>> ;; map :  (X -> Y) [Listof X] -> [Listof Y]
>> ;; fold : T (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?
>
> T would have to be a list.

"list" is not a class of data.  What kind of list?  A [Listof  
String]?  (Probably not, since the word String doesn't appear  
anywhere in the contract for map...)

>> When you do this  plugging in, what is the resulting instantiated  
>> contract for fold?
>
> ;fold : list (S list of S -> list of S)

I can't read this.  Either you have the parentheses mixed up in your  
contract, or you're telling me in some manner that fold is not a  
function, but instead a list of functions, which doesn't make sense  
for fold.

-Felix