如何理解這兩個函式的區別（Haskell）？

1樓：

其實沒區別，，區別是編譯器造成的，，有個叫CAF 的東西，(必應谷歌或者Haskell Wiki 中搜尋 (Haskell) CAF,）第二個中的 x 破壞了這個，編譯器，在 O0 下會自動優化(當然，在不要這個)優化的方式就是備忘錄法，memorization,,

對於第乙個，當你計算第n個數的時候，時間複雜度是O(n)，而對於此時，如果你要計算第 n-1 個數的時候時間複雜度應該是乙個"常數"，不太清楚memorization 底層是如何實現的，但這個時間消耗基本上是O(1) 的常數級別(如果底層查表的實現不是O(1)之前的O(n)有待商榷)

2樓：韓冬

這個事兒挺好理解的，如果不進行任何優化的話，第二個 fib' 處在乙個函式體裡面，將會被每次執行 fib 的時候重新動態定義（heap-allocation!）。而乙個 fib' 不在，所以第乙個 fib 函式執行的時候直接進入了 let ...

in 後面的閉包裡面求值去了。GHC 的 float-in/float-out 優化就是解決這個的。

當然因為 fib' 沒有被浮出，導致了乙個災難性的後果就是 map 生成的列表沒辦法被記憶下來，於是就慢很多了。

寫JS的時候就經常需要手動做閉包浮出優化（把一些被閉包捕獲的變數變成引數，然後就可以把閉包定義的位置從函式體/迴圈體裡移到外面了，從而避免重複定義）。

PS. 乙個反直覺的事實是，GHC 不能自由地做 eta 轉換，因為 f 可能是 _|_ ，但 \ x -> f x 就不是了（是乙個實打實的可以進入的閉包）。

啊，可惡的 _|_ 。

3樓：

為什麼要用list做記憶化……list的隨機訪問是O(n)的啊。

對第二個函式每次呼叫都會重新計算一遍fib'。因為編譯器不知道fib 1和fib 2中的fib'是不是乙個東西。

不理解底層的渣渣不太理解你們Haskell為啥用了eta展開就沒法做lambda lifting……OCaml程式設計師用了一大堆eta展開也沒啥效率問題啊。

感謝大佬提醒，如果開-O2優化的話Haskell還是能優化掉這個的。