Y Combinator (Y 组合子) 是函数式编程中最重要且优美的概念之一,但也是出了名的抽象和难以理解。《黑客与画家》的作者,硅谷创业教父 Paul Graham 甚至用此命名他的投资公司,以显示对它的喜爱。
本文将从一个最简单的例子开始,逐步地构造出这种优雅的数学结构。
从 Lambda 演算开始
Lambda 演算只有 3 条最近本的规则:
- 变量定义:
x
- 函数定义:
lambda x, y. x + y
- 函数求值:
(lambda x, y. x + y)(1 2)
令人惊讶的是,从这些简单的规则出发,我们可以得到和图灵机完全等价的计算模型。为了达到这个目的,首先要解决的一个问题就是递归。
下面的推到过程中,将全部使用 C# 来说明。原因是:
- 比起 Lisp, Haskell 等语言,语法上更容易理解。
- 强类型约束,更能体现之后的结构。
第一次尝试
先来看看图灵演算下的递归函数
int fact(int n)
{
if(n == 0)
{
return 1;
}
return n * fact(n-1);
}
在函数体内部,又使用了 fact
这个函数的名字。但是,Lambda 演算中只有匿名的函数。那么,一个直观的想法就是把“自己”也当成一个参数传进去,也就是
int selfFact(Func<int,int> self, int n)
{
if(n == 0)
{
return 1;
}
return n * self(n-1);
}
其中 Func<In, Out>
表示一个参数为 In
类型,返回值为 Out
类型的函数。
但这里又引入了新的问题:self
这个函数是什么?
转换形式
从含义上说,self
就应该是递归函数本身,如果能也写成一样的形式就好了。于是就有
delegate int Self(Self self, int n);
int fact2(Self self, int n)
{
if(n == 0)
{
return 1;
}
return n * self(self, n-1);
}
int result = fact2(fact2, 5); //120
这里定义了一个新的函数类型 Self
, 它的参数是 Self
和 int
,返回值是 int
.
于是,就可以把自身传给自身,从而间接的得到了递归的效果。
只是这个 fact2(fact2, 5)
过于的丑陋,难道就不能得到只需要一个参数的函数吗?
自由变量外提
为了实现递归的效果,需要把函数作为参数传递给自身。但是函数原本的参数应该是和这一个过程没有关系的。于是就可以把它(在这个例子里是 int n
)提取出来,得到:
delegate T P<T>(P<T> p);
Func<int, int> fact3(P<Func<int, int>> self)
{
return (n) =>
{
if(n == 0)
{
return 1;
}
return n * self(self)(n-1);
};
}
Func<int, int> fac = fact3(fact3);
fac(5); //120
至此,第一不目标已经达成。注意:
- 在
fact3
函数中,并没有使用fact3
这个名字。 - 最后得到的
fac
函数的类型是Func<int, int>
. 也就是说只需要一个参数n
.
更加通用
显然,这个方法不只局限于求阶乘。如果我们能把阶乘的逻辑从里面剥离出来,就可以实现一个通用的变化方法。这也就是说,把self(self)
从中间拿出来,变成 f
的一个参数。
Func<int, int> fact4(P<Func<int, int>> self)
{
return (n) =>
{
Func<Func<int,int>, Func<int, int>> f = (q) =>
{
return (m) =>
{
if(m == 0)
{
return 1;
}
return m * q(m-1);
};
};
return f(self(self))(n);
};
}
仔细观察一下中间用到的临时函数 f
, 完全就是之前不成功的 selfact
嘛。那干脆直接用之前定义好的。
Func<int, int> fact5(P<Func<int, int>> self)
{
return (n) => selfFact(self(self), n);
}
Y 组合子
从 fact5
函数,我们就得到了一个把 “不成功” 递归的函数变成递归的方法。再加上 fact3
里提到的封装方式,就可以得到一个函数签名也满足需求的函数了,也就是
Func<int, int> Y(Func<Func<int, int>, int, int> f)
{
P<Func<int, int>> g = (self) =>
{
// fact5 里的调用方法
return (n) => f(self(self), n);
};
// fact3 中的封装
return n => g(g)(n);
}
或者更一般的
Func<In, Out> Y<In, Out>(Func<Func<In, Out>, In, Out> f)
{
P<Func<In, Out>> g = (self) =>
{
return (n) => f(self(self), n);
};
return n => g(g)(n);
}
然后这样使用
Y<int,int>((self, n) => n == 0 ? 1 : n * self(n - 1))(5); //120
这样,就实现了在匿名函数里进行递归的方法。由此扩展到更多数量的参数,或者别的语言,也是显而易见的事情了。