日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
使用Lambda表達(dá)式編寫遞歸一：前言及基礎(chǔ)

前言

這是一個(gè)比較古老的話題，三年半之前，老趙就此寫過(guò)一篇很文章《使用Lambda表達(dá)式編寫遞歸函數(shù)》。其中提出了偽遞歸的概念，提出了自己的解決方式，也引出了裝配腦袋 使用不動(dòng)點(diǎn)組合子 的解決辦法。此后好長(zhǎng)一段時(shí)間，偽遞歸和不動(dòng)點(diǎn)組合子成了兩個(gè)園子里的兩大熱門話題。

當(dāng)年我也寫了篇文章《反駁 老趙 之 “偽”遞歸》參與了爭(zhēng)論，不過(guò)對(duì)老趙提出的解決方式及裝配腦袋的不動(dòng)點(diǎn)組合子思路，一直沒(méi)弄清楚。中間一段時(shí)間，工作忙，忘卻了。

最近比較輕閑，靜下心來(lái)學(xué)習(xí)了下相關(guān)的的一些理論，并深入思考，略有所悟，在此和大家分享下。

本文及后續(xù)章節(jié)會(huì)用到相當(dāng)復(fù)雜的泛型及 lambda 表達(dá)式，請(qǐng)做好相關(guān)技術(shù)和心理準(zhǔn)備。

使用 Lambda 表達(dá)式構(gòu)建遞歸函數(shù)

很多朋友認(rèn)為這很容易，隨手便可用 lambda 表達(dá)式寫出一個(gè)階乘遞歸：

 
 
 
      
  
  
  1. Func fact = x => x <= 1 ? 1 : x * fact(x - 1); 
    2.

不過(guò)，很抱歉，這行代碼是無(wú)法通過(guò)編譯的，VS 提示：使用了未賦值的變量 fact。

有種簡(jiǎn)單的解決辦法，把上面這行代碼拆成兩行：

 
 
 
      
  
  
  1. Func fact = null;  
    2.   
  
  
  2. fact = x => x <= 1 ? 1 : x * fact(x - 1); 
    3.

不過(guò)這種寫法也有問(wèn)題，老趙說(shuō)得比較清楚，我就不在贅述了，請(qǐng)查看《使用Lambda表達(dá)式編寫遞歸函數(shù)》一文中偽遞歸部分。

那么如何解決 lambda 表達(dá)式構(gòu)建遞歸函數(shù)的問(wèn)題呢？根據(jù)函數(shù)式編程理論，我們可以使用不定點(diǎn)組合子。

在學(xué)習(xí)不定點(diǎn)組合子之前，需要先了解更基礎(chǔ) λ 演算。

λ 演算

λ 演算的基礎(chǔ)請(qǐng)大家參考維基百科：

http://zh.wikipedia.org/wiki/Lambda_演算

http://en.wikipedia.org/wiki/Lambda_calculus

非形式化的描述

請(qǐng)確保你已經(jīng)理解了文中幾個(gè)表達(dá)式的等價(jià)關(guān)系：

 
 
 
      
  
  
  1. (λf. f 3)(λx. x + 2) == (λx. x + 2) 3 == 3 + 2   
    2.   
  
  
  2. (λx. λy. x - y) 7 2 == (λy.7 - y) 2 == 7 - 2 
    3.

還清楚知道函數(shù)應(yīng)用（application）的概念及其左結(jié)合性：

 
 
 
      
  
  
  1. f x y == (f x) y 
    2.

還有它的各種等價(jià)變換

 
 
 
      
  
  
  1. f x y == (f x) y = (f(x))y = (f(x))(y) = f(x)(y) 
    2.

歸約

并會(huì)運(yùn)用三個(gè)常用的規(guī)約（Reduction）

1.α-變換（α-conversion）

2.β-歸約（β-reduction）

3.η-變換（η-conversion）

不動(dòng)點(diǎn)組合子

請(qǐng)參考：

http://zh.wikipedia.org/wiki/不動(dòng)點(diǎn)組合子

http://en.wikipedia.org/wiki/Fixed-point_combinator

定義

不動(dòng)點(diǎn)組合子（Fixed-point combinator，或不動(dòng)點(diǎn)算子，使用 FIX 表示）是計(jì)算其他函數(shù)的一個(gè)不動(dòng)點(diǎn)的高階函數(shù)。

不動(dòng)點(diǎn)算子具有以下特性，對(duì)于任何函數(shù) f 都有：

 
 
 
      
  
  
  1. FIX ff = f (FIX f) 
    2.

定義匿名的遞歸函數(shù)

不動(dòng)點(diǎn)組合子允許定義匿名的遞歸函數(shù)，具體來(lái)說(shuō)是將一個(gè)非遞歸的單步函數(shù)（只執(zhí)行遞歸中的一步，a single step of this recursion，使用 g 表示）轉(zhuǎn)換為遞歸函數(shù)。

