seq/parametricity properties/free theorems and a proposal/question
wren ng thornton
wren at freegeek.org
Sat Mar 19 05:44:07 CET 2011
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
More information about the Libraries
mailing list