Y不動點組合子用在哪裡？

對於求階乘的函數,在傳名求值策略下,

我可以寫成

let F = lambda n. IF_Else n==0 1 n*F(n-1).


這樣的話不就用不到Y不動點組合子了嗎?

而且Y不動點組合子也只能傳名求值策略下被使用,在傳值策略下會發散.不動點組合子

---

用來實現遞歸。

在正統的 Lambda 演算里函數全部是沒有名字的，因此遞歸函數無法實現，考慮

由於 Lambda 表達式本身沒有名字，因此在上式中 fib 實際上是自由變數（if-then-else 可以用閉合 Lambda 表達式表示，它並不是庫函數），和「遞歸」大相徑庭。但是我們可以玩一點技巧：

0),mathrm{then},(x imes (f,(x-1))),mathrm{else},(1)" eeimg="1">

這個函數是閉合的，我們用參數 f 代表遞歸，fib 本身的定義則是：

還是有問題，不要緊，進一步處理它

，其中

把它展開看看，結果是：

完美~

於是我們現在惟一的任務就是寫出一個閉合的 Lambda 表達式和 Y 等效，所幸 Haskell B. Curry 找到了一個：

試試調用它（在傳名調用下）：

完美！

---

Y組合子的用處是使得 lambda 表達式不需要名字。

如你所說，階乘函數可以這樣定義：

let F = lambda n. n==0 ? 1 : n*(F n-1)


當我們需要調用的時候，我們只需要這樣寫就可以了：

F 4


但你有沒有想過，如果我們沒有 let 這個關鍵字怎麼辦？沒有 let，就不能對一個 lambda 表達式命名。實際上，在 lambda 演算里確實沒有 let，換句話說，let 只是個語法糖，讓我們寫起來更加舒適而已。沒有 let，並沒有對lambda表達式造成什麼實質性的傷害。

數學家們推崇：

如無必要，勿增實體

是的。所以，你不能對任何lambda表達式命名。這就像你中了一個沉默魔法一樣。

我們先來看看如果沒有遞歸，無名 lambda 表達式是如何使用的。

我們來寫一個求平方的lambda：

lambda x. x * x


這個lambda是無名的。如果要調用，我們只能這麼調用：

( lambda x. x * x ) 3


結果自然是返回 9 了。

看來沒有名字，lambda 世界還是可以正常運轉的。且慢，我們不要忘記遞歸。遞歸函數，似乎真的是個問題——如果沒有名字，自身如何調用自身？其實也不是啥大問題。不過，要解決這個問題，我們先假設我們可以使用名字。別擔心，這只是前進途中的曲折。最後，我們會去掉名字的，大家先不要著急。

我們以階乘函數為例，先看看我們現階段的成果：

let F = lambda n. n==0 ? 1 : n*(F n-1)


首先我們先設法消除掉 lambda 函數體中的函數名稱（對不起，一激動就用上了函數這個說法，如果你不知道什麼叫函數，那麼你就可以理解為函數就是 lambda，二者是等同的）。方法就是將函數作為參數傳進去。

let F = lambda f. lambda n. n==0 ? 1 : n*((f f) (n-1))


這個函數的接受一個參數，返回一個函數，這個返回的函數才是真正做計算的階乘函數。

調用此函數的方法如下：

F F 4


將會返回24。

接下來的一步將是至關重要的。我們現在就拋棄let關鍵字。我們將F的名字換成F的定義，於是調用階乘函數的的方式將變成如下的樣子：

( lambda f. lambda n. n==0 ? 1 : n*((f f) (n-1)) ) ( lambda f. lambda n. n==0 ? 1 : n*((f f) (n-1)) ) 4


看到了沒，這裡的所有 lambda 都沒有名字，不過，這絲毫沒有影響 lambda 表達式的威力。

如果你看到這裡，就會發現，我們可以用類似的方法定義所有的遞歸函數，而用不著Y組合子。是的。你是對的。上面這種方法叫做窮人的Y組合子。但Y組合子的作用就是提供了一個通用的方法來定義遞歸函數。

