Monoids

Monoid 是我們將要介紹的第一個純粹的代數資料結構，僅由代數性質定義。

什麼是 Monoid？

Monoid 來自於數學，在 Category Theory 中，它意思為一個 category 只有一個 object，數學上的定義在這裡不太重要（詳細的說明可以看維基百科）。

首先我們來看一下連續字串的代數性質，foo + bar 會等於 foobar，而空字串 "" 在這裡面被稱為 identity element (單位元素)，如果我們用 (s + "") 或 ("" + s)，其結果都會是 s，

進一步來看，如果我們合併 3 個字串 (r + s + t)，其算子是具有 Associative property (結合律) 性質的，也就是說不管我們怎麼用括號分隔，((r + s) + t) 或 (r + (s + t))，其結果都相同，

相同的定律對數字也適用，例如 (x + y) + z 始終會等於 x + (y + z)，它的單位元素是 0，

而 && 或 || 同樣也具有結合律；

這種型態的代數性就稱為 Monoid，而 Monoid 定律會由下列項目組成：

某個型態 A。
有一個具有結合律的 function combine，它接受 2 個型態為 A 的參數，然後合併它們做為結果，combine(combine(x, y), z) == combine(x, combine(y, z))，其 x, y, z 的型態皆為 A。
有一個稱為 empty 的值，它是單位元素並能滿足以下操作，combine(x, empty) == x 和 combine(empty, x) == x，x 的型態為 A。

把這些用 Scala 表示的話程式長這樣，

trait Monoid[A]:
  def combine(a1: A, a2: A): A
  def empty: A

用字串來實作的話長這樣。

  val stringMonoid: Monoid[String] = new:
    def combine(a1: String, a2: String) = a1 + a2
    val empty = ""

無參數的 function 可以在實作時用 val 實作。

Exercise D22-1

來實作加、乘、AND 和 OR 操作吧！

val intAddition: Monoid[Int]
val intMultiplication: Monoid[Int]
val booleanAnd: Monoid[Boolean]
val booleanOr: Monoid[Boolean]

Exercise D22-2

用 Option 來實作 Monoid 介面。

def optionMonoid[A]: Monoid[Option[A]]

Monoid 就是能用一個相同型態二元操作 function 滿足結合律且有著單位元素的東西啦！

用 monoids folding List

Monoid 跟 List 有著相當緊密的關係，Scala 下的 Functional 資料結構 (2) 的 List 中我們有用到 2 個 function，foldLeft 和 foldRight，它們的 function 宣告長這樣，

def foldLeft[B](z: B)(op: (B, A) => B): B
def foldRight[B](z: B)(op: (A, B) => B): B

如果我們讓它們都變成同一個型態 A 呢？

def foldLeft(z: A)(op: (A, A) => A): A
def foldRight(z: A)(op: (A, A) => A): A

此時 Monoid 的組成相當適合這 2 個 function，假設我們有 List[String]，我們可以用 stringMonoid 的 combine 和 empty 來把這些字組合起來，

scala> val words = List("This", " ", "is", " ", "sparta")

scala> val foldLeftResult = words.foldLeft(stringMonoid.empty)(stringMonoid.combine)
val foldLeftResult: String = This is sparta

scala> val foldRightResult = words.foldRight(stringMonoid.empty)(stringMonoid.combine)
val foldRightResult: String = This is sparta

因為結合律的關係，Monoid 下的 foldLeft 和 foldRight 沒有太大區別，所以最後我們可以寫一個 function 來用 Monoid 摺 List，

def combineAll[A](as: List[A], m: Monoid[A]): A =
  as.foldLeft(m.empty)(m.combine)

但如果我們沒有該 List 型態的 Monoid 時要怎麼做呢？我們始終可以用 map function 來轉換任何東西！

Exercise D23-1

實作 foldMap。

def foldMap[A, B](as: List[A], m: Monoid[B])(f: A => B): B

關聯性和平行性

如果是 Monoid 的 foldLeft 和 foldRight，我們其實可以用平衡的方式來 fold List，這可以讓它更有效率且能支援平行化運算，

假設我們有 a, b, c, d，如果我們用 Monoid 來做 foldLeft 的話會是這樣，

combine(combine(combine(a, b), c), d)

但如果用平衡方式來做的話會這樣，

combine(combine(a, b), combine(c, d))

此時就可以對裡面 2 個 combine 平行化運算，因為它們是彼此獨立計算的，越平衡的樹在處理上會越有效率，可以想像成把 List 變成 二元平衡樹 (balanced binary tree)。

二元平衡樹中任意一個節點的左右子樹的高度相差不能大於 1 。

Exercise D23-2

用 indexedSeq 來實作平衡版本的 foldMap。

Scala 的 indexedSeq 在把 2 個 Seq 對半切時會更有效率，且也支持的 random access。

def foldMapV[A, B](as: IndexedSeq[A], m: Monoid[B])(f: A => B):

Monoid 的同態 (homomorphisms)

直接看例子吧！

"foo".length + "bar".length == ("foo" + "bar").length

左邊是整數的 Monoid，右邊是字串的 Monoid，而 length 這個 function 保留了 Monoid 結構，這個 function 就稱為 monoid homomorphisms，一個 monoid homomorphisms f 在 M 和 N 這 2 個 Monoid 之間會遵守以下定律：

M.combine(f(x), f(y)) == f(N.combine(x, y))

可摺疊的資料結構

