Scala with Cats 学习笔记3-Monoids和Semigroups

发表于 | 分类于 |

Abstract: 继续阅读 Scala with Cats， 开始学习 Monoids 和 Semigroups，其中文翻译分别为 幺半群（还有翻译成 独异点） 和 半群

数学背景

Monoids 和 Semigroups 实际上是严格的数学定义。

Group 群

G为非空集合，如果在G上定义的二元运算*，满足

  • （1）封闭性（Closure）：对于任意 $a，b∈G$，有 $a \times b∈G$
  • （2）结合律（Associativity）：对于任意 $a，b，c∈G$，有 $(a \times b) \times c=a \times (b \times c)$.
  • （3）幺元（Identity）：存在幺元 $e$，使得对于任意 $a∈G，e \times a=a \times e=a$
  • （4）逆元：对于任意 $a∈G$，存在逆元 $a^{-1}$，使得 $a^{-1} \times a=a \times a^{-1}=e$

则称 $(G，\times)$ 是群，简称 $G$ 是群。

SemiGroup 半群

如果仅满足封闭性和结合律，则称G是一个半群（Semigroup）；

Monoid 幺半群

如果仅满足封闭性、结合律并且有幺元，则称G是一个含幺半群（Monoid）。

举例

本书为了让读者理解这个数学概念举了很多例子，比如（整数，+） 就满足 封闭性，结合律和幺元的特性。

1
2
3
4
5
6
7
8
// 封闭性
2 + 1 // res0: Int = 3
// 幺元（0）
2 + 0 // res1: Int = 2
0 + 2 // res2: Int = 2
// 结合律
(1 + 2) + 3 // res3: Int = 6
1 + (2 + 3) // res4: Int = 6

（String 类型，拼接操作 ++）也满足这些特性：

1
2
3
4
5
6
7
8
// 封闭性
"One" ++ "two" // res9: String = Onetwo
// 幺元 （空字符串）
"" ++ "Hello" // res10: String = Hello
"Hello" ++ "" // res11: String = Hello
// 结合律
("One" ++ "Two") ++ "Three" // res12: String = OneTwoThree
"One" ++ ("Two" ++ "Three") // res13: String = OneTwoThree

Scala 精简定义

（建议阅读本书时先 Semigroup 再看 Monoid）
首先我们为了从程序角度理解这两个概念，我们可以通过 Scala 来描述一下这两个概念：

1
2
3
4
5
6
7
trait Semigroup[A] {
  def combine(x: A, y: A): A
}

trait Monoid[A] extends Semigroup[A] {
  def empty: A
}

这个只是接口，具体的类型和二元操作需要自行根据实际场景定义。比如整型和加法：

1
2
3
object IntSemiGroup extends Semigroup[Int] {
  def combine(a: Int, b: Int): Int = a + b
}

理论上我们需要验证我们的实现是不是符合半群的要求，比如减法并不符合结合律。

1
2
3
4
5
6
7
8
def associativeLaw[B](x: B, y: B, z: B)(implicit m: Monoid[B]): Boolean = {
  m.combine(x, m.combine(y, z)) ==
    m.combine(m.combine(x, y), z)
}
def identityLaw[B](x: B)(implicit m: Monoid[B]): Boolean = {
  (m.combine(x, m.empty) == x) &&
  (m.combine(m.empty, x) == x)
}

Boolean 案例

我们可以定义4个 Monoid： And，Or，Either，XNOR（异或非）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
implicit val booleanAndMonoid: Monoid[Boolean] =
  new Monoid[Boolean] {
    def combine(a: Boolean, b: Boolean) = a && b
    def empty = true
  }
implicit val booleanOrMonoid: Monoid[Boolean] =
  new Monoid[Boolean] {
    def combine(a: Boolean, b: Boolean) = a || b
    def empty = false
  }
implicit val booleanEitherMonoid: Monoid[Boolean] =
  new Monoid[Boolean] {
    def combine(a: Boolean, b: Boolean) =
      (a && !b) || (!a && b)

    def empty = false
  }
implicit val booleanXnorMonoid: Monoid[Boolean] =
  new Monoid[Boolean] {
    def combine(a: Boolean, b: Boolean) =
      (!a || b) && (a || !b)

    def empty = true
  }

为什么没有 异或 XOR？

Set 案例

Union: Monoid
Intersection：Semigroup
difference： None
symmetric difference： Monoid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
implicit def setUnionMonoid[A]: Monoid[Set[A]] =
  new Monoid[Set[A]] {
    def combine(a: Set[A], b: Set[A]) = a union b
    def empty = Set.empty[A]
  }
  
implicit def setIntersectionSemigroup[A]: Semigroup[Set[A]] =
  new Semigroup[Set[A]] {
    def combine(a: Set[A], b: Set[A]) =
      a intersect b
  }
  
