What have you found for these years?

2011-05-22

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)
ab 是 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 af 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 這樣很混淆...

6 retries:

XOO said...

這東西一步一步來好了。

首先是 Haskell 中所有的 type 作為 object, function 則是 morphisms,那每個 type 都有 identity, morphisms 的 composition 也是 associative 的,所以構成一個 category。用 Hask 來稱呼這個 category 。

那麼,對於 List 則是將一個 type (A) 對應到另個 type (list of A),所以 List 是個從 Hask 對應到 Hask 的。list of something 還是一個在 Haskell 下的一個 type。

因此,List 本身只有構成 functor 需要的 object function。另外,要構成一個 functor 還需要 morphism function ,也就是 fmap。根據定義是將一個 a -> b 的 morphism,也就是 a -> b 的 function 變成一個 List a -> List b 的 function,這也就是 fmap 的 type。

學 category theory 我不大建議 Abstract and Concrete Categories The Joy of Cats 那本。沒有數學背景的話,William Lawvere 的 Conceptual Mathematics: A First Introduction to Categories 應該比較容易,從很基本的數學概念開始導入。但是不耐煩的話,這本可能看不下去。

Lin Jen-Shin (godfat) said...

謝啦,晚點去找找那本

感覺跟我的理解差不多,只差在不能把 List 當成 Hask 的 sub-category 嗎?
因此可以看成 Hask -> List 而不是 Hask -> Hask ?

XOO said...

>因此可以看成 Hask -> List 而不是 Hask -> Hask ?
(上面應該反過來?Hask -> Hask 而不是 Hask -> List Hask

是可以考慮 List A, A 是 Hask 的 object ,以及所有 List A -> List B 的 function 這樣組成的 sub-category。

但是,這樣想就不能直接作 functor compostition 了。中間要再接一層 inclusion function J : List -> Hask。

就像給 f : A -> B,如果寫成 f : A -> f(A)。f(A)會用 existential type 寫成"存在 a : A 使得 b = f(a)",當然那個證明很好找出來,但是要作 function composition 的時候,要多一個 function J : f(A) -> B 把 f(A) 的證明拔掉,剩下那個 b : B,
才能再接上另一個函數 g : B -> C。

Lin Jen-Shin (godfat) said...

噢,原來如此,雖然我不知道「很好找出證明」這件事要怎麼做 XD
以 haskell 為例,是找出 List a 也是 t (某個 Hask object?) 的 function 之類的?

另外在想的是,我猜很難在 haskell 中看到 functor composition?
或是要看 Category 和 Arrow 那些 type class, 我還沒看到那.. :x

XOO said...

Functor composition 很多呀。 lists of lists of A 就是一例:List . List : Hask -> Hask。在定義 datatype 的時候也常常用這樣的方式構造新的 type。

>以 haskell 為例,是找出 List a 也是 t (某個 Hask object?) 的 function 之類的?

不是喔,是用 dependent product 定義 f(A) 成為「(b : B) x (有某個 a 使得 b = f(a)) 」。也就是一個 pair 包含 b 以及 b = f(a) 的證明。而這證明其實就用 f(a) 代換 b 就好了,因為 f(a) : B 。

Lin Jen-Shin (godfat) said...

看來我還需要慢慢想(遠目)
之前看的 agda 全忘光了,需要回想一下 orz

Post a Comment

All texts are licensed under CC Attribution 3.0