What have you found for these years?

2009-12-10

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 了... 雖然名詞用錯或許不是大問題,但我們終究需要使用名詞溝通,有誤用會造成誤解的。

3 retries:

scm said...

這個可不可以貼到 lambdawan 上?(尤其是關於 Y combinator 的誤解... )

Lin Jen-Shin (godfat) said...

Sure! 晚點我整理一下
另外這邊提到誤解,是說因為我看到有人覺得
y f = f y f
這種實作也算是... 但這樣已經是明確使用遞迴了

Lin Jen-Shin (godfat) said...

sorry, it's
y f = f (y f)

Post a Comment

Note: Only a member of this blog may post a comment.



All texts are licensed under CC Attribution 3.0