资讯专栏INFORMATION COLUMN

Javascript 中 Y 组合子的推导

sourcenode / 2816人阅读

摘要:组合子是演算中的一个概念,是任意函数的不动点,在函数式编程中主要作用是提供一种匿名函数的递归方式。组合子如下本文将尽量通俗易懂的以实现匿名函数递归为导向,推导出这一式子。若将替换为,将导致组合子中的作为的参数被立即求值。

Y 组合子是 lambda 演算中的一个概念,是任意函数的不动点,在函数式编程中主要作用是 提供一种匿名函数的递归方式

Y 组合子如下:

$$ λf.(λx.f(x x))(λx.f(x x)) $$

本文将尽量通俗易懂的以 实现匿名函数递归 为导向,推导出这一式子。

一、简介 1. lambda 表达式简介

这部分通过 js 函数介绍 lambda 表达式,如果已经了解 lambda 演算 可以跳过这一部分。

了解一个新领域的最好方法是用已有知识进行类比。
我们可以把每一个 lambda 表达式解释为一个 js 函数:

"λ" 字符可以看作 function 声明,"."字符前为参数列表,"."字符后为函数体。

lambda 表达式不能被命名(赋值给变量),这也是为什么lambda演算需要引入 Y组合子的原因。

lambda 表达式只允许定义一个参数。

使用 lamda 表达式 javascript 箭头函数 javascript 函数表达式
函数 λx.x+1 x=>x+1; (function(x){return x+1;});
函数调用 (λx.x+1)4 (x=>x+1)(4); (function(x){return x+1;})(4);
2. 组合子与不动点

组合子对照 js 可以理解为:函数体内,没有使用外部变量

不动点是函数的一个特征:对于函数 $f(x)$,如果有变量  $a$ 使得  $f(a)=a$ 成立,则称 $a$ 是函数 $f$ 上的一个不动点

二、递归 1. 普通的递归

递归就是函数不断调用自身

一个最基本的调用自身的函数是这样的:

var f = () => f();
f();
//> f()
//> f()
//> ...

但这个函数仅仅是不断的调用自身,什么也没做。

一个正常的递归函数应该有一个状态,每次调用不断的递进状态,最终可以通过判断状态结束递归:

var f = p => judge(p) ? f(step(p)) : value;

// 再加上“计算”的步骤,这样这个函数才有价值:

var f = p => judge(p) ? calc(f(step(p)),p) : value;

一个具体的例子,计算阶乘的函数:

var factorial = n => n ? factorial(n-1)*n : 1;

调用:

factorial(4);
//=> 24
2. 让匿名函数递归

由于不能给函数命名,我们需要把函数作为参数传入一个高阶函数。这样,在高阶函数中,就可以使用 参数名 来引用函数,相当于变相地给函数命了名。

构造一个高阶函数invokeWithSelf,它接受一个函数作为参数,并让这个函数将自身作为参数调用其自身:

var invokeWithSelf = f => f(f);

当这个函数传入自身作为参数时

invokeWithSelf(invokeWithSelf);
//> (f=>f(f))(f=>f(f));
//> (f=>f(f))(f=>f(f));
//> ...

我们得到了一个匿名的无限递归函数,仿照上一节,我们可以把这个函数改造成可以使用的递归函数

//首先需要有一个参数来保存递归状态
var func = f => p => f(f)(p);

//加上状态改变和判断
var func = f => p => judge(p) ? f(f)(step(p)) : value;

//增加计算
var func = f => p => judge(p) ? calc(f(f)(step(p)),p) : value;

具体例子,计算阶乘的函数:

var func = f => n => n ? f(f)(n-1)*n : 1;

调用:

func(func)(4);
//> 24

匿名调用:

(f => n => n ? f(f)(n-1)*n : 1)(f => n => n ? f(f)(n-1)*n : 1)(4);
//> 24

现在我们得到了一个匿名的递归函数,不过它只能用来计算阶乘。为了将其通用,我们希望将 函数的具体计算方式与其递归的形式剥离开来。

三、推导 1. 解耦递归逻辑与计算逻辑,得到 javascript 中的 Y 组合子

对于刚才的函数func,我们尝试一步步将它分解成 计算逻辑递归逻辑 两部分

var func = (f => n => n ? f(f)(n-1)*n : 1)(f => n => n ? f(f)(n-1)*n : 1);