讓我們來看一下Y的定義：

lambda f. (lambda x. (f(x x)) lambda x. (f(x x)))


要講清楚Y的來龍去脈，可是非常難（大家可以去看我的博文重新發明 Y 組合子 Python 版）。事實上，連發現它的哈斯卡大神也感慨不已，覺得自己撿了個大便宜，還因此將Y紋在了自己的胳膊上。我現在就只講Y的用處了。

我們用Y來定義一下遞歸函數

let F = Y ( lambda f. lambda n. n==0 ? 1 : n*(f n-1) )


大家有沒有發現，定義變得比以前的特定方法更加優美了。在之前的特定方法中 f 需要應用於自身，但現在，f 是由 Y 提供的，是一個純階乘函數。

不只是定義更加優雅，連調用也像有名字的lambda一樣優美了。我們現在就優雅的調用階乘函數：

F 4


而去掉F的名字，我們有：

( Y ( lambda f. lambda n. n==0 ? 1 : n*(f n-1) ) ) 4


再去掉Y的名字：

( ( lambda f. (lambda x. (f(x x)) lambda x. (f(x x))) )
( lambda f. lambda n. n==0 ? 1 : n*(f n-1) )
) 4


看，這裡沒有任何名字，但我們定義並且調用了階乘函數。再次強調一下，階乘函數是個遞歸函數哦。

任何一階遞歸函數都可以用Y來定義，就像我們定義階乘函數那樣：

Y (lambda f. &< 真正的函數體，在內部用f指代自身 &>)


多說一句，可以在 JavaScript 中實現Y運算元，如果用上 CoffeScript 提供的語法糖，將非常優雅（這裡我原寫錯了，感謝 @Liu Martin )：

Y = (g) -&>
h = (f) -&>
g(n) -&> f(f) n
h h


Y運算元真是人見人愛。但除了證明lambda只需要alpha/beta/eta三條規則而不需要命名之外，它主要用自身的優美供大家感嘆。在真實的世界中，不論是數學家，還是函數式編程的 coder，都需要給事物命名。

====

更新：函數不動點在編程中的應用 http://www.lfcs.inf.ed.ac.uk/reports/97/ECS-LFCS-97-375/ECS-LFCS-97-375.pdf

---

前面有那麼多種語言的介紹了，加個C#的expression tree的例子吧：LINQ與DLR的Expression tree（5）：用lambda表達式表示常見控制結構

有一次開會遇到Mads Torgersen，給他演示了這個，他還表示好好玩 &>_&<

---

不動點組合子如果恰當使用，可以成為強悍的FP設計模式。

一個例子：term-level的不動點組合子可以用於自動將遞歸函數進行記憶化。

另一個例子：type-level的不動點組合子可以用於實現recursion schemes，許多在遞歸的數據類型上的操作可以免於顯式遞歸/模式匹配來實現，極大簡化代碼。

---

我覺得編程語言偽簡史裡面那個評價lisp的話在這裡很合適：

「在遞歸和逼格提升上尤為典範」

實際上在lambda演算里用遞歸也是為了逼格提升。

來看這個階乘函數

fact m=

λm.car (m (λx.cons (car x)*(cdr x) (cdr x)+1)

(cons 1 1))

其中+,*,cons,car,cdr都可以用完全沒有遞歸的lambda項寫出，這樣寫這個函數用不到遞歸。實際上簡單類型lambda演算不允許任何形式的遞歸，但是它仍然是圖靈完全的

其實y組合子最大的歷史作用是導出了Curry悖論，說明用lambda演算進行邏輯推理是不行的，以下是證明，我只是搬運工，我也不知道是什麼意思……………………

公理1 p→p

公理2 (p→(p→q))→(p→q)

公理3，p和p→q均成立則q成立

現在A是任意命題，f＝λx.x→A，g＝y f

