「浮出」是什麼意思？

在Haskell wiki I read that this：「浮出」是什麼意思？

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

的效率比該：

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

因爲，「在用於每個參數x被（重新）限定的第二殼體FIB」，因而它不能被漂走了。「

我不明白這是什麼意思。

「浮出」是什麼意思？它是如何優化？
爲什麼fib'被重新定義爲每次調用fib？
這是一個eta擴展與否？

來源

2012-01-08 Pubby

這不是一個很好的解釋。

「浮出」只是意味着，在：

\x -> let y = ... in z

如果...沒有提到X然後它可以是浮出拉姆達的：

let y = ... in \x -> z

，這意味着它將只計算一次，如果...昂貴，可以節省大量時間。但是，GHC對於執行這樣的優化是保守的，因爲它們會引入空間泄漏。（雖然它確實爲第二個定義，如果你給它一個類型簽名，就像Daniel Fischer在他的答案中指出的那樣。）

雖然這不是自動優化。第一個片段定義了lambda之外的fib'，而第二個片段定義了其內部（lambda隱含在fib x = ...中，相當於fib = \x -> ...），這就是引用的內容。

然而，即使這並不真正相關，與此相關的是，在第一個片段中，map fib' [0 ..]發生在lambda之外，因此其結果在lambda的所有應用程序（在該代碼中，「lambda」來自部分應用程序(!!)）共享。在後者中，它位於lambda內部，因此很可能會針對fib的每個應用程序重新計算。

最終的結果是前一個實現緩存了值，所以比後者更高效。請注意，第一個代碼段的效率取決於以下事實：fib'不直接遞歸，而是通過fib，因此受益於記憶。

它與eta-expansion相關;後面的片段是第一個的eta擴展。但是你所引用的陳述並不能解釋發生了什麼事情。

請注意，這是特定於實現的行爲，而不是Haskell語義的一部分。但是，所有合理的實現都將以這種方式運行。

來源

2012-01-08 17:08:35 ehird

這個答案和Daniel Fischer的答案現在是相互遞歸的。 – misterbee 2012-02-22 23:20:45

@misterbee：幸運的是，只有Haskell程序員會閱讀它們，而我們很懶，對吧？ – leftaroundabout 2012-03-23 12:57:19

ehird的回答解釋了事情非常好，但是有一點

最終的結果是，前者的實現緩存值，因此比後者更爲有效。

這有時是錯誤的。

如果您編譯包含或者與最佳化定義模塊（我檢查只-02，不-O1，當然只有GHC），有幾種情況要考慮：

沒有類型的第一個定義簽名
類型簽名第二定義fib :: Int -> Integer
多態型的第一個定義fib :: Num a => Int -> a
而不類型簽名第二個定義
類型簽名fib :: Num a => Int -> a

第二定義在情況1中，單態限制產生的類型fib :: Int -> Integer和列表map fib' [0 .. ]跨越的fib所有調用共享。這意味着，如果您查詢fib (10^6)，您將獲得內存中第一百萬（+1）個斐波那契數字的列表，並且只有在垃圾收集器可以確定它不再使用時纔會收集它。這通常是內存泄漏。

在情況2中，結果（正在芯）實際上是相同的外殼1

在情況4中，在列表中不跨越不同fib頂層調用共享（當然;結果可以有很多類型，所以會有很多列表共享），但是它在每個頂級調用中被實例化並且被重複用於來自fib'的調用，所以計算fib n需要O（n）加法和O（n^2）步驟列表。這並不算糟糕。計算完成後收集清單，因此不會有空間泄漏。

情況3是幾乎相同爲4

案例5，但是，比幼稚遞歸更糟。由於它是明確的多態，並且列表綁定在lambda內部，所以列表不能被遞歸調用重用，每次遞歸調用都會創建一個新列表...

來源

2012-01-08 18:47:16

嗯，所以當單形態時，GHC *會將列表浮出第二個定義？很酷，我沒有意識到它可以做到這一點。 – ehird 2012-01-08 18:54:13

GHC非常棒。它變得越來越好:) – 2012-01-08 18:56:29

「浮出」是什麼意思？

回答

相關問題