Well, it’s not perfect, but it is filling a hole that has been mostly absent for far too long: I just uploaded the data-memocombinators library to hackage. The idea is to abstract away the manual memoization everybody keeps doing and pack them away in tidy little combinators.
For those out of loop of popular CS vernacular, “memoization” is a stupid name for “caching”. As a rather trivial example, take the naive definition of the fibonacci function:
fib :: Integer -> Integer
fib n = if n <= 1 then n else fib (n-1) + fib (n-2)
This runs in exponential time (a rather beautiful O(φn) where φ is the golden ratio). If we want to make this run in linear time without using our brains, we just cache (er, memoize) the intermediate results.
import qualified Data.MemoCombinators as Memo
fib :: Integer -> Integer
fib = Memo.integral fib'
where
fib' n = if n <= 1 then n else fib (n-1) + fib (n-2)
Note how the recursive call in fib' is to fib, not fib'.
There is also a library (heh, by Conal—who, contrary to what one might believe by analysis of interests, I am not :-), called MemoTrie, which does the same thing. However I don’t agree with the typeclass approach to this problem. We are concerned not simply whether or not you can memoize a particular type, but how. For example, for some problem you may know that you only want to memoize integers less than 1000, or that you want to use a fast array for those and a binary trie for the rest, or that you accept Eithers, and you want to memoize Lefts but not Rights. This is why, as the name suggests, data-memocombinators provides combinators for building nicely controlled memo tables.
I would like this library to grow, so if anybody has any suggestions or implementations for memo tables they use commonly, do send them along!
Nice library, Luke !
It is pretty fast, too – for the TSP problem below only 2x slower than with the (STUArray-based) Memo module I’ve used originally – which requires to ‘monadify’ the code though. Memo implementations based on Map/IntMap are quite handy sometimes as well – but it depends on your use case, of course.
What other (realistic) uses cases despite DP do you have for memoization ?
-- take the number of nodes, the edge cost function and
-- return the tour with minimal cost (ATSP).
solveTSP :: Int -> (Int -> Int -> Int) -> Int
solveTSP n cost = solver (n-1) (1 `shiftL` (n-1) - 1) where
solver = Memo.memo2 (range n) (range $ 2^(n-1)) puresolver
range n = Memo.unsafeArrayRange (0::Int,n-1)
puresolver :: Int -> Int -> Int
puresolver y 0 = cost y (n-1)
puresolver y set
= minimum $ map (\x -> (cost y x) + solver x (set `clearBit` x))
(filter (set `testBit`) [0..(n-1)])
> This runs in exponential time (a rather beautiful O(φn) where φ is the golden ratio)
A nicer bound is that fib n is
.
I wouldn’t want to take credit for this library. I adapted it from code I got from Spencer Janssen. I liked the solution (based on Ralf Hinze’s work, I assume) so much that I wanted to play with it and share it with others. In the process, I realized the nice tie-in with type class morphisms.