單子 (函數式編程)

在函數式編程中，單子（monad）是一種抽象，它允許以泛型方式構造程序。支持它的語言可以使用單子來抽象出程序邏輯需要的樣板代碼。為了達成這個目標，單子提供它們自己的數據類型（每種類型的單子都有特定的類型），它表示一種特殊形式計算，與之在一起的有兩個過程，一個過程用來包裝單子內「任何」基本類型的值（產生單子值），另一個過程用來函數複合 (電腦科學)那些輸出單子值的函數（叫做單子函數）。

單子的概念和術語二者最初都來自範疇論，這裡的單子被定義為具有額外結構的函子。開始於1980年代晚期和1990年代早期的研究，確立了單子可以將看似完全不同的電腦科學問題置於一個統一的函數式模型之下。範疇論還提供了叫做單子定律的一些形式要求，任何單子都應當滿足它並可以用它來驗證單子代碼。

通過單子，編程者可以把複雜的函數序列變成簡潔的管道，它抽象出了輔助數據管理、控制流或副作用。單子可以簡化範圍寬廣的問題，比如處理潛在未定義值（通過`Maybe`單子），或將值保持在一個靈活而形式正確的列表中（使用`List`單子）。因為單子使得某種計算的語義明確，它們還可以用來實現便捷的語言特徵。一些語言比如Haskell，甚至在它們的核心庫中為通用單子結構提供預製的定義和常用實例。

## 概述

單子可以通過定義一個類型構造子`m`和兩個運算即`unit`和`bind`來建立。C. A. McCann解釋說：「對於單子`m`，類型`m a`的值，表示可以在這個單子上下文內訪問的類型`a`的值。」

- `unit`（也叫做`return`），接受一個類型`a`的值，把它們包裝成使用這個類型構造子建造的類型`m a`的「單子值」。
- bind（典型的表示為`>>=`），接受一個在類型`a`上的函數`f`，並應用`f`於去包裝的值`a`，並可把`f`的結果處理成單體值`m a`。在後面的從函子推導章節有可作為替代的等價構造，使用`join`函數替代了`bind`算子。

通過這些元素，編程者可以複合出一個函數調用的序列（管道），在一個表達式中通過一些bind算子把它們連結起來。每個函數調用轉變它的輸入普通類型值，而bind算子處理返回的單子值，它被填入到序列中下一個步驟。

在每對複合的函數調用之間，bind算子`>>=`可以向單子值`m a`注入在函數`f`內不可訪問的額外資訊，並沿著管道傳遞下去。它還可進行細緻的執行流控制，比如只在特定條件下調用函數，或以特定次序執行函數調用。

## Maybe單子例子

下面的快捷偽代碼例子展示編程者使用單子的動機。未定義的值或運算，是健壯的軟體應當準備好做出優雅處理的一個特殊問題。

完成這個目標的第一步是建立一個可選類型，它標記一個值，要麼承載某個類型`T`（`T`可以是任何類型）的值，要麼沒有承載值。新的類型將叫做`Maybe T`，而這個類型的值，可以包含要麼類型`T`的值，要麼空值`Nothing`。類型`T`的值`x`，若定義並用於`Maybe`上下文，則叫做`Just x`。這麼做是通過區分一個變量，是處在承載了有定義的值的情況，還是處在未定義的情況，來避免混淆。

```haskell
data Maybe T = Just T | Nothing
```

`Maybe T`可以被理解為一種「包裝」類型，把類型`T`包裝成具有內建異常處理的一種新類型，儘管不承載關於異常成因的資訊。

在下列的偽代碼中，前綴著`m`的變量有針對某種類型`T`的類型`Maybe T`。例如，如果變量`mx`包含一個值，那麼它是`Just x`，這裡的變量`x`有類型`T`。`λx -> ...`是匿名函數，它的形式參數`x`的類型是推論而來，而`∘`是函數複合算子。

另一個改進是，函數通過`Maybe`類型，能管理簡單的檢查異常：一旦某個步驟失敗，就短路並返回`Nothing`；如果計算成功則，返回正確的值而無需再評論。

