手機(jī)站首頁散文詩歌雜文隨筆日記小小說

散文網(wǎng) » 科技 »學(xué)習(xí) » 第 75 講：C# 2 之匿名函數(shù)（三）：遞歸匿名函數(shù)

第 75 講：C# 2 之匿名函數(shù)（三）：遞歸匿名函數(shù)

2021-12-27 15:32 作者:SunnieShine 0人讀過 | 我要投稿

今天我們來看一個(gè)全新的內(nèi)容：遞歸匿名函數(shù)。

有沒有想過，匿名函數(shù)這種東西，連自己名字都沒有，那么它能不能遞歸呢？實(shí)際上，匿名函數(shù)也是可以遞歸的。

呃……本節(jié)內(nèi)容因?yàn)闋砍兜綌?shù)學(xué)和計(jì)算機(jī)理論相關(guān)的內(nèi)容，所以難度不小……不過它們也不是特別重要，所以不想學(xué)的話可以跳過。

Part 1 讓我們先來看例子

我們直接來看例子。假設(shè)我們要獲取一個(gè)數(shù)的階乘的話：

好吧，有點(diǎn)過于困難了。這里倒不是打算讓你一下子就看懂的。下面我們來說一下，如何遞歸一個(gè)匿名函數(shù)。

Part 2 匿名函數(shù)的細(xì)節(jié)

2-1 匿名函數(shù)和委托實(shí)例

為了正確和正常銜接后面的內(nèi)容，我還是說一下匿名函數(shù)的這個(gè)知識點(diǎn)。

匿名函數(shù)是一個(gè)表達(dá)式。

是的，記住這句話吧。這句話別看很簡單，但是這個(gè)“表達(dá)式”確定了它的具體使用范疇和內(nèi)容。所謂的表達(dá)式，指的就是一個(gè)整體，它整體表示一個(gè)結(jié)果，不論結(jié)果的數(shù)據(jù)類型是什么（整數(shù)類型的結(jié)果也好、浮點(diǎn)數(shù)類型的結(jié)果也好、字符串類型的結(jié)果也好、委托類型的結(jié)果也好），它得是一個(gè)“值”，并且這個(gè)“值”可以提供給別處使用的這么一個(gè)存在。

是的，既然是一個(gè)值，就可以隨便用。它可以用在：

變量賦值：類型數(shù)值 = 表達(dá)式;；
返回值：return 表達(dá)式;；
傳參：函數(shù)名(表達(dá)式, ...)；
等等……

所以，用于返回值，就相當(dāng)于是把實(shí)例化語句 new 委托(方法組) 的同等效果的語句給作為返回值給返回了；而傳參就不多說了（前面也用得不少了）；然后是變量賦值，也不必多說。

2-2 返回委托的方法

是的，委托類型的對象是可以用作返回的，所以這就會(huì)導(dǎo)致很神奇的現(xiàn)象。假設(shè)我現(xiàn)在試著這么寫代碼：

首先，f 變量表示一個(gè)委托類型的實(shí)例，它表示一個(gè)方法，方法返回了 x 的兩倍，而 g 變量也是一個(gè)匿名函數(shù)，它不要任何的參數(shù)，直接返回了 f。

那么，我如果調(diào)用 g 的話，g() 表示得到一個(gè)類型為 Func<int, int> 的結(jié)果，所以 g() 就等價(jià)于 Func<int, int> 的委托類型實(shí)例；接著，我們對這個(gè)實(shí)例繼續(xù)調(diào)用，就會(huì)得到 result 結(jié)果了。這里我們相當(dāng)于嵌套了一層委托類型的實(shí)例，只是單純?yōu)榱梭w現(xiàn)這種行為，因?yàn)橄旅嫖覀儠?huì)用到這種寫法——“疊委托”的這種效果。

順帶請你注意一下 Func<Func<int, int>> 的寫法。這個(gè)我們以前說到過，怎么去看泛型參數(shù)。

Part 3 不動(dòng)點(diǎn)組合子和遞歸匿名函數(shù)

3-1 牛刀小試：不動(dòng)點(diǎn)組合子的概念