如下是階乘的單步函數(shù)定義：

 
 
 
      
  
  
  1. g = λf. λn. (ISZERO n) 1 (MULT n (f (PRED n))) 
    2.

FIX g 可獲取到匿名的遞歸函數(shù)：

 
 
 
      
  
  
  1. FIX g = λn. (ISZERO n) 1 (MULT n ((FIX g) (PRED n))) 
    2.

向 FIX g 的參數(shù) n 傳入值 5，可最終得出：

 
 
 
      
  
  
  1. FIX g 55 = 5 * (4 * (3 * (2 * (1 * 1)))) = 120 
    2.

常用的不定點(diǎn)組合子

不動(dòng)點(diǎn)組合子中最有名的（也可能是最簡(jiǎn)單的）是 Y 組合子：

 
 
 
      
  
  
  1. Y = λf. (λx. f (x x)) (λx. f (x x)) 
    2.

另一個(gè)常見(jiàn)不動(dòng)點(diǎn)組合子是圖靈不動(dòng)點(diǎn)組合子（阿蘭·圖靈發(fā)現(xiàn)的）:

 
 
 
      
  
  
  1. Θ = (λx. λy. (y (x x y))) (λx.λy.(y (x x y))) 
    2.

傳值調(diào)用（call-by-value）

在 λ 演算中，每個(gè)表達(dá)式（lambda term）都代表一個(gè)只有單獨(dú)參數(shù)的函數(shù)，這個(gè)函數(shù)的參數(shù)本身也是一個(gè)只有單一參數(shù)的函數(shù)，同時(shí)，函數(shù)的值是又一個(gè)只有單一參數(shù)的函數(shù)。

根據(jù)此描述，可知 λ 演算中函數(shù)只有一個(gè)參數(shù)，這個(gè)參數(shù)是一個(gè)函數(shù)，而不是一個(gè)值。而對(duì)于我們常見(jiàn)的遞歸（階乘、斐波那契數(shù)列求值），參數(shù)都是值（自然數(shù)）。兩者是不匹配的。

為了適當(dāng)傳值調(diào)用，需要將不動(dòng)點(diǎn)組合子 η-展開(kāi)：

簡(jiǎn)單而言 η-變換 是說(shuō) λx. f x 和 f 可以互相轉(zhuǎn)換。從 f 這種簡(jiǎn)單形式 η-變換 為 λx. f x 復(fù)雜形式，稱為 η-展開(kāi)。

對(duì)于 Y 組合子，通常是將其中的 (x x) η-展開(kāi)為  λy. x x y，由此得出傳值調(diào)用版本的 Y組合子（也稱為 Z 組合子）：

 
 
 
      
  
  
  1. Y = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y)) 
    2.

如果不展開(kāi)呢？會(huì)怎樣？

如果使用不展開(kāi)的不動(dòng)點(diǎn)算子，也能寫出可編譯通過(guò)的代碼，但最終執(zhí)行會(huì)陷入死循環(huán)，直至堆棧溢出。

小結(jié)

后續(xù)章節(jié)將使用以下符號(hào)和名稱，不再另行說(shuō)明：

1.FIX：不動(dòng)點(diǎn)組合子

2.g：?jiǎn)尾胶瘮?shù)

3.n：表示遞歸函數(shù)的參數(shù)（在階乘、斐波那契數(shù)列求值中是一個(gè)自然數(shù)）

對(duì)于 FIX、g、n：

1.FIX g： 將會(huì)生成對(duì)應(yīng)的遞歸函數(shù)

2.FIX g n： 將進(jìn)行遞歸運(yùn)算

λ 演算表達(dá)式與 c# lambda 表達(dá)式的對(duì)應(yīng)關(guān)系

λx. x + 2

λx. x + 2 在 c#中的 lambda 表達(dá)式可表式為：x => x+ 2；

假定 x 的 int 類型，可寫作：

 
 
 
      
  
  
  1. Func f = x => x + 2; 
    2.

相應(yīng) (λx. x + 2) 1 可寫為：

 
 
 
      
  
  
  1. var result = f(1);    // 結(jié)果為 3 
    2.

λx. λy. x + y

復(fù)雜點(diǎn)，λx. λy. x + y 用 c# 的 lambda 表達(dá)式表示為：x => y => x + y；

x, y 類型為均整數(shù)時(shí)，可寫作：

 
 
 
      
  
  
  1. Func> f = x => y => x + y; 
    2.

相應(yīng) (λx. λy. x + y) 1 2 便是：

 
 
 
      
  
  
  1. var result = f(1)(2);     // 結(jié)果為 3 
    2.

λx. λy. λz. x + y + z

再?gòu)?fù)雜些，λx. λy. λz. x + y + z 表示為：x => y=> z => x + y + z，三個(gè)參數(shù)都為 int 時(shí) c# 代碼：

 
 
 
      
  
  
  1. Func>> f = x => y => z => x + y + z; 
    2.

