用haskell的概念解釋範疇論。翻譯自 wikibook : http://en.wikibooks.org/wiki/Haskell/Category_theory
Haskell與範疇論
本文對範疇論做一個簡單的介紹，最終目的是為了將它應用到Haskell語言。為了達到這個目的，我們一邊介紹數學上的定義，一邊給出對應的Haskell代碼。我們不追求這個對應有多精確，只期望讀者在讀完以後，能對範疇論的基本概念及其跟Haskell之間的聯繫有一個直觀的感受。
一個簡單的範疇，由三個對像 A, B 和 C 組成，有三個單位態射
 ,  和  ，還有另外兩個態射  和  。第三個組成元素（即如何對態射進行組合）沒有展示出來。 | 本質上講，範疇由三部分組成：
 ， H 的操作符是  ，那麼函數  只要滿足如下條件就是一個態射：
|
) 都構成範疇， P 中的元素就是該範疇的對象，任意兩個元素 a 和 b 只要滿足 
，那麼 
就是一個態射。另外，在相同的源對像和目的對象之間可以存在多個態射。我們拿 Set 範疇為例， 
和 
都是從 
到 
的函數，但是他們是不同的態射。範疇公理
範疇需要滿足三個公理。第一個就是態射的組合操作要滿足結合律。記作：
第二，態射在組合操作下是閉合的。所以如果存在態射
和 
，那麼範疇中必定存在態射 
使得 
。以下面這個範疇為例：
f 和 g 都是態射，所以我們一定能夠對他們進行組合併得到範疇中的另一個態射。那麼哪一個是態射
呢？唯一的選擇就是 了。類似地， 
。第三個公理，對任何一個範疇 C ，其中任何一個對像 A 一定存在一個單位態射，
。這個態射是組合操作的單位元。
Hask ，Haskell範疇
本文重點關注一個叫 Hask 的範疇，該範疇由Haskell中所有類型組成，Haskell的函數就是它的態射， (.) 操作符便是態射組合，函數 f::A->B 就是 Hask 中從類型 A 到類型 B 的態射。第一和第三公理很容易驗證通過，因為 (.) 操作符本身就是滿足結合律的函數，而且很顯然，對於任何函數 f 和 g ， f.g 仍然是一個函數。在 Hask 中，單位態射就是函數 id ，而且顯然也滿足第三公理：id . f = f . id = f
函子
OK，我們已經介紹了一些範疇，這些範疇裡面都有些對象，還有一些態射能神奇地把對像關聯在一起。下面我們要介紹一個範疇論中相當重要的概念，那就是 函子 ，它甚至能把兩個範疇關聯在一起。函子本質上說其實就是範疇之間的轉換。比如對於範疇 C 和 D ，函子  能夠：
| 
這是從範疇
 到範疇  的函子。圖中的文字描述了對象 A 和 B 被轉換到了範疇 D 中同一個對象，因此，態射 g 就被轉換成了一個源對像和目標對像相同的態射（不一定是單位態射），而且 和 變成了相同的態射。對像之間的轉換是用淺黃色的虛線箭頭表示，態射之間的轉換是用淺綠色的箭頭表示。 |
