Haskell：爲什麼這個工作 - 一個memoization的例子？

嗨，我從Memoization看下面這個例子：Haskell：爲什麼這個工作 - 一個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)

我只是想知道，爲什麼這甚至工作，因爲對我來說，如果你打電話memoized_fib(n-2)那麼你就「創造」一個新的列表，並用它做的事情，在你從它返回後，包含部分結果的列表將會消失？那麼memorized_fib(n-1)會不會從中受益呢？

來源

2014-01-05 dorafmon

如果您將定義更改爲'memoized_fib n = map fib [0 ..] !!，那麼記憶就會打破您考慮的方式！ N'。我不知道害羞，但也許別人可以闡明它。 – hugomg

http://blog.ezyang.com/2011/04/the-haskell-heap/是關於haskell堆的一個很棒的系列，它也可以解釋這個（不確定），但即使它不是很好的閱讀！ – bennofs

memoized_fib是一個CAF，這是避免創建新的東西的字面常量。沒有變數⇒沒有東西綁定新東西到⇒沒有創建新的東西（簡單來說）。

來源

2014-01-05 16:16:53

那麼這是否意味着只會有一個'''memized_fib''實例？我如何判斷一個函數是否是一個CAF？謝謝:) – dorafmon

是的，只有一個。你檢查鏈接文章中的定義;） –

首先感謝，我的意思是沒有進攻，但這裏的問題是，我點擊進入鏈接後，我發現我不知道任何關於超級combinator，並點擊進入後，我發現我不知道什麼是Combinator，然後它被定義爲「沒有自由變量的函數」，自由變量？從來沒有聽說過。在學習Haskell之前，大概我錯過了最重要的事情，即先學習lambda微積分和範疇論。 – dorafmon

我可以解釋missingno的觀察，它可以幫助你瞭解你所看到的行爲。瞭解where子句的用法很重要。

你給出的代碼是

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

這desugars到

memoized_fib = let fib = ... 
       in \n -> map fib [0 ..] !! n

missingno提出以下，這看起來像一個簡單的ETA擴張，但它不是！

memoized_fib n = map fib [0 ..] !! n 
    where fib = ...

desugars到

memoized_fib = \n -> let fib = ... 
        in map fib [0 ..] !! n

在前者的情況下，你可以看到，fib結構在後一種情況下fib的memoized_fib調用之間共享而每個時間被重建。

來源

2014-01-05 20:18:52

在第一種情況下，你說'fib'是共享的。爲什麼分享？你是說'memoized_fib = let fib = ...'在重新調用時不會重新聲明'fib'？它重用了先前的「fib」？這是否意味着它等同於在'memoized_fib'函數之外定義'fib'？ – CMCDragonkai

是的，它相當於在'memoized_fib'之外定義'fib'。 –

您顯示的代碼取決於給定編譯器的行爲。這裏就像湯姆·埃利斯的脫糖建議：

memoized_fib = 
    let fib 0 = 0 
      fib 1 = 1 
      fib n = memoized_fib (n-2) + memoized_fib (n-1) 
    in 
     (map fib [0 ..] !!)

沒有保證名單map fib [0..]將被重用，即「共享」。特別是當你像我這樣省略類型簽名時，將它作爲多態定義。

更好地作出這樣的名單明確，給它一個名字：

memoized_fib n = 
    let fib 0 = 0 
      fib 1 = 1 
      fib n = g (n-2) + g (n-1) 
      g = (fibs !!) 
      fibs = map fib [0 ..] 
    in 
     g n

這是discussed before。

來源

2014-01-06 14:13:28

Haskell：爲什麼這個工作 - 一個memoization的例子？

回答

相關問題