Y组合子

作者: 普通的人形使 | 来源:发表于2018-01-15 10:47 被阅读0次

    Y组合子要解决的问题是如何用纯正的lambda表达式实现递归
    以阶乘为例,可以采用下面的代码以递归的形式表达:

    f n = if n > 1 then n * f (n-1) else 1
    

    要求一个自然数n的阶乘只要调用f n即可
    上述代码包含了一个赋值语句,而纯正的lambda表达式是没有赋值语句的,那么用纯正的lambda表达式能否实现递归呢?

    可以猜测能求阶乘的函数有很多个,比如f n = foldl (*) [1..n]就是其中之一.于是我们将能求阶乘的函数f当成一个变量,这样定义阶乘就变成了求f的值

    定义

    g f = \n -> if n > 1 then n * f (n-1) else 1
    

    先给出结论: f能求阶乘的充分必要条件是g f == f(==表示等效,下同)

    下面不严谨地证明一下:

    • 必要性
      假设f能计算阶乘,那么将g应用于f可得一个新的函数g f, 即\n -> if n > 1 then n * f (n-1) else 1, ,f能计算阶乘,由阶乘的定义, g f必然也能计算阶乘,也就是g f == f

    • 充分性
      如果g f == f, 那么通过代换可以得到f == \n -> if n > 1 then n * f (n-1) else 1,这就是我们在上面给出的阶乘的递归定义形式,可以确定这样的f是能计算出阶乘的,通过数学归纳法可以证明

    综上, 可以知道g f == f是f能计算阶乘的充分必要条件

    那么问题就变成了"求方程g f == f的解"

    很显然f应该是一个关于g的函数,那么Y组合子其实就是这个函数: f == Y g

    但是具体怎么求这个解就太难了,作为民科的我只能利用前辈们留下的结论自己慢慢凑

    f应该是gen gen这样的形式,gen满足

    gen = \x -> g (x x)
    

    于是gen gen = g gen gen

    这样就找到了g的不动点

    现在我们开始构造Y组合子:
    由上面的讨论可以知道Y g == f == gen gen == g gen gen

    Y g = g gen gen
    

    Y g = gen gen
    

    Y g = (\x -> g (x x)) (\x -> g (x x))
    

    由此便得到了Y组合子

    相关文章

      网友评论

        本文标题:Y组合子

        本文链接:https://www.haomeiwen.com/subject/wlyroxtx.html