[轉載]Haskell與範疇論

2010-04-06 黃毅 原文
用haskell的概念解釋範疇論。翻譯自 wikibook : http://en.wikibooks.org/wiki/Haskell/Category_theory

Haskell與範疇論

本文對範疇論做一個簡單的介紹，最終目的是為了將它應用到Haskell語言。為了達到這個目的，我們一邊介紹數學上的定義，一邊給出對應的Haskell代碼。我們不追求這個對應有多精確，只期望讀者在讀完以後，能對範疇論的基本概念及其跟Haskell之間的聯繫有一個直觀的感受。

一個簡單的範疇，由三個對像 A, B 和 C 組成，有三個單位態射 , 和 ，還有另外兩個態射 和 。第三個組成元素（即如何對態射進行組合）沒有展示出來。

本質上講，範疇由三部分組成： 一組 對像 一組 態射 。每個態射捆綁兩個對像（一個源對象，一個目標對像）。（也有人把它們叫做箭頭，我們這裡不這麼叫它，因為這個詞語在Haskell裡面有其他含義。譯註：其他含義指的是 Control.Arrow 。）如果 f 是一個從源對像 A 到目標對像 B 的態射，我們把它記作 。 一個稱為 態射組合 的概念。如果 h 是態射 f 和 g 的組合，我們記作： 。 許多事物都構成範疇。比如全部的集合就構成範疇 Set ，函數（譯註：這裡說的函數是指集合論中的函數）是它的態射，態射的組合就是函數的組合。全部的群也構成範疇 Grp ，保持群結構的函數就是它的態射（群同態），比如任意兩個群 G 和 H ， G 的操作符為 ， H 的操作符是 ，那麼函數 只要滿足如下條件就是一個態射：

乍看之下似乎所有態射都是函數，實際上不一定，比如下面這個例子，任何偏序結構 (P, ) 都構成範疇， P 中的元素就是該範疇的對象，任意兩個元素 a 和 b 只要滿足 ，那麼 就是一個態射。另外，在相同的源對像和目的對象之間可以存在多個態射。我們拿 Set 範疇為例， 和 都是從 到 的函數，但是他們是不同的態射。