匿名递归,即使用固定点组合子的方式,在命令式、强类型语言中并不常见。原因很简单,因为给函数起一个名称比定义执行相同任务的匿名函数更容易。此外,面向对象分析与设计(OOA&D)教导我们,具有多个引用价值的代码不应重复,而应该命名,并从公共位置访问。Lambda表达式本质上是一次性的,它是指定几行非常特定代码以在更通用的算法(如循环结构)中使用的一种方式。大多数递归算法都是具有相当普遍应用的事物(如排序、递归序列生成等),这些算法通常会使它们变得更广泛可用。
除了λ演算之外,在大多数编程语言中,必须存在匿名函数F才能使用它。这排除了以自身为基础定义函数的可能性。在某些函数式语言(如Erlang)中,函数F是使用“重载”定义的,其中较简单的函数用作更复杂函数的基本情况:
Fact(0) -> 1
Fact(i) -> Fact(i-1) * i
这本来没问题,但在Erlang世界中这是一个命名函数“Fact”,调用该方法时程序会“落”到一个重载上,直到找到第一个参数匹配的重载为止。在C#中没有这样精确的构造,因为C#不支持基于值选择重载。
关键是要以某种方式获得可以传递给函数的函数引用。有许多方法,所有方法都需要预先存在的引用。如果无法通过名称引用函数,则FP组合器函数的类型为
Func<Func<Func<Func<Func<...
。Konrad的方法最简单,但在C#中却成了一种hack(虽然它编译了,但ReSharper仍然会抱怨它可能会引发InvalidOperationException;无法调用空方法指针)。
以下是我在简单情况下使用的代码,基本上使用委托解决了不能隐式类型化隐式类型化lambda的问题:
public static class YCombinator
{
public delegate TOut RLambda<TIn, TOut>(RLambda<TIn, TOut> rLambda, TIn a);
public static Func<T,T> Curry<T>(this RLambda<T,T> rLambda)
{
return a => rLambda(rLambda, a);
}
}
var curriedLambda = YCombinator.Curry<int>((f, i) => i <= 0 ? 1 : f(f, i - 1)*i)
var shouldBe120 = curriedLambda(5);
您可以声明一个
Curry<TIn, TOut>
重载函数来处理输入类型与输出类型不同的情况,例如生成前N个质数列表等;该函数P可以被递归地定义为产生所有不被任何较小的质数整数整除的正整数列表函数。固定点P(1) => 2定义了一个基本情况,递归算法可以从中定义(尽管不是很高效):
var curriedLambda =
YCombinator.Curry<int, List<int>>(
(p, i) => i == 1
? new List<int>{2}
: p(p, i - 1)
.Concat(new[]
{
Enumerable.Range(p(p, i - 1)[i - 2],
int.MaxValue - p(p, i - 1)[i - 2])
.First(x => p(p, i - 1).All(y => x%y != 0))
}).ToList()
);
Assert.AreEqual(new []{2,3,5,7,11}, curriedLambda(5));
因此,难题出现了;虽然你当然可以将所有内容定义为高阶函数,但是如果以命令式而不是函数式的方式定义这个素数查找器,它会更快。主要的加速是在每个级别上定义p(p,i-1),使其不被每个递归级别评估3次。一种更智能的设计用于函数工作的语言会为您做到这一点。
Y
将允许在本质上不支持递归的语言中实现递归。递归地定义Y
会打败它最初的目的(尽管在某些情况下仍然有用)。 - Charlesfix
函数的定义:fix f = let x = f x in x
。[来源(haskell.org)](http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/Data-Function.html#fix) - Dan Burton