@hackage stable-memo0.1.1

Whereas most memo combinators memoize based on equality, stable-memo does it based on whether the exact same argument has been passed to the function before (that is, is the same argument in memory).

• This can be more suitable for recursive functions over graphs with cycles.

• stable-memo doesn't retain the keys it has seen so far, which allows them to be garbage collected if they will no longer be used. Finalizers are put in place to remove the corresponding entries from the memo table if this happens.

• Data.StableMemo.Weak provides an alternative set of combinators that also avoid retaining the results of the function, only reusing results if they have not yet been garbage collected.

• There is no type class constraint on the function's argument.

stable-memo will not work for arguments which happen to have the same value but are not the same heap object. This rules out many candidates for memoization, such as the most common example, the naive Fibonacci implementation whose domain is strict Ints; it can still be made to work for some domains, though, such as the lazy naturals.

data Nat = Succ Nat | Zero

fib :: Nat -> Integer
fib = memo fib'
  where fib' Zero                = 0
        fib' (Succ Zero)         = 1
        fib' (Succ n1@(Succ n2)) = fib n1 + fib n2

This implementation is largely based on the one found in "Stretching the storage manager: weak pointers and stable names in Haskell", from Simon Peyton Jones, Simon Marlow, and Conal Elliott (http://community.haskell.org/~simonmar/papers/weak.pdf).