函数式编程(Functional Programming)

982 阅读16分钟

基础理论

永久原文地址函数式编程期待你的star

  • 函数式编程(Functional Programming)其实相对于计算机的历史而言是一个非常古老的概念,甚至早于第一台计算机的诞生。函数式编程的基础模型来源于 λ (Lambda x=>x*2)演算,而 λ 演算并 非设计于在计算机上执行,它是在 20 世纪三十年代引入的一套用于研究函数定义、函数应用和递归的形式系统。
  • 函数式编程不是用函数来编程,也不是传统的面向过程编程。主旨在于将复杂的函数符合成简单的函数(计算理论,或者递归论, 或者拉姆达演算)。运算过程尽量写成一系列嵌套的函数调用
  • 真正的火热是随着React的高阶函数而逐步升温

范畴论Category Theory

  • 函数式编程是范畴论的数学分支是一门很复杂的数学, 认为世界上所有概念体系都可以抽象出一个个范畴
  • 彼此之间存在某种关系概念、事物、对象等等,都构成范畴。任何事物只要找出他们之间的关系,就能定义
  • 箭头表示范畴成员之间的关系,正式的名称叫做"态射" (morphism)。范畴论认为,同一个范畴的所有成员, 就是不同状态的"变形"(transformation)。通过"态射", 一个成员可以变形成另一个成员。

函数式编程常用核心概念

  • 纯函数
  • 偏应用函数、函数的柯里化
  • 函数组合
  • Point Free
  • 声明式与命令式代码
  • 惰性求值

纯函数

定义:对于相同的输入,永远会得到相同的输出,而且没有任 何可观察的副作用,也不依赖外部环境的状态。

var xs = [1,2,3,4,5];
// Array.slice是纯函数,因为它没有副作用,对于固定的 输入,输出总是固定的

xs.slice(0,3); // [1,2,3]
xs.slice(0,3); // [1,2,3]

优点:

import _ from 'lodash';
var sin = _.memorize(x => Math.sin(x));

// 第一次计算的时候会稍慢一点
var a = sin(1);

// 第二次有了缓存,速度极快
var b = sin(1);

// 纯函数不仅可以有效降低系统的复杂度,还有很多很棒的特性,比如可缓存性

缺点:

//不纯的
var min = 18;
var checkAge = age => age > min;

//纯的,这很函数式
var checkAge = age => age > 18;

// 在不纯的版本中,checkAge不仅取决于age还有外部依赖的变量min。
// 纯的 checkAge 把关键数字18硬编码在函数内部,扩展性比较差,柯里化优雅的函数式解决。

纯度和幂等性

幂等性是指执行无数次后还具有相同的效果,同一的参 数运行一次函数应该与连续两次结果一致。幂等性在函 数式编程中与纯度相关,但有不一致。

Math.abs(Math.abs(-42))

偏应用函数

  • 传递给函数一部分参数来调用它,让它返回一个函数去处理剩下的参数。
  • 偏函数之所以“偏”,在就在于其只能处理那些能与至少 一个case语句匹配的输入,而不能处理所有可能的输入
// 带一个函数参数 和 该函数的部分参数
const partial = (f, ...args) =>
(...moreArgs) => f(...args, ...moreArgs)

const add3 = (a, b, c) => a + b + c
// 偏应用 `2` 和 `3` 到 `add3` 给你一个单参数的函数

const fivePlus = partial(add3, 2, 3)
console.log(fivePlus(4)) // 9


//用bind来实现
const add1More = add3.bind(null, 2, 3)
console.log(add1More(4)) // 9

函数的柯里化

  • 柯里化(Curried) 通过偏应用函数实现。
  • 传递给函数一部分参数来调用它,让它返回一个函数去 处理剩下的参数
// 柯里化之前 
function add(x, y) {
  return x + y; 
}
add(1, 2) // 3

// 柯里化之后 
function addX(y) {
  return function (x) {
    return x + y;
  }; 
}
addX(2)(1) // 3

