如何使用Y- Combinator;爲什麼這個無限遞歸返回9？

Question

Ÿ - Combinator的

我一直在努力學習繞Y - 組合子（上的解釋是可愛的，以及）從這個​​跨越一個例子來了。關於這個主題的深入解釋在Haskell或者Python中都是非常讚賞的。 Pleaaase！

代碼

fix :: (a -> a) -> a 
fix f = f (fix f) 

問題

調用的函數返回fix時9是fix應用於(\x -> 9)，我不知道爲什麼;當我沿着堆棧看時，我想象到了f(f ... (fix f) ...)。

>> fix (\x -> 9) 
>> 9 

Answer 1

首先：在fix功能，您必須是直接遞歸實施定點組合子。該Y組合是不需要語法遞歸一個特定不動點組合子所以它完成了同樣的事情，但fix以不同的方式。

如果您好奇，您可以在SO上查看how to implement the Y combinator in Haskell。靜態類型有點棘手 - 它需要遞歸類型才能工作。

至於你的第二個問題，代碼工作得益於懶惰。如果你申請(\ x -> 9)到任何東西，那東西永遠不會被評估。試試這個：

λ> (\ x -> 9) (error "fail") 
9 

這包括定義fix的遞歸調用。看看會發生什麼，當你在fix定義與(\ x -> 9)更換最外層f：

(\ x -> 9) (fix f) 

按照完全相同的邏輯作爲版本error，遞歸調用永遠不會被評估，你只得到一個9出來。