Dynamic programming in Haskell

Question

Does Haskell provide any tools for dynamic programming? In a procedural language, I would use an array to store the calculations based on a recurrence relation. How do I do something similar in Haskell?

Answer 1

Many different ways depending on the situation. That said, often simple dynamic programming algorithms are far simpler in Haskell than in other languages because of Haskelll is lazy

Consider the Fibonacci function (the "Hello World" of functional programming)

fib n | n < 2 = 1
fib n | otherwise = fib (n-1) + fib (n-2)

this runs in exponential time (grr). We could trivially store all the values of fib in a lazy infinitely long list

fibs = map fib [0..]

now we can observe that

fibs !! n
 = (map fib [0..]) !! n =
 = fib ([0..] !! n)
 = fib n

so far this doesn't help us, but we can use this equivalence to our advantage

fib n | n < 2 = 1
fib n | otherwise = (fibs !! (n-1)) + (fibs !! (n-2)) where
  fibs = map fib [0..]

this provides a linear time solution to the Fibonacci function (although it leaks space...don't actually do it this way), and only works because Haskell is lazy. We defined an infinite data-structure in terms of a recurrence relation on itself. The miracle is that this runs in finite time (non strictness), that it runs in linear time is a product of the time optimality of call-by-need (Haskell's cost model). The reason for this linear time performance is that each entry in fibs is computed at most once (or possibly never).