// bind实现柯里化
function foo(p1, p2) {
  this.val = p1 + p2; 
}
var bar = foo.bind(null, "p1");
var baz = new bar("p2");
console.log(baz.val); // p1p2

事实上柯里化是一种“预加载”函数的方法,通过传递较少的参数, 得到一个已经记住了这些参数的新函数,某种意义上讲,这是一种 对参数的“缓存”,是一种非常高效的编写函数的方法

函数组合

为了解决函数嵌套的问题,我们需要用到“函数组合”,让多个函数像拼积木一样

const compose = (f, g) => (x => f(g(x)));

var first = arr => arr[0];

var reverse = arr => arr.reverse();

var last = compose(first, reverse);
console.log(last([1,2,3,4,5])); // 5

Point Free

把一些对象自带的方法转化成纯函数,不要命名转瞬即逝的中间变量。

const compose = (f, g) => (x => f(g(x)));

var toUpperCase = word => word.toUpperCase();

var split = x => (str => str.split(x));

var f = compose(split(' '), toUpperCase);
console.log(f("abcd aaa"));// [ 'ABCD', 'AAA' ]

这种风格能够帮助我们减少不必要的命名,让代码保持简洁和通用。

声明式与命令式代码

命令式代码的意思就是,我们通过编写一条又一条指令去让计算 机执行一些动作,这其中一般都会涉及到很多繁杂的细节。而声明式就要优雅很多了,我们通过写表达式的方式来声明我们想干什么,而不是通过一步一步的指示。

// 命令式
let ceoList = [];
for(var i = 0; i < companies.length; i++)
  ceoList.push(companies[i].CEO)
}
// 声明式
let ceoList = companies.map(c => c.CEO);

惰性求值、惰性函数

惰性函数很好理解,假如同一个函数被大量范围,并且这个函数内部又有许多判断来来检测函数,这样对于一个调用会浪费时间和浏览器资源,所有当第一次判断完成后,直接把这个函数改写,不在需要判断。

// 根据浏览器环境,执行不同的功能

// 普通写法
function normalCreate() {
  if (isChrome()) {
    console.log('normal create in chrome');
  } else {
    console.log('normal create in other browser');
  }
}
normalCreate();
normalCreate();

// 惰性函数写法
function lazyLoadCreate () {
  console.log('first creating'); //  pos-1
  if (isChrome()) {
    lazyLoadCreate = function () {
      console.log('create function in chrome');
    }
  } else {
    lazyLoadCreate = function () {
      console.log('create function in other browser');
    }
  }
  return lazyLoadCreate();
}

lazyLoadCreate();
lazyLoadCreate();

函数式编程-更加专业的术语

  • 高阶函数
  • 尾调用优化PTC
  • 闭包
  • 容器、Functor
  • 错误处理、Either、AP
  • IO
  • Monad

高阶函数

函数当参数,把传入的函数做一个封装,然后返回这个封装 函数,达到更高程度的抽象。

var add = function(a, b){
  return a + b;
};

function math(func,array){
  return func(array[0], array[1]);
}
math(add,[1,2]); // 3

尾调用优化

指函数内部的最后一个动作是函数调用。该调用的返回值,直接返回给函数。。 函数调用自身,称为递归。如果尾调用自身,就称为尾递归。递归需要保存大量的调用记录,很容易发生栈溢出错误,如果使用尾递归优化,将递归变为循环,那么只需要保存一个调用记录,这样就不会发生栈溢出错误了。

// 普通递归
function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

// 尾递归
function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

传统递归

普通递归时,内存需要记录调用的堆栈所出 的深度和位置信息。在最底层计算返回值, 再根据记录的信息,跳回上一层级计算, 然后再跳回更高一层,依次运行,直到最外层的调用函数。在cpu计算和内存会消耗很多,而且当深度过大时,会出现堆栈溢出

function sum(n){ 
  if (n === 1) return 1;
  return n + sum(n - 1);
}

