郁郁青青 长过千寻

函数式编程-要点记录

    笔记本
    1. Document
      1. 函数
      2. 纯函数
        1. 纯函数和副作用
        2. 坚持纯函数的原因
      3. 柯里化
      4. 代码组合
        1. pointfree
        2. 管理程序控制流的组合子
      5. Hindley-Milner 类型签名
      6. 容器
        1. Container
        2. Maybe
        3. Either
        4. IO
        5. Task
        6. 定律
      7. Monad
        1. 制作一个洋葱般的 Monad
        2. join
        3. chain
        4. 定律
      8. Applicative Functor
        1. lift
        2. 定律
    2. 本
    3. ほしのかけら
    4. Reference

什么是函数式编程functional programming：编程范例a programming paradigm；编码风格a coding style；心态a mindset。

函数式属于声明式代码：指明的是做什么，不是怎么做。

注意点：使用高阶函数；不遍历；避免数据突变。

代码中将用到例如 Ramda，Lodash, folktale 这些函数式库，它们作为工具来帮助非纯粹函数式语言的 JavaScript 模拟函数式语言的核心特性。

Document

函数

用一个函数把另一个函数包起来，通常使用这样的方法进行延迟执行，这样不仅多余，而且形成的“胶水”函数让我们很难爽快的对源函数进行改动。此外，为了让一个函数能做更多事情，就要保持它的命名普适抽象。下面代码列举了一些例子。

1
2
3
4
5
6
7
const getServerStuff = callback => ajaxCall(json => callback(json));

// 相当于
const getServerStuff = callback => ajaxCall(callback);

// 相当于
const getServerStuff = ajaxCall; // 何必呢

纯函数

纯函数和副作用

相同输入得到相同输出，而且没有可观察的副作用，这样的函数叫纯函数。

1
2
3
let c = [9, 9, 6];
c.splice(0, 1);
//=> [9] // splice 不是纯函数，因为它产生了可观察的副作用：原函数改变了

除了数据突变，引入一个全局变量也会让函数不纯，那么什么是副作用：计算过程中，系统状态变化了，或者与外部进行了可观察的交互。

如更改文件系统、发送请求、打印、DOM 查询等都是副作用，不用怀疑无副作用编程的可行性，因为我们不是要禁止副作用，只是我们怀疑副作用的行为，因此要学会如何控制它们。

坚持纯函数的原因

纯函数是数学上的函数，也是函数式编程的全部。

  • 可缓存性Cacheable，缓存值或者函数，甚至通过延迟执行把不纯函数变纯；
  • 可移植性/自文档化Portable/Self-Documenting，参数化让使用者知道函数的更多信息，不依赖环境（函数序列化并通过 socket 发送；在 web workers 运行）实现可移植性；
  • 可测试性Testable，输入，并断言输出；
  • 合理性Reasonable，纯函数的引用透明，通过等式推导让一段代码可以替换成他执行所得的结果；
  • 并行代码，纯函数不访问共享内存，也不会因副作用进入竞争态。

柯里化

柯里函数：每传递一个参数调用函数，就返回一个新函数处理剩余的函数。

1
2
3
4
5
6
7
8
9
10
11
12
// curry 的实现
function curry(func) {
	return function curried(...args) {
		if (args.length >= func.length) {
			return func.apply(this, args);
		} else {
			return function(...args2) {
				return curried.apply(this, args.concat(args2));
			}
		}
	};
}

下面对原生提供的迭代函数柯里化。

1
2
3
4
5
6
7
8
9
10
var match = curry((what, str) => str.match(what));
var replace = curry((what, replacement, str) => str.replace(what, replacement));
var filter = curry((f, ary) => ary.filter(f));
var map = curry((f, ary) => ary.map(f));
var slice = curry((start, end, xs) => xs.slice(start, end));

match(/\s+/g, "hello world")
var hasSpaces = match(/\s+/g)
hasSpaces("hello world")
filter(hasSpaces, ["tori_spelling", "tori amos"])