我們來說一個(gè)概念。在說它之前，我們先來看看如何構(gòu)造遞歸匿名函數(shù)。這事，我們得先從遞歸方法說起。

C# 的遞歸是允許的，這意味著我們可以在一個(gè)叫做 F 的方法里再次使用 F 自己。假設(shè)我們使用遞歸完成階乘運(yùn)算，那么，它的代碼肯定是這樣的：

這肯定是顯然的，因?yàn)?0! 是我們的規(guī)定結(jié)果，而其它的數(shù)字的階乘都可以通過數(shù)學(xué)公式計(jì)算得到，因此我們完全不必對 n 是別的數(shù)值進(jìn)行枚舉。至于遞歸的邏輯我們就不再說明了，如果不懂怎么遞歸的朋友，可以參考我以前寫的 C# 方法里的遞歸的內(nèi)容。

我們來思考一下，我們要想讓匿名函數(shù)可以遞歸，那么起碼得有個(gè)名字吧。因?yàn)槟涿瘮?shù)拿出來自己是沒有名字的，那么，我起碼得讓一個(gè)匿名函數(shù)有一個(gè)名字才可能有辦法讓它遞歸。是的，匿名函數(shù)的“名字”是破解這個(gè)問題的關(guān)鍵?？蓡栴}就在于，我上哪里去給匿名函數(shù)取名?。磕氵@不是在逗我？！匿名函數(shù)能有名字，我把教程吃了！

還真有辦法。匿名函數(shù)總歸是一個(gè)委托類型的表達(dá)式吧，那么既然是表達(dá)式，那么自然就會(huì)有賦值方（表達(dá)式本身）和接收方（變量）的概念。那么，接收方如果是一個(gè)同樣委托類型的變量呢？那么這個(gè)變量名，能不能作為匿名函數(shù)的名字呢？這就是我們構(gòu)造匿名函數(shù)的名字的辦法。

接著，我們需要對這個(gè)匿名函數(shù)傳參并且完成遞歸計(jì)算的過程。先不考慮別的，我這么寫代碼：

先不管這個(gè) f。我們來思考一下里面的嵌套匿名函數(shù)。我們第 4 到第 7 行代碼包裹的是一層匿名函數(shù)，它的執(zhí)行邏輯是一個(gè)遞歸。這下好了，遞歸要使用遞歸的方法名，這哪里來呢？我們外面套一層匿名函數(shù)，然后參數(shù)名是這個(gè)不就行了？

我外面嵌套一個(gè) fac 參數(shù)，它是 Func<int, int> 的委托類型的變量。這一看就很符合現(xiàn)在我們的要求嘛。因?yàn)槲覀円f歸，方法確實(shí)是傳入一個(gè) int，返回一個(gè) int，那不就是 Func<int, int>？

那么，我們相當(dāng)于得到了一個(gè)用來遞歸執(zhí)行求階乘的匿名函數(shù)表達(dá)式?？桑瑔栴}來了。這我咋用這個(gè) f ?。窟@就需要一個(gè)新的概念了：不動(dòng)點(diǎn)組合子（Y-Combinator 或 Fixed-Point Combinator）。它的精確定義是這樣的：有兩個(gè)函數(shù) f 和 g，如果函數(shù) g 滿足 g(f) = f，那么我們就把 g 函數(shù)稱為 f 函數(shù)的不動(dòng)點(diǎn)組合子。

這個(gè)概念有些抽象。我們先來說一下這個(gè)概念的 g(f) = f 表達(dá)式。我們好比把這里的 f 當(dāng)成代碼里的這個(gè) f 變量。我們現(xiàn)在要找到一個(gè)變量 g（是 Func<int, int> 類型的），在將 f 當(dāng)參數(shù)傳入到 g 里調(diào)用之后，會(huì)得到 f，這樣的話，我們就可以稱為 g 是 f 的不動(dòng)點(diǎn)組合子了。那這個(gè)概念跟我接下來說的有什么關(guān)系呢？就這個(gè)題來說，我們確實(shí)需要找到的是一個(gè)遞歸的入口?；貞浺幌缕胀ǖ倪f歸方法，我們這么寫代碼就可以了：