// 执行过程
// sum(5)
// (5 + sum(4))
// (5 + (4 + sum(3)))
// (5 + (4 + (3 + sum(2))))
// (5 + (4 + (3 + (2 + sum(1)))))
// (5 + (4 + (3 + (2 + 1))))
// (5 + (4 + (3 + 3)))
// (5 + (4 + 6))
// (5 + 10)
// 15

细数尾递归

function sum(x, total) {
  if (x === 1) {
    return x + total; 
  }
  return sum(x - 1, x + total);
}

// 执行过程
// sum(5, 0)
// sum(4, 5)
// sum(3, 9)
// sum(2, 12)
// sum(1, 14)
// 15

整个计算过程是线性的,调用一次sum(x, total)后,会进入下一个栈,相关的数据信息和 跟随进入,不再放在堆栈上保存。当计算完最后的值之后,直接返回到最上层的 sum(5,0)。这能有效的防止堆栈溢出。

注意

  • 尾递归的判断标准是函数运行【最后一步】是否调用自身, 而不是 是否在函数的【最后一行】调用自身, 最后一行调用其他函数 并返回叫尾调用。
  • 按道理尾递归调用调用栈永远都是更新当前的栈帧而已,这 样就完全避免了爆栈的危险。但是现如今的浏览器并未完全支持。原因有二 1在引擎层面消除递归是一个隐式的行为,开发者意识不到。2堆栈信息丢失了 开发者难已调试。

闭包

如下例子,虽然外层的 makePowerFn 函数执行完毕,栈上的调用 帧被释放,但是堆上的作用域并不被释放,因此 power 依旧可以 被 powerFn 函数访问,这样就形成了闭包

function makePowerFn(power) {
  function powerFn(base) {
    return Math.pow(base, power);
  }
  return powerFn;
}
var square = makePowerFn(2);
square(3); // 9

范畴与容器

  1. 我们可以把”范畴”想象成是一个容器,里面包含两样东西。值 (value)、值的变形关系,也就是函数。

  2. 范畴论使用函数,表达范畴之间的关系。

  3. 伴随着范畴论的发展,就发展出一整套函数的运算方法。这套方法 起初只用于数学运算,后来有人将它在计算机上实现了,就变成了今 天的”函数式编程"。

  4. 本质上,函数式编程只是范畴论的运算方法,跟数理逻辑、微积分、 行列式是同一类东西,都是数学方法,只是碰巧它能用来写程序。为什么函数式编程要求函数必须是纯的,不能有副作用?因为它是一种数学运算,原始目的就是求值,不做其他事情,否则就无法满足函数运算法则了。

  5. 函数不仅可以用于同一个范畴之中值的转换,还可以用于将一个范畴转成另一个范畴。这就涉及到了函子(Functor)

  6. 函子是函数式编程里面最重要的数据类型,也是基本的运算 单位和功能单位。它首先是一种范畴,也就是说,是一个容器,包含了值和变形关系。比较特殊的是,它的变形关系可 以依次作用于每一个值,将当前容器变形成另一个容器。

Functor(函子)

  1. $(...) 返回的对象并不是一个原生的 DOM 对象,而是对于原生对象的一种封装,这在某种意义上就是一个“容器”(但它并不函数式)

  2. Functor(函子)遵守一些特定规则的容器类型

  3. Functor 是一个对于函数调用的抽象,我们赋予容器自己去调用函数的能力。把东西装进一个容器,只留出一个接口 map 给容器外的函数,map一个函数时,我们让容器自己来运行这个函数, 这样容器就可以自由地选择何时何地如何操作这个函数,以致于 拥有惰性求值、错误处理、异步调用等等非常牛掰的特性

var Container = function(x) {
  this.__value = x; 
}

//函数式编程一般约定,函子有一个of方法
Container.of = x => new Container(x);

//一般约定,函子的标志就是容器具有map方法。该方法将容器 里面的每一个值,映射到另一个容器。
Container.prototype.map = function(f) {
  return Container.of(f(this.__value))
}

Container.of(3)
  .map(x => x + 1) // 结果 Container(4)
  .map(x => 'Result is ' + x); // Container('Result is 4')

