Haskell/Category theory (0)

(希望沒寫錯的，沒啥時間細琢 ><)

零零碎碎斷斷續續悽悽慘慘戚戚(?)讀了些 category theory 的東西，
最有系統的一次大概是讀 Abstract and Concrete Categories -
The Joy of Cats 吧。不過我只看了前面一點，沒多久就看不下去了。
除了他所謂的 concrete 對我來說還是太 abstract 外[0], 沒多久忽然
間就變得很難，定義和定理看了一堆我也不知道能做什麼.....

我大概還是不適合看太抽象的東西 (笑)

所以還是比較希望能在程式裡表現這些東西。無奈在 haskell 中，
因為需求與環境不同使然，很多東西都無法直接對應，而是用另一種
方式來表現或是傳達。有時候不同的東西，就會被當成同一種東西來
呈現。這樣光從程式裡去看，就根本看不出來背後的意義究竟有什麼
差別。就像太早去看 design pattern, 大概很難看出到底有什麼意義。

因此看來看去，還是不太清楚 category theory 中的 functor 跟
haskell 中的 functor 到底是怎麼接在一起的。haskell 中的 functor,
光看字面我覺得沒什麼好特別說的，就很單純是 generalized map...

fmap :: Functor f => (a -> b) -> f a -> f b

而在 category theory 中，直接引用該書中的一段描述...

Notice that a functor F : A → B is technically a family of functions;
one from Ob(A) to Ob(B), and for each pair (A,A′) of A-objects, one
from hom(A,A′) to hom(FA,FA′).

講白話一點可能可以說是分成兩個部份，一個能夠將 A 變成 B, 另一個則是
將所有 A -> A 的 morphism 都變成 B -> B. 可是 haskell 中，看起來就
只有那個孤獨的 fmap 而已。我們說 List 是 functor, 那 fmap 就是
map, 然後呢？

這個問題困擾我一段時間了。

一陣子前，從 jaiyalas 那邊得知 Edward Z. Yang 的 blog, 然後從他的
個人網站中，看到他推薦閱讀 Brent Yorgey 撰寫的 Typeclassopedia,
發表在 Monad.Reader issue 13.

這篇非常明確地說明了不少在 haskell 中，這一堆的 class 之間究竟有
什麼關係，還有為什麼 haskell 有些 class 設計很怪，跟理論上的東西
好像有點接不起來。還提到了 Pointed 這個應該有卻沒有的 class[1].

可惜後面 Category 和 Arrow 的 class 都太複雜了，我一時三刻還沒
看懂。另一方面，有幾段的 further reading 裡提到 Haskell wikibook
裡的 category theory:

Haskell/Category theory

這個在 google search 上通常都在很前面，所以我也翻過很多次了，不過
一直沒有仔細細看過，或是其實只是單純沒看懂？總之這時回頭來翻，發現
這篇對於解釋 category theory 跟 haskell 間關係，說不定是最清楚的
一篇也說不定？

關鍵在於，假使 haskell 的 type 是 object, function 是 morphism,
令 Hask 是 haskell 的 category, 則 fmap 中的：

fmap :: Functor f => (a -> b) -> (f a -> f b)

a 與 b 是 Hask 的 object, 而 a -> b 則是 Hask 的 morphism,
借用上面的定義：

Notice that a functor F : A → B is technically a family of functions;
one from Ob(A) to Ob(B), and for each pair (A,A′) of A-objects, one
from hom(A,A′) to hom(FA,FA′).

這邊的 a -> b 就是上面的 (A, A'), 也就是 hom(Hask, Hask'), 後面的
f a -> f b 即是 hom(F Hask, F Hask'). 也就是說，F Hask 和 F Hask'
就是 B, 也就是 haskell 中的 f a 與 f b. 假使這個 functor 是 List,
則 B 這個 category, 則是 Hask 中的 sub-category, 也就是 Lst (List),
即所有的 List value 和所有的 List function.
(
functor law 這邊都先跳過... identity 和 composition (associative?)
這些有時候我覺得滿直覺的，最後再討論就好了。
)
也就是說，fmap 本身確實就是 functor 中 morphism 的部份。
那 object 的部份呢？以 List 為例的話，那就是 List 本身了。
因此，構成 functor 的部份，實際上是這兩部份：

map  :: (a -> b) -> (List a -> List b)
List :: Hask -> Lst

map 是 morphism 的 mapping, List 是 object 的 mapping,
給一個 Hask object, 轉換成一個 Lst object. 令這邊的 Hask 是
Int, 則 List Int 是一個 Lst 的 object.

因此應該可以說，List 本身和其 fmap 的實作構成一個 functor
A -> B, 這邊的 A 是 Hask (所有 haskell type), 而 B 則是 Lst
(所有 List of something).

同時，或許也可以說，所有 haskell 裡的 functor, 全部都是 Hask -> ?

想到這裡，就覺得想在 haskell 裡 model category theory 應該不對吧。
怎麼可能用一個比較小的東西，去描述一個比較大的東西？遑論描述自己
都沒辦法了，因此只有 quasicategory of all categories, 沒有
category of all categories... (暈)

* * *

很多東西之所以看半天搞不懂，總覺得是有些最基本的概念，或是動機
不理解。不過大概也只能這樣不斷摸索揣測歸納吧。至少我自己的理解
方式大概是這樣。

接下來看能不能搞懂 category theory 中的 natural transformation 和
monad 了。然後再像 functor 那樣找到究竟是怎麼跟 haskell 連在一起。

---

不過仔細想想，這些東西好像離程式有點遠了喔..? @@

---

[0] 他 concrete example 我只有 set 的東西比較能看懂，
其他什麼 group, vector, monoid (現在或許比較懂了), topology,
ring, matrix, relation, automata, metric, Banach, 諸如此類...
有些之前我根本沒聽過 :s

[1] 這篇比較難，比較簡單的描述可以看 Learn You a Haskell for Great Good!
一個讓我很恍然的東西是，其實應該是 Functor => Pointed => Applicative
=> Monad 這樣一路串起來才對。然後 fmap 就是 liftM, 與其把 fmap 看成：

fmap :: Functor f => (a -> b) -> f a -> f b

不如看成：

fmap :: Functor f => (a -> b) -> (f a -> f b)

這樣就能很容易理解 fmap 其實就是 liftM... 就是上面提到
「A -> A 的 function 都變成 B -> B」的那一部份。
接著 Pointed 提供 pure, 也就是 unit, 也就是 return... Applicative
提供 <*>, 也就是 ap. 然後 class Monad 本身沒有限制一定要是
Applicative 只是單純因為 Monad 比 Applicative 還早加入 haskell.

呃，難道就不能改一下嗎？ :s 這樣很混淆...