seq/parametricity properties/free theorems and a proposal/question

[wren ng thornton]

On 3/18/11 11:12 AM, Max Bolingbroke wrote:
> Furthermore, this solution
> would not help unless you did not have a Seq (a ->  b) instance,

Exactly put.

> but
> such an instance could be necessary to avoid some space leaks, since
> you can write stuff like:
>
> case holds_on_to_lots_of_memory of
>    True ->  \x ->  x-1
>    False ->  \x ->  x+1
>
> So there are eminently practical reasons for polymorphic seq.

You can do more than avoid memory leaks with this sort of thing. In my 
current project I use tricks like this extensively in order to perform 
partial _evaluation_, thereby lifting shared computations out of loops 
and improving the computational complexity of the program. (As well as 
constant factors. The constant factors alone give ~10% speedup.)

Of course, I am relying on the fact that I will never pass an undefined 
value to the resulting function (I hope). Otherwise, as mentioned 
elsewhere, performing the partial evaluation wouldn't be correct. One 
way to have this cake and eat it too would be if we explicitly 
distinguished between pointed and unpointed function spaces. It'd be 
perfectly fine to have,

     instance Seq (!a -> b) where seq = compilerMagic

Since the types ensure that eta conversion won't affect semantics.

-- 
Live well,
~wren