ES6写法

class Functor {
  constructor(val) {
    this.val = val;
  }
  map(f) {
    return new Functor(f(this.val));
  }
}

(new Functor(2)).map(function (two) {
  return two + 2;
}); // Functor(4)

map

  • 上面代码中,Functor是一个函子,它的map方法接受函数f作为参数,然后返回一个新的函子,里面包含的值是被f处理过的 (f(this.val))
  • 一般约定,函子的标志就是容器具有map方法。该方法将容器里面的每一个值,映射到另一个容器
  • 上面的例子说明,函数式编程里面的运算,都是通过函子完成, 即运算不直接针对值,而是针对这个值的容器----函子。函子本 身具有对外接口(map方法),各种函数就是运算符,通过接口 接入容器,引发容器里面的值的变形
  • 因此,学习函数式编程,实际上就是学习函子的各种运算。由 于可以把运算方法封装在函子里面,所以又衍生出各种不同类 型的函子,有多少种运算,就有多少种函子。函数式编程就变 成了运用不同的函子,解决实际问题

Maybe 函子

函子接受各种函数,处理容器内部的值。这里就有一个问题,容器内部的值可能是一个 空值(比如null),而外部函数未必有处理空值的机制,如果传入空值,很可能就会出错

var Maybe = function(x) {
  this.__value = x;
}

Maybe.of = function(x) {
  return new Maybe(x);
}

Maybe.prototype.map = function(f) {
  return this.isNothing() ? Maybe.of(null) : Maybe.of(f(this.__value));
}

Maybe.prototype.isNothing = function() {
  return (this.__value === null || this.__value === undefined);
}

Either 函子

条件运算if...else是最常见的运算之一,函数式编程里面,使用 Either 函子表达。Either 函子内部有两个值:左值(Left)和右值(Right)。右值是正常情况下使用的值,左值是右值不存在时使用的默认值

class Either extends Functor {
  constructor(left, right) {
    this.left = left;
    this.right = right;
  }

  map(f) {
    return this.right ? 
      Either.of(this.left, f(this.right)) :
      Either.of(f(this.left), this.right);
  }
}

