理解函数式编程中的函数组合--Monoids(二)

时间  2021-03-08 标签 html git github 编程 数组 app dom 编程语言 ide 函数式编程

使用函数式语言来创建领域模型--类型组合
理解函数式编程语言中的组合--前言(一)html

理解函数式编程中的函数组合--Monoids(二)

继上篇文章引出《范畴论》以后，我准备经过几篇文章，来介绍函数式编程语言中的若干"行话"，例如Functor, Applicative, Monad。若是给这些名字一个通俗的名称，我以为Combinator（组合子)比较形象一些，组合子能够将函数组合起来。我在一篇文章中还看到过一个另外一个通俗的说法--“胶水函数”，简而言之就是若是两个函数与不可以直接组合，那么就能够经过一种像胶水同样的函数，把两个函数粘接起来，从而达到组合函数的目的。git

在正式讲解这些概念以前，我想提一下“行话”这一现象，其实不光是函数式编程领域，OO设计里也有很多“行话”或者说“术语“，例如，”依赖注入“， ”多态“， ”桥接模式“，这些词你们听着都不陌生，源于你们对OO的长期实践。可是若是摒弃偏见，理解并灵活应用这些概念并非一蹴而就的。有时候你以为简单，只是由于更熟悉而已。github

这篇文章为你们介绍《范畴论》里的一个基础概念-Monoids（注意，不是Monad)。另外本文的例子都经过TypeScript来描述，另外本文的术语都会保持英文名称，由于这些术语翻译为汉语价值不大，另外保持英文名称也方便你们搜索相关介绍。编程

Monoids

首先Monoids一词来源于数学家，翻译成中文没有任何意义，你不会从中文翻译里面获得任何关于Monoids含义的线索，若是非要给他一个中文翻译，我会翻译为”可聚合的事物"。当你理解了Monoids, 你就会发如今生活中，到处存在着Monoids。 只不过数学家善于概括总结，给与了这一类事物一个确切的定义和相应的定律。数组

让咱们还原一下数学家发现这类事物的场景：app

可聚合的事物

1 + 2 = 3

这行数学运算能够描述为：两个“数字”经过“相加”运算，获得了一个结果，其结果任然为“数字”。dom

"a" + "b" = "ab"

上面这行运算能够描述为：两个"字符“经过”拼接“操做，获得了一个结果，其结果任然为”字符串“。
若是咱们将上面的这两个运算进一步泛化，就会获得类下面的模式(pattern):编程语言

  • 有两个事物
  • 两个事物可以经过一种组合方式将他们组合起来
  • 获得的事物跟以前的类型是一致的

这个规律可以运用在非数字或者字符串以外的其余事物上面吗？假如这种事物能够经过某种方式组合到一块儿，是否是就可以符合这一规律呢？
钱算不算？ide

type Money = {
  amount: number
};

const a: Money = { amount: 10.2 }
const b: Money = { amount: 2.8 }
const c: Money = { amount: a.amount + b.amount }

你若是熟悉DDD中提到的ValueObject，你能够将这模式应用在不少事物(ValueObject)上。
为何这个模式要强调组合以后的事物跟以前的类型是一致的(closure)？
由于你能够把这个模式推广到list上。
换句话说，若是一个二元运算若是返回的类型跟以前一致，就能够把这个操做符应用到一个list上，这个函数叫作reduce。函数式编程

[0, 2, 3, 4].reduce((acc, val) => acc + val);
["a", "b", "c", "d"].reduce((acc, val) => acc + val);

MapReduce你们应该都不陌生，为何叫Map? 由于须要将数据转化为Monoids, 为何要Reduce? 由于须要聚合数据。

结合律

实际上，只符合上面的模式，还不能称之为为Monoids, 确切的说叫作Magma。咱们小学数学都学习过结合律(Associative)，注意不是交换律(commutative)，例如：

(1 + 2) + 3 = 1 + (2 + 3) = 6

结合律说左右组合顺序不重要，获得的结果都是同样的，这必定律实际上对事物组合的运算符作出了限制，例如，针对数字运算，乘法符合结合律吗？

(1 * 2) * 3 = 1 * (2 * 3) = 6

答案是符合，那么除法和减法呢？

(1 - 2) - 3 != 1 - (2 - 3)
(1 % 2) % 3 != 1 % (2 % 3)

除法和减法不符合结合律，为何结合律这么重要？
由于当顺序不是问题的时候，并行计算和累加就显得垂手可得。由于执行顺序不是问题，你就能够把计算量分配到若干个机器上，而后累加结果。或者说今天计算了任务的30%，等明天启动任务的时候接着计算，而不须要从新计算整个数据集。

Identity元素

目前为止，获得的事物叫Semigroups，只差最后一个条件即可称之为Monoids。看下面的运算：

1 + 0 = 1
"a" + "" = "a"

有什么规律呢？针对数字和”加法“运算，任何数字加0，获得的结果跟以前同样。针对字符串和”加法“运算，任何字符串和”空字符串“拼接起来，获得的结果也跟以前同样。
对于数字和”乘法“运算来讲，0元素是1：

10 * 1 = 10

对于list而言，0元素是空list:

