Haskell中的动态编程

Question

Haskell是否提供动态编程的任何工具？在过程语言中,我将使用数组来存储基于递归关系的计算.我如何在Haskell中做类似的事情？

Answer 1

根据情况有很多不同的方式.也就是说,Haskell中的简单动态编程算法通常比其他语言简单得多,因为Haskelll很懒惰

考虑Fibonacci函数(函数式编程的"Hello World")

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

这是以指数时间(grr)运行的.我们可以在一个懒惰的无限长列表中平凡地存储fib的所有值

fibs = map fib [0..]

现在我们可以观察到

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

到目前为止,这对我们没有帮助,但我们可以利用这种等同性来发挥我们的优势

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

这为Fibonacci函数提供了一个线性时间解决方案(虽然它泄漏了空间......实际上并没有这样做),并且只有在Haskell是懒惰的情况下才有效.我们根据自身的递归关系定义了无限的数据结构.奇迹是它在有限的时间内运行(非严格),它在线性时间内运行是需要调用的时间最优性(Haskell的成本模型)的乘积.这种线性时间性能的原因是每个条目fibs最多计算一次(或可能永远不会).