Monoid in Functional Programming

Monoid 是什么?

我们先看两组例子:

1
2
3
4
5
6
7
8
9
// string concatenation
concat("foo","bar") == "foobar"
concat("", "latte") == concat("latte", "") == "latte"
concat("a", concat("b", "c")) == concat(concat("a", "b"), "c") == "abc"

// integer addition
3 + 5 == 8
0 + 42 == 42 + 0 == 42
1 + (2 + 3) == (1 + 2) + 3 == 6

我们可以发现,这两组操作其实有着相同的模式:

  • 有一个“零值”,记作zero,例子中分别是空串0
  • 有一个二元操作符,记作op,例子中分别是concat+
  • op满足结合律(associativity),即op(x, op(y, z)) == op(op(x, y), z)
  • 零值是单位元,即op(zero, x) == op(x, zero) == x

那么我们可以这样表示monoid:

1
2
3
4
trait Monoid[A] {
def op(m: A, n: A): A // 满足 op(x, op(y, z)) == op(op(x, y), z)
def zero: A // 满足 op(zero, x) == op(x, zero) == x
}

事实上,monoid是十分普遍的,比如:

  1. 乘法,单位元是1
  2. 布尔运算&&,单位元是true
  3. Integer的最大值max,单位元是Integer.MIN_VALUE
  4. List的连接,单位元是Nil(空列表)
  5. 自函数(参数与返回值的类型相同,即类型为A => A的函数)的组合compose,单位元是id

第5个并不是那么显而易见,实现如下:

1
2
3
4
5
6
def endoMonoid[A]: Monoid[A => A] = new Monoid[A => A] {
override def op(f: A => A, g: A => A): A => A =
g compose f // you can choose (g compose f) or (f compose g)
override def zero: A => A =
(x => x) // aka. id
}

那么monoid是什么?

一个可结合的二元操作符和一个单位元元素,构成一个monoid。

Monoid 有什么用?

Monoid是一种抽象,我们总是可以通过抽象来写出更加通用的代码:事实上,我们可以不关心monoid里的具体类型,直接写出可以对任何monoid都有效的代码。

计算的灵活性

事实上,对于monoid,我们并不关心计算发生的顺序,结合律保证了结果的一致:

1
2
3
4
5
6
7
8
// 1. foldRight
a + (b + (c + (d + (e + (f + (g + h))))))
// 2. foldLeft
((((((a + b) + c) + d) + e) + f) + g) + h
// 3. run in parallel
(a + b + c) + (d + e + f) + (g + h + 0)
// 4. fold like a binary tree
((a + b) + (c + d)) + ((e + f) + (g + h))

我们可以用任何顺序进行计算,甚至直接将每个任务分派给不同节点开始并行计算!

List的折叠

仔细观察,你会发现当我们对一个List进行fold操作(aka reduce in JavaScript/Python)时,传给fold的操作,恰好是monoid的opzero

1
2
3
4
5
6
7
List(1,2,3,4,5).foldLeft(0)((x, y) => x + y) == 
List(1,2,3,4,5).foldLeft(intAddtion.zero)(intAddtion.op)

val intAddtionMonoid: Monoid[Int] = new Monoid[Int] {
override def op(x: Int, y: Int): Int = x + y
override val zero: Int = 0
}

所以可以写一个更加通用的函数,接收一个List[A]和一个Monoid[A],并用这个monoid去折叠:

1
2
def concatenate[A](as: List[A], m: Monoid[A]): A = 
as.foldLeft(m.zero)(m.op)

甚至可以将List[A] map 成List[B]

1
2
def foldMap[A, B](as: List[A], m: Monoid[B])(f: A => B): B = 
as.foldLeft(m.zero)(b => a => m.op(b, f(a)))

通用折叠

事实上,对于所有的可折叠数据结构,我们都可以忽略其具体结构,直接用monoid进行折叠。

比如,我们有一个存放了Int的可折叠结构,计算其总和:

1
ints.foldRight(intAddtionMonoid.zero)(intAddtionMonoid.op)

我们并不关心,这个ints,究竟是List还是Array还是Vector,甚至可能是Tree或者Stream

对于这些结构,我们给它起个名字,叫做Foldable,我们可以抽象成这样:

1
2
3
4
5
6
7
trait Foldable[F[_]] {
def foldRight[A, B](as: F[A])(z: B)(f: (A, B) => B): B
def foldLeft[A, B](as: F[A])(z: B)(f: (B, A) => B): B
def foldMap[A, B](as: F[A])(f: A => B)(mb: Monoid[B]): B
def concatenate[A](as: F[A])(m: Monoid[A]): A =
foldLeft(as)(m.zero)(m.op)
}

PS:F[_]代表一个F是一个类型构造器,接收一个类型参数。比如,F[A]可以具象成List[Int]Stream[String]等等。

Monoid的组合

若类型AB是monoid,那么tuple类型(A, B)同样也是monoid。

我们只需要将A和B的opzero组合成tuple就可以了。

1
2
3
4
5
6
7
// am: Monoid[A], bm: Monoid[B]
def tupleMonoid[A, B]: Monoid[(A, B)] = new Monoid[(A, B)] {
override def op(t1: (A, B), t2: (A, B)): (A, B) = (t1, t2) match {
case ((a1, b1), (a2, b2)) => (am.op(a1, a2), bm.op(b1, b2))
}
override val zero: (A, B) = (am.zero, bm.zero)
}

闲谈

  • Monoid可以算作FP中最简单的纯代数(purely algebraic)结构。
  • 这种抽象的意义在于——和编程中的任何抽象一样——消除重复代码:抽出通用的结构,表达为抽象的类型和接口,从而消除重复。另外,这种抽象还能降低沟通成本。
  • Monoid中文名称叫做幺半群,十分拗口,所以全文都没有出现这个名字。
  • Monoid名称出自于抽象代数,我们也完全可以叫作AssociateWithIdentity,对我们编程也是毫无影响的。

References

  1. What monoids teach us about software

  2. All about monoids

  3. Categories Great and Small

  4. Chapter 10 of Functional Programming in Scala