使用Lambda表达式编写递归二

上一篇文章介绍的 λ 演算是无类型的，对于 FIX、g 我们只知道：它们都是有独个参数的函数，它们的参数本身也是一个只有单一参数的函数；同时，它们值是又一个只有单一参数的函数。

成都创新互联公司是一家集网站建设,丰泽企业网站建设,丰泽品牌网站建设,网站定制,丰泽网站建设报价,网络营销,网络优化,丰泽网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

基于这种描述，是无法将 FIX、g 转化为 c# 代码的，我们需要推断出 FIX、g 类型。

我们先做一些假定，基于假定进行推导，得出结论再抽象为通用类型。

递归参数及返回值类型假定

对于常见的递归函数，如：阶乘、斐波那契数列求值，我们先作如下假定：

1.参数为 int 类型（Int32）；

2.返回值为 long 类型（Int64）。

基于假推断各类型

FIX g 类型

根据上篇文章中的描述：

 
 
 

  
  
  
FIX g = λn. (ISZERO n) 1 (MULT n ((FIX g) (PRED n)))
  
  
  
FIX g 55 = 5 * (4 * (3 * (2 * (1 * 1))) = 120
 
 
 

FIX g 返回的是我们需要的递归函数，这个递归函数

·接收一个 int 参数（上面假定第 1 条）值为 5

·返回一个 long 型数值（上面假定第 2 条）120。

因此，确定出 FIX g 的类型可表示为 Func。

同时也能看出 n 是递归函数的参数，n 类型为 int。

g 类型

阶乘单步函数如下：

 
 
 

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

c# 中可表达为：g => f => n => n == 0 ? 1 : n * f(n – 1)

先来推断 f 的类型：

·f 的参数：f 接收 n – 1 作为参数，因此，f 参数的类型和 n – 1 类型相同，即 n 的类型：int；

·f 的返回值：为 0 时返回 1，否则返回 n * f(n-1)，f 的返回值类型也就是整个递归函数的返回值类型，即 long。

可确定 f 类型为 Func。

n => n == 0 ? 1 : n * f(n – 1)是传入一个 int 返回一个 long，其类型 Func。

先来变换下 g 的表示形式：

 
 
 

  
  
  
var g = (Func f) => { 
  
  
  
    Func t =  
  
  
  
        n => n == 0 ? 1 : n * f(n - 1); 
  
  
  
    return t; 
  
  
  
};  // 示意代码
 
 
 

从上面这段代码可以清楚到看出 g 接收一个 Func 类型的参数 f，返回一个类型为 Func 的委托，可得出：

g 的类型为 Func, Func>

FIX 类型

FIX g 可写作 FIX(g)，可以看出： FIX g 的类型 == FIX(g) 的类型 == FIX 返回值的类型。前面得知 FIX g 类型为 Func，也就可推出 FIX 返回值类型为 Func。

FIX 接受 g 作为参数，FIX 的参数类型也就是 g 的类型，可知 FIX 参数类型为 Func, Func>。

由此得出 FIX 的类型为：Func, Func>, Func>。

（估计这是多数开发人员见过的最复杂的泛型了。后面还在更复杂的吆！）

小结

通用类型

基于以上部分的推演和小结，我们可以归纳出通用类型：

基于本文推断出的类型，不动点组合子转换为 c# 代码了不容易多了。下一篇文章将以 Y 组合子为例进行说明。

网页题目：使用Lambda表达式编写递归二
当前路径：http://www.mswzjz.cn/qtweb/news48/523248.html

攀枝花网站建设、攀枝花网站运维推广公司-贝锐智能，是专注品牌与效果的网络营销公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 贝锐智能