大到可以小说的Y组合子(二)

问:上一回,你在最后曾提到“抽象性不足”,这话怎么说?

答:试想,如果现在需要实现一个其它的递归(比如:Fibonacci),就必须把之前的模式从头套一遍,然后通过fib_maker(fib_maker)来返回一个fib函数。可见,这个产生递归过程的“接口”让用户相当不舒服。

问:嗯,fib_maker(fib_maker)这种形式看起来的确不怎么舒服,那又如何对其进行抽象,以得到更好的接口呢?

答:这里,有两条路可以走。其一,就是对fact_maker(fact_maker)进一步抽象,便可得到传说中的Y组合子;其二,则是否定之前所为,走一条能反应Y组合子本质的路。二选一,你走那条?

问:???...

答:那就走第二条路吧,至于如何抽象出Y组合子,放到第(四)章谈。 在开始今天的讨论之前,我们先来定义一些委托类型,以方便后文的表达:

//C#
delegate T OuroborosFunc<T>(OuroborosFunc<T> self);
class Y<T, TResult>
{
public delegate TResult Func1(T p);
public delegate Func1 Func2(Func1 f1);
public delegate Func1 Func3(Func2 f2);
... ...
}

这样就可以得到(==表示类型等价,并且在下文使用时省略Y<int,int>限定):

//C#伪码
Func1 == Func<int,int>
Func2 == Func<Func1,Func1> == Func<Func<int,int>,Func<int,int>>
Func3 == Func<Func2,Func1> == Func<Func<Func<int,int>,Func<int,int>>,Func<int,int>>

OK,让我们回忆一下上一章的讨论:

//C#
OuroborosFunc<Func<int, int>> fact_maker =
self => x => x == 0 ? 1 : x * self(self)(x - 1);

为了传递fact_maker给self,我们在Lambda的主体内做了让步——以self(self)的形式来表达fact递归。试想,如果我们不打算传入fact_maker,而是直接传入一个能表达递归的Lambda(类型为Func<int,int>,即Func1),且同时能返回这个Lambda,那么,将得到如下结果:

//C#
Func2 fact_seed = fact => x => x == 0 ? 1 : x * fact(x - 1);

对此,我们来做一个形式化的描述,令F为fact_seed,f为那个表达递归的Lambda,则:F(f) = f, 也就是说f是F的一个不动点。所谓函数的不动点,即函数作用于之得到的仍是其本身的那个点,如:若F(x)=x*x, 则1则是F的一个不动点,因为F(1)=1. 到这里,大家应该可以看出来了,我们期望得到的那个匿名递归fact,其实正是fact_seed的不动点。再试想,如果我们有这么一个函数Fix,它的作用就是求某个函数的不动点,那么,所要求的fact即为Fix(fact_seed).  终于,理想的接口产生了,那就是只要把诸如fact_seed这样的Lambda交给Fix,得到的不动点就是问题的解。

//C#
Func1 fact = Fix(fact_seed);
//或者
Func1 fact = Fix(fact => x => x == 0 ? 1 : x * fact(x - 1));

问:那这个Fix到底是什么呢?

答:根据以上伪码,Fix的类型已然昭昭:Func3,再根据其功能,似乎应该是这样一个高阶函数:

//C#伪码
Func3 Fix = f=>(f的不动点);

而f的不动点怎么表示呢?Fix(f),这样代入上式其实什么也没有做。既然Fix(f)是f的不动点,那Fix(f)=f(Fix(f))=f(f(Fix(f)))...都应该是f的不动点。于是得到(当然也可以取f(f(Fix(f))),我没测试过,应该没问题):

//C#
Func3 Fix = f=>f(Fix(f));

这里需要稍加甄别,对于lazy求值的函数语言来说,上式的定义的确没问题,但是C#是eager求值的,所以Fix(some_f)表答的意思是——将f应用于Fix(some_f)的求值,而Fix(some_f)的求值势必导致新一轮的求值,直至堆栈溢出,可以这样修正这个问题:

//C#
Func3 Fix = f=>f(x=>Fix(f)(x));

现在可以来测试一下结果了:

//C#
int result = Fix(fact => x => x == 0 ? 1 : x * fact(x - 1))(5);
Console.WriteLine(result); //120

依然非常棒,得到了正确的结果。

问:慢着...这里似乎有问题啊,我们的目的是完成一个匿名的递归,那个fact_seed的确是可以做到匿名,但是Fix却是一个普通的递归啊!

答:Good Question! 那你想想应该怎么解决这个问题呢?

问:嗯,让我好好想想,再听你下回分解吧。

答:待续...

上一篇:UVa437 The Tower of Babylon(巴比伦塔)


下一篇:Shell文本处理四剑客