Yifu's Blog
0%

Monoid in Functional Programming

Posted on Edited on In

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的op和zero：

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的组合

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

我们只需要将A和B的op和zero组合成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的例子

There are monoids for all the following:
· approximate sets such as the Bloom filter;
· set cardinality estimators, such as the HyperLogLog algorithm;
· vectors and vector operations like stochastic gradient descent;
· quantile estimators such as the t-digest
to name but a few.

– Chapter 9, Scala with Cats

闲谈

  • 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