ES6与Lambda演算

缘起

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

repository-tree

技术栈:

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

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

探索发现之旅

尾调用

尾调用是函数式编程的一个重要概念,其概念很简单理解,就是指一个函数的的尾部调用另一个函数。

例如:

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

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

尾调用的重要性在于它可以不在调用栈上面添加一个新的堆栈帧——而是更新它,如同迭代一般。尾递归因而具有两个特征:

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

而形式上只要是最后一个return语句返回的是一个完整函数,它就是尾递归

尾递归

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

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

factorial(6) // => 720

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

factorial(6) // => 720  

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

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

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

factorial(6, 1) // => 720

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

factorial(6, 1) // => 720  

Alt text

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

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

柯里化(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  

上面代码通过柯里化,将尾递归变为只接受单个参数的 factorial ,看似简洁了不少,得到了我们想要的factorial(6)独参函数,这又那么像lambda演算,在lambda演算中,所有的函数都是独参函数 。

让我们就用lambda表达式写出递归,使用具有递归效果的lambda表达式,将lambda表达式作为参数之一传入其自身。

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

factorial(factorial, 6) // => 720

// ES6
let factorial = (self, n) => n === 1 ? 1 : n * self(self, n - 1)

factorial(factorial, 6) // => 720  

是的,这么做还是太难看了,没人希望写一个阶乘函数还要传入其他参数。解决方案仍然是柯里化

let factorial = (self, n) => n === 1 ? 1 : n * self(self, n - 1)

// 构建 currying 工厂函数
let factory = f => n => f(f, n)

factorial = factory(factorial)

factorial(6) // => 720  

我们达到了目的,得到了独参函数factorial。就此停下探索嘛。No,我发现了黑魔法Lambda演算

Lambda演算

黑魔法Lambda演算

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

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

用Y组合子实现匿名递归函数

// 阶乘尾递归ES6 lambda Y组合子写法
const Y = f =>  
    (x => f(y => x(x)(y)))
    (x => f(y => x(x)(y)))

const factorial = Y(  
    f => (n) => n === 1 ? 1 : n * f(n - 1)
)

factorial(6) // => 720  

它不仅适用于阶乘函数的递归处理,任意递归工厂函数经过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  

德罗斯特效应

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

Alt text

总结

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

comments powered by Disqus