柯里化时，参数的顺序很重要，被柯里化后的函数具有了“预加载”的能力。和 curry 函数差不多，但是更自由的、不用被参数顺序所限制的函数是 partial 函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const partial = function(fn, ...partialArgs) {
  let args = partialArgs.slice(0);
  return function partialedFn(...extraArgs) {
    console.log(args)
    let arg = 0;
    let undefN = 0;
    for (let i = 0; arg < extraArgs.length && i < args.length; ++ i) {
      if (args[i] === undefined) {
        args[i] = extraArgs[arg];
        undefN = extraArgs[arg] == null ? undefN + 1 : undefN;
        ++ arg;
      }
    }
    if (undefN === 0) {
      return fn.apply(this, args);
    } else {
      return partialedFn;
    }
  }
}

代码组合

组合compose若干函数会搭建成一个新函数，执行它就向它投喂 1 个参数，这个参数会从最右边的若干函数开始向左执行。

被组合的函数都是一元函数，并且满足数学中的结合律。它带来的好处是灵活、易读和强表达性。下面用组合的三种方式完成一项工作。

1
2
3
4
5
6
7
8
9
10
var loudLastUpper = compose(exclaim, toUpperCase, head, reverse);

// 或
var last = compose(head, reverse);
var loudLastUpper = compose(exclaim, toUpperCase, last);

// 或
var last = compose(head, reverse);
var angry = compose(exclaim, toUpperCase);
var loudLastUpper = compose(angry, last);

柯里化、组合结合起来还能实现无点样式 point-free；在函数式代码里 debug 也利用 compose 插入用于 debug 的函数，如插入一个 trace 函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// compose 的实现
function compose(/* fns */) {
	let args = arguments;
	let start = args.length - 1;
	return function() {
		let i = start;
		let result = args[start].apply(this, arguments);
		while (i --) {
			result = args[i].call(this, result);
		}
		return result;
	};
}

// 或
function compose(...fns) {
	return value => reduce(fns.reverse(), (acc, fn) => fn(acc), value); // reduce 的妙用
}

// 或
const compose = (...funcs) => {
  return funcs.reverse().reduce((f, g) => (x) => f(g(x)));
}

pointfree

pointfree 和点记法 dot notation syntax 的作用一样，都是链式执行一系列操作，但前者的优势体现在构造函数时不用依赖实例以及线性的执行流程。

pointfree 也避免了函数调用的嵌套情况，例如f(g(n))的 pointfree 版本是compose(f, g)(n)。

管理程序控制流的组合子

编写利用组合的 point-free 风格的代码时，将对程序产生影响，例如：错误处理和调试；使用条件逻辑或按某种方式执行多个函数。

关于控制流程，就可以使用这些常见函数组合子：

  • identity
  • tap
    • tap 会忽略执行结果而返回入参；
    • 可以用在打印日志的功能上；
    • tap :: (a -> *) -> a -> a
1
2
3
const debug = R.tap(debugLog); // 部分实例代码演示
const isValidSsn = R.compose(debug, checkLengthSsn, debug, cleanInput);
isValidSsn('444-44-4444')
  • alternation（OR-组合子）
    • 入参是两个函数，如果第一个函数返回值未定义则返回第二个函数返回值；
1
2
3
4
5
6
const alt = function(func1, func2) { // alt 函子的实现
	return function(val) {
		return func1(val) || func2(val);
	}
};
const alt = R.curry((func1, func2, val) => func1(val) || func2(val)); // curry 与 lambda 表达式的版本
  • sequence（S-组合子）
    • 入参是许多函数，执行时将用一个值顺序执行这些函数，但是不返回值；
    • seq 组合子和 tap 组合子结合，可以嵌入函数组合间；
1
2
3
4
5
6
7
8
const seq = function(/*funcs*/) { // seq 组合子的实现
	const funcs = Array.prototype.slice.call(arguments);
	return function(val) {
		funcs.forEach(function(fn) {
			fn(val);
		});
	};
}
  • fork (join)
    • 入参是 3 个函数，执行时两个函数的执行结果作为第三个函数的入参并返回执行结果；
1
2
3
4
5
const fork = function(join, func1, func2) {
	return function(val) {
		return join(func1(val), func2(val));
	};
};

Hindley-Milner 类型签名

类型签名不但可以用于编译时检测，也是最好的文档，它在写纯函数时作用很大，下面是一个类型签名的例子。

1
2
3
4
5
6
var R = require('ramda');
var curry = R.curry;
//  reduce :: (b -> a -> b) -> b -> [a] -> b
var reduce = curry(function(f, x, xs) {
	return xs.reduce(f, x);
});

