data-memocombinators

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!

About these ads

3 thoughts on “data-memocombinators

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

  2. > This runs in exponential time (a rather beautiful O(φn) where φ is the golden ratio)

    A nicer bound is that fib n is \Phi(fib n).

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

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s