yegao

yegao 查看完整档案

南京编辑  |  填写毕业院校vivo  |  front-end 编辑 www.github.com/yegao 编辑
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

个人动态

yegao 关注了收藏夹 · 2019-04-06

JS 数据结构与算法

关注 396

yegao 关注了收藏夹 · 2019-02-09

网络协议

关注 293

yegao 关注了专栏 · 2019-02-01

终身学习者

我要先坚持分享20年,大家来一起见证吧。

关注 40756

yegao 赞了文章 · 2019-01-05

Javascript 中 Y 组合子的推导

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+1x=>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 真是厉害,什么编程方法都能用...

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

查看原文

赞 10 收藏 5 评论 1

yegao 关注了专栏 · 2018-12-27

lcxfs1991

heyli's blog

关注 224

yegao 提出了问题 · 2018-12-26

在小程序中调用wx.login的时候,小程序内部到底做了什么事情,返回的code是怎么来的?

wx.login({
    success(res){
        console.log(res.code)
    }
}) 

小程序内部是否向哪个地方发送了appId了?为什么要先生成code然后再用code换取openId?

关注 2 回答 1

yegao 回答了问题 · 2018-12-20

解决typescript中的联合类型在运算符中引发的问题

好像是故意设计成这样的issues/29098

关注 3 回答 3

yegao 提出了问题 · 2018-12-19

解决typescript中的联合类型在运算符中引发的问题

以下是我在调试的时候写的代码,但是报错了

function fn (x: number | string,y: number | string){
    return x+y 
}

但是这样写没有问题

function fn (x: number,y: string){
    return x+y 
}

下面这种写法也会报错

function fn (x: number | string,y: number){
    return x+y 
}

我的理解里+运算是number和string共有的操作符号,为什么会报错呢?

关注 3 回答 3

yegao 回答了问题 · 2018-12-18

git 切换分支 忽略文件都不见了

我也发生了和你一样到问题,请问楼主解决了吗,怎么解决到?

关注 2 回答 1

yegao 提出了问题 · 2018-12-17

解决使用Object.defineProperty一个构造函数的prototype出现的奇怪的问题?

有一天我在看MDN上对defineProperty的时候,有一段没看明白,所以就在浏览器上跑了一段这样的代码做调试

var Foo = function(){};

Object.defineProperty(Foo.prototype,"x",{
    get(){
        return 3;
    }
});

var foo = new Foo();

console.dir(foo);

我期待的结果应该是

Foo {
    __proto__:{
        constructor: ƒ (),
        x: 3,
        __proto__: Object
    }
}

但是真正的结果是

Foo {
    x: 3,
    __proto__:{
        constructor: ƒ (),
        x: 3,
        __proto__: Object
    }
}

为什么在最外层就已经出现了x属性呢?求大神和老师解惑

关注 3 回答 1

认证与成就

  • 获得 2 次点赞
  • 获得 4 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 4 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2016-11-11
个人主页被 195 人浏览