//调用:
func(4);
//> 24

开始化简 func

var func = n => {
    return (f => n => n ? f(f)(n-1)*n : 1)(f => n => n ? f(f)(n-1)*n : 1);
}

提取重复形式 f => n => n ? f(f)(n-1)*n : 1

var func = n => {
    var fa = f => n => n ? f(f)(n-1)*n : 1;
    return fa(fa);
};

//改写形式
var func = n => {
    var fa = f => {
        return n => n ? f(f)(n-1)*n : 1;
    };
    return fa(fa);
};

可以看出,其主要递归逻辑来自 f(f), 我们将这一部分解耦:

var func = n => {
    var fa = f => {
        var fb = n => f(f)(n);
        return n => n ? fb(n-1)*n : 1;
    };
    return fa(fa);
};

可以看到 返回值 不再需要 fc 接收的参数 f, 将返回值表达式具名, 以便提取出 fc, 分离逻辑:

var func = n => {
    var fa = f => {
        var fb = n => f(f)(n);
        var fc = n => n ? fb(n-1)*n : 1;
        return fc;
    };
    return fa(fa);
};

fc 还在依赖 fb, 将 fb 作为参数传入 fc, 解除 fcfb 的依赖:

var func = n => {
    var fa = f => {
        var fb = n => f(f)(n);
        var fc = fb => n => n ? fb(n-1)*n : 1;
        return fc(fb);
    };
    return fa(fa);
};

可以发现 fc 是计算逻辑部分,将 fc 提取出 fa

var func = n => {
    var fa = fc => f => {
        var fb = n => f(f)(n);
        return fc(fb);
    };
    var fc = fb => n => n ? fb(n-1)*n : 1;
    return fa(fc)(fa(fc));
};

构造一个函数 fd, 化简返回值的形式:

var func = n => {
    var fa = fc => f => {
        var fb = n => f(f)(n);
        return fc(fb);
    };
    var fc = fb => n => n ? fb(n-1)*n : 1;
    var fd = fa => fc => {
        return fa(fc)(fa(fc));
    }
    return fd(fa)(fc);
};

fa 带入 fd, 得到递归逻辑部分:

var func = n => {
    var fc = fb => n => n ? fb(n-1)*n : 1;
    var fd = fc => {
        var fa = fc => f => {
            var fb = n => f(f)(n);
            return fc(fb);
        };
        return fa(fc)(fa(fc));
    }
    return fd(fc);
};

//化简fd
var func = n => {
    var fc = fb => n => n ? fb(n-1)*n : 1;
    var fd = fc => {
        var fa = f => {
            var fb = n => f(f)(n);
            return fc(fb);
        };
        return fa(fa);
    }
    return fd(fc);
};

//化简fd
var func = n => {
    var fc = fb => n => n ? fb(n-1)*n : 1;
    var fd = fc => (f => fc(n => f(f)(n)))(f => fc(n => f(f)(n)));
    return fd(fc);
};

可以看到,两部分逻辑已经分离,可以得到 javascript 中的 Y 组合子:

var fn = fc;
var Y = fd;

将参数名替换一下,得到 Y 组合子与计算逻辑 fn

var fn = f => n => n ? f(n-1)*n : 1;
var Y = y => (x => y(n => x(x)(n)))(x => y(n => x(x)(n)));

调用测试:

Y(fn)(4);
//> 24
2. Y组合子与惰性求值

你可能注意到,刚才推导出的 Y 组合子形式与 其 λ 表达式的等价形式不一致

/*λ 表达式的等价形式*/
Y = y => (x => y(x(x)))(x => y(x(x)));

/*推导出的形式*/
Y = y => (x => y(n => x(x)(n)))(x => y(n => x(x)(n)));

对比不难发现 n => x(x)(n) 应化为 x(x),并且尝试直接使用等价形式时会发生爆栈

我们知道,上面的两种形式几乎是等价的,例如:

var print = str => console.log(str);

// 在一个参数的情况下,等价于:
var print = console.log;

但当它们作为函数参数时,其实有着略微不同:

//接收一个函数,但不使用它
var y = xn => {
    console.log("run y");
    return false ? xn(1) : 0;
};

//接收任意一个参数,返回一个函数
var x = n => {
    console.log("run x");
    return n1 => n1;
};

//调用,将参数直接传入
y(x(1));
//> "run x"
//> "run y"

