单子_(函数式编程)

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

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

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

## 概述

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

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

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

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

### 例子：Maybe 單子

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

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

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

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

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

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

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

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

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

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

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

　
:

## 定義

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

* 類型構造子 `M`，建造一個單子類型 `M T`
* 類型轉換子，經常叫做 **unit** 或 **return**，將一個物件 `x` 嵌入到單子中：
* 組合子，典型的叫做 **bind**（約束變數的那個 bind），並表示為中綴算子 `>>=`，去包裝一個單體變數，接著把它插入到一個單體函式 / 表達式之中，結果為一個新的單體值：

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

* `unit` 是 bind 的左單位元：
* `unit` 也是 bind 的右單位元:
* bind 本質上符合結合律：

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

## 用途

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

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

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

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

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

## 歷史

在編程中術語「單子」（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 標準。

## 分析

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

### 匯出自函子

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

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

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

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

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

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

### 例子：List 單子

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

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

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

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

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

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

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

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

## 技術

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

### 語法糖 do 表示法

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

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

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

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

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

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

## 更多例子

### IO 單子（Haskell）

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

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

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

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

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

### Writer 單子（JavaScript）

另一個常見的情況是儲存紀錄檔檔案或以其他方式報告程式的進度。有時，編程者想要記錄更特殊的技術資料用於以後的效能分析或除錯。**Writer 單子**可以通過生成逐步積累的輔助輸出來處理這些任務。

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

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

定義輸出具有除錯注釋的 `Writer` 物件的簡單函式只需要 `unit`：

真正的單子仍需要 `bind`，但是對於 `Writer`，這簡單的相當於將函式的輸出附加至單子的連結串列：

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

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

## 註解

## 參照

## 參見

* 類型類
* 函子
* 應用式函子

## 外部連結

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.