顯然g＝f(g)＝g→A

根據1，g→g

根據g＝g→A，g→(g→A)

根據2，g→A

根據g=g→A，g

根據3，A

所以用lambda演算來進行邏輯推理，什麼命題都能推出來

---

我來歪個題

不動點組合子滿足

在λ-calculus里Y組合子的實現為:

在除了λ-calculus中, 不動點組合子的意義更多是在理論上的, 比如在PLT里的指稱語義里會用到不動點組合子.

語義定義為

為狀態集合,

為非終止狀態(死循環了)

可以顯然的定義語義(這個語義是我隨便寫的, 不是很嚴格, 僅當闡述原理使用吧)

舉例來說

(變數表示每個子表達式節點的語義值)

那麼對於while的語義是什麼呢?

可以通過遞歸來定義while

這個定義並沒有給出while的語義, 這個方程只是對while語義進行了約束, 值得注意的是這個方程的解不唯一.

考慮, 根據上面的定義將會給出

對於任意均有

並不能給出任何while語義信息(該情況下while語義可以是任意語義)

對於上述while表達式期望的語義應為對於任意均有

為了給出準確的while語義, 定義

是的一個不動點

定義不動點組合子

對於任意滿足

則while的語義由不動點組合子給出:

簡略證明如下:

定義表達式序列

顯然有

定義偏序

對於while的期望語義為該偏序的上界. 可以證明F連續, 根據Kleene fixed-point theorem, 該上界是F的一個最小不動點, 滿足之前的遞歸定義, 不動點組合子即是求該不動點.

最後便得到while語義:

為不動點組合子

換個方式理解, 類比λ-calculus, 此處不動點組合子同樣也是用於"遞歸", 遞歸求解while語義, 只是表現形式不太一樣.

---

Y組合子證明了lambda表達式具有表達遞歸調用的能力。

如你給出的代碼不是lambda表達式，並且，對於一些解析器的確會無法理解這種語法，會認為F是未定義的函數（解析函數體時F尚未定義）。

---

不太懂 lambda 演算。。自己用 js 寫了個簡易的 Y 組合子。。我也不知道對不對。。驗算是對的。

首先是原版階乘

const F = n =&> n &> 1 ? n * F(n - 1) : 1;
F(4) === 24; // true


看了上面大神的回答，知道 Y 組合子解決的是在定義這個匿名函數的時候，不能調用自身。

那能不能通過另外一個函數，將這個匿名函數本身當作參數交還給這個匿名函數使用呢？

於是有了下面這一版

const Y = func =&> x =&> func(Y(func))(x);
const F2 = Y(self =&>
x =&> x &> 1 ? self(x - 1) * x : 1
);
F2(4) === 24; // true


簡而言之 self 這個參數，應當等於自身：

x =&> x &> 1 ? self(x - 1) * x : 1


來看第一版中的 Y，它應當是一個高階函數，第一層接受的參數是我們要使用的函數 func，第二層接受的參數就是函數輸入了，用 x 表示。由於到了最裡層，肯定會需要調用 func 兩階來進行期中的計算過程，它的函數體的形式應當是 func(T)(x) 這樣的。而 T 是什麼，T 就是 self，就是 Y(func)。

這個時候離一個單獨的組合子已經不遙遠了，既然 Y 要調用自身。。那就再來個高階函數

const Z = Y =&> func =&> x =&> func(Y(Y)(func))(x);
const B = Z(Z);


這裡 B 就是最終的一個組合子了，展開一下就可以得到

// C = B = Z(Z)
const C = (Y =&> func =&> x =&> func(Y(Y)(func))(x)) (Y =&> func =&> x =&> func(Y(Y)(func))(x));


驗算一下

const F3 = C(self =&> x =&>
x &> 1 ? self(x - 1) * x : 1
);
F3(4) === 24; // true


大概能用就行了？？大神幫我檢查檢查對不對………………

補一個 erlang 實現

