The Y Combinator (Slight Return)

updated 2009-12-13: 浪打王版

The Y Combinator (Slight Return)

Tiger got to hunt,
Bird got to fly;
Lisper got to sit and wonder, (Y (Y Y))?

Tiger got to sleep,
Bird got to land;
Lisper got to tell himself he understand.

— Kurt Vonnegut, modified by Darius Bacon

有點懶得細看，因為很長，不過大致翻了一下，這篇講得非常清楚明白，
而且大抵上講的都是對的。之所以說講的是「對」的，因為發現很多人
誤解了 y/fixed-point combinator... 雖然名詞用錯或許不是大問題，
但我們終究需要使用名詞溝通，有誤解會造成困擾的。（有誤用會造成誤解的）

我想這篇可以算是不錯的教學吧，連一些常見的誤解都解釋了。

****************
Mike Vanier 寫了一篇非常詳細的 Y Combinator 說明：
The Y Combinator (Slight Return)
開頭引用了一段很有趣的話：

Tiger got to hunt,
Bird got to fly;
Lisper got to sit and wonder, (Y (Y Y))?

Tiger got to sleep,
Bird got to land;
Lisper got to tell himself he understand.

    — Kurt Vonnegut, modified by Darius Bacon

什麼是 Y combinator? 如果我們不能 refer 自己，不能在 function 裡面引用自己的名字，那要怎麼做遞迴？Y combinator 就可以做到。由於這篇講得非常清楚且詳細，也說明了一些常見的誤解，因此非常推薦還不是很熟悉 functional programming 的人閱讀，可以和自己的理解相印證看看。

曾偶然在有些地方看到有人把 y f = f (y f) 也當成 Y combinator 的實作，例如這篇裡面的 y: Fixed point combinators in C++ 但事實上 y f = f (y f) 本身就是 explicitly recursive, 就像 The Y Combinator (Slight Return) 前面的一句話：

A combinator is just a lambda expression with no free variables.

而在 f (y f) 裡的 y 就已經是 free variable 了... 雖然名詞用錯或許不是大問題，但我們終究需要使用名詞溝通，有誤用會造成誤解的。