类型签名能推断函数实现，也带来了“自由定理”，下面是一个例子，说明了虽然实现不同，但是定理普适。

1
2
// filter :: (a -> Bool) -> [a] -> [a]
compose(map(f), filter(compose(p, f))) == compose(filter(p), map(f));

容器

Container

1
2
3
4
var Container = function(x) {
	this.__value = x;
}
Container.of = function(x) { return new Container(x); };
  • Container是个只有一个属性的对象，大多数情况下也只有一个；
  • __value不能是某个特定类型；
  • 直接用.__value获取数据有悖初衷，只能在 Container 内部获取。

要操作容器里的值就用 map，想要怎么操作值，自己定义传入 map 的参数 f 即可。

1
2
3
4
5
6
7
8
9
10
// (a -> b) -> Container a -> Container b
Container.prototype.map = function(f) {
	return Container.of(f(this.__value));
}

// pointfree
// map :: Functor f => (a -> b) -> f a -> f b
var map = curry((f, any_functor_at_all) => {
	return any_functor_at_all.map(f);
});

实现了函数 map 的容器就是函子 functor。

Maybe

Maybe这个 functor 调用 map 的时候先检查自己的值是否为空，然后调用传进来的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var Maybe = function(x) { // 纸糊的程序变壮了
	this.__value = x;
}
Maybe.of = function(x) {
	return new Maybe(x);
}
Maybe.prototype.isNothing = function() {
	return (this.__value === null || this.__value === undefined);
}
Maybe.prototype.map = function(f) {
	return this.isNothing() ? Maybe.of(null) : Maybe.of(f(this.__value));
}

// pointfree
// maybe :: b -> (a -> b) -> Maybe a -> b
const maybe = curry((x, f, m) => m.isNothing() ? x : f(m.__value););

函子 Maybe 的实现（folktale）

函子 Maybe 的实现：JavaScript 函数式编程指南 5.3.2

函子 Maybe 的实现（Mostly Adequate Guide to Functional Programming）

Either

错误抛出的时候，如果要收到一个返回值，使用Either，它还比Maybe能说明更多的事情。下面的例子里，省去了Either，Left和Right是Either的抽象类型的两个子类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var Left = function(x) {
	this.__value = x;
}
Left.of = function(x) {
	return new Left(x);
}
Left.prototype.map = function(f) {
	return this;
}
var Right = function(x) {
	this.__value = x;
}
Right.of = function(x) {
	return new Right(x);
}
Right.prototype.map = function(f) {
	return Right.of(f(this.__value));
}

// pointfree
const either = curry((f, g, e) => {
	switch(e.constructor) {
		case Left: return f(e.__value);
		case Right: return g(e.__value);
	}
});

此外，Either能做更多，它表示逻辑或，也体现了范畴学里的 coproduct 的概念，它还是标准的 sum type（不交并集，disjoint union of sets），等，但这里作为函数式的函子只用它处理错误。

Maybe 和 Either 通常被用来：

  • 隔离不纯；
  • 合并判空逻辑；
  • 避免异常；
  • 支持函数组合；
  • 中心化逻辑，用于提供默认值。

IO

把会产生副作用的函数包裹在另一个函数里，看起来就像个纯函数，它的输出值就定了（被包裹的函数），但是要使用这个副作用，就要依靠IO。

1
2
3
4
5
6
7
8
9
10
11
let IO = function(f) {
	this.__value = f;
};
IO.of = function(x) {
	return new IO(function() {
		return x;
	});
};
IO.prototype.map = function(f) {
	return new IO(_.compose(f, this.__value));
}

数据封闭在包裹着的函数 wrapper 中，终究会被释放出来的，释放者的责任就是把这个危险动作以公开的方式进行，通过__value()或unsafePerformIO()得到数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//  url :: IO String
var url = new IO(function() { return window.location.href; });

//  toPairs =  String -> [[String]]
var toPairs = compose(map(split('=')), split('&'));

//  params :: String -> [[String]]
var params = compose(toPairs, last, split('?'));

//  findParam :: String -> IO Maybe [String]
var findParam = function(key) {
  return map(compose(Maybe.of, filter(compose(eq(key), head)), params), url);
};
findParam("searchTerm").__value();

Task

异步任务

定律

同一律

