ES6函数与Lambda演算

es6-lambda

缘起

造了一个轮子,根据GitHub项目地址,生成项目目录树,直观的展现项目结构,以便于介绍项目。欢迎Star。

repository-tree

技术栈:

  • ES6
  • Vue.js
  • Webpack
  • Vuex
  • lodash
  • GitHub API

应用涉及到了展现目录树,实现方法不可或缺的一定是递归遍历。进而开启了我对lambda演算的探索发现之旅。

探索发现之旅

本次乘坐的 斐波那契 号邮轮,下面会涉及到一些 JavaScript 函数式编程中的一些基本概念。如果出现眩晕、恶心(kan bu dong)等不良反应,想下船的旅客纯属正常。常旅客请安心乘坐。

高阶函数

函数式编程中,接受函数作为参数,或者返回一个函数作为结果的函数通常就被称为高阶函数

mapfilterreduce 均属于高阶函数,高阶函数并不神秘,我们日常编程也会用到。

ES6 中的 map 例子

const arr = [1, 2, 3, 4, 5, 6]

const powArr = arr.map(v => v * v)

console.log(powArr) // [ 1, 4, 9, 16, 25, 36 ]

尾调用

尾调用(Tail Call)是函数式编程的一个重要概念,本身非常简单,是指某个函数的最后一步是调用另一个函数。尾调用即是一个作为返回值输出的高阶函数。

例如:

function f(x) {
  return g(x);
}

函数f()在尾部调用了函数g()

尾调用的重要性在于它可以不在调用栈上面添加一个新的堆栈帧,而是更新它,如同迭代一般。

尾递归

递归我们都不陌生,函数调用自身,称为递归。如果尾调用自身,就称为尾递归。通常被用于解释递归的程序是计算阶乘

// ES5
function factorial(n) {
  return n === 1 ? 1 : n * factorial(n - 1);
}

factorial(6) // => 720

// ES6
const factorial = n => n === 1 ? 1 : n * factorial(n - 1)

factorial(6) // => 720

递归非常耗费内存,因为需要同时保存成千上百个调用记录,很容易发生“栈溢出”错误(stack overflow)。但对于尾递归来说,由于只存在一个调用记录,所以永远不会发生“栈溢出”错误。对函数调用在尾位置的递归或互相递归的函数,由于函数自身调用次数很多,递归层级很深,尾递归优化则使原本 O(n) 的调用栈空间只需要 O(1)

尾递归因而具有两个特征:

  • 调用自身函数(Self-called);
  • 计算仅占用常量栈空间(Stack Space)。

再看看尾递归优化过的阶乘函数:

// ES5
function factorial(n, total) {
  return n === 1 ? total : factorial(n - 1, n * total);
}

factorial(6, 1) // => 720

// ES6
const factorial = (n, total) => n === 1 ? total : factorial(n - 1, n * total)

factorial(6, 1) // => 720

Alt text

在ES6中,只要使用尾递归,就不会发生栈溢出,相对节省内存。

上面的阶乘函数factorial,尾递归优化后的阶乘函数使用到了total这个中间变量,为了做到递归实现,确保最后一步只调用自身,把这个中间变量改写成函数的参数,这样做是有缺点的,为什么计算6的阶乘,还要传入两个变量6和1呢?解决方案就是柯里化

柯里化

柯里化(Currying),是把接受多个参数的函数变换成接受一个单一参数的函数,并且返回接受余下的参数而且返回结果的新函数的技术。

维基百科上的解释稍微有点绕了,简单来说,一个 currying 的函数只传递给函数一部分参数来调用它,让它返回一个闭包函数去处理剩下的参数。

// 阶乘尾递归优化写法
function currying(fn, n) {
  return function (m) {
    return fn.call(this, m, n);
  };
}

function tailFactorial(n, total) {
  if (n === 1) return total;
  return tailFactorial(n - 1, n * total);
}

const factorial = currying(tailFactorial, 1);

factorial(6) // => 720

下面看下 ES6 中的 柯里化:

const fact = (n, total) => n === 1 ? total : fact(n - 1, n * total)

const currying = f => n => m => f(m, n)

const factorial = currying(fact)(1)

factorial(6) // => 720

上面代码通过柯里化,将尾递归变为只接受单个参数的 factorial,得到了想要的factorial(6) 独参函数。

思考🤔,有木有更简单的方法实现上面独参尾递归栗子。当然有,利用ES6的函数新特性,函数默认值。

简单化问题:

const fact = (n, total = 1) => n === 1 ? total : fact(n - 1, n * total)

factorial(6) // => 720

Lambda表达式

JavaScript 中,Lambda表达式可以表示匿名函数。

恒等函数在 JavaScript 中的栗子:

// ES5
var f = function (x) {
  return x;
};

// ES6
const f = x => x

lambda表达式 来写是这样子的:λx.x

现在试着用lambda表达式写出递归(匿名函数递归),使用具有递归效果的lambda表达式,将lambda表达式作为参数之一传入其自身。

// ES5
function factorial(f, n) {
  return n === 1 ? 1 : n * f(f, n - 1)
}

factorial(factorial, 6) // => 720

// ES6
const factorial = (f, n) => n === 1 ? 1 : n * f(f, n - 1)

factorial(factorial, 6) // => 720

是的,这么做还是太难看了,没人希望写一个阶乘函数还要传入其他参数。解决方案仍然是柯里化。尾调用优化后的Lambda表达式递归:

