网络埋伏纪事

组合软件:6. 函子和范畴

网络埋伏纪事 · 2017-05-08翻译 · 1051阅读 原文链接

一个函子(Functor)是可以映射的某个事物。也就是说,函子是一个带有接口的容器,这个接口可以用于将一个函数应用到容器内的值。看到函子(functor)这个词时,就应该想到可映射

术语函子来自范畴论。在范畴论中,函子是范畴之间的映射。粗略地讲,范畴(Category)是一组事物,这里每个事物都可以是任何值。在代码中,函子有时候被表示为一个带有 .map() 方法的对象,这个 .map() 方法用来将一组值映射为另一组值。

函子为其内部的零到多个事物提供了一个盒子,以及一个映射接口。数组就是函子的一个不错的例子,但是很多其它类型的对象也可以被映射,包括单值对象、流、树、对象等等。

对集合(数组、流等)而言,.map() 通常会遍历集合,并且将指定函数应用到集合中的每个值,但是并非所有函子都可以迭代。

在 JavaScript 中,数组和 Promise 都是函子(.then() 是遵从函子定律的),不过有很多库也可以把各种其它事物转换为函子。

在 Haskell中,函子类型被定义为:

fmap :: (a -> b) -> f a -> f b

给出一个函数,该函数有一个参数 a,并返回一个 b 和一个有零到多个 a 在其中的函子:fmap 返回一个其中有零到多个 b 的盒子。f af b 位可以被读为 a 的函子和 b 的函子,意思是 f a 的盒子中有 af b 的盒子中有 b

使用函子很简单 - 只要调用 map() 即可:

const f = [1, 2, 3];
f.map(double); // [2, 4, 6]

函子定律

范畴有两个重要的属性:

  1. 恒等(Identity)
  2. 组合(Composition)

既然函子是范畴之间的映射,那么函子就必须遵从恒等和组合。二者在一起称为函子定律。

恒等

如果将恒等函数(x => x)传递给 f.map(),这里 f 是任何函子,那么结果应该等价于 f(即与 f 有相同含义):

const f = [1, 2, 3];
f.map(x => x); // [1, 2, 3]

组合

函子必须遵从组合定律:F.map(x => f(g(x))) 等同于 F.map(g).map(f)

函数组合就是将一个函数应用到另一个函数的结果上,例如,给出一个 x 和函数 f 以及 g,组合 (f ∘ g)(x)(通常简写为 f ∘ g -- (x) 被隐含)即指 f(g(x))

很多函数式编程术语都来自于范畴学,范畴学的精髓就是组合。范畴学是最开始很可怕,但是很简单,就像从跳水板跳下或者坐过山车一样。如下是范畴学基础的几个要点:

  • 一个范畴是对象以及对象之间箭头的一个集合(这里对象从字面上可以是指任何东西)。
  • 箭头被称为态射(morphism)。态射可以被认为就是函数,并且可以在代码中表示为函数。
  • 对于任何连接的对象组,a -> b -> c,必定有一个组合可以直接从 a -> c
  • 所有箭头都可以被表示为组合(即使它只是一个带有对象的恒等箭头的组合)。一个范畴中的所有对象都有恒等箭头。

假设有函数 g,该函数有一个参数 a,并返回 b;还有另一个函数 f,该函数有一个参数 b,并返回一个 c;那么就一定还有一个函数 h 代表 fg 的组合。所以,从 a -> c 的组合就是组合 f ∘ gfg 之后)。于是,h(x) = f(g(x))。函数组合是从右向左组合,而不是从左向右,这就是为什么 f ∘ g 经常被称 fg 之后。

组合是可结合的。这基本上意味着在组合多个函数(如果你觉得喜欢,也可以称为态射)时,不需要圆括号:

h∘(g∘f) = (h∘g)∘f = h∘g∘f

下面我们用 JavaScript 再看看组合:

给出一个函子 F

const F = [1, 2, 3];

如下的语句都是等同的:

F.map(x => f(g(x)));

// 等同于...

F.map(g).map(f);

自函子

自函子(endofunctor)是一个将范畴映射回自身的函子。

一个函子可以将一个范畴映射到另一个范畴:F a -> F b

一个自函子将一个范畴映射到同一个范畴:F a -> F a

这里 F 代表一种函子类型,a 代表一个范畴变量(意思是它可以表示任何范畴,包括一个集合或者一个同一类数据类型的所有可能值的范畴)。

一个单子(monad)就是一个自函子。记住:

> “一个单子(Monad)说白了不过就是自函子(Endofunctor)范畴上的一个幺半群(Monoid)而已,这有什么难以理解的?”

希望这个引证开始变得更好懂点。我们稍后将开始接触幺半群和单子。

创建你自己的函子

如下是一个函子的简单示例:

const Identity = value => ({  map: fn => Identity(fn(value))});

正如你所见,它满足函子定律:

// trace() 是一个让我们更容易检测内容的实用程序
const trace = x => {
  console.log(x);
  return x;
};

const u = Identity(2);

// 恒等定律
u.map(trace);             // 2
u.map(x => x).map(trace); // 2

const f = n => n + 1;
const g = n => n * 2;

// 组合定律
const r1 = u.map(x => f(g(x)));
const r2 = u.map(g).map(f);

