Writing Efficient Dynamic Programming Algorithms in Haskell

Dynamic programming (DP) relies on two properties: optimal substructure and overlapping subproblems. In imperative languages, DP typically means filling in a mutable array in a specific order. Haskell does not have mutable variables by default, so implementing DP efficiently requires a different mindset. The good news is that Haskell's lazy evaluation provides a natural mechanism for memoization, and the language offers several array types that support O(1) indexing.

This article covers four practical techniques for DP in Haskell, progressing from the simplest lazy-list approach to high-performance mutable arrays in the ST monad.

Technique 1: Lazy List Memoization

Haskell's laziness means that values in a data structure are not computed until they are needed, and once computed, they are cached. You can exploit this by defining a list (or other lazy structure) where each element depends on previously computed elements:

1fibs :: [Integer]
2fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
3
4-- Usage
5-- fibs !! 10 = 55
6-- take 10 fibs = [0,1,1,2,3,5,8,13,21,34]

This works because Haskell evaluates each element of fibs at most once. The list acts as a memo table. However, list indexing with !! is O(n), so this approach is only suitable for problems where you access elements sequentially or need only the last few values.

For the classic 1D DP problem of counting stair-climbing ways (you can take 1 or 2 steps at a time):

1climbStairs :: Int -> Integer
2climbStairs n = ways !! n
3  where
4    ways = 0 : 1 : 2 : [ways !! (i-1) + ways !! (i-2) | i <- [3..n]]

Technique 2: Immutable Array Memoization

For O(1) random access, use Data.Array. You can define an array where each element's value depends on other elements in the same array. Haskell's laziness ensures elements are computed on demand:

1import Data.Array
2
3fibonacci :: Int -> Integer
4fibonacci n = table ! n
5  where
6    table = listArray (0, n) [fib i | i <- [0..n]]
7    fib 0 = 0
8    fib 1 = 1
9    fib i = table ! (i - 1) + table ! (i - 2)

This pattern generalizes to any DP problem. Here is the classic 0/1 knapsack:

1import Data.Array
2
3knapsack :: [Int] -> [Int] -> Int -> Int
4knapsack weights values capacity = table ! (n, capacity)
5  where
6    n = length weights
7    ws = listArray (1, n) weights
8    vs = listArray (1, n) values
9
10    table = listArray ((0, 0), (n, capacity))
11      [dp i w | i <- [0..n], w <- [0..capacity]]
12
13    dp 0 _ = 0
14    dp _ 0 = 0
15    dp i w
16      | ws ! i > w = table ! (i - 1, w)
17      | otherwise   = max (table ! (i - 1, w))
18                          (vs ! i + table ! (i - 1, w - ws ! i))

The array bounds define the full DP table, and each cell references other cells via the table array. Lazy evaluation ensures no cell is computed more than once.

Technique 3: Mutable Arrays with the ST Monad

For the best performance, especially on large DP tables, use mutable arrays inside the ST monad. This gives you the same fill-in-order style as imperative DP while keeping the overall computation pure:

1import Data.Array.ST
2import Data.Array.Unboxed
3import Control.Monad (forM_)
4import Control.Monad.ST
5
6editDistance :: String -> String -> Int
7editDistance s1 s2 = runST $ do
8    let m = length s1
9        n = length s2
10        a1 = listArray (1, m) s1 :: UArray Int Char
11        a2 = listArray (1, n) s2 :: UArray Int Char
12
13    dp <- newArray ((0, 0), (m, n)) 0 :: ST s (STUArray s (Int, Int) Int)
14
15    -- Base cases
16    forM_ [0..m] $ \i -> writeArray dp (i, 0) i
17    forM_ [0..n] $ \j -> writeArray dp (0, j) j
18
19    -- Fill the table
20    forM_ [1..m] $ \i ->
21        forM_ [1..n] $ \j -> do
22            let cost = if a1 ! i == a2 ! j then 0 else 1
23            above <- readArray dp (i - 1, j)
24            left  <- readArray dp (i, j - 1)
25            diag  <- readArray dp (i - 1, j - 1)
26            writeArray dp (i, j) (minimum [above + 1, left + 1, diag + cost])
27
28    readArray dp (m, n)

STUArray is an unboxed mutable array, which stores values without pointer indirection and is significantly faster than boxed arrays for numeric types. The runST function ensures the mutable state does not escape, so the function remains pure from the caller's perspective.

Technique 4: Using Data.Map for Sparse DP

When the DP state space is large but only a small fraction of states are actually visited (sparse problems), using Data.Map is more memory-efficient than allocating a full array:

1import qualified Data.Map.Strict as Map
2
3type Memo = Map.Map (Int, Int) Int
4
5coinChange :: [Int] -> Int -> Int
6coinChange coins target = fst $ solve target (length coins - 1) Map.empty
7  where
8    coinArr = listArray (0, length coins - 1) coins
9               :: Array Int Int
10
11    solve 0 _ memo = (1, memo)
12    solve amount idx memo
13      | amount < 0 || idx < 0 = (0, memo)
14      | otherwise = case Map.lookup (amount, idx) memo of
15          Just v  -> (v, memo)
16          Nothing ->
17            let (r1, memo1) = solve (amount - coinArr ! idx) idx memo
18                (r2, memo2) = solve amount (idx - 1) memo1
19                result = r1 + r2
20                memo3  = Map.insert (amount, idx) result memo2
21            in (result, memo3)

This approach threads the memo map through the recursion. While it works, the explicit state threading is verbose. For cleaner code, consider using the MemoTrie library or Data.MemoTable for automatic memoization.

Choosing the Right Technique

The decision depends on the problem characteristics:

1-- Small 1D problems with sequential access:
2--   Use lazy lists. Simple and idiomatic.
3
4-- Medium-sized problems with random access:
5--   Use Data.Array (immutable). Clean self-referential definition.
6
7-- Large problems requiring maximum performance:
8--   Use STUArray in the ST monad. Comparable speed to C.
9
10-- Sparse state spaces:
11--   Use Data.Map.Strict. Memory-efficient for large but sparse tables.

Common Pitfalls

• Using lists for random access. List indexing with !! is O(n) per lookup. For a 2D DP table of size N x M, this turns an O(NM) algorithm into O(N^2 * M^2). Always use arrays when random access is needed.
• Space leaks from laziness. Lazy evaluation can accumulate unevaluated thunks that consume far more memory than the actual values. Use seq or strict arrays (Data.Array.Unboxed, Data.Map.Strict) to force evaluation and avoid space leaks.
• Boxed vs unboxed arrays. Data.Array stores elements as pointers to heap objects. For numeric DP, this pointer indirection slows things down considerably. Use Data.Array.Unboxed (for immutable) or Data.Array.ST with STUArray (for mutable) to store values inline.
• Incorrect bounds in self-referential arrays. If an array element references an index outside the declared bounds, you get a runtime error. Double-check your base cases and boundary conditions.
• Forgetting strictness in Map-based memoization. Using Data.Map.Lazy with numeric values builds up thunks for every inserted value. Use Data.Map.Strict to evaluate values at insertion time.

Summary

Haskell provides several effective approaches for dynamic programming. Lazy list memoization is the simplest but only works well for sequential access. Immutable arrays from Data.Array offer O(1) lookup with a clean self-referential definition that leverages lazy evaluation for automatic memoization. For maximum performance, mutable unboxed arrays in the ST monad match imperative DP speeds while remaining pure. Sparse problems benefit from Data.Map.Strict to avoid allocating the full state space. The most important considerations are choosing the right data structure for your access pattern and being vigilant about space leaks caused by unevaluated thunks.