Function memoization goes back at least as far as Donald Michie’s 1968 paper. The idea is to stash away results of a function call for reuse when a function is called more than once with the same argument. Given an argument, the memoized function looks up the argument in the internal memo table (often a hash table). If found, the previously computed result is reused. Otherwise, the function is applied, and the result is stored in the table, keyed by the argument. The table and its mutation are kept private from clients of the memo function.
Perhaps surprisingly, memoization can be implemented simply and purely functionally in a lazy functional language. Laziness allows the implementation to build the memo table once and for all, filling in all the results for the function at all domain values. Thanks to laziness, the values don’t actually get computed until they’re used. As usual with lazy data structures, once a component has been evaluated, future accesses come for free.
The implementation described in this post is based one I got from Spencer Janssen. It uses the essential idea of Ralf Hinze’s paper Generalizing Generalized Tries. The library is available on Hackage and a darcs repository. See the wiki page and hackage page for documentation and source code. I’ve compiled it successfully with ghc versions 6.8.2 through 6.10.3.
- 2009-02-12: Fixed typo.
- 2009-11-14: Hackage page pointer.
- 2009-11-20: Fixed source code pointer.
The central idea of the function memoizer is associating a type of trie to each domain type want to memoize over.
class HasTrie a where
data (↛) a ∷ * → *
a ↛ b represents a trie that maps values of type
a to values of type
b. The trie representation depends only on
a. For more information on the recent "associated types" feature of Haskell, see Associated Types with Class.
In addition to the trie type, the
HasTrie class contains converters between functions and tries:
trie ∷ (a → b) → (a ↛ b)
untrie ∷ (a ↛ b) → (a → b)
untrie methods must be inverses:
trie ∘ untrie ≡ id
untrie ∘ trie ≡ id
HasTrie class, memoization is trivial to implement:
memo ∷ HasTrie a ⇒ (a → b) → (a → b)
memo = untrie ∘ trie
The second inverse property implies that memo is the identity function (semantically).
Multi-argument curried functions can be memoized by repeated uses of
memo. See the source code.
Some trie representations
Now let’s consider choices for trie representations. As in Generalizing Generalized Tries, the key is to exploit some type isomorphisms.
1 → a ≅ a
(a + b) → c ≅ (a → c) × (b → c)
(a × b) → c ≅ a → (b → c)
which correspond to the familiar laws of exponents
a1 = a
ca + b = ca × cb
ca × b = (cb)a
Writing these type isomorphisms in Haskell:
(() → a) ≅ a
(Either a b → c) ≅ (a → c, b → c)
((a,b) → c) ≅ (a → (b → c))
Start with the simplest domain, namely
(). Since there is only one (non-bottom) value of type
(), a trie over
() contains just a single value, as suggested in the isomorphism equation.
instance HasTrie () where
data () ↛ a = UnitTrie a
trie f = UnitTrie (f ())
untrie (UnitTrie a) = const a
A trie for sum-valued domains contains two tries:
instance (HasTrie a, HasTrie b) ⇒ HasTrie (Either a b) where
data (Either a b) ↛ x = EitherTrie (a ↛ x) (b ↛ x)
trie f = EitherTrie (trie (f ∘ Left)) (trie (f ∘ Right))
untrie (EitherTrie s t) = either (untrie s) (untrie t)
While a trie for pair-valued domains contains nested tries:
instance (HasTrie a, HasTrie b) ⇒ HasTrie (a,b) where
data (a,b) ↛ x = PairTrie (a ↛ (b ↛ x))
trie f = PairTrie (trie (trie ∘ curry f))
untrie (PairTrie t) = uncurry (untrie ∘ untrie t)
Exercise: Prove that
untrie are inverses of each other (in both directions) for the definitions above. My proofs are in the source code.
Tries for other types, such as
Bool, can be implemented via isomorphisms using the types above, or directly. For instance, an unsigned word can be converted to a list of booleans:
instance HasTrie Word where
data Word ↛ a = WordTrie ([Bool] ↛ a)
trie f = WordTrie (trie (f ∘ unbits))
untrie (WordTrie t) = untrie t ∘ bits
bits ∷ Bits t ⇒ t → [Bool]
unbits ∷ Bits t ⇒ [Bool] → t
I hope you’ve gotten a taste of the elegance this functional means of making memo functions. Future blog posts will include:
- algebraic construction of memo tries, using type class morphisms, and
- the use of memo tries for simple and efficient representations of general linear maps.