Memoizing higher-order functions
Memoization incrementally converts functions into data structures. It pays off when a function is repeatedly applied to the same arguments and applying the function is more expensive than accessing the corresponding data structure.
In lazy functional memoization, the conversion from function to data structure happens all at once from a denotational perspective, and incrementally from an operational perspective. See Elegant memoization with functional memo tries and Elegant memoization with higher-order types.
As Ralf Hinze presented in Generalizing Generalized Tries, trie-based memoization follows from three simple isomorphisms involving functions types:
1 → a ≅ a
(a + b) → c ≅ (a → c) × (b → c)
(a × b) → c ≅ a → (b → c)
which correspond to the familiar laws of exponents
a ^ 1 = a
ca + b = ca × cb
ca × b = (cb)a
When applied as a transformation from left to right, each law simplifies the domain part of a function type. Repeated application of the rules then eliminate all function types or reduce them to functions of atomic types. These atomic domains are eliminated as well by additional mappings, such as between a natural number and a list of bits (as in patricia trees). Algebraic data types corresponding to sums of products and so are eliminated by the sum and product rules. Recursive algebraic data types (lists, trees, etc) give rise to correspondingly recursive trie types.
So, with a few simple and familiar rules, we can memoize functions over an infinite variety of common types. Have we missed any?
Yes. What about functions over functions?
Edits:
- 2010-07-22: Made the memoization example polymorphic and switched from pairs to lists. The old example accidentally coincided with a specialized version of
trieitself. - 2011-02-27: updated some notation