foo(Self) -&>
fun
(1) -&> 1;
(X) -&> Self(X - 1) * X
end
.

c(F) -&>
(
(fun (Y) -&>
fun (Func) -&>
fun (X)
-&> (Func((Y(Y))(Func)))(X)
end
end
end)
(fun (Y) -&>
fun (Func) -&>
fun (X)
-&> (Func((Y(Y))(Func)))(X)
end
end
end)
) (F).

main() -&>
Frac3 = c(fun foo/1),
io:format("Method 2: ~w~n", [Frac3(4)])
.


---

遞歸

---

我來講一個實際點的妙用。用於找工作面試。

有了 Y組合子，你從此可以統一的應付一切 」如何不用遞歸，不用循環實現X？」的面試題。不讓用循環、不讓用遞歸，那我們自己實現遞歸咯。

最初想到是室友問了一道面試題，如何不用遞歸、不用循環實現從1加到100。好像答案是 new Logic_In_Constructor_Of_This_Class[100]，然後我給的答案是Y組合子……

---

一般來說，當你發現你需要用Y Combinator的時候，一定是哪裡出了問題。比如當你不能給函數命名的時候，你就需要Y Combinator了。舉個例子，如果你用Erlang的時候，只用Erlang Shell，你就會發現你會不停地寫Y Combinator了。當然了，從Erlang R17開始終於可以不寫Y Combinator了。完全無法理解那幫整天吹Y Combinator的。

就是這樣

---

闡釋了命名的重要性

你命名它 它就被你擁有

---

#lang racket

;; Y Combinator

;; lambda caculus: Y-combinator 用於使用匿名函數表達遞歸.

;; 這段來自百度百科

;; Y-combinator 是一種不動點組合子(Fixed-point combinator).不動點組合子是計算其它函數的一個不動點的高階函數.函數 f 的不動點是一個值 x 使得 f(x) = x. 例如, 0 和 1 是 f(x) = x * x 的不動點. 高階函數 f 的不動點是另一個函數 g, 使得 f(g) = g. 因此不動點運算元是任何函數 fix 使得對於任何函數 f 都有:

;; f(fix(f)) = fix(f)

;; 在無類型 lambda 演算中眾所周知的不動點組合子叫做 Y 組合子.它是 Haskell B. Curry 發現的, 定義為

;; Y = f.(x.f(x x))(x.f(x x))

;; 用一個例子函數 g 來展開它, 我們可以看到上面這個函數是怎麼成為一個不動點組合子的：

;; by definition of Y

;; Y g --&> (f.(x.f(x x))(x.f(x x)))g

;; by beta-reduction of f: applied Y to g

;; --&> (x.g(x x))(x.g(x x))

;; by beta-reduction of x: applied left function to right function

;; --&> g((x.g(x x))(x.g(x x)))

;; by second equality

;; --&> g(Y g)

;; by repeatedly applying this equality we get,

;; Y g = g(Y g) = g(g(Y g)) = g (...g(Y g)...)

;; 百度百科引用完畢...

;; ====================

;; 下面搬運一個, Y-combinator 是如何一步步試出來的, 用的語言是 scheme

;; In this file we derive the Y combinator, one of the fundamental results of recursive procedure theory. You already know that in some cases it is not necessary to give a procedure a name. for example,

;; ((lambda (x) (+ x 1)) 6)

;; adds 1 to 6 without naming the procedure that does it.

;; But, what about a recursive procedure? For example,

;; 但是, 當不使用函數名時, 要如何表達遞歸呢?

;; 比如下面這個遞歸, 如果沒有 fact 這個函數名, 如何表達遞歸?

(define fact
(lambda (n)
(if (zero? n)
1
(* n (fact (- n 1))))))
(display "a simple recursive function, factorial, (fact 5): ")
(fact 5)
(newline)


;; step-1. The first idea is simply to pass "fact" in as an argument in much the same way that we did for

(define op-maker
(lambda (op)
(lambda (x y)
(op x y))))