implicit def symDiffMonoid[A]: Monoid[Set[A]] =
  new Monoid[Set[A]] {
    def combine(a: Set[A], b: Set[A]): Set[A] =
      (a diff b) union (b diff a)
    def empty: Set[A] = Set.empty
  }

Cats 的 Monoids 实现

1
2
import cats.Monoid
import cats.Semigroup

Object

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
27
28
29
30
import cats.Monoid
import cats.instances.string._ // for Monoid

Monoid[String].combine("Hi ", "there")
// res0: String = Hi there

Monoid[String].empty
// res1: String = ""

import cats.Semigroup

Semigroup[String].combine("Hi ", "there")
// res4: String = Hi there

import cats.Monoid
import cats.instances.int._ // for Monoid

Monoid[Int].combine(32, 10)
// res5: Int = 42

import cats.instances.option._ // for Monoid

val a = Option(22)
// a: Option[Int] = Some(22)

val b = Option(20)
// b: Option[Int] = Some(20)

Monoid[Option[Int]].combine(a, b)
// res6: Option[Int] = Some(42)

Syntax

1
2
3
4
5
6
7
8
9
10
import cats.instances.string._ // for Monoid
import cats.syntax.semigroup._ // for |+|

val stringResult = "Hi " |+| "there" |+| Monoid[String].empty
// stringResult: String = Hi there

import cats.instances.int._ // for Monoid

val intResult = 1 |+| 2 |+| Monoid[Int].empty
// intResult: Int = 3

使用案例

Monoid 是为某种类型提供的一种抽象的能力，这种能力是组合或相加。

SuperAdd

作为第一个案例，实现的功能很简单，就是实现一个 List 的累加，我们可以逐步提高这个累加功能的通用性：

累加 List[Int]

1
2
3
4
5
6
import cats.Monoid
import cats.instances.int._    // for Monoid
import cats.syntax.semigroup._ // for |+|

def add(items: List[Int]): Int =
  items.foldLeft(Monoid[Int].empty)(_ |+| _)

这里利用了 foldLeft 算子来实现这个功能，如果不用 Monoid，可以直接使用该算子def add(items: List[Int]): Int = items.foldLeft(0)(_ + _)。

累加 List[A]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import cats.Monoid
import cats.instances.int._    // for Monoid
import cats.syntax.semigroup._ // for |+|

def add[A](items: List[A])(implicit monoid: Monoid[A]): A =
  items.foldLeft(monoid.empty)(_ |+| _)
  
def add[A: Monoid](items: List[A]): A =
  items.foldLeft(Monoid[A].empty)(_ |+| _)
  
add(List(1, 2, 3))
// res9: Int = 6

add(List(Some(1), None, Some(2), None, Some(3)))
// res10: Option[Int] = Some(6)

如果 List 是一个泛型，这时候我们使用 Monoid 就有优势了，因为 Monoid 就是抽象了一种 combine 的能力，所以只要List 的泛型是 Monoid，就可以使用 Monoid 方法来处理合并。

累加自定义类

1
2
3
4
5
6
7
8
9
10
11
case class Order(totalCost: Double, quantity: Double)

implicit val monoid: Monoid[Order] = new Monoid[Order] {
  def combine(o1: Order, o2: Order) =
    Order(
      o1.totalCost + o2.totalCost,
      o1.quantity + o2.quantity
    )

  def empty = Order(0, 0)
}

上一节我们将 add 方法扩展到泛型，并且允许所有 Monoid 进行累加操作，对于基础类型，Cats 以及提供了Instance，对于自定义的类，需要自行实现 Monoid 的定义来处理 combine 操作。

Big Data

大数据合并结果：

  1. 计算访问人数，就是对 Int 的 Monoid 实例进行合并。
  2. 计算访问 unique 用户，就是对 Set[User] 的 Monoid 实例进行合并
  3. 计算 99% 相应时间，对 QTree 的 Monoid 实例进行合并

Distributed Systems

用于分布式系统一致性协议中，帮助进行不同节点数据的合并。

A particular class of data types support this reconciliation. These data types are called commutative replicated data types (CRDTs)

这里引出了一种数据类型：CRDTs，这就是一种具有 Monoid 实例的数据类型，具有合并的能力。我们在 Akka Distributed Data 的使用中会设计这种类型，帮助 Akka Cluster 实现数据的最终一致性。

总结

通过这个总结，我们用简短的语言再次描述一遍 Monoid 和 SemiGroups：

  1. 他们是 Type Classes 的一种
  2. 他们提供了合并或相加能力的抽象
  3. Monoid 和 SemiGroups 都提供了合并或相加操作
  4. Monoid 额外多一个空集或零元
  5. 使用 Cats Monoid 符合 Type Classes 的三部曲：Type Classes，Instance，Syntax or Object
  6. Cats Monoid 三部曲 cats.Monoid cats.instances.string._ cats.syntax.semigroup._
  7. 最佳用途：为依赖累加的方法提供抽象

所以当你遇到需要对某些数据类型进行累加或者合并的时候，就需要考虑一下是否引入 Monoid。