用 Python 實現 Y Combinator by caterpillar | CodeData
top

用 Python 實現 Y Combinator

分享:

會想要寫這個主題,主要是由於 聽說是某天很夯的 fibonacci number XD 討論中,談到了 Y Combinator,我試著用 Python 實現了一個,過程中有些想法,想要略做記錄一下。有關於 Fixed Point 與 Y Combinator 的推導,可以先參考 〈函数式编程 – FUNCTIONAL PROGRAMMING〉,如果你不想花太多時間看推導,那就來看看接下來的 Python 程式碼實作,從中瞭解如何實作 Y Combinator。

先來個簡單的開始,如何用遞迴寫個計算階乘的函式?

def fact(n):
    return 1 if(n < 2) else n * fact(n - 1)

這樣是定義一個 fact 函式,現在要求用 lambda 來實現,那麼你可以寫成 fact = lambda n: 1 if(n < 2) else n * fact(n - 1),接下來要求必須是完全匿名,只寫 lambda n: 1 if(n < 2) else n * fact(n - 1) 顯然是不行的,因為 fact 沒有定義,怎麼辦呢?那就再來層 lambda

lambda fact: lambda n: 1 if n < 2 else n * fact(n - 1)

這個 lambda 就合法了,只是想執行這個 lambda 時怎麼辦?誰來給這個 lambda 一個真正的遞迴函式,以便讓 fact 參數可以參考?透過一些巧妙的結合,其實有辦法產生一個真正的遞迴函式,而且是匿名的。

聽說是某天很夯的 fibonacci number XD 中就完成了讓 lambda n, fib: n if(n == 0 or n == 1) else fib(n - 1, fib) + fib(n - 2, fib) 可遞迴的實現,那時沒想太多,因而選擇了讓 fib 的第二個參數又帶入了匿名函式,如果現在打算也找出個函式,可以給 lambda fib: lambda n: n if(n == 0 or n == 1) else fib(n - 1) + fib(n - 2) 一個真正的遞迴函式,以便讓 fib 參數可以參考,那也是有可能的。

不過,階乘與費式數這兩個需求下的函式有沒有可能是同一個?也許是吧!總之,先來看看階乘時會需要的函式是什麼,假設定義為 y 好了:

def y(f):
    # 假設存在一個 fact
    return f(fact)

因為 f(fact)(n) 就可以得到階乘結果,那麼傳回 lambda n: f(fact)(n) 不就是階乘函式?可是 fact 變數還是沒解決啊?那就 …

def y(f):
    fact = lambda n: f(fact)(n)
    return f(fact)

很取巧對吧!只是把變數 fact 藏到 y 裏頭而已,這樣算什麼呢?y 函式有沒有辦法全部用匿名函式實現?假設有個 get_f 能做到這點,那麼就可以變成這樣:

def y(f):
    def get_f():
        # 假設都用匿名函式實現 ...
    return get_f()

實際上,get_f 看來又像個騙子,只是把問題藏到裏頭而已:

def y(f):
    def get_f():
        fact = lambda n: f(fact)(n)
        return f(fact)
    return get_f()

要騙就騙到底好了,既然 f(fact) 就是 get_f() 的傳回結果,那麼就改成這樣:

def y(f):
    def get_f():
        fact = lambda n: get_f()(n)
        return f(fact)
    return get_f()

咦?好像不用 fact 變數了,那就改成這樣:

def y(f):
    def get_f():
        return f(lambda n: get_f()(n))
    return get_f()

只不過,get_f 依舊是個具名的遞迴函式,這樣下去沒完沒了的,假設 get_f 函式有個 get_f 參數,那麼就可以把傳進來的參數再傳給自己,就像實現 聽說是某天很夯的 fibonacci number XD 時的 lambda n, fib: n if(n == 0 or n == 1) else fib(n - 1, fib) + fib(n - 2, fib)

...
    def get_f(get_f):
        return f(lambda n: get_f(get_f)(n))
...

那麼原先的 y 實作就可以改為:

def y(f):
    def get_f(get_f):
        return f(lambda n: get_f(get_f)(n))
    return get_f(get_f)

然後改為 lambda 版本:

def y(f):
    get_f = lambda get_f: f(lambda n: get_f(get_f)(n))
    return get_f(get_f)

既然 get_f = lambda get_f: f(lambda n: get_f(get_f)(n)),那麼 returnget_f 變數就可以替代為:

def y(f):
    get_f = lambda get_f: f(lambda n: get_f(get_f)(n))
    return (lambda get_f: f(lambda n: get_f(get_f)(n)))(lambda get_f: f(lambda n: get_f(get_f)(n)))

既然如此,那 get_f 變數就可以不用了:

def y(f):
    return (lambda get_f: f(lambda n: get_f(get_f)(n)))(lambda get_f: f(lambda n: get_f(get_f)(n)))

咦?沒有變數了?只剩下參數 get_f 了?名稱有點長,改成 x 好了,順便也把 y 改成接受lambda

y = lambda f: (lambda x: f(lambda n: x(x)(n)))(lambda x: f(lambda n: x(x)(n)))

這就是我們想要的了,y 的實現全都是匿名函式!你可以這麼使用它來產生一個可遞迴的階乘函式:

y(lambda fact: lambda n: 1 if n < 2 else n * fact(n - 1))(5) # 120

要不要自己試著也來推導一個可傳回遞迴費式數計算的函式呢?結果其實會是相同的,也就是說,上頭這個 y 也可以用來產生計算費式數的遞迴函式,例如:

y(lambda fib: lambda n: n if(n == 0 or n == 1) else fib(n - 1) + fib(n - 2))(10) # 55

好玩對吧!Y Combinator 看來很神奇,像是可以運行程式的程式(a program that runs programs),美國有間創投公司命名為 Y Combinator,因為它們覺得自己就類似可運行程式的程式 Y Combinator,只不過它們是間協助新創公司的公司。

實用性呢?好像沒有!不過我在這過程中玩得很高興就是了,因為很久前看過 Y Combinator 這名詞出現過幾次了,只不過一直沒去細究它,直到有人在 聽說是某天很夯的 fibonacci number XD 又提到 Y Combinator,我才好奇,原先我實作的版本會跟 Y Combinator 有什麼關係,進一步地,想試著用 Python 來玩玩看!

一切都只是為了有趣!… XD

 

 

 

分享:
按讚!加入 CodeData Facebook 粉絲群

留言

留言請先。還沒帳號註冊也可以使用FacebookGoogle+登錄留言

LungZeno12/24

是否實用,我沒有驗證過。但能想到 Y Combinator 幾個用處。

1、在環境受限的情況下使用。當不支援具名 lambda , closure 支援又有限,例如 PHP 5.3 。

2、解耦合。Y Combinator 的做法其實把遞迴功能分離了出來,就像各種純函數式語言一樣,功能分得細細的。有更高組合性,能做出更多預製組件,更厲害的程式碼復重。

3、Inversion of control,提供遞迴功能。對於無法或不便修改的已有函式,如果接收回呼函式,則有機會能以 Y Combinator 這類方式修改。

12/24

一般的遞迴每次遞迴只需要一個function call,使用Y Combinator會需要四次。如果function call的效率不好(例如PHP),使用上還是要考慮。

熱門論壇文章

熱門技術文章