阿凡达

未来可期

285篇博客

最新博客

最新资源下载

编辑推荐

网易数帆开源API网关与容器云项目，让云原生生产落地“多快好网易汪源：统一负载与多云环境的“开放姿态”，才是云原生网易数帆如何用 Kubernetes“原语”搞定云原生中间件快手打新挤爆券商系统，网易数帆推出券商稳定性保障方案探索智慧校园新模式，网易有数在教育行业的实践分享金融行业大数据治理之路——数据模型篇

不动点和Y算子

阿凡达2018-07-09 14:16
一:

对于编程了解或熟悉的人，对于函数的调用一定不会陌生。

假设有递归阶乘函数: n!
那我们采用scheme的编程语言实现 
(define (fact n)
    (if (= n 1)
        1
        (* n (fact (- n 1)))))

(fact 5); //120
如上，通过将函数名和函数体绑定，调用函数名来执行函数体。
那么，如果不能通过函数名调用函数体应该怎么办？ 
lambda算子是一种没有函数名却可以执行的函数。

二：
那么对于上述的递归阶乘函数：n! 
((lambda (n)
   ((lambda (fact)
            (fact fact n))
    (lambda (ft k)
      (if (= k 1)
          1
          (* k (ft ft (- k 1)))))))
 5)
为什么把自己通过参数传给自己了，可以实现上述的递归调用了？且lambda算子里的函数不是只接受一个参数，这不是和上述矛盾了？
lambda算子把自己通过参数传递给自己，从而实现函数的执行， 上述(ft k)是一个操作，它作为一个整体作为lambda的参数。解决上述问题需要理解不动点理论。

三：
1、不动点理论:
不动点：函数f(x)=x^2.对于某些点，有f(x) = x,这样的点称为不动点。 那么如何计算出函数的不动点？
2、高阶抽象函数的不动点
假定函数f，是阶乘计算函数，f(n)=(f n)=n!。若有F(f)=(F f)=f，对于函数((F f) n) = (f n),f是函数F的不动点。
lambda表达式可以为： 
    F = 
       (lambda (f)
           (lambda (n)
               (if (< n 2)
                    1
                    (* n (f (- n 1))))))
 上述是一个柯里化函数，当我们传递函数f给F的时候，由于f是不动点，F(f)=f,那么，上述要计算f，也就是计算出F的真正的不动点。
如何计算函数的不动点？
3、Y算子
Y算子：是一种高阶函数，它用于计算任意函数的不动点。
Y算子基础：假定对于函数f，存在不动点x，有f(x)=x，那么Y（f）=x。因此，f(Y(f))=Y(f),schema格式(f (Y f))=(Y f)这为Y算子。
Y算子的scheme的表达式： 
    (define Y
       (lambda (f)
           (let ((g (lambda (h)
                 (lambda (x) ((f (h h)) x)))))
               (g g))))
 验证：使Y作用于上述F可得： 
    (let ((f (Y (lambda (h)
                (lambda (n)
                  (if (< n 2) 1 (* n (h (- n 1)))))))))
       (display (f 5)))
//120
分析如下：
1、let赋值里面计算f，f=(Y F)。F函数如上面，在let之后，F的值被唯一确定。
2、将F作为Y的参数计算Y
3、在Y中需要计算g，g是一个lambda表达式(这个lambda表达式中有没有算出来的未知数)
4、Y返回的结果为(g g)，所以f=(g g)=(lambda (x) ((F (g g)) x))，有了f就可以计算(f 5)了
5、(f 5)=((F g g) 5)=((F f) 5),则f是不动点，产生了
6、(f 5)则需要计算的是((F (g g)) 5),而我们知道(g g)的展开结果，带入((F (lambda (x) (F (g g)) x)) 5),对于F计算。带入F则成为依次循环下去,直到n=1.
3.1：Y算子的推导
1、假设定义如下 
    (define f
        (lambda (n)
           (if (< n 2)
               1
               (* n (f (- n 1))))))
2、重复传入递归函数本身,避免自身引用的问题 
    (let ((g (lambda (h n)
           (if (< n 2) 1 (* n (h h (- n 1))))))) 
       (g g 10)

3、将上面的函数柯里化，转换为下面的函数。

    (let ((g (lambda (h)
           (lambda (n) 
             (if (< n 2) 1 (* n ((h h) (- n 1))))))))
       ((g g) 10))

4、将上面的函数转换为下面的样子。  

    (let ((g (lambda (h) 
           (lambda (n) 
             (let ((f (lambda (q n)
                        (if (< n 2) 1 (* n (q (- n 1)))))))
               (f (h h) n))))))
      (display ((g g) 10)))

5、再柯里化一遍。

    (let ((g (lambda (h)
           (lambda (n)
             (let ((f (lambda (q)
                        (lambda (n)
                          (if (< n 2) 1 (* n (q (- n 1))))))))
               ((f (h h)) n))))))
       (display ((g g) 10)))

上述获得Y算子。

本文来自网易实践者社区，经作者王海玲授权发布。

推荐博客