記憶化遞歸

Question

我想了解Haskell realization of memoization，但我不明白它是如何工作：

memoized_fib :: Int -> Integer 
memoized_fib = (map fib [0..] !!) 
    where fib 0 = 0 
       fib 1 = 1 
       fib n = memoized_fib(n - 2) + memoized_fib(n - 1) 

首先我甚至不明白爲什麼「map'功能得到三個參數（函數 - 纖維，列表[0 ..]和||），但不是兩個它必須做的。

更新時間：

我試圖重寫代碼，但得到了不同的結果：

f' :: (Int -> Int) -> Int -> Int 
f' mf 0 = 0 
f' mf 1 = 1 
f' mf n = mf(n - 2) + mf(n - 1) 

f'_list :: [Int] 
f'_list = map (f' faster_f') [0..] 

faster_f' :: Int -> Int 
faster_f' n = f'_list !! n 

爲什麼？我的推理中是否有任何錯誤？

Answer 1

第一：Haskell支持運算符部分。因此(+ 2)等於\ x -> x + 2。這意味着map的表達式等於\ x -> map fib [0..] !! x。其次，它是如何工作的：這是利用Haskell的call-by-need評估策略（它的懶惰）。

最初，由map產生的列表未被評估。然後，當你需要到達某個特定的索引時，到目前爲止的所有元素都會被評估。然而，一旦一個元素被評估，它不會再被評估（只要你指的是相同的元素）。這是給你記憶的東西。

基本上，Haskell的懶惰評估策略涉及記憶強制值。這個被記憶的fib函數只是依賴於該行爲。

這裏「強制」一個值意味着評估稱爲thunk的延遲表達式。因此，這個清單基本上是作爲一個清單的「承諾」存儲起來的，強迫它將「承諾」轉化爲實際價值，並承諾爲更多價值。這些「承諾」只是一個沉重的代價，但我希望稱它爲一個承諾更有意義。

我簡化了一下，但是這應該說明實際的memoization是如何工作的。

Answer 2

map這裏不帶三個參數。

(map fib [0..] !!) 

部分適用（切片）的功能與(!!)map fib [0..]，列表，作爲其第一個（左手）參數。

Answer 3

也許是更清晰的寫它：

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

所以它只是從列表中取n個元素，並且該列表懶洋洋地評估。

這個operator section東西和正常的部分應用完全一樣，但是對於中綴操作符。事實上，如果我們寫一個普通函數，而不是!!綴操作相同的形式，看看它的樣子：

import Data.List (genericIndex) 

memoized_fib :: Int -> Integer 
memoized_fib = genericIndex (map fib [0..]) 
    where fib 0 = 0 
       fib 1 = 1 
       fib n = memoized_fib(n - 2) + memoized_fib(n - 1)