const a = [1, 2, 3]
const b: number[] = []
const c = [...a, ...b]

expect(c).toEqual(a);

数学家把这个相似于0同样的元素称之为identity元素，为何须要identity元素呢？
试想一下如何对一个空数组作reduce?

const a: number[] = [];
const result = a.reduce((acc, val) => acc + val);

这行代码会报错，reduce函数会抱怨你没有提供一个初始值，而这个不影响计算结果的初始值，实际就是identity元素。

const result = a.reduce((acc, val) => acc + val, 0);

大部分语言把提供初始值的函数称之为fold函数。不过fold的基础并非Monoids, 而是Catamorphisms，在此再也不细说。

Monoids定律

数学家将上面的三个规律定义为三个定律(laws):

  • 定律1 (Closure): 两个事物合并后总能获得相同类型的事物。
  • 定律2 (Associativity): 当组合一组事物时，组合的顺序不会影响结果(不是交换律的那种顺序）。
  • 定律3 (Identity element): 有一个0元素，任何事物跟0元素合并以后的结果不变。
    用数学家的话说，凡是符合上面三个定律的事物被称之为Monoids。符合定律1的叫作Magma, 同时符合定律1和定律2的称之为Semigroups。

用一句话归纳，Monoids是一个可以知足结合律，拥有Identity元素的二元运算。若是用代码来定义，大概以下：

interface Monoid<A> {
  readonly concat: (x: A, y: A) => A
  readonly empty: A
}

结合律则要知足下面的等式：

concat(x, concat(y, z)) = concat(concat(x, y), z)

上面用来描述Monoids的方式，在函数式编程语言里叫作type classes。严格来讲，TypeScript原生并不支持type classes，也不支持Higher Kinded Types(HKT), 上面的例子只是咱们用interface来模拟了一个type classes定义。
对于原生支持type classes的语言，例如Haskell, Monoid被定义为：

class Monoid m where  
    mempty :: m  
    mappend :: m -> m -> m  
    mconcat :: [m] -> m  
    mconcat = foldr mappend mempty

让咱们对这个定义作个简单分析，首先，m这种类型能够做为Monoid实例，只要符合：

  • mempty表明Identty 元素
  • mappend表明一个函数，接受两个相同类型的参数，而后返回一个类型也同样的值，能够理解为二元操做符
  • mconcat是一个函数，接受一组monoid值，而后聚合为一个值。它拥有一个默认实现，使用mappend操做符和mempty做为默认值，来fold一个列表

能够看出Haskell里面的的type class基本跟咱们在TypeScript里用interfaced定义出来的type class差很少，其实是不是原生支持Type classes，并不影响TypeScript能够做为一门函数式编程语言，相似的语言还有F#等。

函数也能够是Monoids

你们要明白《范畴论》的抽象程度很高，Monoid并不仅仅指咱们在文章中提到的字符串，数字之类，它能够是宇宙中的任何符合Monoids law的事物，这个事物也能够是函数。在TypeScript里，定义一个具备一个参数和返回类型的函数以下：

type func = <T1, T2>(x: T1) => T2

这个函数的签名以下：

T1 -> T2

在一个函数a->b中，若是b是monoid，那么这个函数也是一个monoid。也就是说函数签名相同的两个函数是能够组合的。相关过程我再也不证实，在Haskell里，这样的一条规则能够被描述为:

instance Monoid b => Monoid (a -> b)

特别的，当函数是一个monoid而且其输入类型和输出类型一致时，被称为Endomorphism monoid。

type func = <T>(x: T) => T

Monoid实战

若是说“数字”再加上"加法"操做符就是Monoid, 那么经过reduce就能够垂手可得的将一堆数字累加起来。让咱们看一个稍微复杂的例子，例如在购物车里，每一个商品均可以用下面的类型来表示：

type OrderLine = {
  id: number,
  name: string,
  quality: number,
  total: number
}

用命令式的思想来汇总总价，一般就是一个for循环，而后累加结果。不过，你应该想到，Monoid就是用来解决数据的累加问题，咱们能够经过reduce解决问题，你可能会想到这样作：

const total = orderLines.reduce((acc, val) => acc.total + val.total)

这行代码会报错，编译器会抱怨你在reduce函数里传入的高阶函数签名不符合要求，由于你传入的函数签名以下：

OrderLine -> OrderLine -> number

这个函数不符合Monoid定律，即返回类型不是一个OrderLine类型。Reduce指望你传入的函数类型签名为：

OrderLine -> OrderLine -> OrderLine

咱们只须要将这个高阶函数的返回类型也定义为OrderLine便可，即：

const addTwoOrderLines = (line1: OrderLine, line2: OrderLine): OrderLine => (
  {
    name: "total",
    quality: line1.quality + line2.quality,
    total: line1.total + line2.total
  }
)
const total = orderLines.reduce(addTwoOrderLines)

结束语

本文经过描述Monoid带你们进入函数式编程和《范畴论》的世界，为了进一步用代码实现这些例子，我在接下来的文章中还会引入fp-ts，从而经过TypeScript来展现一些实例。

联系我们 沪ICP备2021010478号-7