而我們調(diào)用的時(shí)候，因?yàn)槲覀兪侵苯又肋f歸的過程，因此 F 能夠完美被我們直接從外部調(diào)用起來：比如 F(10)。可問題就在于，我們前文構(gòu)造的雙層匿名函數(shù)的表達(dá)式，我們內(nèi)層的執(zhí)行邏輯才是我們真真正正要用到的邏輯，而問題就在于它沒有名字，因此我們無法從外界訪問和獲取它。顯然這是不可能的。

現(xiàn)在我們構(gòu)造的這個(gè)“面目全非”的究極嵌套匿名函數(shù)表達(dá)式是沒辦法直接用的。我們把它當(dāng)成 f 的話，我們要想做的就是，找到一個(gè)入口點(diǎn) g，然后傳參進(jìn)去，得到目標(biāo)的結(jié)果。這不就是不動(dòng)點(diǎn)組合子的概念么？是的，我們要找的就是 f 這個(gè)匿名函數(shù)的不動(dòng)點(diǎn)組合子。有了這個(gè) g，我們才能使用比如 g.Invoke(10) 來完成求 10 的階乘。

這不可能吧！我要通過函數(shù)求一個(gè)比它還高一階的函數(shù)，這怎么可能？！不定積分都能求，為啥不動(dòng)點(diǎn)組合子不能求？下面我們就上手給大家推導(dǎo)一遍。

3-2 百尺竿頭：尋找合適的不動(dòng)點(diǎn)組合子

為了能夠嚴(yán)謹(jǐn)?shù)仃U述我要說明的內(nèi)容，我這里借用和使用了一門叫做 λ 演算的學(xué)科的數(shù)學(xué)語言來表示下面的內(nèi)容。

著名的數(shù)學(xué)家和邏輯學(xué)家 Haskell Curry 發(fā)現(xiàn)了 f 作為遞歸函數(shù)的不動(dòng)點(diǎn)組合子 Y 的表達(dá)式：

$Y%20%3D%20%5Clambda%20f.(%5Clambda%20x.%20f(x%5C%20x))(%5Clambda%20x.f(x%5C%20x))$

這個(gè)寫法肯定看不懂，因?yàn)樗?λ 演算（Lambda Calculus）這門科目里的數(shù)學(xué)語言寫法。我們把一個(gè) delegate (p) { return r; } 這么一個(gè)表達(dá)式用數(shù)學(xué)語言表達(dá)出來是寫成 $%5Clambda%20p.%20r$ ?的，這個(gè) p 是參數(shù)的意思，r 則是返回值的意思。舉個(gè)例子，比如 $%5Clambda%20x.x%2B1$ ?就等于是在帶入 int x 求 x + 1 的結(jié)果，即 delegate (int x) { return x + 1; }。而如果要對 λ 演算帶入數(shù)值的話，數(shù)學(xué)語言是直接寫在 λ 演算表達(dá)式的后面的。比如 $(%5Clambda%20x.x%20%2B%201)%5C%203$ ?就是在計(jì)算，將 3 帶入到 delegate (int p) { return p + 1; } 這樣的匿名函數(shù)里參與運(yùn)算，并得到結(jié)果，即 4。

那么，我們先來說說 Y 整個(gè)表達(dá)式是個(gè)啥。這個(gè)東西先從里面往外看。首先我們注意 $%5Clambda%20x.%20f(x%5C%20x)$ ，是重復(fù)的，左右兩邊都有這個(gè)相同的內(nèi)容。在 λ 演算里，這個(gè)小括號是不可省略的。如果這個(gè)小括號沒有了的話，這個(gè)寫法就變?yōu)檫@樣： $%5Clambda%20x.%20(f%5C%20x)%5C%20x$ ，這意味著我執(zhí)行的 λ 演算部分是 $%5Clambda%20x.%20f%20x$ ，即類似編程語言寫法的 delegate (int x) { return f(x); } 的東西。這里的 x 是形式參數(shù)，所以換成什么都可以；但是注意到 $%5Clambda%20x.(f%5C%20x)%5C%20x$ ?的后面還有一個(gè) x，這才是真正的實(shí)際參數(shù)，比如可能是從上面拿下來的變量 x，也可以代表的是一個(gè)真正的數(shù)值。

