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中的每個條目最多隻能計算一次（或可能不會）。