記憶化的作家單子

注意我只是想了解正在發生的事情如下所示的代碼這個特殊的一塊。我知道這可能不是解決問題的最好方法。記憶化的作家單子

我正在嘗試使用帶有memozied斐波納契函數的lazy Writer monad來計算函數被調用的次數。該函數快速返回正確的值，但環境永遠不會返回，並且不使用任何CPU或內存。

import Control.Monad.Writer.Lazy as W 

fib :: Int -> Writer (Sum Int) Int 
fib = let fibs = mapM fib' [0..] 
      fib' 0 = return 0 
      fib' 1 = return 1 
      fib' n = liftM2 (+) (fib $ n-1) (fib $ n-2) 
     in \n -> tell (Sum 1) >> fibs >>= return . (!!n) 

Prelude W> runWriter $ fib 51 
(20365011074,Sum {getSum = Interrupted.

有人可以解釋發生了什麼事嗎？爲什麼環境不會返回一個值？

編輯

無限名單[0..]是不是這裏的問題。我試過用有限的列表替換它，例如[0..10]或[0..n]，但問題仍然存在。 如果無限的名單是它會一直很內存密集型計算的問題，這就是爲什麼我上面提到的，它不消耗任何CPU或內存這正是讓我困惑。

我認爲，由於懶惰，有評估fib功能的節點時出現莫名其妙的地方陷入僵局。

來源

2014-03-02 haskelline

你的猜測是正確的。每次調用'fib'都會嘗試執行一次性操作'fibs'，它最終會嘗試自我評估，以免卡住。並且因爲這是使用圖減少完成的，所以沒有實際的計算正在發生，只是一個節點本身被阻塞。由於純粹性，編譯器不需要在圖中遍歷這個無限循環，所以它不會，這就解釋了CPU /內存使用情況。 – is7s

問題是mapM fib' [0..]。這是一個有效的計算，它計算monad中的無限列表，對於它也需要組合無限數量的效果，在這種情況下爲tell (Sum 1)。由於Writer的懶惰，你可以訪問結果，但monoid部分內的計數永遠不會結束。

更新：即使您使列表有限，它仍然不起作用。問題是mapM fib' [0..10]代表「斐波納契數字列表和計算它們所需的總調用次數」。因此，在您的表達tell (Sum1) >> fibs >>= ...中，您總是將總數添加到計數器，這顯然是您不想要的。

此外，它創建一個無限循環：於fib任何調用調用fib'，其計算爲它的所有元素的呼叫的數量，因此，調用（除其他呼叫）fib' 2，這再次調用fib。無限遞歸僅在您將列表限制爲[0..1]時停止。再次，問題是mapM結合了給定一元計算的所有影響。

相反，你需要像這樣：

import Control.Monad.Writer.Lazy as W 

fib :: Int -> Writer (Sum Int) Int 
fib = let fibs = map fib' [0..] -- <<<< 
      fib' 0 = return 0 
      fib' 1 = return 1 
      fib' n = liftM2 (+) (fib $ n-1) (fib $ n-2) 
     in \n -> tell (Sum 1) >> fibs !! n -- <<<<

這裏fibs :: [Writer (Sum Int) Int]，所以對於每一個元素它包含的兩個結果，需要爲它的計算呼叫的數量。

來源

2014-03-02 16:59:19

不，這不是問題，如果用'[1..10]'或任何有限列表替換'[1 ..]'，問題仍然存在。 – haskelline

@haskelline我更新了答案。問題仍然是'mapM'，它不適合這個問題。它不計算你想要的，並且在這種情況下導致無限循環。 –

記憶化的作家單子

回答

相關問題