構造Y組合子

構造Y組合子

Y組合子（Y-Combinator）是Lambda演算的一部分，也是FP編程中為人所津津樂道的一種方法。對于FP程序員來講，估計也仍有不少人對其要么陌生、要么茫茫然。

Y組合子能夠神奇地利用匿名函數/Lambda的方式來表述遞歸調用。Y組合子或不動點組合子的概念可以參考各類百科，這里就不再贅述。

由于最近在鉆研Go語言，因此這里就用Go語言進行描述（文章最后也會列出其他幾種語言的Y組合子實現）。但Y組合子的概念實現思路都是一致的，掌握了思路，用其他語言實現應該沒問題。

話說回來，由于Go語言的類型語言特點，在Go中實現Y組合子很容易被函數定義繞暈了，動態語言則實現起來相對輕松一些。

接下來一步步解釋Y組合子構建思路。

示例描述

在這里，我們隨意選擇了「The Go Programming Language」中的一個例子，作為我們的講解案例：

func comma(s string) string {
    n := len(s)
    if n <= 3 {
        return s
    }
    return comma(s[:n-3]) + "," + s[n-3:]
}

該示例用來對 1234567890 這樣的字符串進行自右往左每隔3個字符加一個逗號： 1,234,567,890 。

這是構建遞歸調用的傳統思路，一般情況下，我們的遞歸就是像上述代碼這樣實現的。可以稱之為一般性遞歸（Natural Recursion）。

Y組合子構建

一 邁出構建Y組合子的第一步

我們可以發現，在一般性遞歸中，必須有個函數名，才能使用遞歸調用。而Y組合子的神奇之處就在于，它能夠利用匿名函數/Lambda的方式來表述遞歸調用。

這是如何做到的？要消除函數名，關鍵是構建一個能夠“自己調用自己”的匿名函數——這是很自然就能想到的，否則無法消除函數名。

下面，看看我們是怎么玩的。

縱使是匿名函數，我們姑且也給這個“無名”一個名字—— f ，因此 f 就變成了（偽代碼）：

f{
    return f(s[:n-3]) + ...
}

接下來，我們就需要確實消除這個“無名”的名，這可聽起來像是什么高深莫測、難以理解的高深武功吶。別急，一步步來。

首先，我們需要添加一個真正的匿名函數作為包裹函數（偽代碼）：

func(f) {
    return ...
}

這里的 return 該返回啥呢？我們知道 f 是個遞歸，如果只返回 f 是不夠的，那跟直接使用 comma 沒什么區別，反而造成內層的 f(s[:n-3]) 遞歸調用無法實現，因為——“無名”。

要返回一個匿名形式的遞歸函數，也就是要返回一個不斷調用自身的函數，其形式為：

f(f)

這個很關鍵。所以有了這樣的代碼（偽代碼）：

func(f) {
    return f(f)
}

上述偽代碼就實現了匿名函數遞歸調用自身的功能，外層加了個包裹函數是為了返回這個遞歸調用的匿名函數 f(f) 。

不管怎么變來變去的，我們要的是 comma 的最初實現。包裝器的返回類型必然跟 comma 函數的類型定義一樣：

func(string) string

所以，我們定義一個 baseFnType ，其跟 comma 的類型定義一樣：

type baseFnType func(string) string

由于匿名函數遞歸調用自身， f 的參數必須接受自身，同時 f 最終也是返回一個 baseFnType 類型，這樣才能跟包裝器的返回類型一致：

type fnType2 func(fnType2) baseFnType

看看 fnType2 ，參數是自己，返回是 baseFnType 類型—— fnType2 也是一個“遞歸類型”。

func(f fnType2) baseFnType {
    return f(f)
}

最后，如何調用這個匿名遞歸函數呢？

很容易，把邏輯以匿名函數的方式包裝一下傳遞給這個匿名遞歸調用即可：

comma :=
    func(f fnType2) baseFnType {
        return f(f)
    }(func(f fnType2) baseFnType {
        return func(s string) string {
            n := len(s)
            if n <= 3 {
                return s
            }
            return f(f)(s[:n-3]) + "," + s[n-3:]
        }
    })

等等，為何最后有個 return f(f)... ？怎么會是 f(f) 呢？因為前面說了，遞歸調用的匿名函數現在是 f(f) 。

好了，先來試試看：

fmt.Printf("%v\n", comma("1234567890"))

很神奇，真的輸出了：

1,234,567,890

最關鍵的一步邁出去了。

二 簡單才好

簡化，遵循Scheme十誡之第八戒——“使用輔助函數來抽象表示方式”