r1.map(trace); // 5
r2.map(trace); // 5

现在我们就可以映射任何数据类型,就跟映射数据一样。很不错!

这跟在 JavaScript 中创建函子一样简单,不过 JavaScript 中缺失一些我们想要的数据类型的特性。下面我们就添加这些特性。如果 + 运算符可以对数字和字符串值都起作用,那是不是很酷?

要让这玩意儿生效的话,我们要做的就是实现 .valueOf() -- 这个方法也看起来像将值从函子中打开的一种简便方法:

const Identity = value => ({
  map: fn => Identity(fn(value)),

  valueOf: () => value,
});

const ints = (Identity(2) + Identity(4));
trace(ints); // 6

const hi = (Identity('h') + Identity('i'));
trace(hi); // "hi"

不错。不过,如果我们想在控制台中检测一个 Identity 实例又该怎么办呢?如果控制台中能说 "Identity(value)" 就很棒了,对吧。下面我们添加一个 .toString() 方法:

toString: () => `Identity(${value})`,

酷!我们可能还应该启用标准 JS 迭代协议。我们可以通过添加一个自定义的迭代器来实现:

  [Symbol.iterator]: () => {
    let first = true;
    return ({
      next: () => {
        if (first) {
          first = false;
          return ({
            done: false,
            value
          });
        }
        return ({
          done: true
        });
      }
    });
  },

现在下面的代码就可以运行了:

// [Symbol.iterator] 启用标准 JS 迭代
const arr = [6, 7, ...Identity(8)];
trace(arr); // [6, 7, 8]

如果我们想以 Identity(n) 为参数,并返回一个包含 n + 1n + 2 等等的 Identity 数组该怎么办?很简单,对吧?

const fRange = (
  start,
  end
) => Array.from(
  { length: end - start + 1 },
  (x, i) => Identity(i + start)
);

对,不过如果我们想让这可以作用于任何函子该怎么办?如果有一个规定说,一个数据类型的每个实例必须有一个对其构造器的引用,该怎么办?可以这样做:

const fRange = (
  start,
  end
) => Array.from(
  { length: end - start + 1 },

  // 将 `Identity` 变为 `start.constructor`
  (x, i) => start.constructor(i + start)
);

const range = fRange(Identity(2), 4);
range.map(x => x.map(trace)); // 2, 3, 4

如果我们想测试看看一个值是否是一个函子该怎么办?我们可以在 Identity 上添加一个静态方法来检测。这样做时,我们应该插入一个静态的 .toString()

Object.assign(Identity, {
  toString: () => 'Identity',
  is: x => typeof x.map === 'function'
});

下面我们把所有东西放在一起:

const Identity = value => ({
  map: fn => Identity(fn(value)),

  valueOf: () => value,

  toString: () => `Identity(${value})`,

  [Symbol.iterator]: () => {
    let first = true;
    return ({
      next: () => {
        if (first) {
          first = false;
          return ({
            done: false,
            value
          });
        }
        return ({
          done: true
        });
      }
    });
  },

  constructor: Identity
});

Object.assign(Identity, {
  toString: () => 'Identity',
  is: x => typeof x.map === 'function'
});

注意,要成为一个函子或者自函子,并不需要所有这些额外的东西。这只是为了方便。对于函子来说,所有我们所需要的就是符合函子定律的一个 .map() 接口。

为什么要用函子?

函子之所以牛叉,是有很多原因的。最重要的是,它们是一种抽象,我们可以用它们以作用于任何数据类型的方式来实现很多有用的事情。比如,如果我们想启动一连串操作,但是这些操作要排除掉函子内值为 undefined 或者 null 的,该怎么办呢?

// 创建断言
const exists = x => (x.valueOf() !== undefined && x.valueOf() !== null);

const ifExists = x => ({
  map: fn => exists(x) ? x.map(fn) : x
});

const add1 = n => n + 1;
const double = n => n * 2;

// 什么都没有发生...
ifExists(Identity(undefined)).map(trace);
// 依然是什么都没有发生...
ifExists(Identity(null)).map(trace);

// 42
ifExists(Identity(20))
  .map(add1)
  .map(double)
  .map(trace)
;

当然,函数式编程都是组合小函数,来创建更高层的抽象。如果我们想有一个可以作用域任何函子的通用映射该怎么办?通过这种方式,我们可以偏应用参数来创建新函数。

很简单。捡起你喜欢的自动柯里化,或者就使用之前的这个魔咒:

const curry = (
  f, arr = []
) => (...args) => (
  a => a.length === f.length ?
    f(...a) :
    curry(f, a)
)([...arr, ...args]);

现在我们可以定制 map:

const map = curry((fn, F) => F.map(fn));

const double = n => n * 2;

const mdouble = map(double);
mdouble(Identity(4)).map(trace); // 8

总结

函子是我们可以映射的事物。更具体地说,一个函数是从范畴到范畴的一个映射。一个函子甚至可以将一个范畴映射到同一范畴(即,自函子)。

范畴是对象的集合,对象之间有箭头。箭头代表态射(即函数,即组合)。范畴中的每个对象都有一个恒等态射(x => x)。对于任何对象链 A ->B -> C,必然存在组合 A -> C

函子是更高层的抽象,允许我们创建各种作用于任何数据类型的通用函数。

相关文章