//调用,将参数包裹在匿名函数中传入
y((n1)=>x(1)(n1));
//> "run y"

可以看到,在 y(x(1)) 的过程中,根本没有用到参数 x(1) 的值,但程序不在乎这一点,首先求出了 x(1) 的值;
第二个表达式中参数 x(1) 被“包裹”在一个匿名函数中,并没有运行。

对于函数参数的求值策略,不同的语言不相同:

在函数调用时,立即求值,称作“严格求值”(Eager evaluation), js / c++ / c# 均使用严格求值

在函数运行时动态地求值,称作“惰性求值”(Lazy evaluation), 以 Haskell 为代表的函数式编程语言默认使用

javascript 中使用的是严格求值,而 lambda 表达式中使用的是惰性求值。

若将 n => x(x)(n) 替换为 x(x),将导致 Y 组合子中的 x(x) 作为 y 的参数被立即求值。
由于右边部分中 x(x) 是一个无限递归的的式子,对它求值会使它不断地调用自身,最终导致堆栈溢出。

只进行左边部分的替换并不会导致无限调用:

Y = y => (x => y(n => x(x)(n)))(x => y(n => x(x)(n)));

//可化为
Y = y => (x => y(x(x))(x => y(n => x(x)(n)));

在计算这个式子时,会首先计算 参数 y 的值
完成后在计算左边的 x(x) 之前、会计算左边部分中 x 参数的值
而左边式子中 x 的值取决于右边部分的结果,右边返回值使左边的 x(x) 不再是无限递归。

四、总结

函数式编程的方法感觉着实有点烧脑,还没怎么实操过。

不过 js 真是厉害,什么编程方法都能用...

一直希望能够找到一种符合人们思考方式(至少符合我自己)的编程方法,让程序变得自然、易读、易写。不断尝试中。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/81345.html

相关文章

  • 函数式编程(二)

    摘要:代码组合在函数式编程中,通过将一个个功能单一的纯函数组合起来实现一个复杂的功能,就像乐高拼积木一样,这种称为函数组合代码组合。函数式编程就变成了运用不同的函子,解决实际问题。 高阶函数 满足以下两点的函数: 函数可以作为参数被传递 函数可以作为返回值输出 叫高阶函数,很显然js中的函数满足高阶函数的条件。 函数作为参数: function pow(x) { return x...

    lixiang 评论0 收藏0
  • JavaScript函数式编程入门经典

    摘要:函数式编程的定义函数是一段可以通过其名称被调用的代码。纯函数大多数函数式编程的好处来自于编写纯函数,纯函数是对给定的输入返回相同的输出的函数,并且纯函数不应依赖任何外部变量,也不应改变任何外部变量。 一个持续更新的github笔记,链接地址:Front-End-Basics,可以watch,也可以star。 此篇文章的地址:JavaScript函数式编程入门经典 正文开始 什么是函...

    silvertheo 评论0 收藏0
  • 编程范式与函数式编程

    摘要:声明式编程一种编程范式,与命令式编程相对立。常见的声明式编程语言有数据库查询语言,正则表达式逻辑编程函数式编程组态管理系统等。函数式编程,特别是纯函数式编程,尝试最小化状态带来的副作用,因此被认为是声明式的。 编程范式与函数式编程 一、编程范式的分类 常见的编程范式有:函数式编程、程序编程、面向对象编程、指令式编程等。在面向对象编程的世界,程序是一系列相互作用(方法)的对象(Class...

    noONE 评论0 收藏0
  • 一、C++11新特性:auto类型推导

    摘要:宋体关键字中的含义宋体不再是一个存储类型指示符如为纯粹类型指示符,而是一个新的类型指示符等是类型指示符来指示编译器,声明变量的类型必须由编译器在编译时期推导而得。 ...

    gityuan 评论0 收藏0
  • 基于JavaScript的一些函数式编程概念讲解

    摘要:以此类推,不定参数的方程也就被称为可变参数函数。一般来说,函数式编程中的值都被认为是不可变值。实现了函数的对象,即可以与其他对象进行对比判断是否属于同一类型,被称为。半群一个拥有,即将另一个对象转化为相同类型的函数,函数的对象称为。 原文地址译者的Github 系列文章地址本文原作者尚未全部完成,有兴趣的可以到原文或者译文地址关注更新 Functional Programming Ja...

    scola666 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<