另一個 Haskell 教程/單子
| Haskell | |
|---|---|
| |
| 另一個 Haskell 教程 | |
| 前言 | |
| 簡介 | |
| 入門 | |
| 語言基礎 (解決方案) | |
| 型別基礎 (解決方案) | |
| IO (解決方案) | |
| 模組 (解決方案) | |
| 高階語言 (解決方案) | |
| 高階型別 (解決方案) | |
| 單子 (解決方案) | |
| 高階 IO | |
| 遞迴 | |
| 複雜度 | |
學習 Haskell 時最難掌握的概念是理解和使用單子。我們可以在這裡區分兩個子部分：(1) 學習如何使用現有的單子，以及 (2) 學習如何編寫新的單子。如果你想使用 Haskell，你必須學習如何使用現有的單子。另一方面，只有當你想要成為“超級 Haskell 大師”時，你才需要學習編寫自己的單子。不過，如果你能掌握編寫自己的單子，那麼在 Haskell 中程式設計會更加愉快。
到目前為止，我們已經看到了單子的兩種用法。第一種用法是 IO 操作：我們已經看到，透過使用單子，我們可以擺脫困擾“真實世界” IO 解決方案的問題，如在“IO”章節中所述。第二種用法是在“類-計算”部分中表示不同型別的計算。在這兩種情況下，我們都需要一種方法來對操作進行排序，並發現一個足夠定義（至少對於計算而言）是
class Computation c where
success :: a -> c a
failure :: String -> c a
augment :: c a -> (a -> c b) -> c b
combine :: c a -> c a -> c a
讓我們看看這個定義是否能夠讓我們執行 IO。本質上，我們需要一種方法來表示從一個操作中取出一個值，並對其執行一些新的操作（如“函式-IO”部分中的示例，稍微改寫一下）
main = do s <- readFile "somefile" putStrLn (show (f s))
但這正是 augment 的作用。使用 augment，我們可以將上面的程式碼寫成
main = -- note the lack of a "do" readFile "somefile" `augment` \s -> putStrLn (show (f s))
這似乎已經足夠了。事實上，它比我們需要的還要多。
單子的定義是我們 Computation 類的簡化版本。Monad 類有四種方法（但第四種方法可以用第三種方法來定義）
class Monad m where
return :: a -> m a
fail :: String -> m a
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
在這個定義中，return 等效於我們的 success；fail 等效於我們的 failure；>>=（讀作：“繫結”）等效於我們的 augment。>>（讀作：“然後”）方法只是 >>= 的一個版本，它忽略了 a。這將被證明是有用的；儘管如前所述，它可以根據 >>= 來定義
a >> x = a >>= \_ -> x
我們已經暗示單子與 do 語法之間存在聯絡。在這裡，我們使這種關係具體化。do 語法實際上沒有任何魔法之處——它只是單子操作的“語法糖”。
如前所述，使用我們的 Computation 類，我們可以將上面的程式定義為
main =
readFile "somefile" `augment` \s ->
putStrLn (show (f s))
但我們現在知道在單子世界中 augment 被稱為 >>=。因此，此程式實際上讀取的是
main =
readFile "somefile" >>= \s ->
putStrLn (show (f s))
在這一點上，這完全是有效的 Haskell：如果你定義了一個函式 f :: Show a => String -> a，你就可以編譯並執行這個程式）
這表明我們可以將
x <- f g x
轉換為 f >>= \x -> g x。這正是編譯器所做的。如果我們不使用隱式佈局（參見有關“佈局”部分的說明，瞭解如何執行此操作），那麼談論 do 會變得更容易。有四個轉換規則
do {e}→edo {e; es}→e >> do {es}do {let decls; es}→let decls in do {es}do {p <- e; es}→let ok p = do {es} ; ok _ = fail "..." in e >>= ok
同樣，我們將逐一詳細說明這些規則
第一個轉換規則 do {e} → e 指出（正如我們之前所說）在執行單個操作時，使用或不使用 do 是無關緊要的。這本質上是 do 的歸納定義的基例。基例有一個操作（這裡就是 e）；另外三個轉換規則處理存在多個操作的情況。
這表明 do {e; es} → e >> do {es}。這告訴我們在有一個操作（e）後跟一個操作列表（es）時該怎麼做。在這裡，我們使用的是之前定義的 >> 函式。此規則只是簡單地指出要 do {e; es}，我們首先執行操作 e，丟棄結果，然後 do es。
例如，如果 e 是某個字串 s 的 putStrLn s，那麼 do {e; es} 的轉換就是執行 e（即列印字串），然後 do es。這顯然是我們想要的。
這表明 do {let decls; es} → let decls in do {es}。此規則告訴我們如何處理 do 語句中的 let。我們將 let 中的宣告提升出來，並 do 宣告之後的任何內容。
這說明 do {p <- e; es} → let ok p = do {es} ; ok _ = fail "..." in e >>= ok。同樣地，這段程式碼的作用並不十分明瞭。然而，該規則的另一種等價形式是：do {p <- e; es} → e >>= \p -> es。在這裡，我們可以清楚地看到發生了什麼。我們執行操作 e，並將結果傳遞給 es，但首先將結果命名為 p。
複雜定義的原因在於，p 不僅僅是一個變數，它可以是一個複雜的模式。例如，以下程式碼是有效的
foo = do ('a':'b':'c':x:xs) <- getLine
putStrLn (x:xs)
在這裡，我們假設操作 getLine 的結果將以字串 "abc" 開頭，並且至少包含一個額外的字元。問題在於，如果模式匹配失敗，應該發生什麼。編譯器可以像往常一樣簡單地丟擲一個錯誤，用於失敗的模式匹配。但是，由於我們是在一個單子中，我們可以訪問一個特殊的 fail 函式，我們更傾向於使用該函式而不是 "catch all" 的 error 函式來失敗。因此，根據定義，翻譯允許編譯器使用適當的錯誤訊息填充 ...，以說明模式匹配失敗。除此之外，這兩個定義是等效的。
所有單子都必須遵守三個規則，稱為 "單子定律" (保證你的單子遵守這些規則是你的責任)。
return a >>= f≡f af >>= return≡ff >>= (\x -> g x >>= h)≡(f >>= g) >>= h
讓我們逐個看一下這些定律。
這說明 return a >>= f ≡ f a。假設我們將單子視為計算。這意味著，如果我們建立一個簡單的計算，它僅僅返回值 a，而不考慮其他任何事情 (這就是 return a 部分)；然後將它與其他計算 f 繫結在一起，那麼這等效於直接對 a 執行計算 f。
例如，假設 f 是函式 putStrLn，a 是字串 "Hello World"。該規則指出，將結果為 "Hello World" 的計算繫結到 putStrLn 與直接將它列印到螢幕上相同。這似乎很有道理。
在 do 符號中，該定律指出以下兩個程式是等效的
law1a = do x <- return a f x law1b = do f a
第二個單子定律指出，對於某個計算 f，f >>= return ≡ f。換句話說，該定律指出，如果我們執行計算 f，然後將結果傳遞給簡單的 return 函式，那麼我們所做的只是執行了該計算。
該定律必須成立應該很明顯。要了解這一點，可以將 f 視為 getLine (從鍵盤讀取字串)。該定律指出，讀取字串然後返回讀取的值與僅僅讀取字串是完全一樣的。
在 do 符號中，該定律指出以下兩個程式是等效的
law2a = do x <- f return x law2b = do f
這說明 f >>= (\x -> g x >>= h) ≡ (f >>= g) >>= h。乍一看，該定律並不像其他兩個定律那樣容易理解。它本質上是單子的結合律。
注意
在單子世界之外，一個函式 是結合的，如果 。例如，+ 和 * 是結合的，因為對這些函式進行括號操作不會產生影響。另一方面，- 和 / 不是結合的，例如，。
如果我們忽略掉 lambda 的複雜性，我們會發現該定律指出：f >>= (g >>= h) ≡ (f >>= g) >>= h。該定律背後的直覺是，當我們將操作串聯在一起時，操作的組合方式無關緊要。
舉個具體的例子，令 f 為 getLine。令 g 為一個操作，它接收一個值作為輸入，將它列印到螢幕上，透過 getLine 讀取另一個字串，然後返回新讀取的字串。令 h 為 putStrLn。
讓我們考慮 (\x -> g x >>= h) 的作用。它接收一個名為 x 的值，並對其執行 g，將結果傳遞給 h。在本例中，這意味著它將接收一個值，列印它，讀取另一個值，然後列印該值。因此，整個定律的左側首先讀取一個字串，然後執行我們剛剛描述的操作。
另一方面，考慮 (f >>= g)。該操作從鍵盤讀取一個字串，列印它，然後讀取另一個字串，將新讀取的字串作為結果返回。當我們將它與定律右側的 h 繫結時，我們將得到一個操作，它執行 (f >>= g) 所描述的操作，然後列印結果。
顯然，這兩個操作是相同的。
雖然這個解釋非常複雜，定律的文字也相當複雜，但它真正的含義很簡單：如果我們有三個操作，並且以相同的順序組合它們，那麼我們將括號放在哪裡並不重要。其他部分僅僅是符號。
在 do 符號中，該定律指出以下兩個程式是等效的
law3a = do
x <- f
do y <- g x
h y
law3b = do
y <- do x <- f
g x
h y
我們可以建立的最簡單的單子之一是狀態傳遞單子。在 Haskell 中，所有狀態資訊通常必須作為引數顯式傳遞給函式。使用單子，我們可以有效地隱藏一些狀態資訊。
假設我們有一個型別為 a -> b 的函式 f，並且需要為該函式新增狀態。通常，如果狀態的型別為 state，我們可以透過將 f 的型別更改為 a -> state -> (state, b) 來對其進行編碼。也就是說，新版本的 f 接收原始型別的引數 a 和一個新的狀態引數。此外，除了返回型別為 b 的值之外，它還返回一個更新後的狀態，以元組的形式進行編碼。
例如，假設我們有一個二叉樹，定義如下
data Tree a = Leaf a | Branch (Tree a) (Tree a)
現在，我們可以編寫一個簡單的 map 函式，將某個函式應用於所有葉節點的值
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree f (Leaf a) = Leaf (f a)
mapTree f (Branch lhs rhs) =
Branch (mapTree f lhs) (mapTree f rhs)
這很好用，直到我們需要編寫一個對葉節點從左到右進行編號的函式。從某種意義上說，我們需要將狀態新增到 mapTree 函式中，該狀態跟蹤到目前為止我們已經編號了多少個葉節點。我們可以將該函式擴充套件為類似以下內容
mapTreeState :: (a -> state -> (state, b)) ->
Tree a -> state -> (state, Tree b)
mapTreeState f (Leaf a) state =
let (state', b) = f a state
in (state', Leaf b)
mapTreeState f (Branch lhs rhs) state =
let (state' , lhs') = mapTreeState f lhs state
(state'', rhs') = mapTreeState f rhs state'
in (state'', Branch lhs' rhs')
這開始變得有點笨拙，型別簽名也越來越難以理解。我們想要做的是抽象化掉狀態傳遞部分。也就是說，mapTree 和 mapTreeState 之間的區別在於：(1) 擴充套件後的 f 型別，(2) 我們用 -> state -> (state, Tree b) 替換了型別 -> Tree b。注意，這兩種型別都以完全相同的方式發生了變化。我們可以使用型別同義詞宣告來抽象化掉這些變化
type State st a = st -> (st, a)
為了配合該型別，我們編寫了兩個函式
returnState :: a -> State st a
returnState a = \st -> (st, a)
bindState :: State st a -> (a -> State st b) ->
State st b
bindState m k = \st ->
let (st', a) = m st
m' = k a
in m' st'
讓我們依次檢查一下這些函式。第一個函式 returnState 接收型別為 a 的值，並建立一個型別為 State st a 的值。如果我們將 st 視為狀態，並將型別為 a 的值視為值，那麼這是一個不改變狀態並返回值 a 的函式。
bindState 函式看起來非常類似於 mapTreeState 中的內部 let 宣告。它接收兩個引數。第一個引數是一個操作，它返回型別為 a 的值，並帶有狀態 st。第二個引數是一個函式，它接收該 a 並生成型別為 b 的值，並帶有相同的狀態。bindState 的結果本質上是將 a 轉換為 b 的結果。
bindState 的定義接受一個初始狀態 st。它首先將此狀態應用於名為 m 的 State st a 引數。這將返回一個新的狀態 st' 和一個值 a。然後，它讓函式 k 作用於 a，生成一個型別為 State st b 的值，稱為 m'。最後，我們用新的狀態 st' 執行 m'。
我們寫一個新函式 mapTreeStateM 並賦予它型別
mapTreeStateM :: (a -> State st b) -> Tree a -> State st (Tree b)
使用這些“管道”函式（returnState 和 bindState），我們可以編寫這個函式，而無需顯式地提及狀態。
mapTreeStateM f (Leaf a) = f a `bindState` \b -> returnState (Leaf b) mapTreeStateM f (Branch lhs rhs) = mapTreeStateM f lhs `bindState` \lhs' -> mapTreeStateM f rhs `bindState` \rhs' -> returnState (Branch lhs' rhs')
在 Leaf 的情況下，我們將 f 應用於 a，然後將結果與一個函式繫結，該函式接受結果並返回一個具有新值的 Leaf。
在 Branch 的情況下，我們在左側遞迴，將結果與一個函式繫結，該函式在右側遞迴，將結果與一個簡單的函式繫結，該函式返回新建立的 Branch。
正如你可能已經猜到，State st 是一個單子，returnState 類比於過載的 return 方法，而 bindState 類比於過載的 >>= 方法。事實上，我們可以驗證 State st a 遵守單子定律。
定律 1 規定：return a >>= f ≡ f a。讓我們在等式左側進行計算，代入我們的名字
returnState a `bindState` f
==>
\st -> let (st', a) = (returnState a) st
m' = f a
in m' st'
==>
\st -> let (st', a) = (\st -> (st, a)) st
in (f a) st'
==>
\st -> let (st', a) = (st, a)
in (f a) st'
==>
\st -> (f a) st
==>
f a
在第一步中，我們只是代入 bindState 的定義。在第二步中，我們簡化最後兩行並代入 returnState 的定義。在第三步中，我們將 st 應用於 lambda 函式。在第四步中，我們將 st' 重新命名為 st 並刪除 let。在最後一步中，我們進行 eta 簡化。
繼續 定律 2，我們需要證明 f >>= return ≡ f。這可以透過以下方式證明
f `bindState` returnState
==>
\st -> let (st', a) = f st
in (returnState a) st'
==>
\st -> let (st', a) = f st
in (\st -> (st, a)) st'
==>
\st -> let (st', a) = f st
in (st', a)
==>
\st -> f st
==>
f
最後，我們需要證明 State 遵守第三定律：f >>= (\x -> g x >>= h) ≡ (f >>= g) >>= h。這證明起來比較複雜，因此我們只在這裡概述證明過程。請注意，我們可以將等式左側寫成
\st -> let (st', a) = f st
in (\x -> g x `bindState` h) a st'
==>
\st -> let (st', a) = f st
in (g a `bindState` h) st'
==>
\st -> let (st', a) = f st
in (\st' -> let (st'', b) = g a
in h b st'') st'
==>
\st -> let (st' , a) = f st
(st'', b) = g a st'
(st''',c) = h b st''
in (st''',c)
這裡有趣的地方在於，我們在相同的 let 層次上都有動作應用。由於 let 是結合性的，這意味著我們可以按任何我們喜歡的括號方式進行分組，結果不會改變。當然，這是一個非正式的，“手勢”論證，需要我們進行幾個額外的推導才能真正證明，但這提供了總體思路。
現在我們知道 State st 實際上是一個單子，我們希望將其設為 Monad 類的例項。不幸的是，直接這樣做不可行。我們不能寫
instance Monad (State st) where { ... }
這是因為你不能從未完全應用的類型別名建立例項。相反，我們需要做的將類型別名轉換為 newtype，如下所示
newtype State st a = State (st -> (st, a))
不幸的是，這意味著我們需要在 Monad 例項宣告中對 State 建構函式進行一些打包和解包，但這並不難。
instance Monad (State state) where
return a = State (\state -> (state, a))
State run >>= action = State run'
where run' st =
let (st', a) = run st
State run'' = action a
in run'' st'
現在，我們可以將我們的 mapTreeM 函式寫成
mapTreeM :: (a -> State state b) -> Tree a ->
State state (Tree b)
mapTreeM f (Leaf a) = do
b <- f a
return (Leaf b)
mapTreeM f (Branch lhs rhs) = do
lhs' <- mapTreeM f lhs
rhs' <- mapTreeM f rhs
return (Branch lhs' rhs')
這比以前乾淨得多。事實上，如果我們刪除型別簽名，我們會得到更通用的型別
mapTreeM :: Monad m => (a -> m b) -> Tree a ->
m (Tree b)
也就是說，mapTreeM 可以執行在任何單子中，而不僅僅是我們自己的 State 單子。
現在，將計算的有狀態方面封裝起來的好處在於，我們可以提供函式來獲取和更改當前狀態。這些函式看起來像
getState :: State state state getState = State (\state -> (state, state)) putState :: state -> State state () putState new = State (\_ -> (new, ()))
這裡，getState 是一個單子操作，它獲取當前狀態，將其不變地傳遞，然後將其作為值返回。putState 函式接受一個新狀態，並生成一個動作，該動作忽略當前狀態並插入新狀態。
現在，我們可以將我們的 numberTree 函式寫成
numberTree :: Tree a -> State Int (Tree (a, Int))
numberTree tree = mapTreeM number tree
where number v = do
cur <- getState
putState (cur+1)
return (v,cur)
最後，我們需要能夠透過提供初始狀態來執行該動作
runStateM :: State state a -> state -> a runStateM (State f) st = snd (f st)
現在，我們可以提供一個示例 Tree
testTree =
Branch
(Branch
(Leaf 'a')
(Branch
(Leaf 'b')
(Leaf 'c')))
(Branch
(Leaf 'd')
(Leaf 'e'))
並對其進行編號
示例
State> runStateM (numberTree testTree) 1
Branch (Branch (Leaf ('a',1)) (Branch (Leaf ('b',2))
(Leaf ('c',3)))) (Branch (Leaf ('d',4))
(Leaf ('e',5)))
這看起來像是為了做一些簡單的事情而做了很多工作。但是，請注意 mapTreeM 的新功能。我們還可以以從左到右的方式打印出樹的葉子，如下所示
示例
State> mapTreeM print testTree 'a' 'b' 'c' 'd' 'e'
這至關重要地依賴於這樣一個事實，即 mapTreeM 具有更通用的型別，涉及任意單子，而不僅僅是狀態單子。此外，我們可以編寫一個動作，該動作將每個葉子的值設定為其舊值以及所有前面的值
fluffLeaves tree = mapTreeM fluff tree
where fluff v = do
cur <- getState
putState (v:cur)
return (v:cur)
並且可以觀察其執行情況
示例
State> runStateM (fluffLeaves testTree) []
Branch (Branch (Leaf "a") (Branch (Leaf "ba")
(Leaf "cba"))) (Branch (Leaf "dcba")
(Leaf "edcba"))
事實上，你甚至不需要編寫自己的單子例項和資料型別。所有這些都內建在 Control.Monad.State 模組中。在那裡，我們的 runStateM 被稱為 evalState；我們的 getState 被稱為 get；我們的 putState 被稱為 put。
該模組還包含一個狀態轉換器單子，我們將在關於 Transformer 的部分中討論它。
常見單子
[edit | edit source]事實證明，我們許多最喜歡的型別本身就是單子。例如，考慮列表。它們有一個單子的定義，看起來像這樣
instance Monad [] where
return x = [x]
l >>= f = concatMap f l
fail _ = []
這使我們能夠在 do 語法中使用列表。例如，給定以下定義
cross l1 l2 = do x <- l1 y <- l2 return (x,y)
我們得到一個叉積函式
示例
Monads> cross "ab" "def"
[('a','d'),('a','e'),('a','f'),('b','d'),('b','e'),
('b','f')]
這與列表推導形式非常相似，這絕非偶然
示例
Prelude> [(x,y) | x <- "ab", y <- "def"]
[('a','d'),('a','e'),('a','f'),('b','d'),('b','e'),
('b','f')]
列表推導形式只是使用列表的單子語句的縮寫形式。事實上，在早期的 Haskell 版本中，列表推導形式可以用於任何單子，而不僅僅是列表。然而，在當前版本的 Haskell 中，這不再允許。
Maybe 型別也是一個單子，其中失敗表示為 Nothing，成功表示為 Just。我們得到以下例項宣告
instance Monad Maybe where
return a = Just a
Nothing >>= f = Nothing
Just x >>= f = f x
fail _ = Nothing
我們可以在 Maybe 上使用與列表相同的叉積函式。這是因為 do 語法適用於任何單子，並且 cross 函式中沒有特定於列表的部分。
示例
Monads> cross (Just 'a') (Just 'b')
Just ('a','b')
Monads> cross (Nothing :: Maybe Char) (Just 'b')
Nothing
Monads> cross (Just 'a') (Nothing :: Maybe Char)
Nothing
Monads> cross (Nothing :: Maybe Char)
(Nothing :: Maybe Char)
Nothing
這意味著如果我們寫一個函式（比如來自關於 Classes 的部分的 searchAll），它只用單子運算子來寫，那麼我們就可以根據我們的意思，在任何單子中使用它。使用真正的單子函式（不是 do 語法），searchAll 函式看起來像這樣
searchAll g@(Graph vl el) src dst
| src == dst = return [src]
| otherwise = search' el
where search' [] = fail "no path"
search' ((u,v,_):es)
| src == u =
searchAll g v dst >>= \path ->
return (u:path)
| otherwise = search' es
該函式的型別為 Monad m => Graph v e -> Int -> Int -> m [Int]。這意味著無論我們當前使用什麼單子，該函式都將執行計算。假設我們有以下圖表
gr = Graph [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd')]
[(0,1,'l'), (0,2,'m'), (1,3,'n'), (2,3,'m')]
這表示一個具有四個節點的圖，分別標記為 a,b,c 和 d。從 a 到 b 和 c 都有邊。從 b 和 c 到 d 也都有邊。使用 Maybe 單子，我們可以計算從 a 到 d 的路徑
示例
Monads> searchAll gr 0 3 :: Maybe [Int] Just [0,1,3]
我們提供型別簽名，以便直譯器知道我們使用的是什麼單子。如果我們嘗試在相反方向搜尋，則沒有路徑。無法找到路徑在 Maybe 單子中表示為 Nothing
示例
Monads> searchAll gr 3 0 :: Maybe [Int] Nothing
請注意，字串“no path”已經消失，因為 Maybe 單子沒有辦法記錄它。
如果我們在列表單子中執行相同的不可能的搜尋，我們會得到空列表，表示沒有路徑
示例
Monads> searchAll gr 3 0 :: [[Int]] []
如果我們執行可能的搜尋，我們會得到一個包含第一條路徑的列表
示例
Monads> searchAll gr 0 3 :: [[Int]] [[0,1,3]]
你可能期望此函式呼叫返回所有路徑，但正如程式碼所示，它沒有。請參閱關於 Plus 的部分，瞭解有關使用列表來表示非確定性的更多資訊。
如果我們使用 IO 單子，我們實際上可以獲取錯誤訊息，因為 IO 知道如何跟蹤錯誤訊息
示例
Monads> searchAll gr 0 3 :: IO [Int] Monads> it [0,1,3] Monads> searchAll gr 3 0 :: IO [Int] *** Exception: user error Reason: no path
在第一種情況下，我們需要鍵入 it 才能讓 GHCi 實際評估搜尋。
此 searchAll 實現有一個問題：如果它找到一條不導致解決方案的邊，它將無法回溯。這與 search' 內部對 searchAll 的遞迴呼叫有關。例如，考慮如果 searchAll g v dst 沒有找到路徑會發生什麼。此實現沒有辦法恢復。例如，如果我們刪除從節點 b 到節點 d 的邊，我們仍然應該能夠找到從 a 到 d 的路徑，但是此演算法找不到它。我們定義
gr2 = Graph [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd')]
[(0,1,'l'), (0,2,'m'), (2,3,'m')]
然後嘗試搜尋
示例
Monads> searchAll gr2 0 3 *** Exception: user error Reason: no path
為了解決這個問題，我們需要一個類似於 Computation 類中的 combine 的函式。我們將在關於 Plus 的部分中看到如何做到這一點。
| 練習 |
|---|
驗證 Maybe 是否遵守三個單子定律。 |
| 練習 |
|---|
|
型別 instance Monad (Either String) where 開頭。 |
單子組合器
[edit | edit source]Monad/Control.Monad 庫包含一些非常有用的單子組合器，這些組合器還沒有得到充分的討論。我們將在本節中討論的組合器及其型別如下所示
(=<<) :: (a -> m b) -> m a -> m bmapM :: (a -> m b) -> [a] -> m [b]mapM_ :: (a -> m b) -> [a] -> m ()filterM :: (a -> m Bool) -> [a] -> m [a]foldM :: (a -> b -> m a) -> a -> [b] -> m asequence :: [m a] -> m [a]sequence_ :: [m a] -> m ()liftM :: (a -> b) -> m a -> m bwhen :: Bool -> m () -> m ()join :: m (m a) -> m a
在上述中，始終假設 m 是 Monad 的一個例項。
一般而言，以下劃線結尾的函式等效於沒有下劃線的函式，只是它們不返回值。
=<< 函式與 >>= 完全相同，只是它的引數順序相反。例如，在 IO 單子中，我們可以編寫以下兩種方式中的任何一種
示例
Monads> writeFile "foo" "hello world!" >>
(readFile "foo" >>= putStrLn)
hello world!
Monads> writeFile "foo" "hello world!" >>
(putStrLn =<< readFile "foo")
hello world!
mapM、filterM 和 foldM 是我們以前用過的 map、filter 和 foldl，包裝在單子中。這些函式在使用單子時非常有用（尤其是 foldM）。例如，我們可以使用 mapM_ 將一個列表中的內容列印到螢幕上
示例
Monads> mapM_ print [1,2,3,4,5] 1 2 3 4 5
我們可以使用foldM對列表求和，並在每一步列印中間和
示例
Monads> foldM (\a b ->
putStrLn (show a ++ "+" ++ show b ++
"=" ++ show (a+b)) >>
return (a+b)) 0 [1..5]
0+1=1
1+2=3
3+3=6
6+4=10
10+5=15
Monads> it
15
sequence和sequence_函式只是“執行”一系列操作。例如
示例
Monads> sequence [print 1, print 2, print 'a'] 1 2 'a' Monads> it [(),(),()] Monads> sequence_ [print 1, print 2, print 'a'] 1 2 'a' Monads> it ()
我們可以看到帶下劃線的版本沒有返回每個值，而沒有下劃線的版本返回返回值的列表。
liftM函式將非單子函式“提升”到單子函式。（不要將它與用於單子轉換器（在關於轉換器的部分）的lift函式混淆。）這對於縮短程式碼（以及其他事情）很有用。例如，我們可能想編寫一個函式，用它的行號在檔案的每一行前面加上一個字首。我們可以用以下方法做到這一點
numberFile :: FilePath -> IO () numberFile fp = do text <- readFile fp let l = lines text let n = zipWith (\n t -> show n ++ ' ' : t) [1..] l mapM_ putStrLn n
但是，我們可以使用liftM縮短它
numberFile :: FilePath -> IO () numberFile fp = do l <- lines `liftM` readFile fp let n = zipWith (\n t -> show n ++ ' ' : t) [1..] l mapM_ putStrLn n
事實上，您可以使用liftM對檔案應用任何型別的（純）處理。例如，也許我們還想將行分成單詞；我們可以用以下方法做到這一點
... w <- (map words . lines) `liftM` readFile fp ...
注意，括號是必需的，因為(.)函式的固定性與`liftM`相同。
將純函式提升到單子中在其他單子中也很有用。例如，liftM可以用來在Just中應用函式。例如
Monads> liftM (+1) (Just 5) Just 6 Monads> liftM (+1) Nothing Nothing
when函式僅在滿足條件時執行單子操作。所以，如果我們只想列印非空行
示例
Monads> mapM_ (\l -> when (not $ null l) (putStrLn l))
["","abc","def","","","ghi"]
abc
def
ghi
當然，也可以用filter來實現，但有時when更方便。
最後，join函式是單子等效於列表上的concat。實際上，當m是列表單子時，join正好是concat。在其他單子中，它執行類似的任務
示例
Monads> join (Just (Just 'a')) Just 'a' Monads> join (Just (Nothing :: Maybe Char)) Nothing Monads> join (Nothing :: Maybe (Maybe Char)) Nothing Monads> join (return (putStrLn "hello")) hello Monads> return (putStrLn "hello") Monads> join [[1,2,3],[4,5]] [1,2,3,4,5]
當我們進入本章Io 高階中的更高階主題時，這些函式將變得更加有用。
僅給出>>=和return函式，不可能寫出像combine這樣的函式，它的型別為c a -> c a -> c a。但是，這樣的函式非常有用，以至於它存在於另一個名為MonadPlus的類中。除了具有combine函式之外，MonadPlus的例項還具有一個“零”元素，它是“加”操作（即組合）下的單位元。定義是
class Monad m => MonadPlus m where mzero :: m a mplus :: m a -> m a -> m a
為了獲得對MonadPlus的訪問許可權，您需要匯入Monad模組（或分層庫中的Control.Monad）。
在關於通用的部分中，我們展示了Maybe和列表都是單子。事實上，它們也都是MonadPlus的例項。在Maybe的情況下，零元素是Nothing；在列表的情況下，它是空列表。Maybe上的mplus操作是Nothing，如果兩個元素都是Nothing；否則，它是第一個Just值。對於列表，mplus與++相同。
也就是說，例項宣告看起來像
instance MonadPlus Maybe where mzero = Nothing mplus Nothing y = y mplus x _ = x instance MonadPlus [] where mzero = [] mplus x y = x ++ y
我們可以使用這個類來重新實現我們一直在探索的搜尋函式，以便它能夠探索所有可能的路徑。新函式看起來像
searchAll2 g@(Graph vl el) src dst
| src == dst = return [src]
| otherwise = search' el
where search' [] = fail "no path"
search' ((u,v,_):es)
| src == u =
(searchAll2 g v dst >>= \path ->
return (u:path)) `mplus`
search' es
| otherwise = search' es
現在，當我們遍歷search'中的邊列表時，如果我們遇到匹配的邊，我們不僅探索這條路徑，而且還會在對search'的遞迴呼叫中繼續探索當前節點的出邊。
IO 單子不是MonadPlus的例項；我們無法用這個單子執行搜尋。我們可以看到，當使用列表作為單子時，我們（a）在gr中獲得所有可能的路徑，以及（b）在gr2中獲得一條路徑。
示例
MPlus> searchAll2 gr 0 3 :: [[Int]] [[0,1,3],[0,2,3]] MPlus> searchAll2 gr2 0 3 :: [[Int]] [[0,2,3]]
您可能想將其實現為
searchAll2 g@(Graph vl el) src dst
| src == dst = return [src]
| otherwise = search' el
where search' [] = fail "no path"
search' ((u,v,_):es)
| src == u = do
path <- searchAll2 g v dst
rest <- search' es
return ((u:path) `mplus` rest)
| otherwise = search' es
但請注意，這不是我們想要的。這裡，如果對searchAll2的遞迴呼叫失敗，我們不會嘗試繼續執行search' es。對mplus的呼叫必須位於頂層才能正常工作。
| 練習 |
|---|
|
假設我們改變了 search' es `mplus`
(searchAll2 g v dst >>= \path ->
return (u:path))
當在 |
通常我們想將單子“疊加”在一起。例如，可能有一種情況，您需要透過 IO 單子訪問 IO 操作，並透過某個狀態單子訪問狀態函式。為了實現這一點，我們引入了MonadTrans類，它本質上將一個單子的操作“提升”到另一個單子中。您可以將其視為將單子堆疊在一起。這個類有一個簡單的方法：lift。MonadTrans的類宣告是
class MonadTrans t where lift :: Monad m => m a -> t m a
這裡的想法是t是外部單子，m存在於其中。為了執行型別為Monad m => m a的命令，我們首先將其提升到轉換器中。
轉換器最簡單的示例（可能也是最有用）是狀態轉換器單子，它是一個狀態單子，包裝在任意單子周圍。之前，我們定義狀態單子為
newtype State state a = State (state -> (state, a))
現在，我們不再使用型別為state -> (state, a)的函式作為單子，而是假設存在另一個單子m，並將內部操作轉換為型別為state -> m (state, a)的東西。這產生了狀態轉換器的以下定義
newtype StateT state m a =
StateT (state -> m (state, a))
例如，我們可以將m視為 IO。在這種情況下，我們的狀態轉換器單子能夠在 IO 單子中執行操作。首先，我們將其設為MonadTrans的例項
instance MonadTrans (StateT state) where
lift m = StateT (\s -> do a <- m
return (s,a))
這裡，將函式從m域提升到StateT state域，只需保持狀態（s值）不變並執行操作即可。
當然，我們還需要使StateT本身成為一個單子。這很簡單，前提是m已經是單子
instance Monad m => Monad (StateT state m) where
return a = StateT (\s -> return (s,a))
StateT m >>= k = StateT (\s -> do
(s', a) <- m s
let StateT m' = k a
m' s')
fail s = StateT (\_ -> fail s)
return定義背後的想法是我們保持狀態不變，並簡單地在封閉的單子中返回狀態/a 對。請注意，return在return的定義中的使用是指封閉的單子，而不是狀態轉換器。
在繫結定義中，我們建立了一個新的StateT，它以狀態s作為引數。首先，它將此狀態應用於第一個操作（StateT m）並獲得新的狀態和答案作為結果。然後，它在此新狀態上執行k操作，並獲得一個新的轉換器。最後，它將新狀態應用於此轉換器。這個定義幾乎與我們在關於狀態的部分中描述的標準（非轉換器）State單子的繫結定義相同。
fail函式將對封閉單子中的fail的呼叫傳遞過去，因為狀態轉換器本身不知道如何處理失敗。
當然，為了實際使用這個單子，我們需要提供函式getT、putT和evalStateT。它們類似於我們在關於狀態的部分中描述的getState、putState和runStateM
getT :: Monad m => StateT s m s getT = StateT (\s -> return (s, s)) putT :: Monad m => s -> StateT s m () putT s = StateT (\_ -> return (s, ())) evalStateT :: Monad m => StateT s m a -> s -> m a evalStateT (StateT m) state = do (s', a) <- m state return a
這些函式應該很直觀。但是請注意，evalStateT的結果實際上是封閉單子中的單子操作。這是單子轉換器的典型特徵：它們不知道如何在封閉的單子中實際執行事物（它們只知道如何提升操作）。因此，您得到的將是內部單子中的單子操作（在我們的例子中是 IO），然後您需要自己執行它。
我們可以使用狀態轉換器來重新實現我們在關於狀態的部分中描述的mapTreeM函式的版本。這裡唯一的變化是，當我們到達葉子時，我們打印出葉子的值；當我們到達分支時，我們只打印出“分支”。
mapTreeM action (Leaf a) = do
lift (putStrLn ("Leaf " ++ show a))
b <- action a
return (Leaf b)
mapTreeM action (Branch lhs rhs) = do
lift (putStrLn "Branch")
lhs' <- mapTreeM action lhs
rhs' <- mapTreeM action rhs
return (Branch lhs' rhs')
這個函式與我們在關於狀態的部分中描述的函式唯一的區別是lift (putStrLn ...)作為第一行。lift告訴我們，我們將要在一個封閉的單子中執行命令。在本例中，封閉的單子是IO，因為提升的命令是putStrLn。
這個函式的型別比較複雜
mapTreeM :: (MonadTrans t, Monad (t IO), Show a) =>
(a -> t IO a1) -> Tree a -> t IO (Tree a1)
先忽略類約束，它表示mapTreeM接受一個操作和一棵樹，並返回一棵樹。這與之前一樣。在這個過程中，我們要求t是一個單子轉換器（因為我們對它應用了lift）；我們要求t IO是一個單子，因為我們使用putStrLn，我們知道封閉的單子是IO；最後，我們要求a是show的例項——這僅僅是因為我們使用show來顯示葉子的值。
現在，我們只需將numberTree更改為使用此版本的mapTreeM以及get和put的新版本，最終得到
numberTree tree = mapTreeM number tree
where number v = do
cur <- getT
putT (cur+1)
return (v,cur)
使用它，我們可以執行我們的單子
示例
MTrans> evalStateT (numberTree testTree) 0
Branch
Branch
Leaf 'a'
Branch
Leaf 'b'
Leaf 'c'
Branch
Leaf 'd'
Leaf 'e'
*MTrans> it
Branch (Branch (Leaf ('a',0))
(Branch (Leaf ('b',1)) (Leaf ('c',2))))
(Branch (Leaf ('d',3)) (Leaf ('e',4)))
我們在MonadPlus的討論中沒有提到一個問題，即我們的搜尋演算法將無法在包含迴圈的圖中終止。考慮
gr3 = Graph [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd')]
[(0,1,'l'), (1,0,'m'), (0,2,'n'),
(1,3,'o'), (2,3,'p')]
在這個圖中，從節點b到節點a有一條回邊。如果我們嘗試執行searchAll2，無論我們使用哪個單子，它都將無法終止。此外，如果我們將此錯誤邊移到列表的末尾（並將其稱為gr4），那麼searchAll2 gr4 0 3的結果將包含無限條路徑：我們可能只想要不包含迴圈的路徑。
為了解決這個問題，我們需要引入狀態。也就是說，我們需要跟蹤我們訪問過的節點，這樣我們就不再訪問它們。
我們可以用以下方法做到這一點
searchAll5 g@(Graph vl el) src dst
| src == dst = do
visited <- getT
putT (src:visited)
return [src]
| otherwise = do
visited <- getT
putT (src:visited)
if src `elem` visited
then mzero
else search' el
where
search' [] = mzero
search' ((u,v,_):es)
| src == u =
(do path <- searchAll5 g v dst
return (u:path)) `mplus`
search' es
| otherwise = search' es
這裡，我們隱式地使用狀態轉換器（參見對getT和putT的呼叫）來跟蹤訪問過的狀態。只有在我們遇到尚未訪問過的狀態時，我們才會繼續遞迴。此外，當我們遞迴時，我們將當前狀態新增到我們的已訪問狀態集中。
現在，我們可以執行狀態轉換器，即使在迴圈圖上，也能得到正確的路徑
示例
MTrans> evalStateT (searchAll5 gr3 0 3) [] :: [[Int]] [[0,1,3],[0,2,3]] MTrans> evalStateT (searchAll5 gr4 0 3) [] :: [[Int]] [[0,1,3],[0,2,3]]
這裡，作為evalStateT引數提供的空列表是初始狀態（即，初始已訪問列表）。在我們的例子中，它是空的。
我們還可以提供一個execStateT方法，該方法不返回結果，而是返回最終狀態。這個函式看起來像
execStateT :: Monad m => StateT s m a -> s -> m s execStateT (StateT m) state = do (s', a) <- m state return s'
這在我們這裡不太有用，因為它將返回與evalStateT完全相反的結果（嘗試一下，您就會發現！），但在一般情況下可能有用（例如，如果我們需要知道numberTree中使用了多少個數字）。
| 練習 |
|---|
|
編寫一個基於 示例 Exploring 0 -> 3 Exploring 1 -> 3 Exploring 3 -> 3 Exploring 2 -> 3 Exploring 3 -> 3 MTrans> it [[0,1,3],[0,2,3]] 為了做到這一點，您必須定義自己的列表單子 轉換器，併為其建立適當的例項。 |
| 練習 |
|---|
|
將本節中的 |
事實證明，某些型別的解析器都是 Monad。這使得在 Haskell 中構建解析庫變得非常簡潔。在本章中，我們首先在關於 簡單解析 Monad 的部分構建自己的（小型）解析庫，然後在最後一部分介紹 Parsec 解析庫。
考慮解析任務。一個簡單的解析 Monad 就像一個狀態 Monad，其中狀態是未解析的字串。我們可以精確地表示為
newtype Parser a = Parser
{ runParser :: String -> Either String (String, a) }
我們再次使用 Left err 表示錯誤狀態。這產生了 Monad 和 MonadPlus 的標準例項
instance Monad Parser where
return a = Parser (\xl -> Right (xl,a))
fail s = Parser (\xl -> Left s)
Parser m >>= k = Parser $ \xl ->
case m xl of
Left s -> Left s
Right (xl', a) ->
let Parser n = k a
in n xl'
instance MonadPlus Parser where
mzero = Parser (\xl -> Left "mzero")
Parser p `mplus` Parser q = Parser $ \xl ->
case p xl of
Right a -> Right a
Left err -> case q xl of
Right a -> Right a
Left _ -> Left err
現在，我們想要構建一個解析“基本元素”的庫。最基本的基本元素是一個解析特定字元的解析器。此函式看起來像
char :: Char -> Parser Char
char c = Parser char'
where char' [] = Left ("expecting " ++ show c ++
" got EOF")
char' (x:xs)
| x == c = Right (xs, c)
| otherwise = Left ("expecting " ++
show c ++ " got " ++
show x)
在這裡，解析器僅當輸入的第一個字元是預期的字元時才成功。
我們可以使用此解析器來構建解析字串“Hello”的解析器
helloParser :: Parser String helloParser = do char 'H' char 'e' char 'l' char 'l' char 'o' return "Hello"
這表明將這些解析器組合在一起是多麼容易。我們不需要擔心底層字串——Monad 會為我們處理它。我們只需要將這些解析器基本元素組合起來。我們可以透過使用 runParser 並提供輸入來測試此解析器
示例
Parsing> runParser helloParser "Hello"
Right ("","Hello")
Parsing> runParser helloParser "Hello World!"
Right (" World!","Hello")
Parsing> runParser helloParser "hello World!"
Left "expecting 'H' got 'h'"
我們可以有一個稍微更通用的函式，它將匹配任何符合描述的字元
matchChar :: (Char -> Bool) -> Parser Char
matchChar c = Parser matchChar'
where matchChar' [] =
Left ("expecting char, got EOF")
matchChar' (x:xs)
| c x = Right (xs, x)
| otherwise =
Left ("expecting char, got " ++
show x)
使用它，我們可以編寫一個不區分大小寫的“Hello”解析器
ciHelloParser = do c1 <- matchChar (`elem` "Hh") c2 <- matchChar (`elem` "Ee") c3 <- matchChar (`elem` "Ll") c4 <- matchChar (`elem` "Ll") c5 <- matchChar (`elem` "Oo") return [c1,c2,c3,c4,c5]
當然，我們可以使用類似 matchChar ((=='h') . toLower) 的東西，但上面的實現也能正常工作。我們可以測試此函式
示例
Parsing> runParser ciHelloParser "hELlO world!"
Right (" world!","hELlO")
最後，我們可以有一個函式，它將匹配任何字元
anyChar :: Parser Char
anyChar = Parser anyChar'
where anyChar' [] =
Left ("expecting character, got EOF")
anyChar' (x:xs) = Right (xs, x)
在這些基本元素之上，我們通常構建一些組合器。例如，many 組合器將接收一個解析型別為 a 的實體的解析器，並將其轉換為一個解析型別為 [a] 的實體的解析器（這是一個 Kleene 星號運算子）
many :: Parser a -> Parser [a]
many (Parser p) = Parser many'
where many' xl =
case p xl of
Left err -> Right (xl, [])
Right (xl',a) ->
let Right (xl'', rest) = many' xl'
in Right (xl'', a:rest)
這裡的想法是，首先我們嘗試應用給定的解析器 p。如果失敗，我們成功，但返回空列表。如果 p 成功，我們遞歸併繼續嘗試應用 p 直到它失敗。然後我們返回我們積累的成功列表。
一般來說，會有很多類似的函式，它們會被隱藏在一個庫中，這樣使用者實際上就無法檢視 Parser 型別內部。但是，使用它們，你可以構建例如一個解析（非負）整數的解析器
int :: Parser Int int = do t1 <- matchChar isDigit tr <- many (matchChar isDigit) return (read (t1:tr))
在這個函式中，我們首先匹配一個數字（isDigit 函式來自模組 Char/Data.Char），然後匹配儘可能多的數字。然後我們read結果並返回它。我們可以像以前一樣測試這個解析器
示例
Parsing> runParser int "54"
Right ("",54)
*Parsing> runParser int "54abc"
Right ("abc",54)
*Parsing> runParser int "a54abc"
Left "expecting char, got 'a'"
現在，假設我們想要解析一個 Haskell 風格的 Int 列表。這變得有點困難，因為在某個時候，我們將解析一個逗號或一個右括號，但我們不知道什麼時候會發生這種情況。這就是 Parser 是 MonadPlus 例項的用武之地：首先我們嘗試一個，然後我們嘗試另一個。
考慮以下程式碼
intList :: Parser [Int]
intList = do
char '['
intList' `mplus` (char ']' >> return [])
where intList' = do
i <- int
r <- (char ',' >> intList') `mplus`
(char ']' >> return [])
return (i:r)
此程式碼首先解析並開啟一個左括號。然後，使用 mplus，它嘗試兩種事情中的一種：使用 intList' 解析，或解析一個右括號並返回一個空列表。
intList' 函式假設我們還沒有到達列表的末尾，因此它首先解析一個整數。然後它解析列表的其餘部分。但是，它不知道我們是否已經到達末尾，因此它再次使用 mplus。一方面，它試圖解析一個逗號，然後遞迴；另一方面，它解析一個右括號並返回一個空列表。無論哪種方式，它都只是將其解析的整數自身附加到開頭。
你應該注意的一件事是，你為 mplus 提供引數的順序。考慮以下解析器
tricky = mplus (string "Hal") (string "Hall")
你可能期望此解析器解析“Hal”和“Hall”這兩個詞；但是，它只解析前者。你可以透過以下方式看到這一點
示例
Parsing> runParser tricky "Hal"
Right ("","Hal")
Parsing> runParser tricky "Hall"
Right ("l","Hal")
這是因為它試圖解析“Hal”，它成功了，然後它沒有費心去嘗試解析“Hall”。
你可以嘗試透過提供一個解析器基本元素來修復它，該基本元素檢測檔案結尾（實際上是字串結尾）
eof :: Parser ()
eof = Parser eof'
where eof' [] = Right ([], ())
eof' xl = Left ("Expecting EOF, got " ++
show (take 10 xl))
然後你可以使用 eof 重寫 tricky
tricky2 = do s <- mplus (string "Hal") (string "Hall") eof return s
但這也不起作用，正如我們可以輕易看到的那樣
示例
Parsing> runParser tricky2 "Hal"
Right ("",())
Parsing> runParser tricky2 "Hall"
Left "Expecting EOF, got \"l\""
這是因為，同樣地，mplus 不知道它需要解析整個輸入。因此，當你提供它“Hall”時，它只解析“Hal”並將最後的“l”留著供以後解析。這會導致 eof 產生錯誤訊息。
正確的實現方法是
tricky3 =
mplus (do s <- string "Hal"
eof
return s)
(do s <- string "Hall"
eof
return s)
我們可以看到這有效
示例
Parsing> runParser tricky3 "Hal"
Right ("","Hal")
Parsing> runParser tricky3 "Hall"
Right ("","Hall")
這有效正是因為 mplus 的每一側都知道它必須讀取末尾。
在這種情況下，修復解析器以接受“Hal”和“Hall”兩者都很簡單，因為我們假設我們將在之後立即讀取檔案結尾。不幸的是，如果我們不能立即消除歧義，生活會變得更加複雜。這是一個解析中的普遍問題，與 Monadic 解析關係不大。大多數解析器庫（例如，Parsec，參見關於 Parsec 的部分）採用的解決方案是隻識別“LL(1)”語法：這意味著你必須能夠用一個標記前瞻來消除輸入的歧義。
| 練習 |
|---|
|
編寫一個解析器 |
有了這個 Monadic 解析器，新增關於源位置的資訊就相當容易了。例如，如果我們正在解析一個大型檔案，報告錯誤發生的哪一行可能會很有用。我們可以簡單地透過擴充套件 Parser 型別並修改例項和基本元素來做到這一點
newtype Parser a = Parser
{ runParser :: Int -> String ->
Either String (Int, String, a) }
instance Monad Parser where
return a = Parser (\n xl -> Right (n,xl,a))
fail s = Parser (\n xl -> Left (show n ++
": " ++ s))
Parser m >>= k = Parser $ \n xl ->
case m n xl of
Left s -> Left s
Right (n', xl', a) ->
let Parser m2 = k a
in m2 n' xl'
instance MonadPlus Parser where
mzero = Parser (\n xl -> Left "mzero")
Parser p `mplus` Parser q = Parser $ \n xl ->
case p n xl of
Right a -> Right a
Left err -> case q n xl of
Right a -> Right a
Left _ -> Left err
matchChar :: (Char -> Bool) -> Parser Char
matchChar c = Parser matchChar'
where matchChar' n [] =
Left ("expecting char, got EOF")
matchChar' n (x:xs)
| c x =
Right (n+if x=='\n' then 1 else 0
, xs, x)
| otherwise =
Left ("expecting char, got " ++
show x)
char 和 anyChar 的定義沒有給出，因為它們可以用 matchChar 來編寫。many 函式只需要修改以包含新的狀態。
現在，當我們執行解析器並且出現錯誤時，它會告訴我們哪一行包含錯誤
示例
Parsing2> runParser helloParser 1 "Hello" Right (1,"","Hello") Parsing2> runParser int 1 "a54" Left "1: expecting char, got 'a'" Parsing2> runParser intList 1 "[1,2,3,a]" Left "1: expecting ']' got '1'"
我們可以使用之前練習中的 intListSpace 解析器來檢視它實際上是否有效
示例
Parsing2> runParser intListSpace 1
"[1 ,2 , 4 \n\n ,a\n]"
Left "3: expecting char, got 'a'"
Parsing2> runParser intListSpace 1
"[1 ,2 , 4 \n\n\n ,a\n]"
Left "4: expecting char, got 'a'"
Parsing2> runParser intListSpace 1
"[1 ,\n2 , 4 \n\n\n ,a\n]"
Left "5: expecting char, got 'a'"
我們可以看到，錯誤發生的哪一行隨著我們在錯誤的“a”之前新增更多換行符而增加。
當你繼續開發你的解析器時，你可能想要新增越來越多的功能。幸運的是，Graham Hutton 和 Daan Leijen 已經在 Parsec 庫中為我們做好了這些。本節旨在介紹 Parsec 庫；它絕不涵蓋整個庫，但應該足以讓你入門。
與我們的庫一樣，Parsec 提供了一些基本函式來從字元構建解析器。這些是：char，它與我們的 char 相同；anyChar，它與我們的 anyChar 相同；satisfy，它與我們的 matchChar 相同；oneOf，它接收一個 Char 列表並匹配其中的任何一個；以及 noneOf，它是 oneOf 的反面。
Parsec 用於執行解析器的主要函式是 parse。但是，除了解析器之外，此函式還接收一個字串，該字串代表你要解析的檔案的名稱。這樣它就可以給出更好的錯誤訊息。我們可以嘗試使用上面的函式進行解析
示例
ParsecI> parse (char 'a') "stdin" "a"
Right 'a'
ParsecI> parse (char 'a') "stdin" "ab"
Right 'a'
ParsecI> parse (char 'a') "stdin" "b"
Left "stdin" (line 1, column 1):
unexpected "b"
expecting "a"
ParsecI> parse (char 'H' >> char 'a' >> char 'l')
"stdin" "Hal"
Right 'l'
ParsecI> parse (char 'H' >> char 'a' >> char 'l')
"stdin" "Hap"
Left "stdin" (line 1, column 3):
unexpected "p"
expecting "l"
在這裡，我們可以看到我們的解析器和 Parsec 之間的幾個區別：首先，當我們執行 parse 時，字串的其餘部分不會被返回。其次，產生的錯誤訊息要好得多。
除了基本字元解析函式之外，Parsec 還提供了用於以下方面的基本元素：spaces，它與我們的相同；space，它解析單個空格；letter，它解析一個字母；digit，它解析一個數字；string，它與我們的相同；以及其他一些。
我們可以用 Parsec 編寫我們的 int 和 intList 函式
int :: CharParser st Int
int = do
i1 <- digit
ir <- many digit
return (read (i1:ir))
intList :: CharParser st [Int]
intList = do
char '['
intList' `mplus` (char ']' >> return [])
where intList' = do
i <- int
r <- (char ',' >> intList') `mplus`
(char ']' >> return [])
return (i:r)
首先，注意型別簽名。st 型別變數只是一個我們沒有使用的狀態變數。在 int 函式中，我們使用 many 函式（內置於 Parsec）和 digit 函式（也內置於 Parsec）。intList 函式實際上與我們之前編寫的一模一樣。
但是，請注意，顯式使用 mplus 不是組合解析器的首選方法：Parsec 提供了一個 <|> 函式，它是 mplus 的同義詞，但看起來更漂亮
intList :: CharParser st [Int]
intList = do
char '['
intList' <|> (char ']' >> return [])
where intList' = do
i <- int
r <- (char ',' >> intList') <|>
(char ']' >> return [])
return (i:r)
我們可以測試一下
示例
ParsecI> parse intList "stdin" "[3,5,2,10]" Right [3,5,2,10] ParsecI> parse intList "stdin" "[3,5,a,10]" Left "stdin" (line 1, column 6): unexpected "a" expecting digit
除了這些基本組合器之外，Parsec 還提供了一些其他有用的組合器
choice接收一個解析器列表，並在它們之間執行一個或操作（<|>）。
option接收一個型別為a的預設值和一個返回型別為a的解析器。然後它嘗試使用解析器進行解析，但如果解析失敗，它使用預設值作為返回值。
optional接收一個返回()的解析器，並可選地執行它。
between接受三個解析器：一個起始解析器、一個結束解析器和一箇中間解析器。它按順序執行它們並返回中間解析器的值。例如，這可以用來處理我們intList解析器的括號。
notFollowedBy接收一個解析器並返回一個僅在給定解析器失敗時才成功的解析器。
假設我們想要解析一個簡單的計算器語言，其中只包含加號和乘號。此外，為了簡單起見，假設每個嵌入的表示式必須用括號括起來。我們可以為這種語言給出資料型別如下
data Expr = Value Int
| Expr :+: Expr
| Expr :*: Expr
deriving (Eq, Ord, Show)
然後為這種語言編寫一個解析器如下
parseExpr :: Parser Expr
parseExpr = choice
[ do i <- int; return (Value i)
, between (char '(') (char ')') $ do
e1 <- parseExpr
op <- oneOf "+*"
e2 <- parseExpr
case op of
'+' -> return (e1 :+: e2)
'*' -> return (e1 :*: e2)
]
在這裡，解析器在兩種選項之間交替（我們本可以使用 <|>，但我想要展示 choice 組合器的實際應用）。第一個選項簡單地解析一個整數，然後將其包裝在 Value 建構函式中。第二個選項使用 between 來解析括號之間的文字。它首先解析一個表示式，然後解析加號或乘號，然後解析另一個表示式。根據運算子是什麼，它返回 e1 :+: e2 或 e1 :*: e2。
我們可以修改這個解析器，使其不再計算 Expr，而是簡單地計算值
parseValue :: Parser Int
parseValue = choice
[int
,between (char '(') (char ')') $ do
e1 <- parseValue
op <- oneOf "+*"
e2 <- parseValue
case op of
'+' -> return (e1 + e2)
'*' -> return (e1 * e2)
]
我們可以將其用作
示例
ParsecI> parse parseValue "stdin" "(3*(4+3))" Right 21
現在，假設我們想要在我們的語言中引入繫結。也就是說，我們也想要能夠在我們的表示式中說“let x = 5 in”，然後使用我們定義的變數。為了做到這一點，我們需要使用 Parsec 中內建的 getState 和 setState（或 updateState）函式。
parseValueLet :: CharParser (FiniteMap Char Int) Int
parseValueLet = choice
[ int
, do string "let "
c <- letter
char '='
e <- parseValueLet
string " in "
updateState (\fm -> addToFM fm c e)
parseValueLet
, do c <- letter
fm <- getState
case lookupFM fm c of
Nothing -> unexpected ("variable " ++ show c ++
" unbound")
Just i -> return i
, between (char '(') (char ')') $ do
e1 <- parseValueLet
op <- oneOf "+*"
e2 <- parseValueLet
case op of
'+' -> return (e1 + e2)
'*' -> return (e1 * e2)
]
int 和遞迴情況保持不變。我們添加了另外兩種情況，一種處理 let 繫結，另一種處理使用。
在 let 繫結情況下，我們首先解析一個“let”字串，然後解析我們要繫結的字元（letter 函式是 Parsec 的一個原語，用於解析字母字元），然後解析其值（一個 parseValueLet）。然後，我們解析“in”並將狀態更新為包含此繫結。最後，我們繼續並解析剩下的部分。
在使用情況下，我們只需解析字元，然後在狀態中查詢它。但是，如果它不存在，我們使用 Parsec 原語 unexpected 來報告錯誤。
我們可以使用 runParser 命令來檢視這個解析器的實際應用，它使我們能夠提供一個初始狀態
示例
ParsecI> runParser parseValueLet emptyFM "stdin"
"let c=5 in ((5+4)*c)"
Right 45
*ParsecI> runParser parseValueLet emptyFM "stdin"
"let c=5 in ((5+4)*let x=2 in (c+x))"
Right 63
*ParsecI> runParser parseValueLet emptyFM "stdin"
"((let x=2 in 3+4)*x)"
Right 14
請注意，括號不影響變數的定義。例如，在最後一個示例中，在某種意義上，“x”的使用超出了定義的範圍。但是，我們的解析器沒有注意到這一點，因為它以嚴格的從左到右的方式執行。為了解決這個遺漏，繫結必須被移除（參見練習）。
| 練習 |
|---|
|
修改 |