加法函數`add`，在做二個`Maybe`值`mx`和`my`的加法之時，就實現了上述改進，它可以如下這樣定義：

```haskell
add :: Maybe Number -> Maybe Number -> Maybe Number
add mx my  = ...
    if mx is Nothing then
        ... Nothing
    else if my is Nothing then
        ... Nothing
    else
        ... Just (x + y)
```

書寫函數來逐一處理`Maybe`值的各種情況可能相當枯燥，並且隨著定義更多函數而變得更甚。將多個步驟連結起來的運算，是減輕這種狀況的一種方式，通過使用中綴算子如`mx >>= f`，甚至可以直觀的表示出，將每個步驟得出的（可能未定義的）結果，填入下一步驟之中。因為每個結果在技術上被插入到另一個函數之中，這個算子轉而接受一個函數作為一個形式參數。由於`add`已經指定了它的輸出類型，保持這個算子的靈活性，而接受輸出與其輸入不同類型的函數應當沒有什麼傷害：

```haskell
>>= :: Maybe T -> (T -> Maybe U) -> Maybe U
(mx >>= f) = ...
    if mx is (Just x) then
        ... f(x)    -- f返回类型Maybe U的定义值
    else
        ... Nothing -- f不返回值
```

在具有`>>=`可用時，`add`可以被精製為更緊湊的表述：

```haskell
add mx my  = 
    mx >>= λx ->
        (my >>= λy ->
            Just (x + y))
```

這更加簡潔，而一點額外的分析就能揭示出它的強大之處。首先，`Just`在`add`中扮演的唯一角色，就是將一個低層值標記（tag）為也是`Maybe`值。為了強調`Just`通過包裝低層值而在其上施加作用，它也可以被精製為函數，比如叫做`eta`：

```haskell
eta :: T -> Maybe T
eta x  =  Just x
```

整體情況是這兩個函數`>>=`和`eta`被設計用來簡化`add`，但是他們明顯的不以任何方式依賴於`add`的細節，只是有關於`Maybe`類型。這些函數事實上可以應用於`Maybe`類型的任何值和函數，不管底層的值的類型。例如，下面是來自Kleene三值邏輯的一個簡潔的NOT算子，也使用了相同的函數來自動化未定義值：

```haskell
trinot :: Maybe Boolean -> Maybe Boolean
trinot mp  =  mp >>= λp -> (eta ∘ not) p
```

可以看出來`Maybe`類型，和與之一起的`>>=`和`eta`，形成了單子。儘管其他單子會具體化不同的邏輯過程，而且一些單子可能有額外的屬性，它們都有三個類似的構件（直接或間接的）服從這個例子的綱要。

## 定義

對函數式編程中的單子的更常用的定義，比如在上面的例子中用到的，實際上基於了Kleisli範疇，而非範疇論的標準定義。兩個構造可以證明在數學上是等價的，任何定義都能產生有效的單子。給定任何良好定義的基本類型`T`、`U`，單子構成自三個部份：

- 類型構造子 `M`，建造一個單子類型`M T`Semantically, M is not trivial and represents an endofunctor over the category of all well-typed values: $M: \mathit{Val} \to \mathit{Val}$
- 類型轉換子，經常叫做unit或return，將一個對象`x`嵌入到單子中：
- `unit(x) :: T -> M T`While a (parametrically polymorphic) function in programming terms, (often called η in category theory) is mathematically a natural transformation, which maps between functors: $\eta_{A} : \mathrm{id}(\mathit{Val}_{A}) \to M(\mathit{Val}_{A})$
- 組合子，典型的叫做bind（約束變量的那個bind），並表示為中綴算子`>>=`，去包裝一個單體變量，接著把它插入到一個單體函數/表達式之中，結果為一個新的單體值：
- `(mx >>= f) :: (M T, T -> M U) -> M U`bind, on the other hand, is not a natural transformation in category theory, but rather an extension $-^{*}$ that lifts a mapping (from values to computations) into a morphism between computations: $\forall f : \mathit{Val}_{A} \to M(\mathit{Val}_{B}), f^{*}: M(\mathit{Val}_{A}) \to M(\mathit{Val}_{B})$

但要完全具備單子資格，這三部份還必須遵守一些定律：