1
compose(map(f), map(g)) === map(compose(f, g))

交换律

1
compose(F.of, f) === compose(map(f), F.of)

一点理论

Monad

制作一个洋葱般的 Monad

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//    hey :: String -> IO String
const hey = function(say) {
	return new IO(function() {
		return 'hey, ' + say;
	});
};
//    print :: String -> IO String
const print = function(x) {
	return new IO(function() {
		console.log(x);
		return x;
	});
}
//    show :: IO(IO String)
const show = compose(map(print), hey);
show('let me show').__value().__value(); // hey, let me show

每次 map 解析函子后又会多嵌套一层，要解决这个问题就需要有压扁能力的 monad，monad 实现了 join 或者 chain 方法。

join

join 会将两层或多层 Monadic 结构合并成一层。

Monadic 类型：是 Monad 的具体实现，Monad 为 Monadic 提供抽象接口。

1
2
3
4
5
6
Wrapper.prototype.join = function() {
	if (!(this.__value instanceof Wrapper) {
		return this;
	}
	return this.__value.join();
}

chain

chain 叫做>>=（读作 bind）或者 flatMap。

1
2
3
const chain = curry(function(f, m) {
	return compose(join, map(f))(m); // 或者 m.map(f).join()
})

chain-函数

定律

结合律

1
2
3
4
5
6
compose(join, map(join)) == compose(join, join)
//  M(M(Ma)) -----map(join)-----> M(Ma)
//           |                  |
//      join |                  | join
//           v                  v
//     M(Ma) -------join--------> Ma

同一律

1
2
3
4
5
6
7
8
compose(join, of) == compose(join, map(of)) == id
//  Ma -----of-----> M(Ma) <---map(of)--- Ma
//   \                 |                  /
//    -----            |             -----
//      id \           | join       / id
//          -----      |       -----
//               \     v      /
//                -->  Ma  <--

monad 来自一个叫“Kleisli 范畴”的范畴。

Applicative Functor

ap 函数能把一个 functor 的函数应用到另一个 functor 的值上。

1
2
3
4
5
Container.prototype.ap = function(other_container) {
	return other_container.map(this.__value);
}
// 例子：
Container.of(add).ap(Container.of(3)).ap(Container.of(4)) // Container {__value: 5}

lift

有了 ap 就可以让同类型的 functor 互相应用了，虽然 chain 也可以，但是这会让所有代码在前一个 monad 执行完后才执行。

上面的 ap 有普通函数调用的感觉，下面是 ap 的 pointfree 版本。

1
2
3
4
5
6
const liftA2 = curry(function(f, functor1, functor2) {
	return functor1.map(f).ap(functor2);
})
const liftA3 = curry(function(f, functor1, functor2, functor3) {
	return functor1.map(f).ap(functor2).ap(functor3);
})

定律

同一律

1
A.of(id).ap(v) == v

同态

1
2
3
A.of(f).ap(A.of(x)) == A.of(f(x))
// 所有计算都放在容器里（等式左边）== 现在外面进行计算然后再放到容器里（等式右边）
// 例子：Either.of(_.toUpper).ap(Either.of("oreos")) == Either.of(_.toUpper("ereos"))

互换

1
v.ap(A.of(x)) == A.of(function(f) { return f(x) }).ap(v)

组合

1
A.of(compose).ap(u).ap(v).ap(w) == u.ap(v.ap(w))

本

函数式编程入门经典；JavaScript函数式编程指南；

PHP：编程范式篇

冒号课堂

ほしのかけら

Clojure 入门教程

JIT 优化代码相关视频

函数式程序设计为什么至关重要

are-you-ok

mostly-adequate-guide-chinese

mostly-adequate-guide

图解 Monad

Folktale

JavaScript之js对象终极序列化(可序列化函数)

Ramda 函数库参考教程

Pointfree 编程风格指南：http://www.ruanyifeng.com/blog/2017/03/pointfree.html。

ramdajs：函数式编程工具，https://ramda.cn。

中 英 解释 来源
系统状态 system state 外部变量是系统状态的一部分 再次强调“纯”
认知负荷 cognitive load 引入了外部环境 同上
引用透明性 referential transparency 纯函数的好处 追求“纯”的理由
等式推导 equational reasoning “一对一”替换 同上
程序性执行的怪异行为 quirks of programmatic evaluation 手动执行代码，不考虑 qpe，像“等式推导” 同上
竞争态 race condition 并行代码
局部调用 partial application 传递函数一部分参数，减少大量样板代码 不仅仅是双关语／咖喱
样板代码 boilerplate code 同上
高阶函数 higher order function 参数或返回值为函数的函数 同上
可变的组合 variadic compose 函数可以组合，产出不同功能的函数 函数饲养
高级规范 high level specification 声明式代码
自由定理 free theorems 初识类型
编译时检测 compile time checks 同上
函数性 functionally 同上
多态性 polymorphism 同上
可能性范围的缩小 narrowing of possibility 同上
parametricity 同上
类型约束 type constraints 获取信息功能、限制作用范围 类型约束
点记法 dot notation syntax 足够函数式的方法 薛定谔的 Maybe
非纯执行函数 impure action 王老先生有作用
衍生函数 derived function 免费开瓶器
计算上的大和谐 computational harmony 同上
  1. 范畴论
    • 范畴的概念
      • “范畴就是使用箭头连接的物体。”，箭头即“态射（morphism）”。
    • 数学模型
      • 集合（所有成员） + 函数（变形关系）
    • 范畴与容器
      • 范畴想象成容器；Category类（容器），有一个值this.val和一种变形关系addOne，这里的范畴就是所有彼此差 1 的数字。
    • 范畴论与函数式编程的关系
      • 范畴论使用函数，伴随范畴论的发展，形成一整套函数运算方法，在计算机上实现后就是“函数式编程”；作为数学运算，函数的原始目的就是求值，因此要求函数要纯；函数像管道（pipe）。
  2. 函数的合成和柯里化
    • 函数的合成
      • 运算的过程中，合并中间步骤成一个函数，叫函数的合成（compose），f(x)和g(x)合成为f(g(x))；函数合成连接管道，数据穿过其中。
    • 柯里化
      • 合成的时候，单个参数函数很方便，但是函数多参时，就需要柯里化了；add(x, y)柯里化成add(y)(x)。
  3. 函子
    • 函子的概念
      • 范畴的运算是函子（Functor），它的变形关系作用于每个值，将当前容器变形成另一个容器；a--->f--->b 传入函子F变成Fa--->Ff--->Fb。
    • 函子的代码实现
      • 函子的标志是容器具有map方法，该方法将容器里每个值映射成另一容器；
      • functor 是实现了 map 函数并遵守一些特定规则的容器类型。
    • 利：抽象，对函数运用的抽象。
  4. of 方法
    • of 方法生成新容器，代替 new 命令（面向对象的标志）。
  5. Maybe 函子
    • 函数管道未必有处理空值的能力这一些列问题，为了解决它们，出现 Maybe 函子。
  6. Either 函子
    • Either 函子内部有左值（Left）和右值（Right），正常情况使用左值，如果不存在使用默认值右值，因此它能提供默认值、代替try...catch。
  7. ap 函子
    • 是 applicative 的缩写，部署 ap 方法后的函子就是ap 函子；
    • “ap 函子的意义在于，对于那些多参数的函数，就可以从多个容器之中取值，实现函子的链式操作。”。
  8. Monad 函子
    • “Monad 函子的作用是，总是返回一个单层的函子。它有一个flatMap方法，与map方法作用相同，唯一的区别是如果生成了一个嵌套函子，它会取出后者内部的值，保证返回的永远是一个单层的容器，不会出现嵌套的情况。”。

Reference

Functor, Applicative, 以及 Monad 的图片阐释

有哪些函数式编程在前端的实践经验？

函数式编程进阶：应用函子（网易云前端文章，同时作者赵祥涛创作大量函数式文章）

用 JS 代码完整解释 Monad（知乎，后台很久了）

前端中的 Monad（知乎，扫过一遍）

2021年 8月15日 星期日 01时08分45秒 CST - “世界上只有一种真正的英雄主义，那就是看清生活的真相之后，依然热爱生活。”，很热血，我忍不住翻成了代码：Hero = Compose(Repeat, Work, Sleep, Code);，这个函数或许可以鼓励生活中重复或者看不见意义的沮丧时刻，比如调用Hero('me');的时候，我也许就充满了英雄主义和燃起来了。

页阅读量:  ・  站访问量:  ・  站访客数: