Haskell中的动态编程

Question

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

Answer 1

根据情况有很多不同的方法。这就是说，往往简单的动态编程算法远远大于因Haskelll的其他语言简单的Haskell是懒惰

考虑斐波那契功能（“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..] 

这提供了一个线性时间解决了斐波那契功能（尽管它泄漏的空间......实际上没有做这种方式），并且仅适用，因为Haskell是懒惰。我们根据自身的递归关系定义了一个无限的数据结构。奇迹在于它运行在有限的时间内（非严格性），它在线性时间内运行是呼叫需求（Haskell的成本模型）的时间最优性的产物。此线性时间性能的原因是fibs中的每个条目最多只能计算一次（或可能不会）。