2015/08/08

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

[ScaVa->Scala] 什麼是Functor, Applicative, Monad, Semigroup, Monoid?

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

這篇同步發佈在我的BlogGist

之前曾經寫過一篇 什麼是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)並且我們有f1f2,如果我們想把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.

張貼留言

My World