可 $%5Clambda%20x.f(x%5C%20x)$ ?的意思就完全不同了。兩個(gè)并在一起的 x 意味著此時(shí)是一個(gè)遞歸函數(shù)。而 $f(x%5C%20x)$ ，告訴了你，它是跟外層 $%5Clambda%20f$ ?里的這個(gè) f 相關(guān)的函數(shù)式子。為什么說它遞歸呢？因?yàn)? $f(x%5C%20x)$ ?的后面這個(gè) x 是用作前面這個(gè) x 帶入的實(shí)際參數(shù)值，而前面的 x 只是一個(gè)虛幻的表示。

請注意，我在整個(gè)表達(dá)式 $%5Clambda%20f.(%5Clambda%20x.%20f(x%5C%20x))$ ?的末尾還寫了一次 $%5Clambda%20x.%20f(x%5C%20x)$ ，這顯然不是搞笑，這是實(shí)際值。換句話說，我想要對這個(gè)函數(shù)自身作為數(shù)值傳入到 Y 里，就可以達(dá)到遞歸 $%5Clambda%20x.%20f(x%5C%20x)$ ?的作用，這就是我想要的寫法?？墒牵@太抽象了。我們來看看前面的例子吧。

而我們仔細(xì)對照 λ 演算的表達(dá)式寫法 \lambda f.(\lambda x. f(x\ x))，是不是很眼熟？我們來看下這個(gè)圖片的內(nèi)容吧！

如圖所示，每一層我都給你表示出來了。

那么，我們來看看完整的推導(dǎo)過程吧。

$%5Cbegin%7Balign%7D%0AY%20%26%3D%20%5Clambda%20f.(%5Clambda%20x.%20f(x%5C%20x))(%5Clambda%20x.f(x%5C%20x))%5C%20g%20%26%20%5Ctext%7BDefinition%20of%20%7D%20Y%5C%5C%0A%26%3D(%5Clambda%20x.g(x%5C%20x))(%5Clambda%20x.g(x%5C%20x))%20%26%20%5Cbeta-%5Ctext%7Breduction%20of%20%7D%5Clambda%20f%5C%5C%0A%26%3Dg((%5Clambda%20x.g(x%5C%20x))(%5Clambda%20x.g(x%5C%20x)))%20%26%20%5Cbeta-%5Ctext%7Breduction%20of%20%7D%5Clambda%20x%5C%5C%0A%26%3Dg(Yg)%20%26%20%5Ctext%7BSecond%20equality%7D%0A%5Cend%7Balign%7D$

是的，我們這里的目標(biāo)寫法 g (Y g)，就是我們這里所需的代碼了，其中這個(gè) g，就是代指我們前文給出的 f = 嵌套匿名函數(shù) 的這個(gè) f 了。簡單說一下推導(dǎo)過程。

首先，我們將 g 作為整個(gè)表達(dá)式傳入到 Y 這個(gè)我們目標(biāo)給出的式子里去，按照 λ 演算的基本規(guī)則，我們自然是寫在整個(gè)式子的最后即可。接著，寫進(jìn)去后，我們可以使用一次對 $%5Clambda%20f$ ?的 β-規(guī)約。所謂的 β-規(guī)約（Beta-reduction），指的是帶入的時(shí)候，按定義規(guī)則替代變量，以簡化整個(gè) λ 演算的表達(dá)式?？梢钥吹皆诘仁教鎿Q后，原本的表達(dá)式 $%5Clambda%20f.(%5Clambda%20x.%20f(x%5C%20x))(%5Clambda%20x.f(x%5C%20x))$ ?里的 $f(x%5C%20x)$ ?被改成了 $g(x%5C%20x)$ 。這是顯然的，因?yàn)槲覀兇_實(shí)是這么帶入的——最外層的 f 用于遞歸代表里面的表達(dá)式；而 g 則是實(shí)際我們傳入進(jìn)去用的“變量”，因此很顯然這么替換是正確的。

