2012-02-23 1 views
7

我想了解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 

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

+1

他們可能已經把一些額外的括號存在,使其更有點明顯'(圖fib [0 ..] !!)'=='((map fib [0 ..])!!)' – soulcheck 2012-02-23 09:48:13

+1

更新中的不同結果是由於'Int'溢出。改用'Integer';除此之外,乍一看似乎是對的。 – yatima2975 2012-02-23 11:58:00

回答

9

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

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

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

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

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

+0

謝謝。我試圖用新的知識重寫我的代碼,但得到不同的結果(在我的問題更新部分)。爲什麼?正如我所看到的這段代碼必須是平等的。 – demas 2012-02-23 10:17:15

+0

爲什麼在函數調用'memoized_fib(n-2)'和'memoized_fib(n-1)'中,列表'map fib [0 ..]'指向內存中的同一個列表? – 2016-03-11 23:44:50

2

map這裏不帶三個參數。

(map fib [0..] !!) 

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

2

也許是更清晰的寫它:

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) 
+1

這是兩個版本的功能(http://pastebin.com/sA6ib2kp)。爲什麼第一個運行得更快,但第二個 - 更慢? – demas 2012-02-23 10:21:57

+0

因爲該列表在第一個版本中共享,但不在第二個版本中共享。 – 2013-02-24 23:28:58