可如下調(diào)用：

 
 
 
      
  
  
  1. // (λx. λy. λz. x + y + z) 1 2 3  
    2.   
  
  
  2. var result1 = f(1)(2)(3);    //結(jié)果為 6  
    3.   
  
  
  3.  
    4.   
  
  
  4. // (λx. λy. λz. x + y + z) 1  →  λy. λz. 1 + y + z   
    5.   
  
  
  5. Func> g = f(1);   
    6.   
  
  
  6. // (λy. λz. 1 + y + z) 2  →  λz. 1 + 2 + z  →  λz. 3 + z  
    7.   
  
  
  7. Func h = g(2);  
    8.   
  
  
  8. // (λz. 3 + z) 3  →  3 + 3  →  6  
    9.   
  
  
  9. var result2 = h(3);        // 結(jié)果為 6 
    10.

每 5 行，向 f 傳入一個(gè)常量 1，返回一個(gè)新的方法 g；再經(jīng)過(guò)第 7 行，向 g 傳入常量 2，再次返回一個(gè)新方法 h。

方法 h 只能接受一個(gè)參數(shù)，***得出 h(3) = 6。

為什么不是  (x, y, z) => x + y + z？

也許你會(huì)有疑問(wèn)，不就是 x、y、z 三個(gè)整數(shù)加起來(lái)嘛，為什么搞這么復(fù)雜，像下面這樣不是更簡(jiǎn)單嗎？

 
 
 
      
  
  
  1. Func f = (x, y, z) => x + y + z;  
    2.   
  
  
  2. var result = f(1, 2, 3); 
    3.

確實(shí)簡(jiǎn)單，不過(guò)：

在 λ 演算中，每個(gè)表達(dá)式（lambda term）都代表一個(gè)只有單獨(dú)參數(shù)的函數(shù)，這個(gè)函數(shù)的參數(shù)本身也是一個(gè)只有單一參數(shù)的函數(shù)，同時(shí)，函數(shù)的值是又一個(gè)只有單一參數(shù)的函數(shù)。

注意都是只有一個(gè)參數(shù)，對(duì)應(yīng)到 c# 的 lambda 表達(dá)式，也應(yīng)是一個(gè)參數(shù)，所以是：x => y=> z => x + y + z。

總結(jié)

λ 演算表達(dá)式c# lambda 表達(dá)式
λx. x + 2x => x+ 2
λx. λy. x + yx => y => x + y
λx. λy. λz. x + y + zx => y=> z => x + y + z

好像有些規(guī)律：對(duì)于一個(gè) Lambda terms，去掉“λ”并把“.”替換為”=>”便可變成對(duì)應(yīng) lambda 表達(dá)式。（注意，這個(gè)規(guī)律不嚴(yán)謹(jǐn)?。?/p>

練習(xí)一下，看看下面這個(gè)如何轉(zhuǎn)為 lambda 表達(dá)式：

 
 
 
      
  
  
  1. λx. λn. (g (x x) n) 
    2.

先對(duì)它進(jìn)行一步演算得出：

 
 
 
      
  
  
  1. λx. λn. (g (x(x)) (n))  
    2.

運(yùn)用上的的規(guī)律，可以寫出 lambda 表達(dá)式：x => n => g((x(x))(n)

對(duì)于復(fù)雜點(diǎn)的如：λx. f ( λv. (x x) v)，這條規(guī)律就不適用了。文后續(xù)部分會(huì)通過(guò)演算繞開(kāi)這種復(fù)雜的轉(zhuǎn)換，不對(duì)此進(jìn)行討論。

理解本文中的泛型和 lambda 表達(dá)式

對(duì)于上一部分使用的泛型和 lambda 表達(dá)式，尤其是下面這行代碼，你需要花點(diǎn)時(shí)間去理理思路（因?yàn)楹罄m(xù)章節(jié)中泛型要遠(yuǎn)比此復(fù)雜）：

 
 
 
      
  
  
  1. Func>> f = x => y => z => x + y + z; 
    2.

如果對(duì)你對(duì)泛型和 lambda 認(rèn)識(shí)不是非常深刻的話，難度有點(diǎn)大，不妨先從下面這個(gè)簡(jiǎn)單點(diǎn)的開(kāi)始：

 
 
 
      
  
  
  1. Func> f = x => y => x + y; 
    2.

換種寫法，或許有助于理解：

 
 
 
      
  
  
  1. Func>  f = x => {                
    2.   
  
  
  2.     Func g =  y => { return x + y ;};  
    3.   
  
  
  3.     return g;  
    4.   
  
  
  4. }; 
    5.

本文簡(jiǎn)單闡述了 lambda 構(gòu)建遞歸函數(shù)的問(wèn)題，粗略提及 λ 演算及不動(dòng)點(diǎn)組合子的知識(shí)，并總結(jié)了下 λ 演算表達(dá)式與 c# lambda 表達(dá)式的對(duì)應(yīng)關(guān)系。


當(dāng)前文章：使用Lambda表達(dá)式編寫遞歸一：前言及基礎(chǔ)
URL分享：http://www.5511xx.com/article/codpeso.html