;; The first lambda passes the name of the operation and the second lambda is the nameless operation. Let"s try this with "fact". The first attempt is

;; (define fact-maker
;; (lambda (procedure)
;; (lambda (n)
;; (if (zero? n)
;; 1
;; (* n (procedure (- n 1)))))))


;; The idea will be to pass "fact-maker" in through "procedure". Thus, what we would like to do is invoke (fact-maker fact-maker) to produce our nameless (well, almost nameless) factorial procedure. This would allow us to write,

;; for example

;; &> ((fact-maker fact-maker) 5)

;; But, this doesn"t work because "fact-maker" is a procedure which takes as input one argument that is a procedure but "procedure", which is supposed to be identical to "fact", requires a numeric argument.

;; &<-- 但是這樣是行不通的, 因為 "fact-maker" 是一個只接受一個過程/函數作為輸入參數的函數, 但是我們想要的是等同於原階乘函數的過程("procedure"), 而原階乘函數需要的是一個數值參數.

;; The solution is the following:

(define fact-maker
(lambda (procedure)
(lambda (n)
(if (zero? n)
1
(* n ((procedure procedure) (- n 1)))))))


(display "Y-combinator step-1, ((fact-maker fact-maker) 5): ")
((fact-maker fact-maker) 5)
(newline)


;; Well, we got the name out of the body of the procedure but we still have to pass the procedure in and so far we have been using a name to do that. So let"s try to get the whole dependence on a name out.

;; Step-2. Recall we demand that "fact" be identical to (procedure procedure) which in turn must be identical to

(fact-maker fact-maker) (recall the example ((fact-maker fact-maker) 5)

which gives the same result as (fact 5)). Thus, we can write "fact-maker" in the following way, making use of the result of step 1.

(define fact-step2
((lambda (procedure)
(lambda (n)
(if (zero? n)
1
(* n ((procedure procedure) (- n 1))))))
(lambda (procedure)
(lambda (n)
(if (zero? n)
1
(* n ((procedure procedure) (- n 1))))))
)
)


;; 我們幾乎成功了:

(display "Y-combinator Step-2, (fact-step2 5): ")
(fact-step2 5)


;; 去掉 define, 我們成功了, 只是有點兒長...:

(display "Y-combinator Step-2, nameless!: ")
(((lambda (procedure)
(lambda (n)
(if (zero? n)
1
(* n ((procedure procedure) (- n 1))))))
(lambda (procedure)
(lambda (n)
(if (zero? n)
1
(* n ((procedure procedure) (- n 1))))))
)
5)
(newline)


;; This produces the factorial of 5 because the procedure which is invoked (the huge mess) is exactly the definition of "fact." But, lo and behold, there is no name for this procedure anywhere!

;; In what follows, we try to generalize this to all procedures and wind up with the dreaded applicative-order Y-combinator.

;; &<-- 我們嘗試將其對所有函數一般化

;; Step-3. First, we need to separate out the part that pertains to computing the factorial. The goal is to write this part in one place and when code for other problems is substituted for the factorial code, the result will be a new recursive procedure. This step is a little tricky because we insist on using, with no significant changes, code that was designed assuming a procedure name. The section of factorial code we currently have,

;; from step 2, is

;; &<-- 首先我們將計算階乘的部分分離出來. 目標是另外一個解決其它問題的代碼,

;; 可以直接替換掉階乘代碼的佔位, 從而得到一個新的遞歸函數.

;; 這步需要刷一點兒花招, 因為我們要堅持使用原來設計的假設有函數名的代

;; 碼, 不使它有顯著的變化.

;; 根據第二步, 我們做的是:

;; (define F
;; (lambda (n)
;; (if (zero? n)
;; 1
;; (* n ((procedure procedure) (- n 1))))))


;; This is different from what we want because it contains a (procedure procedure) where we would like to see a plain old procedure. So, we use a trick to get it out. In general, isn"t

