Category theory(範疇論)之什麼是Functor, Applicative, Monad, Semigroup, Monoid?

這篇同步發佈在我的Blog和Gist。

之前曾經寫過一篇 什麼是Monad? ，裡面提到了對於Monad的解釋，而今天進一步解釋這些在Functional Programming中常見到的詞：Functor, Applicative, Monad, Semigroup, Monoid。
透過放在一起比較，讓我們更清楚這些之間的差別與關係。

Functor

在提到Functor之前，請先了解一下scala中map的作用，map可以讓你傳入一個function，而透過這個function是可以從F[A]轉換成F[B]，這裡的F不管他(就是代表外面的包裝不會變)，而裡面的A型態轉成B型態。

例如：

val a = List(1,2,3)
val b = a.map( x => x.toString )

這裡面的 x=>x.toString 是一個scala Function1[Int,String]的implementation，也就是一個(x:Int):String傳入Int，回傳String的function。

這裡的a的型態會是List[Int]，而b是List[String]，所以map就是把F[A]轉成F[B]，轉的方式就是你傳入的function。

再回來說Functor的定義：

• Identity：一個類型，他有提供F[A]->F[B]的function(在Scala裡就像是map)。
• Composition：這個類型，他有所提供上述條件的function(也就是map)，具有組合(composition)的特性。

第一點沒問題，就是剛才舉的例子。
第二點，什麼是”組合的特性”?

val f1 = (x:Int)=>x+1
f1: Int => Int = <function1>

val f2 = (x:Int)=>x*2
f2: Int => Int = <function1>

scala> List(1,2,3).map(f1).map(f2)
res8: List[Int] = List(4, 6, 8)

scala> List(1,2,3).map(f2 compose f1)
res9: List[Int] = List(4, 6, 8)

scala> List(1,2,3).map(f1 andThen f2)
res10: List[Int] = List(4, 6, 8)

註：注意這裡的compose是 f2 compose f1

就是說，.map(a).map(b) 會等於 .map(b compose a) 或是 .map(a andThen b)

Applicative

而接下來介紹的Applicative，是Functor的延伸，加上了以下兩點的特性。

• pure，這個表示能將一個值或是一個function，包進F[]中，像是List(1) 或 Some(1)
• Homomorphism：提供了能把一堆function分別套給F[]裡的每個值運算，然後結果還是包在F[]裡的特性。
• Interchange：就是a*b=b*a這種交換性嘍(不過運算子是針對Applicative的)。

第一、三點比較沒問題。我們直接來解釋第二點。
舉個例來說，在上面的例子我們有個List(1,2,3)並且我們有f1和f2，如果我們想把f1和f2套用到List的每個值中，在Scala的作法可以用for comprehensive：

for{
  x <- List(1,2,3)
  y <- f1(x)
  z <- f2(z)
} yield (z)

套用scalaz的<*>這個運算子，可以讓F[A]吃F[(A)=>B]，也就是

List(1,2,3) <*> List(f1,f2)

他把1,2,3這些值分別套到f1,f2中。

再一個比較簡單的例子我們有List(1,2,3)和List(2,4,6)，想要把他相乘，用for comprehensive

scala> for{
     | a <- List(1,2,3)
     | b <- List(2,4,6)
     | } yield (a*b)
res0: List[Int] = List(2, 4, 6, 4, 8, 12, 6, 12, 18)

若用scalaz的|@|的運算子，則可以寫成

(List(1,2,3) |@| List(2,4,6)) {(_*_)}

List和Option都是Applicative Functor的例子，可以用這兩個的特性來思考一下！

Monad

Monad就是Applicative的延伸，加上bind的特性，像是這樣：

trait Monad[M[_]] {
  def bind[A, B](m: M[A], f: A => M[B]): M[B]
}

其實在scala也就是flatMap，舉個例子

val a : List[Int] = List(1,3,5)
val f : (Int)=>List[Int] = (i:Int)=>List(i+1,i+2)
val result : List[Int] = a.flatMap(f)

result: List[Int] = List(2, 3, 4, 5, 6, 7)

若不用flatMap的話，你拿到的會是List(List(2,3),List(4,5),List(6,7))，flatMap把你把他整理好了！

Semigroup

A semigroup is anything that supports appending.

這句話簡潔明瞭！
數字2和3可以被append，(用+的就是5，用*的就是6)，所以數字是semigroup。
List和Option也能append，所以他們也是semigroup。
這裡要注意的定義是：

• Closure：當F這個型態是semigroup的時候，若A, B是屬於F型態，A+B之後也必須是F型態。
• Associative：就像是1 * ( 2 * 3 ) 和 ( 1 * 2 ) * 3 是一樣的。

在scalaz中，semigroup的append運算子是|+|，所以我們可以這樣加：

List(1,2,3) |+| List(4,5,6)
res: List[Int] = List(1, 2, 3, 4, 5, 6)

或是

1.some |+| 2.some
res: Option[Int] = Some(3)

Associative的例子就像這樣：

scala> List(1) |+| List(2) |+| List(3)
res1: List[Int] = List(1, 2, 3)

scala> List(1) |+| ( List(2) |+| List(3) )
res2: List[Int] = List(1, 2, 3)

scala> ( List(1) |+| List(2) ) |+| List(3)
res3: List[Int] = List(1, 2, 3)

Monoid

Monoid是semigroup加上zero

這個zero的特性是

1. 不管是原本的型態的值加上這個zero
2. 或是zero加上原本的型態的值

結果都會是原來的值

就像是5+0 = 5, 0就是數字加法中的zero
而5*1=5, 1就是數字乘法中的zero
List的zero就會是Nil

所以當要建立自己的Monoid的時候，要注意到這個特性。

Reference
- Category theory jargon cheat sheet
- CodeData Haskell Tutorial
- Examples of Applicative Functor usage in Scala
- learning Scalaz - Functor Laws

Written with StackEdit.