-----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-----