Monads 定律 1 - 結合律 (Associative Law)

假設我們有個 Item 和 Order 類別，

case class Item(name: String, price: Double)
case class Order(item: Item, quantity: Int)

在來用 for-comprehensions 來產生 Option[Order]，

  val order: Option[Order] = for
    name <- Some("iphone 15")
    price <- Some(45900.0)
    quantity <- Some(1)
  yield Order(Item(name, price), quantity)

Scala for-comprehensions 的說明請參考 Day 8 - 如何不拋出例外的處理錯誤 (3)。

有時候我們也會以這樣的方式來產生 Option[Order]，

  val optItem: Option[Item] = for
    name <- Some("iphone 15")
    price <- Some(45900.0)
  yield Item(name, price)

  val order: Option[Order] = for
    item <- optItem
    quantity <- Some(1)
  yield Order(item, quantity)

這 2 個 Order 都是透過 for-comprehensions 而產生，乍看起來這 2 個 Order 相同是非常合理的，

但若我們將它們細部拆解會得到下面的調用順序，

// case 1
  Some("iphone 15").flatMap(name =>
    Some(45900.0).flatMap(price =>
      Some(1).map(quantity =>
        Order(Item(name, price), quantity))))

// case 2
  Some("iphone 15").flatMap(name =>
    Some(45900.0).map(price =>
      Item(name, price)).flatMap(item =>
      Some(1).map(quantity =>
        Order(item, quantity))))
}

這程式看起來就很不一樣了，那為什麼我們對第一個版本的 for-comprehensions 會有這種 2 個 Order 是一樣的感覺呢？

因為 flatMap 也是遵守著 Associative property (結合律)：

x.flatMap(f).flatMap(g) == x.flatMap(a => f(a).flatMap(g))

這定律可用在所有 Monad 上。

證明看看阿你

這裡我們一樣可以用 Option 來證明上面的定律為真，我們要做的就是把 x 替換成 Some 或 None 來看最後是不是相等，

Option 型態的說明請參考 Day 7 - 如何不拋出例外的處理錯誤 (2)。

None

None.flatMap(f).flatMap(g) == None.flatMap(a => f(a).flatMap(g))

None 的 flatMap 還是 None，所以簡化等號 2 邊後會得到，

None == None

所以 None 符合該定律。

Some

若 x 等於包裹著任一值 v 的 Some(v)，

首先是替換 x，

Some(v).flatMap(f).flatMap(g) == Some(v).flatMap(a => f(a).flatMap(g)) 

因為 f 是接受一個參數並回傳 Option，所以我們可以簡化 Some(v).flatMap(f) 這個算式為 f(v)，

f(v).flatMap(g) == (a => f(a).flatMap(g))(v)

最後等號右邊的算式可以分 2 個部份看，左半部是 higher-order function (a => f(a).flatMap(g))，右半部是 (v)，意思就是把 v 當做左半部的 function 的參數傳入，

有點難理解的話請參考以下程式，除了可以把 x 宣告成 function 外，也能用匿名的方式直接調用

scala> val x: (Int => Int) = ((a: Int) => a + 1)

scala> x(5)
val res1: Int = 6

scala> ((a: Int) => a + 1)(5)
val res2: Int = 6

但因為 function (a => f(a).flatMap(g)) 也沒做什麼特別的事，所以我們可以繼續簡化，

f(v).flatMap(g) == f(v).flatMap(g))

完整推導過程如下：

x.flatMap(f).flatMap(g) == x.flatMap(a => f(a).flatMap(g))

Some(v).flatMap(f).flatMap(g) == Some(v).flatMap(a => f(a).flatMap(g)) 

f(v).flatMap(g) == (a => f(a).flatMap(g))(v)

f(v).flatMap(g) == f(v).flatMap(g))

最後可以觀察到 Some 也符合該定律。

Kleisli Composition

這個結合律真的很難讓人理解，好消息是我們有個方法可以讓它好理解些，

如果我們不從 Monad 的值 F[A] 來理解，而是從像 A => F[B] 的 Monad function 來思考，然後組合多個 function 成結合律的結果，

def compose[A, B, C](f: A => F[B], g: B => F[C]): A => F[C] =
	a => f(a).flatMap(g)

這個 A => F[B] 方法也被稱為 Kleisli arrow，而這個組合方法被稱為 Kleisli Composition，

最後 Monad 的結合律可以寫成跟 Monoid 一樣比較好理解。

compose(compose(f, g), h) == compose(f, compose(g, h))

Monads 定律 2 - 同一律 (identity laws)

Identity laws 就像 Monoid 的 empty 被稱為 identity element (單位元素) 一樣，Monad 的 identity element 是 unit，

def unit[A](a: => A): F[A]

任何跟 unit 組合的 function 會是相同的，這個通常會用 2 個定律來表示：Left identity 和 Right identity。

compose(unit, f) == f // Left identity
compose(f, unit) == f // Right identity

Exercise D27-1

map, unit, join 是另外一組 Monad 的一元組合器方法，試著用 flatMap 來實作 join 吧，它主要是用來移除最外那層的 F。

def join[A](ffa: F[F[A]]): F[A]

總結

這 3 天介紹了 Functor 和 Monad 介面，就是 map 和 flatMap 方法的抽象介面，這些也都是從數學 Category Theory 來的概念，整個抽象的過程都大同小異，有核心 API、定律和延伸出的組合器方法，雖然得花點時間理解，但能用 Monad 讓資料支援 map, flatMap 操作是件很棒的事情。

Day 27 - Exercise answer