看看邏輯混搭在這個函數里也是怪難受的，我們首先來分離邏輯和骨架。

首先把函數調用同邏輯處理做一定的分離：

comma :=
    func(f fnType2) baseFnType {
        return f(f)
    }(func(f fnType2) baseFnType {
        g := func(s string) string {
            return f(f)(s)
        }

        return func(s string) string {
            n := len(s)
            if n <= 3 {
                return s
            }
            return g(s[:n-3]) + "," + s[n-3:]
        }
    })

然后我們需要為：

return func(s string) string {
    ...
}

里面的業務邏輯定義一個函數，然后通過這個函數，把業務邏輯“注入”進來，這樣，以后不同的業務邏輯都能夠通過這個函數“注入”進來，內部的骨架就不用調整了。因此，該函數也是個包裝器函數。

在此之前我們需要定義一個包裝器的函數類型，該類型以 baseFnType 為參數類型——因為我們傳入的函數類型是 func(s string) string ，根據 return f(f)(s[:n-3]) + "," + s[n-3:] ，包裝器返回的也是一個 baseFnType 類型。因此，我們就有了：

type fnType1 func(baseFnType) baseFnType

以下是簡化后的代碼：

comma :=
    func(fn fnType1) baseFnType {
        return func(f fnType2) baseFnType {
            return f(f)
        }(func(f fnType2) baseFnType {
            g := func(s string) string {
                return f(f)(s)
            }

            return fn(g)
        })
    }

來試試代碼正確與否：

comma :=
    func(fn fnType1) baseFnType {
        return func(f fnType2) baseFnType {
            return f(f)
        }(func(f fnType2) baseFnType {
            g := func(s string) string {
                return f(f)(s)
            }

            return fn(g)
        })
    }(func(g baseFnType) baseFnType {
        return func(s string) string {
            n := len(s)
            if n <= 3 {
                return s
            }
            return g(s[:n-3]) + "," + s[n-3:]
        }
    })

fmt.Printf("%v\n", comma("1234567890"))

OK！輸出：

1,234,567,890

接下來，我們把 g 定義直接放進到 fn 里：

y :=
    func(fn fnType1) baseFnType {
        return func(f fnType2) baseFnType {
            return f(f)
        }(func(f fnType2) baseFnType {
            return fn(func(s string) string {
                return f(f)(s)
            })
        })
    }

嗯！這就是大名鼎鼎的Y組合子。

來測試一下：

comma :=
    y(func(g baseFnType) baseFnType {
        return func(s string) string {
            n := len(s)
            if n <= 3 {
                return s
            }
            return g(s[:n-3]) + "," + s[n-3:]
        }
    })

fmt.Printf("%v\n", comma("1234567890"))

結果OK！

甚至還可以帶入不同邏輯，比如：

upper :=
    y(func(g baseFnType) baseFnType {
        return func(s string) string {
            n := len(s)
            if n == 0 {
                return s
            }
            return g(s[:n-1]) + strings.ToUpper(s[n-1:])
        }
    })

fmt.Printf("%v\n", upper("abcdefghijklmnopqrstuvwxyz."))

將輸出：

ABCDEFGHIJKLMNOPQRSTUVWXYZ.

至此本文告一段落。

其他

由于動態語言沒有強類型要求，因此實現的Y組合子更簡單。下面分別列出Python、JavaScript、Scheme的Y組合子形式。

Python實現：

Y = lambda fn: (lambda f: f(f))(lambda f: fn(lambda s: f(f)(s)))

Y(lambda g:
    lambda s:
        s if len(s)==0
          else g(s[:len(s)-1]) + s[len(s)-1].upper())("abcdefghijklmnopqrstuvwxyz.")

輸出：

JavaScript：

const Y = function(fn) {
    return (function (f) {
        return f(f);
    } (function (f) {
        return fn(function (s) {
            return f(f)(s);
        });
    }));
}

Y(function(g) {
    return function(s) {
        let n = s.length;
        if (n === 0) {
            return s;
        }
        return g(s.substring(0, n-1)) + s.substring(n-1).toUpperCase();
    }
})("abcdefghijklmnopqrstuvwxyz.")

輸出：

Scheme：

(define Y
(lambda (fn)
    ((lambda (f)
    (f f)) (lambda (f)
            (fn (lambda (s) ((f f) s)))))))

((Y (lambda (g)
(lambda (s)
    (cond
    ((null? s) '())
    (else
        (cons (string-upcase (car s)) (g (cdr s)))))))) '("a" "b" "c" "d" "e"))

輸出：

 

來自：http://www.2gua.info/post/66