之前有提到 Monoid 跟 List 有著相當緊密的關係，其實不管是 List、LazyList 或其它有用到 foldLeft 或 foldRight 的地方，我們並不在意摺的東西是什麼，配合 Monoid 的話，其實我們可以把摺的動作抽象成 Foldable 這個資料結構：

trait Foldable[F[_]]:

  extension[A] (as: F[A])
    def foldRight[B](acc: B)(f: (A, B) => B): B

    def foldLeft[B](acc: B)(f: (B, A) => B): B

    def foldMap[B](f: A => B)(using mb: Monoid[B]): B =
      as.foldRight(mb.empty)((a, b) => mb.combine(f(a), b))

    def combineAll(using ma: Monoid[A]): A =
      as.foldLeft(ma.empty)(ma.combine)

    def toList: List[A] =
      as.foldRight(List.empty[A])(_ :: _)

Functor[F[_]] 型態建構子的相關說明請參考能自由組合的解析器 Library (1) ；

extension 的說明請參考純粹的 functional 狀態 (2)；

Scala 3 加入了 contextual abstraction，概念很像 Scala 2 的 implicits，主要是在 function 中可以加入 using 關鍵字，把它變成具有上下文關係的參數 (context parameters)，在呼叫該 function 時，只要在程式中 given 一下，就能在不用給 using 參數的情況下使用它。
scala> trait Ord[T]:
  |   def compare(x: T, y: T): Int
  |   extension (x: T)
  |     def < (y: T) = compare(x, y) < 0
  |     def > (y: T) = compare(x, y) > 0
  |
  | given Ord[Int] with
  |   def compare(x: Int, y: Int) =
  |     if x < y then -1 else if x > y then +1 else 0

scala> def max[T](x: T, y: T)(using ord: Ord[T]): T =
  |   if ord.compare(x, y) < 0 then y else x

scala> val r = max(2, 3) // 調用 max 時並沒有給 ord 這個參數
val r: Int = 3

然後我們嘗試用 List 來實作 Foldable 吧！

object Foldable:

  given Foldable[List] with
    extension[A] (as: List[A])
      def foldRight[B](acc: B)(f: (A, B) => B): B =
        as.foldRight(acc)(f)

      def foldLeft[B](acc: B)(f: (B, A) => B): B =
        as.foldLeft(acc)(f)

配合 stringMonoid，我們就可以用 Foldable 做 foldMap。

scala> import Foldable.given
scala> given Monoid[String] = stringMonoid

scala> val foldedString = List(1, 2, 3).foldMap(_.toString)
val foldedString: String = 123

Monoids 的組合性

Monoid 最強大的地方在於它的組合性，如果 A 和 B 都是 Monoid，配對後的 tuple 型態 (A, B) 也是 Monoid。

Exercise D24-1

用以上的概念實作 productMonoid function 吧！

def productMonoid[A, B](ma: Monoid[A], mb: Monoid[B]): Monoid[(A, B)]

組裝更複雜的 Monoids

某些資料型態的 Monoid 能包含其他的 Monoid 進去，舉例來說，我們這裡有一個能合併 map 的 Monoid，

  def mapMergeMonoid[K, V](mv: Monoid[V]): Monoid[Map[K, V]] = new:
    def combine(a: Map[K, V], b: Map[K, V]) =
      (a.keySet ++ b.keySet).foldLeft(empty): (acc, k) =>
        acc.updated(k, mv.combine(a.getOrElse(k, mv.empty),
          b.getOrElse(k, mv.empty)))

    val empty = Map.empty

然後來組裝成這種類型的 Monoid，

scala> val M: Monoid[Map[String, Map[String, Int]]] = mapMergeMonoid(mapMergeMonoid(intAddition))
val m: Monoid[Map[String, Map[String, Int]]] = anon$1@1f40bb80

最後我就可以用 Monoid 來合併 2 個 Map[String, Map[String, Int]]，不需要額外的程式執行合併動作。

scala> val m1 = Map("o1" -> Map("i1" -> 1, "i2" -> 2))
val m1: Map[String, Map[String, Int]] = Map(o1 -> Map(i1 -> 1, i2 -> 2))

scala> val m2 = Map("o1" -> Map("i2" -> 3))
val m2: Map[String, Map[String, Int]] = Map(o1 -> Map(i2 -> 3))

scala> val m3 = M.combine(m1, m2)
val m3: Map[String, Map[String, Int]] = Map(o1 -> Map(i1 -> 1, i2 -> 5))

用組合式的 Monoid 來融合迭代

最後，我們組合多個 Monoid 為一個，這意味著我們在摺疊資料時可以同時執行多個計算，舉例來說，我們用 Monoid 在一個迭代同時計算 List 的長度和加總，最後在算出平均值：

scala> val m = productMonoid(intAddition, intAddition)
val m: Monoid[(Int, Int)] = anon$1@bd8f424

scala> val p = List(1,2,3,4).foldMap(a => (1, a))(using m)
val p: (Int, Int) = (4,10)

scala> val mean = p._2 / p._1.toDouble
val mean: Double = 2.5

總結

今天介紹了第一個純粹的代數資料結構 Monoid，還有可摺疊的資料結構 Foldable，還有許多 Monoid 用在寫程式上的特性，透過 Monoid 的組合性，我們可以寫出許多有用的 helper 程式來幫助我們操作資料並簡化某些計算。

D22 – Exercise answer

D23 – Exercise answer

D24 – Exercise answer