所以Monad 到底是什麼 — Functor

在認識 Monad 之前，必須先了解什麼是 Functor。Functor 定義為可以 map 的類型：

class Functor f where
  map :: forall a b. (a -> b) -> (f a -> f b)

這個 map 就是陣列的 map 的推廣，例如 js 的 Array.map，因此像是 List, Array 都是functor，也就是存在一個合法的實作：

instance functorArray :: Functor Array where
  map :: forall a b. (a -> b) -> (Array a -> Array b)  map func = _

Array.map 的作用就是把原本容器 Array a 裡的數值取出，對每個數值應用給定函式 func，再把數值放到新的容器 Array b 裡。如果是在習慣使用mutation的指令式程式語言，常常需要手動寫下這些步驟，這個方法似乎只是提供一個比較方便的函式，但對函數式編程這才是最基礎的特性。同樣的操作也可以應用到 Map String, Set, Tree 等結構上，所以他們都是 Functor（除了 Set）。基於這個印象，若 f 為 Functor，f a 代表的是裝有類型為 a 的數值的容器，在這裡 f 可以是 List, Array, Map String, Tree 等類型的容器，而 a 可以是任意類型。事實上 a 必須是任意類型，因為 map 的定義用 forall a 讓呼叫端能夠使用任意類型，同時也限定了實作時必須編寫對任何類型 a 都適用的函式。也是因為如此 Set 才不能是 Functor，它的數值必須是可排序的。因此現在可以更新一下我們對於 Functor 的印象：若 f 為 Functor，f a 代表的就是可以裝有類型為 a 的數值的容器，且對於任何類型 a 都適用。

其實 Set 也有自己的 map，只是它限定 func 的回傳類型必須是能夠排序的，這是因為它所裝的數值順序與結構有關。例如在實作上它可能是用二元樹實現的，而其結構必須由數值的順序決定，因此當我們應用一些會改變順序的函式作 map，它的結構就會發生改變。反過來說，Functor 的 map 不能根據 func 回傳的結果改變容器的結構，畢竟如果結果可以是任意類型，等於你不知道它的任何特性，也就不能根據它改變結構。如果不管 Set 二元樹的結構直接作 map，雖然它的確就能變成 Functor，但是卻也不再是 合法的 Set。就算使用其他實作方法也不能解決這個問題，畢竟只要應用 \_ -> 1 這種常數函式作 map，就能把任意大小的 Set 變成只有一個元素。那如果今天是 MultiSet （可以有重複元素的集合）是不是就沒這個問題了？理論上是沒錯，但是要在不知道元素順序的情況下是不可能有效率地實現的。如果不做排序當然可以沒有效率地實現 MultiSet，但它基本上沒有任何好處，你為何不乾脆直接使用 List？

Functor 不只限制 map 後結構不能根據 func 回傳的結果改變，事實上不管 func 為何結構都不能發生改變，就算 func 是 \a -> a 也一樣。這個限制可以透過以下規則描述：

map f >>> map g = map (f >>> g)

這裡的 >>> 是函式組合算子，它代表先應用前面的函式再應用後面的函式。這個規則說明先組合函式再做 map 的結果應該要跟分別做 map 一樣。從容器的角度來看，就是看你要在一次 for loop 就做完全部，還是分兩次做，直觀上內容物的確要是一樣的。這個規則的重點不在於內容物，而是容器本身，它告訴你 map 一次和 map 兩次沒有什麼不同，因此你不能在 map 的時候偷偷做其他事情，例如紀錄使用幾次 map，例如：

data MapCounter a = MapCounter Int a

map :: forall a b. (a -> b) -> (MapCounter a -> MapCounter b)
map f (MapCounter n a) = MapCounter (n + 1) (f a)

這個 map 就不是合法的 Functor.map。同樣地，對 List 做 map 時不能偷改數量和順序，對 Map String 做 map 時不能偷換 key，對 Tree 做 map 必須保持原本的樹結構不變。

這個規則可以透過一些「魔法」簡化成 map id = id 或是 map id a = a，也就是什麼都不做的 map 相當於什麼都不做。注意，我們規則都是寫成 = 而非 ==，這裡的 == 是由使用者定義的意義上的相等（typeclass Eq），而 = 則是代表與意義無關的完全相等（稱為外延性相等，在 haskell/PureScript 裡並沒有這種語法，它只是概念性的描述）。這代表這個規則的等號左右不僅是概念上相等的，它們實作細節上的結構也是相同的。例如 Map 的實作結構可能是未優化的二元搜尋樹，儘管兩個 Map 在樹結構上是不同的，它們仍可能作為 Map 是相等的，這個概念上的相等性可藉由實作 Eq 定義。但根據這個規則的限制，你甚至不能在 map 時偷偷整理樹結構，否則就會改變實作細節上的結構。你會在這類 typeclass 常看到這種限制，因為他根本不會去管參數在概念上的意義，它只關心規範上的一致性。而且「兩者是否在概念上相同」這件事是由 Eq 定義的，map 不會限制回傳值必須實作 Eq，實質上也有可能回傳如函式等不能比較的結果，也就無從根據這種相等性做限制。如果你真的想要只考慮概念上相等的 map，你應該自己定義一個 typeclass，並在說明文件上寫明白，不應直接使用原本的 typeclass。因為很多使用 Functor 的函式都是嚴謹地通過這些規則來證明正確性，而非透過思考概念上合不合理來判斷，胡亂地破壞規則會造成不可預期的錯誤。

前面對於 map 規則的描述代表容器本身的結構和內容物之間沒有依賴關係，否則 map 之後就會改變結構。或者說這個容器至少有一個不會改變結構的 map 方法，只看這個方法的話他確實是 Functor。現在讓我們看看有哪些容器屬於 Functor。List 是最容易理解的 Functor，map 的概念（可以看作）就是從這個方法延伸出來的；對於任意有實作 Ord 的類型 k，Map k 也是 Functor，對他做 map 不會改變順序，因為它的順序是由 k 決定的。事實上不論 k 是否實作 Ord，Map k 都是 Functor，畢竟做 map 不需要知道順序，然而要構造出 Map k 通常都需要知道 k 的順序，因此實質上它的確需要 Ord k。data Tree a = Tree a (List (Tree a)) 是 Functor，它在描述樹結構的同時夾帶了關聯數值，可以看作帶有樹結構的容器，其中的數值可以在不改變樹結構的情況下操作。Maybe 是 Functor，它是或許有值的容器，如果有值它才需要做 map。Identity 是 Functor，它是裝有一個數值的容器，其實就是數值本身而已。Const Unit 也是 Functor，它是沒有裝任何數值的容器。可以看到不論是裝有一系列數值的容器，以某個鍵值作為索引的容器，還是可能有值或為空的容器，抑或是根本不能裝任何數值的容器，這些都是 Functor。然而它們之所以是 Functor 並不只是因為它們是容器，容器的結構也不能依賴於內容物，例如 Set 就不是 Functor。整理一下目前為止對於 Functor 的印象：若 f 為 Functor，f a 代表的就是可以裝有類型為 a 的數值的容器，且容器的結構與內容物沒有依賴關係。然而 Functor 並非只能描述容器的特性，它代表的其實是「值」於「情境」的意義，下一篇文章將更深入討論 Functor。