haskell - Haskell 中的动态编程

Question

Haskell 是否提供任何用于动态编程的工具？在过程语言中，我会使用一个数组来存储基于递归关系的计算。我如何在 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).