Thu May 6 14:24:14 EDT 2010

Memoizing (==) in Haskell

Necessity for memoization of (==) pops up when comparing recursively
defined datatypes.

This is actually an interesting problem, as memoization is usually
based on (==) in the first place!

From [1] I'm pointed to Hughes' lazy memo functions[2].  The
introduction talks about memoization as a fix-up ingredient for very
high level programming, preserving modularity.  The `unique' function
implemented in terms of memoized constructors (hash consing) is
probably what I'm looking for.  What I didn't realized is that this
can be defined in terms of a generic `memo' function.  Haskell does
seem to have a standard memo function[3].

[1] http://conal.net/blog/posts/memoizing-polymorphic-functions-part-one/
[2] http://www.cs.chalmers.se/~rjmh/Papers/hughes_85_lazy.pdf
[3] http://www.haskell.org/ghc/docs/5.00/set/memo-library.html
[4] http://www.haskell.org/haskellwiki/Memoization