對於學函數語言的人來說，關於單子 (monad) 的種種似乎是最難跨越的門檻。許多朋友也常問哪有適合的入門教材，看來大家確實很需要一篇適合初學者讀的中文簡介。我試著以比較操作性的方式介紹單子，希望能有一些幫助。多年前我學函數編程時也對 monad 這東西覺得困惑不已，最後是讀了Philip Wadler 的這篇 The Essence of Functional Programming才開始有「好像有點懂了」的感覺。該論文用一個直譯器當作貫穿全文的例子。我們也以類似的方式進行吧。
以下的資料結構表達一個只有整數、負號、和加法的數學式：
data Expr = Num Int | Neg Expr | Add Expr Expr處理這種資料大概是函數語言的強項吧。例如，要算式子的值很容易：
eval :: Expr -> Int eval (Num n) = n eval (Neg e) = - (eval e) eval (Add e1 e2) = eval e1 + eval e2函數 eval 拿一個算式，傳回一個整數。看到 Num n 就直接傳回 n, 否則先把子算式的值算出，再取相反數或是求和。
假設我們添了一個整數除法運算元：
data Expr = Num Int | Neg Expr | Add Expr Expr | Div Expr Expr我們便碰到了一個小難題。要怎麼處理分母是零的狀況呢？
Haskell 有一個 div 函數可做整數除法。碰到分母為零時，div 和大部分語言的除法函數一樣，丟出一個例外讓整個程式當掉。我們不希望這麼做，因此大概得在程式中先檢查一下看分母是否為零。但這時 eval 函數應該傳回什麼呢？
eval (Div e1 e2) = let v2 = eval e2 in if v2 == 0 then ??? else ... 用 Maybe 型別表達部份函數有了除法後，eval 成了一個部份 (partial) 函數 — 某些輸入沒有對應的值。操作上，我們希望 Haskell 提供例外 (exception) 的功能，可以在程式另外某處將 eval 丟出的例外抓住。但例外是一種副作用。之前的函數編程簡介中提及，「函數語言沒有副作用」是個不精確的說法。函數語言程式終究也是得用到副作用的，只是我們會把用到的副作用納為數學模型的一部份，將他們的性質也描述出來。描述部份函數或例外的方法之一是用常見的 Maybe 型別：
data Maybe a = Just a | Nothing把 eval 的型別改為 Expr -> Maybe Int. 正常運算結束便傳回 Just, 碰到分母為零的情形則傳回 Nothing. 呼叫 eval 的地方若得到 Nothing, 就相當於抓到了例外。
我們來看看這個版本的 eval. 碰到 Num n自然是傳回 Just n:
eval (Num n) = Just n處理 Neg e 的條款則比以前稍微複雜了。我們得檢查 eval e 的結果，若是 Just v 便取 v的相反數，但別忘了把結果也包上一個 Just. 如果遇到 Nothing, 表示 e 的運算失敗了，我們只好把 Nothing 再往上傳。
eval (Neg e) = case eval e of Just v -> Just (-v) Nothing -> NothingAdd 的情況下，程式碼看來更冗長了些：
eval (Add e1 e2) = case eval e1 of Just v1 ->case eval e2 of Just v2 -> Just (v1 + v2) Nothing -> Nothing Nothing -> Nothing我們得分別檢查 eval e1 與 eval e2 的結果是 Just 或是 Nothing. 標成紅色的部份負責檢查例外的例行公事，是很機械性的程式碼。最後是 Div e1 e2 的情況，我們先計算 e2, 如果是零傳回 Nothing, 否則做除法運算。在這過程中我們也需要做許多分析檢查：
eval (Div e1 e2) = case eval e2 of Just 0 -> Nothing Just v2 -> case eval e1 of Just v1 -> Just (v1 `div` v2) Nothing -> Nothing Nothing -> Nothing很自然地，我們會希望把標成紅色的例行公事抽象掉。
Maybe 單子我們再看一次處理 Neg 的條款：
eval (Neg e) = case eval e of Just v -> Just (-v) Nothing -> Nothing我們真正想表達的僅是「把 eval e 的結果，如果有的話，送給 \v -> Just (-v)」。這只是多加了一點手續的函數應用 (application)。Haskell 有一個函數應用運算元，f $ x 就是把x 餵給 f, 也就是 f x。也許我們可以自己定義一個函數應用運算元 =<<，把檢查 Just 或Nothing 的動作藏在裡面：
eval (Neg e) = (\v -> Just (-v)) =<< eval e習慣用函數 composition 的人可能會更想寫成 Just . negate =<< eval e，但目前的習慣是把這個運算元的左右顛倒：參數寫前面，函數寫後面。我們可以定義:
(>>=) : Maybe a -> (a -> Maybe b) -> Maybe b (Just x) >>= f = f x Nothing >>= f = Nothing函數 eval 的前兩個條款便可以改寫如下：
eval (Num n) = return n eval (Neg e) = eval e >>= (\v -> return (-v))我們把 Just 寫成 return，等下會解釋為什麼。Add 和 Div 的情況也可以用 >>= 改寫:
eval (Add e1 e2) = eval e1 >>= \v1 -> eval e2 >>= \v2 -> return (v1 + v2) eval (Div e1 e2) = eval e2 >>= \v2 -> if v2 == 0 then mzero else eval e1 >>= \v1 -> return (v1 `div` v2)處理 Add 的程式碼很清楚：先算出 eval e1, 把結果叫做 v1；再算 eval e2, 把結果叫做v2, 然後相加。別忘了 v1 + v2 仍得用一個 return 轉成 Maybe 型別。遇到 Nothing 的狀況已在 >>= 的定義中處理掉了 -- eval e1 的結果若是 Nothing, 算式 eval e2 >>= ... 直接變成 Nothing 而不會算到 eval e2. 處理 Div 的程序也類似，如果 v2 為零，我們直接傳回 Nothing。此處把 Nothing 寫成 mzero, 含意待會兒解釋。
Maybe 是單子的一例。Haskell 中把單子定義成一個 type class：
class Monad m where (>>=) :: m a -> (a -> m b) -> m b return :: a -> m a對任一個型別建構元 m, 如果我們能定義出 >>= 和 return 兩個函數，並滿足後述的一些條件，m 就是一個單子。對 type class 我們不在此解釋太多，只需知道這是 Haskell 允許我們重載 (overload) >>= 和 return 等符號、使許多型別的類似函數可以用同一組符號表示的機制就可以了。型別 m a 代表一個「結果為型別 a 的運算」，運算過程中可能產生單子 m 希望描述的副作用，如同 Maybe a 用來表示一個結果是 a, 但可能會產生例外的運算。函數return 把一個型別為 a 的值「提升」到 m a. 在 Maybe 的例子中，return 就是 Just. 函數>>= 則是提升到 m 之上的函數應用，左手邊是一個 m a，右手邊是一個從 a 到 m b 的函數；x >>= f 大致上的意思是執行 x 代表的運算，如果得到一個型別是 a 的值，把他傳給f. 結果的型別是 m b. 我們等下會看到更多單子的例子。
上述的解釋是稍稍簡化過的版本。目前 Haskell 的 Monad class 中另有兩個 method, 在此省略不談。採用 return 和 >>= 兩個 method 是 Haskell 為適合程式寫作選擇的設計。在更早的單子文獻中則用 return, map, join 三個運算元。這兩種定義是等價的。
單子定律單子的 return 與 >>= 兩個函數當然不能隨便寫。 型別建構元 m 要稱為單子，return 和>>= 須滿足下面三個定律：
- (return x) >>= f == f x,
- m >>= return == m,
- (m >>= f) >>= g == m >>= (\x -> f x >>= g).
頭兩條定律談到 return 的合理行為。第一條確保 return x 不含副作用： (return x) >>= f 應該和把 x 直接丟給 f 一樣。第二條定律中，把 m 的結果直接 return 回來並不改變其值。第三條是 >>= 的遞移律，可和函數組合的定義比較：
f (g x) = (f . g) x這條定律確保 >>= 的行為確實類似函數應用。
讀者可以檢查一下 Maybe 的 return 與 >>= 確實滿足這三條定律。目前 Haskell 本身無法自動檢查這三條定律，只能希望程式員遵守。程式員照理說也希望所有單子都滿足這些定律，以便於程式的推理分析。不幸的是確實有些很有用的「單子」為了效率因素會在某些情況下違反單子定律。以後有機會再談。
串列單子我們進一步擴充算式，添加一個 Or 運算元：
data Expr = Num Int | Neg Expr | Add Expr Expr | Div Expr Expr | Or Expr Expr此處的Or 倒不是邏輯上的「或」，而是非確定(non-deterministic)運算：Or e1 e2 的值可能是 e1, 也可能是 e2. 非確定運算元有點牽強地用在這裡僅是為了舉例，但在程式語言的應用中，需要處理非確定性的情形並不少見。例如一個文法 parse 一段句子，可能有不只一種 parse 的方法。我們會需要寫程式找出所有 parse.
我們希望找出一個算式所有可能的值，因此 eval 的型別改為 Expr -> [Int]，將所有可能的值放在一個串列中。串列是另一個單子的常見例子。函數 return 將一個型別為 a 的值 x提升成串列， 自然的選擇是傳回 [x], 因為 x 是自己的唯一值：
return :: a -> [a] return x = [x]假設 xs 是一個型別為 [a] 的串列，函數 f 拿一個 a, 將所有的可能結果放在型別為 [b] 的串列中。我們如何把 xs 餵給 f 呢？答案是先用 f 處理 xs 裡的每個元素，再把結果接起來：
(>>=) :: [a] -> (a -> [b]) -> [b] xs >>= f = concat (map f xs)寫成 list comprehension 可能更清楚: xs >>= f = [y | x <- xs, y <- f x]. 注意return 和 >>= 的型別分別是 a -> [a] 和 [a] -> (a -> [b]) -> [b], 符合 Monad class 的要求。（此處為了說明而標上型別。在 Haskell 中，由於型別已在 class 宣告中給過一次，在此是不加型別的。）
函數 eval 該怎麼處理新加的 Or 呢？Or e1 e2 的所有可能值是 e1 的所有可能值以及e2 的所有可能值，所以：
eval (Or e1 e2) = eval e1 ++ eval e2而對於 Num, Neg, Add 等情況，很幸運地，eval 可在不修改的情況下直接使用新的 return與 >>= 定義。例如
eval (Add (Or (Num 1) (Num 3)) (Or (Num 3) (Num 4)))的值會是 [4,5,6,7].
至於 Div 呢？函數 eval 的 Div 條款用了一個 mzero, 當時的值是 Nothing. 在此處只要把mzero 設定為 [] 就可以了 -- 分母為零時 Div 沒有值，因此我們傳回空串列。
串列單子在此處用來表達非確定性計算，有時當我們說「非確定性單子」時，指的是串列。在 Haskell 這種緩式語言中，串列尾端在需要時才會算出來，因此 eval 的行為像是回溯 (backtracking)：先用第一個值去試試看，如果可用就一直使用下去，如果失敗則回溯回來換成下一個值。讀者可以試試看 eval (Div (Num 4) (Add (Neg (Num 2)) (Or (Num 0) (Num 2)))) (4 / (-2 + (0 OR 2))) 是怎麼算出來的。有人也因此把串列稱作「回溯單子」。但不論非確定性或回溯還另有其他資料結構可表示（有的也許會特別強調公平性或效率等等因素）。此處我們還是簡單地稱之為串列單子。
MonadPlusMaybe 與串列不僅是單子，他們都屬於單子的一個子類別。 如果在單子 m 上能定義出一個「加法」運算元和一個「零」，並滿足後述的一些條件，我們稱之為 MonadPlus:
class (Monad m) => MonadPlus m where mzero :: m a mplus :: m a -> m a -> m amzero 和 mplus 至少應形成一個么半群(monoid)：
- mzero `mplus` m = m,
- m `mplus` mzero = m,
- (m `mplus`n) `mplus` k = m `mplus` (n `mplus` k).
至於一些其他的條件則還沒有定論，可參照 Haskell Wiki 上的說明。
操作上的直觀解釋是：mzero 代表一個沒有結果的空運算，mplus 則把兩個運算結果合併起來。串列的 mzero 和 mplus 分別是 [] 和 ++. Maybe 的 mzero 是 Nothing, mplus 則可以定義為：
Nothing `mplus` m = m (Just x) `mplus` m = Just x也就是傳回第一個（最左邊的一個）結果。
模組化的功能代換我們回顧一下最初的例子 --- 只有 Num, Neg, 和 Add 三個條款的 eval 函數：
eval :: Monad m => Expr -> m Int eval (Num n) = return n eval (Neg e) = eval e >>= (\v -> return (-v)) eval (Add e1 e2) = eval e1 >>= \v1 -> eval e2 >>= \v2 -> return (v1 + v2)函數 eval 最一般的型別只要求 m 是某個單子。如果我們把 return 擦掉，把每個 m >>= f代換為 f m，換句話說，把 return 和 >>= 分別定義為：
return x = x m >>= f = f m稍微化簡一下，我們又得到了那個最簡單、沒有副作用的程式：
eval (Num n) = n eval (Neg e) = - (eval e) eval (Add e1 e2) = eval e1 + eval e2這時 m a = a. 這也是一個單子，讀者可檢查滿足這個定義滿足單子三定律。我們稱之為「單位單子 (identity monad)」。1 單位單子是最基礎、不含副作用的單子。
我們可以把單子視為一種允許我們模組化地加入、抽換程式功能的方法。從上面的程式出發，如果我們為 eval 加上一個處理 Div 的條款, 由於其中用到了 mzero, Haskell 的型別系統會知道 m 必須是一個 MonadPlus:
eval :: MonadPlus m => Expr -> m Int我們不能再選 m a = a 了。滿足 MonadPlus 要求的型別很多，Maybe 是其中的一個。
如果我們再加上一個 eval (Or ..) 條款（其中的 ++ 必須寫成 mplus），eval 最通用的型別仍不變。我們還是可以讓 m = Maybe，只是 Maybe 的 mplus 在碰到兩個 Just 時會選擇左邊的結果。而如果我們把 m a 選為 [a]，同一個程式便會傳回所有結果形成的串列。
以後我們會看到更多這種例子：每個種類的單子提供一類副作用，如本文的例外、非確定性，或著環境、狀態 (state)、輸出入、續繼 (continuation)... Haskell 能由程式中使用的 method 判定我們需要哪一種單子，我們則可再選用符合條件的單子實際做出這些副作用。各種副作用可以這種模組化的方式加入程式中。
下次我們再看看其他常用的單子。
附註- 可惜在 Haskell 中若要使用 type class, 我們必須定一個新的資料型別：data Id a = Id a。這麼一來 return 和 >>= 的定義都會多一個資料建構元，看來不那麼清楚。此處先不談這點。
- Philip Wadler. Monads for functional programming. In Marktoberdorf Summer School on Program Design Calculi, August 1992
- Ralf Hinze. Deriving backtracking monad transformers. ICFP 2000.
- Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, and Amr Sabry. Backtracking, interleaving, and terminating monad transformers. ICFP 2005.