stable-memo: Memoization based on argument identity

[ data, library, mit ] [ Propose Tags ]

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

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

Below is an implementation of map that preserves sharing of the spine for cyclic lists. It should even be safe to use this on arbitrarily long, acyclic lists since as long as the garbage collector is chasing you, the size of the memo table should stay under control, too.

map :: (a -> b) -> [a] -> [b]
map f = go
  where go = memo map'
        map' []     = []
        map' (x:xs) = f x : go xs

This library is largely based on the implementation of memo found in "Stretching the storage manager: weak pointers and stable names in Haskell", from Simon Peyton Jones, Simon Marlow, and Conal Elliott (

Versions 0.1.1, 0.1.2, 0.1.3, 0.2.0, 0.2.1, 0.2.2, 0.2.3, 0.2.4, 0.3.0, 0.3.1
Dependencies base (>=4.6 && <5), hashtables (==1.0.*), tagged (==0.4.*) [details]
License MIT
Author Jake McArthur <>
Maintainer Jake McArthur <>
Category Data
Source repo head: darcs get
this: darcs get --tag v0.1.3
Uploaded by JakeMcArthur at Sat Oct 27 22:29:50 UTC 2012
Distributions NixOS:0.3.1
Downloads 3395 total (27 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]
Hackage Matrix CI




Maintainer's Corner

For package maintainers and hackage trustees