- `unit(a) >>= λx -> f(x) '''&harr;''' f(a)`
- `ma >>= λx -> unit(x) '''&harr;''' ma`
- `ma >>= λx -> (f(x) >>= λy -> g(y)) '''&harr;''' (ma >>= λx -> f(x)) >>= λy -> g(y)`

在代數上，這意味任何單子都引起一個範疇（叫做Kleisli範疇）和在函子（從值到計算）的範疇上的么半群，具有單子複合作為二元算子和`unit`作為單位元。

單子為有價值的技術提供了機會，超出了只是組織程序邏輯。單子可以為有用的語法特徵奠定基礎工作，而它們的高級和數學本質能實現重大的抽象。

## 語法糖do表示法

儘管公開的使用`bind`通常就行得通，很多編程者偏好模仿指令式語句的語法（在Haskell中稱為「do表示法」，在OCaml中稱為「perform表示法」，在F♯中稱為「計算表達式」，在Scala中稱為「for推導式」）。這只是將單子管道偽裝成代碼塊的語法糖；編譯器會悄悄的將這些表達式轉換成底層的函數式代碼。

將上述的`Maybe`單子例子中的`add`函數偽碼轉換成Haskell代碼來用行動展示這個特徵。非單子版本的`add`用Haskell寫出來如下這樣：

```haskell
add mx my =
    case mx of
    Nothing -> Nothing
    Just x  -> case my of
               Nothing -> Nothing
               Just y  -> Just (x + y)
```

在使用單子的Haskell中，`return`是`unit`的標準名字，加上必須顯式處置的lambda表達式，即使多了這些技術，`Maybe`單子使得定義更加清晰：

```haskell
add mx my =
    mx >>= (\x ->
        my >>= (\y ->
            return (x + y)))
```

使用do表示法，可以進一步精煉成非常直觀的序列：

```haskell
add mx my = do
    x <- mx
    y <- my
    return (x + y)
```

甚至通用單子定律自身都可以用do表示法來表達：

```haskell
do { x <- return v; f x }            ==  do { f v }
do { x <- m; return x }              ==  do { m }
do { y <- do { x <- m; f x }; g y }  ==  do { x <- m; y <- f x; g y }
```