Either.of = function (left, right) {
  return new Either(left, right);


// 使用

var addOne = function (x) {
  return x + 1;
};

Either.of(5, 6).map(addOne);
// Either(5, 7);

Either.of(1, null).map(addOne);
// Either(2, null);
var Left = function(x) {
  this.__value = x;
}

var Right = function(x) {
  this.__value = x;
}

Left.of = function(x) {
  return new Left(x);
}

Right.of = function(x) {
  return new Right(x);
}

// 这里不同!!! 
Left.prototype.map = function(f) {
  return this;
}
Right.prototype.map = function(f) {
  return Right.of(f(this.__value));
}

Left 和 Right 唯一的区别就在于 map 方法的实 现,Right.map 的行为和我们之前提到的 map 函数一 样。但是 Left.map 就很不同了:它不会对容器做任何事情,只是很简单地把这个容器拿进来又扔出去。 这个特性意味着,Left 可以用来传递一个错误消息。

var getAge = user => 
  user.age ? Right.of(user.age) : Left.of("ERROR!");

getAge({name: 'stark', age: '21'})
  .map(age => 'Age is ' + age); //=> Right('Age is 21')

getAge({name: 'stark'}).map(age => 'Age is ' + age); //=> Left('ERROR!')

Left 可以让调用链中任意一环的错误立刻返回到调用链的尾部, 这给我们错误处理带来了很大的方便.

AP函子

函子里面包含的值,完全可能是函数。我们可以想象 这样一种情况,一个函子的值是数值,另一个函子的值 是函数。

function addTwo(x) {
  return x + 2;
}

const A = Functor.of(2);
const B = Functor.of(addTwo)

上面代码中,函子A内部的值是2,函子B内部的值是函数addTwo. 有时,我们想让函子B内部的函数,可以使用函子A内部的值进行运算。这时就需要用到 ap 函子。

ap 是 applicative(应用)的缩写。凡是部署了ap方法的函子,就是 ap 函子。

class Ap extends Functor {
  ap(F) {
    return Ap.of(this.val(F.val));
  }
}
// ap方法的参数不是函数,而是另一个函子。

// 上面例子可以写成下面的形式
Ap.of(addTwo).ap(Functor.of(2))
// Ap(4)

ap 函子的意义在于,对于那些多参数的函数,就可以从多个容器之中取值,实现函子的链式操作

function add(x) {
  return function (y) {
    return x + y;
  };
}

Ap.of(add).ap(Maybe.of(2)).ap(Maybe.of(3));
// Ap(5)

Monad 函子

Monad就是一种设计模式,表示将一个运算过程,通过函数拆解成互相连接的多个步骤。你只要提供下一步运算 所需的函数,整个运算就会自动进行下去

Monad 函子的作用是,总是返回一个单层的函子。它有一个flatMap方法,与map方法作用相同,唯一的区别是如果生成了一个嵌套函子,它会取出后者内部的值,保证返回的永远是一个单层的容器,不会出现嵌套的情况。

class Monad extends Functor {
  join() {
    return this.val;
  }
  flatMap(f) {
    return this.map(f).join();
  }
}

上面代码中,如果函数f返回的是一个函子,那么this.map(f)就会生成一个嵌套的函子。所以,join方法保证了flatMap方法总是返回一个单层的函子。这意味着嵌套的函子会被铺平(flatten)

IO 操作

真正的程序总要去接触肮脏的世界

Monad 函子的重要应用,就是实现 I/O (输入输出)操作。

I/O 是不纯的操作,普通的函数式编程没法做,这时就需要把 IO 操作写成Monad函子,通过它来完成。

var fs = require('fs');

var readFile = function(filename) {
  return new IO(function() {
    return fs.readFileSync(filename, 'utf-8');
  });
};

var print = function(x) {
  return new IO(function() {
    console.log(x);
    return x;
  });
}

上面代码中,读取文件和打印本身都是不纯的操作,但是readFileprint却是纯函数,因为它们总是返回 IO 函子。

如果 IO 函子是一个Monad,具有flatMap方法,那么我们就可以像下面这样调用这两个函数。

readFile('./user.txt')
  .flatMap(print)

这就是神奇的地方,上面的代码完成了不纯的操作,但是因为flatMap返回的还是一个 IO 函子,所以这个表达式是纯的。我们通过一个纯的表达式,完成带有副作用的操作,这就是 Monad 的作用。

由于返回还是 IO 函子,所以可以实现链式操作。因此,在大多数库里面,flatMap方法被改名成chain

var tail = function(x) {
  return new IO(function() {
    return x[x.length - 1];
  });
}

readFile('./user.txt')
  .flatMap(tail)
  .flatMap(print)

// 等同于
readFile('./user.txt')
  .chain(tail)
  .chain(print)

上面代码读取了文件user.txt,然后选取最后一行输出

总结

函数式编程不应被视为灵丹妙药。相反,它应 该被视为我们现有工具箱的一个很自然的补充 —— 它带来了更高的可组合性,灵活性以及容错 性。现代的JavaScript库已经开始尝试拥抱函数式编 程的概念以获取这些优势。Redux 作为一种 FLUX 的变种实现,核心理念也是状态机和函数式编程。

软件工程上讲『没有银弹』,函数式编程同样也不是万能的,它与烂大街的 OOP 一样,只是一种编程范式而已。很多实际应用中是很难用函数式去表达的,选择 OOP 亦或是其它编程范式或许会更简单。但我们要注意到函数式编程的核心理念, 如果说 OOP 降低复杂度是靠良好的封装、继承、多态以及接口定义的话,那么函 数式编程就是通过纯函数以及它们的组合、柯里化、Functor 等技术来降低系统复 杂度,而 React、Rxjs、Cycle.js 正是这种理念的代言。让我们一起拥抱函数式编程, 打开你程序的大门!

参考阮一峰-函数式编程

参考:@yuanzhijia