const fact = (f, n ,total = 1) => n === 1 ? total : f(f, n - 1, n * total)

const currying = f => n => m => f(f, m ,n)

const factorial = currying(fact)()

factorial(6) // => 720

最终达到了目的,得到了独参函数factorial。

Lambda演算

Lambda演算中的所有函数都是匿名的,它们没有名称,它们只接受一个输入变量,即独参函数。

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

const invokeWithSelf = f => f(f)

用Lambda演算写出递归栗子:

const fact = f => (total = 1) => n => n === 1 ? total : f(f)(n * total)(n - 1)

const factorial = fact(fact)()

factorial(6) // => 720

黑魔法Y组合子

什么是Y组合子

Y = λf.(λx.f(xx))(λx.f(xx))

η-变换后的写法:

Y = λf.(λx.f(λv.x(x)(v)))(λx.f(λv.x(x)(v)))

用ES6箭头函数写出lambda演算Y组合子

const Y = f =>
    (x => f(v => x(x)(v)))
    (x => f(v => x(x)(v)))

Y组合子推导

以匿名函数递归开始

const fact = f => (total = 1) => n => n === 1 ? total : f(f)(n * total)(n - 1)

const factorial = fact(fact)()

factorial(6) // => 720

上面代码有一种模式被重复了三次, f(f) 两次, fact(fact) 一次。为了让代码更加 DRY ,尝试把 f(f) 解耦,当作参数传递。

const fact = f => 
  (g => (total = 1) => n => n === 1 ? total : g(n * total)(n - 1))(f(f))
  
const factorial = fact(fact)()

factorial(6) // => Maximum call stack size exceeded

当然上面代码运行结果会栈溢出,因为 JavaScript 中参数是 按值传递 的,形参必须先求值再作为实参传入函数,f(f) 作为参数传递时,会无限递归调用自身,导致栈溢出。这时候就需要用到 lambda 演算中的 η-变换。其原理是用到了惰性求值

η-变换

什么是η-变换?如果两个函数对于任意的输入都能产生相同的行为(即返回相同的结果),那么可以认为这两个函数是相等的。

lambda演算中有效的η-变换f = λx.(fx)

JavaScript中的η-变换f = x => f(x)

根据η-变换f(f) 作为函数代入,等价于 x => f(f)(x)

const fact = x => (f => (total = 1) => n => n === 1 ? total : f(n * total)(n - 1))(v => x(x)(v))

const factorial = fact(fact)()

factorial(6) // => 720

抽离共性

也许你也已经发现f => (total = 1) => n => n === 1 ? total : f(n * total)(n - 1)这就是柯里化后的递归方法。抽离出 fact 方法。

const fact = f => (total = 1) => n => n === 1 ? total : f(n * total)(n - 1)

const factorial = (x => fact((v => x(x)(v))))(x => fact((v => x(x)(v))))()

factorial(6) // => 720

构建Y

将具名 fact 函数变为匿名函数,构建一个工厂函数 Y,将 fact 函数作为参数传入。

const fact = f => (total = 1) => n => n === 1 ? total : f(n * total)(n - 1)

const Y = f => (x => f(v => x(x)(v)))
               (x => f(v => x(x)(v))) // 瞧,这不就是黑魔法Y组合子嘛

const factorial = Y(fact)()

factorial(6) // => 720

用Y组合子实现的匿名递归函数,它不仅适用于阶乘函数的递归处理,任意递归工厂函数经过Y函数后,都能得到真正的递归函数。


沿途风景

斐波那契数列

在数学上,斐波那契数列是以递归的方法定义的:

Alt text

用文字来说:就是斐波那契数列由0和1开始,之后的斐波那契系数就由之前的两数加和。

0,1,1,2,3,5,8,13,21,34,55,89,144,233......
Alt text

用JavaScript递归实现:

// 非尾递归
function fibonacci (n) {
  if ( n <= 1 ) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

fibonacci(6) // 13

使用尾调用优化的斐波那契数列

// 尾递归写法
function fibonacci (n , before , after) {
  if( n <= 1 ) return before;
  return fibonacci (n - 1, after, before + after);
}

fibonacci(6, 1, 2) // 13

使用lambda表达式的斐波那契数列

// ES6 lambda calculus
const Y = f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)))

const fibonacci = Y(
  f => (n) => n <= 1 ? 1 : f(n - 1) + f(n - 2)
)

fibonacci(6) // 13

德罗斯特效应

在生活中,德罗斯特效应(Droste effect)是递归的一种视觉形式,指一张图片部分与整张图片相同,一张有德罗斯特效应的图片,在其中会有一小部分是和整张图片类似。 而这小部分的图片中,又会有一小部分是和整张图片类似,以此类推,……。德罗斯特效应的名称是由于荷兰著名厂牌德罗斯特(Droste) 可可粉的包装盒,包装盒上的图案是一位护士拿着一个有杯子及纸盒的托盘,而杯子及纸盒上的图案和整张图片相同

Alt text

总结

我在做repository-tree项目的过程中学习到了很多之前没有接触过的东西,这也是我的初衷,想到各种各样的idea,去想办法实现它,过程中自然会提升自己的见识。以此篇博文激励自己继续学习下去。

参考

Lambda演算

JS 函数式编程指南

《ECMAScript 6 入门》

康托尔、哥德尔、图灵——永恒的金色对角线

comments powered by Disqus