[Haskell-cafe] Re: Memoization

[Isaac Dupree]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

apfelmus wrote:
> Mark Engelberg wrote:
>> I'd like to write a memoization utility.  Ideally, it would look
>> something like this:
>>
>> memoize :: (a->b) -> (a->b)
>>
>> memoize f gives you back a function that maintains a cache of
>> previously computed values, so that subsequent calls with the same
>> input will be faster.
> 
> Note that due to parametricity, any function of this type is necessarily
> either id or _|_. In other words, there are only two functions of type
> 
>   ∀a∀b. (a->b) -> (a->b)
> 
> That's because the functions has to work for all types a and b in the
> same way, i.e. it may not even inspect how the given types a or b look
> like. You need type classes to get a reasonable type for the function
> you want
> 
>   memoize :: Memoizable a => (a->b) -> (a->b)

Due to modified parametricity, we have not only
id, ($), undefined :: ∀a∀b. (a->b) -> (a->b)
- --"($) = id" is a correct definition
but also
($!) :: ∀a∀b. (a->b) -> (a->b)
, because of the decision not to require a type-class context for seq.

Also GHC has special id-like functions such as 'lazy' and 'inline'... if
memoize is indistinguishable from id except in space/time usage, it
would be permissible as a compiler primitive.

Isaac
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGWZPSHgcxvIWYTTURAigfAJ0eOBSP5zcXFxj/E/IlhqZRj0y06gCggAjq
We0TmsRK5jYHk9L3SEijEzE=
=wO/L
-----END PGP SIGNATURE-----