轉換為 D 中的 
，它能將群轉換成它底層的集合，並將群的態射轉換成集合上的相同行為的函數。另一個例子就是冪集函子： 
，它能將集合轉換成他們的冪集，並將函數 
轉換成函數 
，後面這個函數接收所有 
組成的集合（譯註：也就是集合 X 的冪集），將它轉換成 
，其中 
。對所有的範疇 C 都可以定義一個所謂的單位函子，也叫做 
，它將對像和態射直接轉換成它們自己。在後面要講的monad公理和他們的重要性 一節中，我們將會看到單位函子的作用。同樣的，函子也需要遵守一些公理。第一，給定一個對像 A 上的單位態射
， 
必須也是 
上的單位態射，也就是說：
第二，函子在態射組合上必須滿足分配率，也就是說：
Hask 上的函子
也許你已經看出來了， typeclass Functor 確實和範疇論中的函子概念關係緊密。函子包括兩部分：首先它將一個範疇中的對象轉換成另一個範疇中的對象，其次它還將一個範疇中的態射轉換成另一個範疇中的態射。Haskell中的 Functor 其實是把 Hask 轉換到 Hask 子範疇 Func 的函子，範疇 Func 是定義在該 Functor 的類型之上的一個範疇。比如函子 list 是從範疇 Hask 轉換到範疇 Lst ，範疇 Lst 只包含一個類型 list ，換句話說函子 list 能將任意類型 T 轉換為 [T] 。範疇 Lst 中的態射就是定義在 list 類型上的函數，即： [T]->[U] 。那麼所有這些東西又如何跟Haskell的 Functor typeclass 聯繫在一起呢？我們回憶一下 Functor 的定義：class Functor (f :: * -> *) where
fmap :: (a -> b) -> (f a -> f b)
我們再定義一個實例：instance Functor Maybe where
fmap f (Just x) = Just (f x)
fmap _ Nothing = Nothing
關鍵點來了：類型構造器 Maybe 將任意類型 T 轉換成新類型 Maybe T ，同時定義在 Maybe 上的 fmap 能將函數 a->b 轉換為函數 Maybe a->Maybe b 。這樣，我們就已經把函子的兩個組成部分都定義了，將 Hask 中的對象轉換到另一個範疇中的對象，並將 Hask 中的態射轉換到該範疇的態射。所以 Maybe 是一個函子。對於Haskell的 Functor 一個直觀的感覺就是，他們代表了一類可以被map的類型。它可以是 list 或是 Maybe ，也可以是樹這樣複雜的結構。利用它我們可以編寫一個執行實際map操作的函數，和 fmap 組合起來，然後就可以傳遞任意 Functor 結構給它。比如你可以寫一個通用函數可以取代 Data.List.map ， Data.Map.map ， Data.Array.IArray.amap ，等等。
我們繼續來看函子公理，多態函數 id 可以替代任意的
，所以第一條公理是滿足的：fmap id = id直觀地看，這句代碼的含義是說map一個結構，然後對其中每一個元素啥也不做，和從一開始就啥也不做是等價的。
第二，因為態射組合就是 (.) ，那麼：
fmap (f . g) = fmap f . fmap g這條公理還挺實用。這裡我們可以把函子想像成類似 list 這樣的容器，等號右邊就是一個要遍歷容器兩遍的算法：首先map這個容器，對其中元素執行函數 g ，產生一個新容器，然後map該新容器，執行 f 。而這條公理告訴我們，這個算法可以換成一個只需遍歷一遍的算法，並對其中每一個元素執行 f . g 。這個過程叫做 fusion 。
將範疇論的概念對應到Haskell
現在我們來總結一下範疇論的概念要如何轉換到Haskell上面，這方面 Functor 提供了一個很好的例子。關鍵在於記住以下幾點：- 我們只探討 Hask 範疇和它的子範疇
- 範疇的對象就是Haskell的類型
- 範疇的態射就是Haskell的函數
- 那些接受類型作為參數並返回另一個類型的東西叫類型構造子
- 那些接受函數作為參數並返回另一個函數的東西叫高階函數
- typeclass 以及它們提供的多態特性，正好反映了這樣一個事實，那就是在範疇論中，其實很多概念都是在一組對像上定義的。
Monads
Monad是Haskell中一個相當重要的概念，實際上，它們最開始就是來自範疇論。monad 是一類特別的函子，它們擁有一些獨特的結構。monad都是從一個範疇映射到其自身的函子。下面我們來看詳細定義，Monad是一個函子  ，並且對於 C 中每一個對像 x 都存在如下兩個態射： 和  。現在我們來看看它是如何對應到Haskell的typeclass Monad 上的： | 
unit 和 join ，對monad中每一個對象都必須存在的兩個態射
|
class Functor m => Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
類型約束 Functor m 可以確保我們已經擁有了函子結構：即對像和態射的一組轉換關係。 return 就是對應的 。不過下面我們就遇到問題了，雖然 return 的類型酷似 unit ，但 (>>=) 的類型卻很難跟 join 聯繫起來。反而下面這樣的函數： join :: Monad m => m (m a) -> m a 看起來倒是跟 join 挺像的。實際上它們之間是可以互相轉換的：join :: Monad m => m (m a) -> m a join x = x >>= id (>>=) :: Monad m => m a -> (a -> m b) -> m b x >>= f = join (fmap f x)所以給出 return 和 join 和給出 return 和 >>= 是等價的。只不過在範疇論中通常用 unit 和 join 來定義monad，而Haskell程序員則更喜歡用 return 和 (>>=) _[3] 。範疇論的方式通常要更合理一點，因為對於一個結構 M 來說，如果存在一種自然的方式將任意對像 X 轉換為
，並能將 
轉換為 ，那麼該結構很可能就是一個monad。這一點可以從下面的示例中看出。示例：冪集函子同時也是monad
前面描述過的冪集函子
可以形成一個monad。對每一個集合 S 都有 
，將其中 S 的每一個元素映射到只含有該元素的一個集合。注意到這些只有一個元素的集合都是 S 的子集，所以 
返回的正是 S 的冪集中的元素，這樣就滿足了 monad 對 unit 的要求。我們再來定義函數 
，輸入為 
，它是：- S 的冪集的冪集的元素.
- 即 S 所有子集組成的集合的所有子集組成的集合的元素 .
- 即 S 的部分子集組成的集合
的一個元素，也即成功地從 
映射到了 
），公式如下。
由此可見 P 確實是一個 monad 。
其實 P 跟 `list` 幾乎是等價的；除了後者處理的是列表而前者是集合，他們在其他地方基本一致。見表：
| 集合上的冪集函子 | Haskell中的List Monad | ||
|---|---|---|---|
| 類型 | 定義 | 類型 | 定義 |
給定集合 S 和態射  ： |
給定類型 T 和函數 f :: A -> B | ||
 |
 |