;; &<-- 這和我們想要的有點不同. 因為它包含一個 (procedure procedure),

;; 但我們希望和原來的函數的形式盡量保持一致.

;; (f arg)

;; inentical to

;; ((lambda (x) (f x)) arg) ?

;; The second statement is a little strange, though, because it makes you pass

;; "arg" into a procedure so that the procedure which would be applied to it

;; anyway is applied. Why do we want to do such a thing? Watch! This means that

;; &<-- 第二個表達式有點奇怪, 因為它讓你傳遞arg到一個lambda函數中, 不過只是

;; 為了讓這個原本就能夠直接應用到arg上的函數f應用arg上(就是說比起第一個

;; 形式來說要冗長, 貌似沒什麼卵用). 但是, 這意味著:

;; ((procedure procedure) (- n 1))

;; is the same as

;; ((lambda (arg) ((procedure procedure) arg)) (- n 1))

;; and we substitute this into our current version of F to get

;; (define F
;; (lambda (n)
;; (if (zero? n)
;; 1
;; (* n ((lambda (arg) ((procedure procedure) arg)) (- n 1))))


;; How has this helped? Well, the (lambda (arg)...) is ONE procedure and

;; procedures can be passed as arguments so F can be defined as

;; &<-- 也就是說 (lambda (arg) ...) 的形式是 "一個" procedure, 因此可以保持

;; 參數傳遞和使用函數時形式的一致性 (見下面的 func-arg, 如果使用類似

;; Step.2 中的 procedure 形式, 那麼參數是單個 procedure, 但使用時卻是

;; (procedure procedure) 的形式, 也就是參數(函數)傳遞和使用函數時的形式

;; 不一致).

;; (define F
;; ((lambda (func-arg)
;; (lambda (n)
;; (if (zero? n)
;; 1
;; (* n (func-arg (- n 1))))))
;; (lambda (arg) ((procedure procedure) arg))))


;; Yes, it"s the same F but the old definition looked like this:

;; (define F (lambda (n) ... &

))

;; and the new definition looks like this:

;; (define F ((lambda (func-arg) (lambda (n) ...)) &

))

;; where &

is the (lambda (arg) ((prcedure ...) ...) ...)

;; expression.

;; Step-4. -Now we are ready to take the result of step 3 and apply it to the

;; result of step 2. Writing out the whole thing, we get:

(define fact-step4
((lambda (procedure)
((lambda (func-arg)
(lambda (n)
(if (zero? n)
1
(* n (func-arg (- n 1))))))
(lambda (arg) ((procedure procedure) arg))))
(lambda (procedure)
((lambda (func-arg)
(lambda (n)
(if (zero? n)
1
(* n (func-arg (- n 1))))))
(lambda (arg) ((procedure procedure) arg))))))

(display "Y-combinator Step-4, (fact-step4 5): ")
(fact-step4 5)


;; you will probably want to study this carefully. Notice the double left parens

;; in front of ((lambda) (func-arg) ... This is because we are writing

;; ...

;; ((lambda (func-arg) &) (lambda (arg) ...))

;; which has the same form as

;; ((lambda (arg) ((procedure procedure) arg)) (- n 1))

;; but is different in that a procedure is passed as an "arg" insteand of an

;; integer.

;; The two expressions beginning with (lambda (func-arg) ...) are exactly the

;; pieces of code that correspond to the factorial code and they are in exactly

;; the right form. So we can get them out of the definition of fact in the

;; following way:

(define F*
(lambda (func-arg)
(lambda (n)
(if (zero? n)
1
(* n (func-arg (- n 1)))))))
(define fact-step4-2
((lambda (procedure)
(F* (lambda (arg) ((procedure procedure) arg))))
(lambda (procedure)
(F* (lambda (arg) ((procedure procedure) arg))))))
(display "Y-combinator Step-4-2, (fact-step4-2 5): ")
(fact-step4-2 5)
(newline)


;; This is significant because we can now use any procedure in place of F* to

;; change functionality to whatever we want. The only problem is that,

;; as written, we still need to name F*. This is easily remedied in the next

;; step.

;; Step-5. Jackpot! Now we write the dreaded applicative-order Y-combinator:

;; f.(x.(f(x x))x.(f(x x)))

;; here represents lambda symbol.

(define Y
(lambda (f)
((lambda (x)
(f (lambda (arg) ((x x) arg))))
(lambda (x)
(f (lambda (arg) ((x x) arg)))))))


;; Notice that the procedure which does our computation is X (we stopped using

;; F* to emphasize this code can be applied to any procedure) and that is passed

;; in as an argument.

;; Step-6. We can write "fact" in terms of the Y-combinator as follows:

;; (define fact (Y F*))

;; Try &>(fact 5) to check the result. For that matter, try &>((Y F*) 5). But Y is

;; general and F* is specific to factorial but with no name! If we wrote the

;; whole thing out it would be

(display "Y-combinator step-6, generic and no name: ")
(((lambda (X)
((lambda (procedure)
(X (lambda (arg) ((procedure procedure) arg))))
(lambda (procedure)
(X (lambda (arg) ((procedure procedure) arg))))))
(lambda (func-arg)
(lambda (n)
(if (zero? n)
1
(* n (func-arg (- n 1)))))))
5)

(display "Y-combinator step-6, generic, use the name Y and F*: ")
((Y F*) 5)
(newline)


;; Look Ma! No name! Just to show the generality of all this let"s use the Y

;; combinator to define another procedure. Say findmax - finding the largest

;; integer in a list.

(define findmax
(lambda (l)
(if (null? l)
"no-list
(if (null? (cdr l))
(car l)
(max (car l) (findmax (cdr l)))))))


;; First create the analog of F* for fact, call it M for max.

(define M
(lambda (func-arg)
(lambda (l)
(if (null? l)
"no-list
(if (null? (cdr l))
(car l)
(max (car l) (func-arg (cdr l))))))))


;; Now try ((Y M) "(4 5 6 3 4 8 6 2)) to see if it works. If you want to build

;; it out it looks like this:

(display "Y-combinator!!! ((Y M) "(4 5 6 3 4 8 6 2)): ")
((Y M) "(4 5 6 3 4 8 6 2))

(display "Y-combinator!!! generic and no name: ")
(((lambda (X)
((lambda (procedure)
(X (lambda (arg) ((procedure procedure) arg))))
(lambda (procedure)
(X (lambda (arg) ((procedure procedure) arg))))))
(lambda (func-arg)
(lambda (l)
(if (null? l)
"no-list
(if (null? (cdr l))
(car l)
(max (car l) (func-arg (cdr l))))))))
"(4 5 6 3 4 8 6 2))
(newline)


---

用不遞歸的形式，表達出遞歸的語義。

---

lambda是匿名函數，不動點組合子是為了解決遞歸時不能用名稱指代原始函數的問題的。

For example,（手機碼字，沒有格式請見諒）

一段js代碼：

n =&> n===0 ? 1 : n*f(n-1);

這個f代表階乘函數，但是這個lambda沒有名稱，不能用f表示。

這時候可以用一個簡單的組合子：

(f =&> (n =&> n===0 ? 1 : n*f(n-1)))(f =&> (n =&> n===0 ? 1 : n*f(n-1)));

這就是一個階乘函數，沒有任何函數的命名。

Y組合子是眾多不動點組合子中的一個，以簡潔優美流暢（誤）而聞名。如果用Y組合子寫一下上面的函數，可讀性會高很多，大概是：

Y(f =&> (n =&> n===0 ? 1 : n*f(n-1)));

當然，可以把Y組合子直接放進去：

(h =&> (f =&> f(f))(f =&> h(v =&> f(f)(v))))((f =&> (n =&> n===0 ? 1 : n*f(n-1))));

我還是去用過程式吧。

---

推薦閱讀：