儘管方便，開發者應當記住這種塊風格只是語法上的並可外觀上替代為單子(甚至非單子的CPS）表達式。使用`bind`來表達單子管道仍在很多情況下是更加清晰的，一些函數式編程擁戴者提議，由於塊風格允許初學者存續來自指令式編程的習慣，應當避免預設的而只在明顯更優越的時候使用它。

## 歷史

在編程中術語「單子」（monad）實際上最早可追溯至APL和J程式語言，它們趨向於是純函數式的。但是，在這些語言中，「monad」僅是只接受一個形式參數的函數的簡稱（有二個形式參數的函數叫做「dyad」）。

數學家Roger Godement最初在1950年代晚期公式化單子概念（起綽號為「標準構造」），而術語「monad」成為主導要歸功於範疇學家桑德斯·麥克蘭恩。但是，上述的使用bind定義的形式，最初由數學家Heinrich Kleisli在1965年描述，用來證明任何單子都可以特徵化為在兩個（協變）函子之間的伴隨。

開始於1980年代，單子模式的模糊概念在電腦科學社區中浮出水面。依據程式語言研究者Philip Wadler，電腦科學家John C. Reynolds於1970年代和1980年代早期，在他討論傳遞續體風格的價值的時候，預見到了它的一些方面，範疇論作為形式語義學的豐富來源，和在值和計算之間的類型區別。研究性語言Opal，它活躍設計直到1990年，還有效的將I/O基於在單子類型之上，但是這個聯繫在當時沒有實現。

電腦科學家Eugenio Moggi最早明確的將範疇論的單子聯繫於函數式編程，在1989年於討論會論文之中，隨後在1991年還有更加精製的期刊提交。在早期的工作中，一些電腦科學家使用範疇論推進為lambda演算提供語義。Moggi的關鍵洞察是真實世界程序不只是從值到另外的值的函數，而是形成在這些值之上計算的變換。在用範疇論術語形式化的時候，這導致的結果是單子作為表示這些計算的結構。

其他一些人以這個想法為基礎並進行了推廣，包括Philip Wadler和Simon Peyton Jones，二者都參與了Haskell規定。特別是，Haskell直到v1.2一直使用有問題的「惰性流」模型來將I/O調和於惰性求值，然後切換到了更靈活的單子接口。Haskell社區繼續將單子應用於函數式編程的很多問題中，使用Haskell工作的研究者最終將單子模式推廣成廣泛的結構層級，包括應用式函子和箭頭 (電腦科學)。

首先，使用單子的編程很大程度上局限於Haskell及其派生者，但是由於函數式編程已經影響了其他編程范型，很多語言結合了單子模式（不這麼稱呼的話也在精神上）。其公式化現已存在於Scheme、Perl、Python、Racket、Clojure、Scala和F#之中，並已經被考慮用於新的ML標準。

## 用途

單子模式的價值超出了只是壓縮代碼和提供到數序推理的聯繫。不管開發者採用的語言或預設編程范型是什麼，遵從單子模式都會帶來純函數式編程的很多利益。通過實化特定種類的計算，單子不僅封裝了這個計算模式的冗長細節，而且它以聲明式方式來這麼做，增進了代碼清晰性。因為單子值所顯式代表的不只是計算出的值，而是計算出的作用（effect），單子表達式在參照透明性上可以被替代為它們的值，非常像純表達式能做到的那樣，允許了基於重寫的很多技術和優化。

典型的，編程者會使用`bind`來把單子函數連結成一個序列，這導致了一些人把單子描述為「可編程的分號」，參照眾多指令式語言使用分號來分割語句。但是，需要強調單子實際上不確定計算的次序；甚至在使用它們作為中心特徵的語言中，更簡單的函數複合可以安排程序內的步驟。單子的一般效用準確的說在於簡化程序的結構並通過抽象來增進關注點分離。

單子結構還可以被看作修飾模式的獨特的數學和編譯時間變種。一些單子可以傳載對函數是不可訪問的額外數據，而且一些單子甚至具有在執行上的更細緻控制，例如只在特定條件下調用一個函數。因為它們讓應用程式員實現領域邏輯，而卸載樣板代碼至預先開發的模塊，單子甚至可以當作面向方面編程的工具。

單子的另一個值得注意的用途，是在其他方面都純函數式的代碼中，隔離副作用，比如輸入/輸出或可變的狀態 (電腦科學)。即使純函數式語言仍可以不使用單子來實現這些「不純」計算，特別是通過對函數複合和續體傳遞風格（CPS）的錯綜複雜混合。但是使用單子，多數這些腳手架可以被抽象出去，本質上通過提取出在CPS代碼中每個反覆出現的模式併集束到一個獨特的單子之中。

如果一個語言預設的不支持單子，仍有可能實現這個模式，經常沒有多少困難。在從範疇論轉換成編程術語的時候，單子結構是概念 (泛型編程)並可以在支持限定的多態的等價特徵的任何語言中直接定義。一個概念在操作底層數據類型時保持對操作細節不可知的能力是強大的，然而單子的獨特特徵和嚴格行為將它們同其他概念區別開來。

## 分析

單子模式的利益之一是將數學上的精確性施加到編程邏輯上。不只是單子定律可以用來檢查實例的有效性，而且來自有關結構（比如函子）的特徵可以通過子類型來使用。

### 從函子推導

儘管在電腦科學中少見，可以直接使用範疇論，它定義單子為有二個額外自然變換的函子。作為開始，一個結構要求叫做map的高階函數（「泛函」）從而具備函子資格：

`map φ :: (a -> b) -> ma -> mb`

但是這不總是一個主要問題，尤其是在單子派生自預先存在的函子的時候，單子馬上就自動繼承`map`。出於歷史原因，在Haskell中這個`map`轉而叫做`fmap`。

單子的第一個變換實際上同於來自Kleisli三元組的`unit`，但是更密切的服從結構的層級，結果是`unit`特徵化一個應用式函子，這是在單子和基本函子之間的中間結構。在應用式的上下文中，`unit`有時被稱為`pure`，但是這仍是相同的函數。在這個構造中有不同的地方是定律`unit`必須滿足；因為`bind`未定義，這個約束轉而依據`map`給出：

`(unit ∘ φ) x ↔ ((map φ) ∘ unit) x`

從應用式函子到單子的最後跳躍來自於第二個變換`join`函數，在範疇論中這個自然變換通常叫做μ，它扁平化單子的嵌套應用：

`join(mma) :: M (M T) -> M T`

作為特徵性函數，`join`必須還滿足三個單子定律的變體：

`join ∘ (map join) mmma ↔ (join ∘ join) mmma ↔ ma`

`join ∘ (map unit) ma ↔ (join ∘ unit) ma ↔ ma`

`join ∘ (map map φ) mma ↔ ((map φ) ∘ join) mma ↔ mb`

不管開發者是否直接定義單子或Kleisli三元組，底層的結構都是相同的，二者形式可以輕易的相互導出：

`(map φ) ma ↔ ma >>= (unit ∘ φ)`

`join(mma) ↔ mma >>= id`

`ma >>= f ↔ (join ∘ (map f)) ma`

### 例子：List單子

<image>

`List`單子天然的展示了如何手工的從更簡單的函子導出單子。在很多語言中，列表結構與很多基本特徵一起是預定義的，所以假定`List`類型構造子和`append`算子（用中綴表示法表示為`++`）已經存在於這裡了。

將一個平常的值嵌入到列表中在多數語言中也是微不足道的：

`unit(x) = [x]`

自此，通過列表推導式迭代的應用一個函數，看起來就是對`bind`的一個容易的選擇，從而將列錶轉換成完全的單子。這個方式的困難在於`bind`預期一個單子函數，它在這種情況下會輸出列表自身；隨著更多函數的應用，嵌套的列表的層次會累加，要求不止一個基本推導式。

但是，在整個列表上應用任何「簡單」函數的過程，也就是`map`，就直截了當了：

`(map φ) xlist = [ φ(x1), φ(x2), ..., φ(xn) ]`

現在，這兩個過程已經將`List`提升為應用式函子。要完全具備單子資格，只需要`join`的一個正確的表示法來扁平化重複的結構，但是對於列表，這意味著去包裝一個外部列表來包含著值的那些內部列表：

`join(xlistlist) = join([xlist1, xlist2, ..., xlistn])`` = xlist1 ++ xlist2 ++ ... ++ xlistn`

結果的單子不只是一個列表，而且在應用函數的時候可以自動調整大小和壓縮自身。`bind`現在可以從一個公式導出，接著被用來通過單子函數的管道向`List`填入值：

`(xlist >>= f) = join ∘ (map f) xlist`

這種單子列表的一個應用是表示非確定性算法。`List`可以持有一個演算法中所有執行路徑的結果，接著每一步驟壓縮自身來忘記那一步導致了這個結果（有時這是同確定性、窮舉演算法的重要區別）。另一利益是檢查可以嵌入到單子中；特定路徑可以透明的在它們第一個失敗點上被剪除，而不需要重寫管道上的函數。

突出`List`的第二種情況是複合多值函數。例如，一個數的`n`次複數方根將產生`n`個不同複數，但是如果另個`m`方根接受了這些結果，最終複合出的`m•n`的值應當同一於一次`m•n`次方根的輸出。`List`完全自動化了這個問題的處置，壓縮來自每一步驟的結果成一個平坦的、數學上正確的列表。

## 更多例子

### IO單子（Haskell）

正如提及過的那樣，純粹的代碼不應有不可管理的副作用，但是不妨礙程序「顯式」的描述和管理各種作用。這個想法是Haskell的IO單子的中心，在這裡一個類型`IO a`的對象，可以被看作包含了程序外部的世界的當前狀態，並計算類型`a`的一個值。不計算值的計算，也就是過程，有著類型`IO ()`，它「計算」虛設值`()`。在編程者bind一個`IO`值到一個函數的時候，這個函數基於世界的場景（來自使用者的輸入、文件等）做出決定，接著產生反映新的世界狀態（程序輸出）的一個單子值。

例如，Haskell有一些函數作用在寬廣的文件系統之上，包括有檢查一個文件存在的一個函數和刪除一個文件的另一函數。二者的類型簽名是：

```haskell
doesFileExist :: FilePath -> IO Bool
removeFile :: FilePath -> IO ()
```

第一個函數關注一個給定文件是否真的存在，作為結果輸出一個布爾值於`IO`單子之內。第二個函數在另一方面，只關心在文件系統上的起到作用，所以對於`IO`容器它們的輸出為空。

`IO`不只限於文件I/O；它甚至允許用戶I/O，還有指令式語法糖，可以模仿典型的Hello World程序：

```haskell
main :: IO ()
main = do
    putStrLn "Hello, world!"
    putStrLn "What is your name, user?"
    name <- getLine
    putStrLn ("Nice to meet you, " ++ name ++ "!")
```

不加語法糖，代碼可以轉寫為如下單子管道（在Haskell中`>>`是`bind`的一種變體，用在只有單子作用是緊要的而底層結果可以丟棄的時候）：

```haskell
main :: IO ()
main =
    putStrLn "Hello, world!" >>
    putStrLn "What is your name, user?" >> 
    getLine >>= (\name ->
        putStrLn ("Nice to meet you, " ++ name ++ "!"))
```

### Writer單子（JavaScript）

另一個常見的情況是保存日誌文件或以其他方式報告程序的進度。有時，編程者想要記錄更特殊的技術數據用於以後的性能分析或調試。Writer單子可以通過生成逐步積累的輔助輸出來處理這些任務。

為了展示單子模式不局限於主要的函數式語言，這個例子用JavaScript實現了`Writer`單子。首先，陣列（具有嵌套的尾部）允許構造`Writer`類型為鍊表。底層的輸出值將位於這個陣列的位置0，而位置1將隱蔽的持有連成一鏈的一些輔助注釋：

```Javascript
const writer = [value, []];
```

定義`unit`是非常簡單的：

```Javascript
const unit = value => [value, []];
```

定義輸出具有調試注釋的`Writer`對象的簡單函數只需要`unit`：

```Javascript
const squared = x => [x * x, [`${x} was squared.`]];
const halved = x => [x / 2, [`${x} was halved.`]];
```

真正的單子仍需要`bind`，但是對於`Writer`，這簡單的相當於將函數的輸出附加至單子的鍊表：

```Javascript
const bind = (writer, transform) => {
    const [value, log] = writer;
    const [result, updates] = transform(value);
    return [result, log.concat(updates)];
};
```

樣例函數現在可以使用`bind`連結起來，但是定義單子複合的一個版本（這裡叫做`pipelog`）允許更加簡潔的應用這些函數：

```Javascript
const pipelog = (writer, ...transforms) =>
    transforms.reduce(bind, writer);
```

最終結果是在逐步計算和為以後審查而記錄之間的清晰的關注分離：

```Javascript
pipelog(unit(4), squared, halved);
// 结果的writer对象 = [8, ['4 was squared.', '16 was halved.']]
```

## 外部連結

HaskellWiki參考：

- " All About Monads " (originally by Jeff Newbern) — A comprehensive discussion of all the common monads and how they work in Haskell; includes the "mechanized assembly line" analogy.
- " Typeclassopedia " (originally by Brent Yorgey) — A detailed exposition of how the leading typeclasses in Haskell, including monads, interrelate.

教程：

- " A Fistful of Monads " (from the online Haskell textbook Learn You a Haskell for Great Good! — A chapter introducing monads from the starting-point of functor and applicative functor typeclasses, including examples.
- " For a Few Monads More " — A second chapter explaining more details and examples, including a `Probability` monad for Markov chains.
- " Functors, Applicatives, And Monads In Pictures (by Aditya Bhargava) — A quick, humorous, and visual tutorial on monads.

個案：

- " UNIX pipes as IO monads " (by Oleg Kiselyov) — A short essay explaining how Unix pipes are effectively monadic.
- Pro Scala: Monadic Design Patterns for the Web (by Gregory Meredith) — An unpublished, full-length manuscript on how to improve many facets of web development in Scala with monads.