for the few of us.

對於學函數語言的人來說，關於單子 (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 -> Nothing

Add 的情況下，程式碼看來更冗長了些：

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 和 >>= 須滿足下面三個定律：

1. (return x) >>= f == f x,
2. m >>= return == m,
3. (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))) 是怎麼算出來的。有人也因此把串列稱作「回溯單子」。但不論非確定性或回溯還另有其他資料結構可表示（有的也許會特別強調公平性或效率等等因素）。此處我們還是簡單地稱之為串列單子。

MonadPlus

Maybe 與串列不僅是單子，他們都屬於單子的一個子類別。 如果在單子 m 上能定義出一個「加法」運算元和一個「零」，並滿足後述的一些條件，我們稱之為 MonadPlus:

class (Monad m) => MonadPlus m where
  mzero :: m a
  mplus :: m a -> m a -> m a

mzero 和 mplus 至少應形成一個么半群(monoid)：

1. mzero `mplus` m = m,
2. m `mplus` mzero = m,
3. (m `mplus`n) `mplus` k = m `mplus` (n `mplus` k).

至於一些其他的條件則還沒有定論，可參照 Haskell Wiki 上的說明。

操作上的直觀解釋是：mzero 代表一個沒有結果的空運算，mplus 則把兩個運算結果合併起來。串列的 mzero 和 mplus 分別是 [] 和 ++. Maybe 的 mzero 是 Nothing, mplus 則可以定義為：

Nothing `mplus` m = Nothing
(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)」。¹ 單位單子是最基礎、不含副作用的單子。

我們可以把單子視為一種允許我們模組化地加入、抽換程式功能的方法。從上面的程式出發，如果我們為 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 判定我們需要哪一種單子，我們則可再選用符合條件的單子實際做出這些副作用。各種副作用可以這種模組化的方式加入程式中。

下次我們再看看其他常用的單子。

附註

1. 可惜在 Haskell 中若要使用 type class, 我們必須定一個新的資料型別：data Id a = Id a。這麼一來 return 和 >>= 的定義都會多一個資料建構元，看來不那麼清楚。此處先不談這點。

參考資料與延伸閱讀

1. Philip Wadler. Monads for functional programming. In Marktoberdorf Summer School on Program Design Calculi, August 1992
2. Ralf Hinze. Deriving backtracking monad transformers. ICFP 2000.
3. Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, and Amr Sabry. Backtracking, interleaving, and terminating monad transformers. ICFP 2005.