fmap f :: [A] -> [B] | fmap f xs = [ f a | a <- xs ] |
 |
 |
return :: T -> [T] | return x = [x] |
 |
 |
join :: [[T]] -> [T] | join xs = concat xs |
monad公理和他們的重要性
正如函子需要滿足函子的公理，monad也有他們的公理要去滿足。我們先把這些公理簡單列舉一下，並轉換成haskell代碼，最後再來探討這些公理的重要性。給定一個monad
和態射 其中 
，有公理如下：
- join . fmap join = join . join
- join . fmap return = join . return = id
- return . f = fmap f . return
- join . fmap (fmap f) = fmap f . join
公理一
| 為了方便理解這條公理，我們先用 list 作為例子。首先這條公理涉及兩個函數， join . fmap join （等式左邊）和 join . join (等式右邊)。這兩個函數的類型是什麼呢？因為我們只探討 list ，所以我們知道 join 的類型是 [[a]] -> [a] ，然後可以推出他們的類型都是： [[[a]]] -> [a] 。所以我們的參數是一個 list 的 list 的 list ，然後對這個三層 list 執行 fmap join ，然後再在返回結果上應用 join 。對 list 來說 fmap 就是我們熟悉的普通 map ，所以我們首先對最外層列表的每一個元素進行 join 操作，也就是將其中每一個元素坍縮成為單層 list 。這個時候我們就得到一個 list 的 list ，我們再在其上應用 join ，最終坍縮成為一個 list 。簡單地說，我們先進入外層 list ，將第二層和第三層 list 坍縮成一層，然後再將這一層和最外層坍縮成一層。 | 
用 list 對公理一進行的演示. 記住在 list monad中 join 就是 concat ， fmap 就是普通的 map 。
|
Maybe 也是一個 monad，因為：
return :: a -> Maybe a return x = Just x join :: Maybe (Maybe a) -> Maybe a join Nothing = Nothing join (Just Nothing) = Nothing join (Just (Just x)) = Just x所以如果我們有一個三層的 Maybe 類型（舉例來說，它可以是 Nothing, Just Nothing, Just (Just Nothing) or Just (Just (Just x)) ），公理一就告訴我們，先坍縮裡面兩層還是先坍縮外面兩層是完全等價的。
公理二
我們再來看看第二條公理， 同樣我們還是用 list 做例子。第二條公理提到兩個函數的類型都是： [a] -> [a] 。等式左邊表達的是對一個 list 進行map的函數，將每一個元素 x 轉換成者有這一個元素的列表 [x]，這樣我們最終就得到一個單元素列表組成的列表。然後這個兩層 list 通過join函數又重新坍縮回單層 list ，右邊部分，接收整個 list [x, y, z, ...]，將它轉換成單元素 list [[x, y, z, ...]] ，然後又坍縮成為單層列表。這條公理的含義沒那麼容易一下子說清楚，不過大概就是說，當你在一個monadic值上面應用return，然後再對見過使用join另它坍縮，不管你是在外層應用return還是在內部應用return，其效果是一樣的。公理三和公理四
最後兩條公理就更加不言而喻了，要展現他們的真實性最簡單的方法就是將他們擴展開來：- \x -> return (f x) = \x -> fmap f (return x)
- \x -> join (fmap (fmap f) x) = \x -> fmap f (join x)
應用到do語法
OK，前面我們已經對monad必須遵守的一些公理進行了一些直觀的陳述，但是這些公理為什麼如此重要？這個問題的答案當我們看到do語法的時候就清除了。我們知道do只是一個語法糖，它其實就是多個 (>>=) 操作的組合：do { x } --> x -- test
do { let { y = v }; x } --> let y = v in do { x }
do { v <- y; x } --> y >>= \v -> do { x }
do { y; x } --> y >>= \_ -> do { x }
另外，我們其實可以通過上面提到的這些公理和 (>>=) 的定義，對 haskell 中的 monad 公理進行證明（證明過程有的地方比較複雜，如果沒有興趣也可以直接跳過）：- return x >>= f = f x 。證明：
return x >>= f = join (fmap f (return x)) -- 根據 (>>=) 的定義 = join (return (f x)) -- 根據公理三 = (join . return) (f x) = id (f x) -- 根據公理二 = f x
- m >>= return = m 。證明：
m >>= return = join (fmap return m) -- 根據 (>>=) 的定義 = (join . fmap return) m = id m -- 根據公理二 = m
- (m >>= f) >>= g = m >>= (\x -> f x >>= g) 。證明（聯想 fmap f . fmap g = fmap (f . g) ）：
(m >>= f) >>= g = (join (fmap f m)) >>= g -- 根據 (>>=) 的定義 = join (fmap g (join (fmap f m))) -- 根據 (>>=) 的定義 = (join . fmap g) (join (fmap f m)) = (join . fmap g . join) (fmap f m) = (join . join . fmap (fmap g)) (fmap f m) -- 根據公理四 = (join . join . fmap (fmap g) . fmap f) m = (join . join . fmap (fmap g . f)) m -- 根據函子的分配率 = (join . join . fmap (\x -> fmap g (f x))) m = (join . fmap join . fmap (\x -> fmap g (f x))) m -- 根據公理一 = (join . fmap (join . (\x -> fmap g (f x)))) m -- 根據函子的分配率 = (join . fmap (\x -> join (fmap g (f x)))) m = (join . fmap (\x -> f x >>= g)) m -- 根據 (>>=) 的定義 = join (fmap (\x -> f x >>= g) m) = m >>= (\x -> f x >>= g) -- 根據 (>>=) 的定義
| 無參(points-free)風格 | do語句塊 |
|---|---|
| return x >>= f = f x | do { v <- return x; f v } = do { f x } |
| m >>= return = m | do { v <- m; return v } = do { m } |
| (m >>= f) >>= g = m >>= (\x -> f x >>= g) | do { y <- do { x <- m; f x };
g y }
=
do { x <- m;
y <- f x;
g y }
|
沒有留言:
張貼留言