How are Dynamic Programming algorithms implemented in idiomatic Haskell?

Question

The common way to do this is via lazy memoization. In some sense, the recursive fibonacci function can be considered dynamic programming, because it computes results out of overlapping subproblems. I realize this is a tired example, but here’s a taste. It uses the data-memocombinators library for lazy memoization.

import qualified Data.MemoCombinators as Memo

fib = Memo.integral fib'
    where
    fib' 0 = 0
    fib' 1 = 1
    fib' n = fib (n-1) + fib (n-2)

fib is the memoized version, and fib' just “brute forces” the problem, but computes its subproblems using the memoized fib. Other DP algorithms are written in this same style, using different memo structures, but the same idea of just computing the result in a straightforward functional way and memoizing.

Edit: I finally gave in and decided to provide a memoizable typeclass. That means that memoizing is easier now:

import Data.MemoCombinators.Class (memoize)

fib = memoize fib'
    where
    fib' :: Integer -> Integer  -- but type sig now required 
    ...

Instaead of needing to follow the type, you can just memoize anything. You can still use the old way if you like it.

Leave a Comment Cancel reply