接著，我們再次對 $%5Clambda%20x$ ?做一次 β-規(guī)約。于是，整個(gè)表達(dá)式就因?yàn)?x 帶入了 $%5Clambda%20x.g(x%5C%20x)$ ?而變?yōu)榈谌械氖阶印＿@次稍微復(fù)雜一些，但還是很正確的替代方式，因?yàn)榍懊媸侵苯?g 替換 $%5Clambda%20f$ ，而這次是 $%5Clambda%20x.g(x%5C%20x)$ ?這一坨去替換 $%5Clambda%20x$ ，就先得有些奇怪，但你多看看，其實(shí)替代也不是不能理解，也沒有任何錯(cuò)誤。

最后，我們發(fā)現(xiàn)到一個(gè)神奇的式子： $g((%5Clambda%20x.g(x%5C%20x))(%5Clambda%20x.g(x%5C%20x)))$ 。這個(gè) g 只是函數(shù)名對吧，我們把這個(gè)表達(dá)式的 g 給改成 f，是不是就是帶入 g 的 Y？所以，帶入 g 的 Y 在這里我們記作 Y g，而它是關(guān)于 g 的一個(gè)函數(shù)，因此，Y = g (Y g) 就是本推算過程的最終結(jié)果了；而這里的 g 就表示我們通過剛才“遞歸化”后得到的那個(gè)復(fù)雜的 f = 嵌套遞歸函數(shù) 的這個(gè) f 了。

那么，編程語言我們要怎么描述 Y = g (Y?g) 呢？其實(shí)也沒有你想象得那么復(fù)雜。請看下面的代碼，它就是 Y 的 C# 版編程語言的寫法。

如代碼所示，對于一個(gè)不動(dòng)點(diǎn)組合子 Y，我們對于任何數(shù)據(jù)類型 T 和 TResult，我們都應(yīng)有這樣的代碼是成立的。這就是我們前文說了一大堆的遞歸函數(shù)入口。通過 Y 方法，我們就可以如愿傳入剛才的 f 委托類型對象，然后提取出遞歸過程了。

順帶一說。既然我們通過這樣復(fù)雜的過程得到了這個(gè)結(jié)論，那么結(jié)論顯然就不是只對這道題有用。但凡只要一個(gè)參數(shù)的匿名函數(shù)要想遞歸，我們?nèi)慷伎梢酝ㄟ^這樣的方式來完成，而這里的 Y 方法，就是通用的、獲取遞歸入口點(diǎn)的方法。你可以用于任何遞歸匿名函數(shù)的地方。

3-3 水落石出：終于可以調(diào)用遞歸匿名函數(shù)了！

這下，我們有了這個(gè)式子之后就可以歡快調(diào)用它了！我們將式子 Y 用作不動(dòng)點(diǎn)組合子，而 f 將其直接傳入，我們就可以獲得 factorial 委托類型的結(jié)果，它就是遞歸入口。

我們運(yùn)行程序，確實(shí)可以得到正確的結(jié)果，因此這樣的作法是完全正確的。這說明了我們完成了遞歸匿名函數(shù)的任務(wù)。

Part 4 直接遞歸是錯(cuò)誤的語法（？

可能你這么想過，也這么去試過：

可它，并不正確。編譯器會(huì)報(bào)錯(cuò)。錯(cuò)誤原因也很簡單：你不能在定義之前使用變量。這是顯然的，因?yàn)?fac 是我這行的變量名，我怎么可能會(huì)允許一個(gè)變量都還沒定義完成就先使用了呢？

要不……我們拆開？

這樣，欸！編譯器沒報(bào)錯(cuò)了！我們試著運(yùn)行 fac.Invoke(10)，確實(shí)是正確的 3628800。

呃……是的……這樣確實(shí)可以……全劇終。

至此我們就完成了匿名函數(shù)的基本底層實(shí)現(xiàn)機(jī)制和語法的學(xué)習(xí)。下一講我們會(huì)學(xué)一個(gè)新的語法特性。

標(biāo)簽：