另一個 Haskell 教程/單子
| Haskell | |
|---|---|
| |
| 另一個 Haskell 教程 | |
| 前言 | |
| 簡介 | |
| 入門 | |
| 語言基礎 (解決方案) | |
| 型別基礎 (解決方案) | |
| IO (解決方案) | |
| 模組 (解決方案) | |
| 高階語言 (解決方案) | |
| 高階型別 (解決方案) | |
| 單子 (解決方案) | |
| 高階 IO | |
| 遞迴 | |
| 複雜性 | |
學習 Haskell 時最難掌握的概念是理解和使用單子。我們可以在這裡區分兩個子元件：(1) 學習如何使用現有的單子，以及 (2) 學習如何編寫新的單子。如果你想使用 Haskell，你必須學習如何使用現有的單子。另一方面，只有當你想要成為“超級 Haskell 大師”時，你才需要學習如何編寫自己的單子。但是，如果你能掌握編寫自己的單子的方法，那麼用 Haskell 程式設計會更加愉快。
到目前為止，我們已經看到了單子的兩種用途。第一個用途是 IO 操作：我們已經看到，透過使用單子，我們可以擺脫在 IO 章節中介紹的 RealWorld 解決方案所帶來的問題。第二個用途是在關於 類-計算 的部分中表示不同型別的計算。在這兩種情況下，我們都需要一種對操作進行排序的方法，並且發現一個足夠好的定義（至少對於計算而言）是
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 符號
[edit | edit source]我們已經暗示了單子與 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
同樣，我們將逐一詳細說明這些規則
轉換規則 1
[edit | edit source]第一個轉換規則 do {e} → e 指出（正如我們之前所說），在執行單個操作時，是否使用 do 都是無關緊要的。這本質上是 do 的歸納定義的基例。基例有一個操作（即這裡的 e）；另外三個轉換規則處理有多個操作的情況。
轉換規則 2
[edit | edit source]這表明 do {e; es} → e >> do {es}。這告訴我們，如果我們有一個操作（e）後跟一個操作列表（es），該怎麼做。在這裡，我們使用了之前定義的 >> 函式。這條規則簡單地說，要 do {e; es}，我們首先執行操作 e，丟棄結果，然後 do es。
例如，如果 e 是對於某個字串 s 的 putStrLn s，那麼 do {e; es} 的轉換就是執行 e（即列印字串），然後 do es。這顯然是我們想要的。
轉換規則 3
[edit | edit source]這表明 do {let decls; es} → let decls in do {es}。這條規則告訴我們如何處理 do 語句中的 let。我們將 let 內的宣告提升出來，並 do 聲明後的所有內容。
轉換規則 4
[edit | edit source]這表明 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)
現在，我們可以編寫一個簡單的對映函式，將某個函式應用於每個葉子的值
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) 我們將型別 `-> Tree b` 替換為 `-> state -> (state, 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)
現在，我們可以提供一個示例樹
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。
此模組還包含一個 狀態轉換器單子，我們將在關於 轉換器 的部分中討論它。
常用單子
[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
這意味著如果我們只使用單子運算子編寫一個函式（例如，來自關於 類 部分的 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 高階。
MonadPlus
[edit | edit source]僅給出 >>= 和 return 函式，就無法編寫型別為 c a -> c a -> c a 的函式，例如 combine。但是，這樣一個函式非常普遍有用，它存在於另一個名為 MonadPlus 的類中。除了具有 combine 函式外，MonadPlus 的例項還具有“零”元素，它是“加”（即組合）操作下的標識。定義是
class Monad m => MonadPlus m where mzero :: m a mplus :: m a -> m a -> m a
為了獲得對 MonadPlus 的訪問許可權，你需要匯入 Monad 模組（或者在層次結構庫中匯入 Control.Monad）。
在關於 Common 的部分中，我們展示了 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))
當你使用列表時，你會期望這如何改變結果 在gr 上的單子？為什麼？ |
單子轉換器
[edit | edit source]通常我們想將單子“疊加”在彼此之上。例如，可能存在一個情況，你需要透過 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 的部分中描述的標準（非轉換器）State 單子的繫結定義相同。
fail 函式將呼叫傳遞給封閉單子中的 fail，因為狀態轉換器本身不知道如何處理失敗。
當然，為了實際使用此單子，我們需要提供函式 getT、putT 和 evalStateT。這些類似於我們在關於 State 的部分中提到的 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）中的單子操作，你需要自己執行它。
我們可以使用狀態轉換器重新實現我們從關於 State 的部分中提到的 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')
此函式與我們在關於 State 的部分中提到的函式之間的唯一區別是 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]] 為了實現這一點，你必須定義自己的列表單子 轉換器併為其建立適當的例項。 |
| 練習 |
|---|
|
將 |
解析單子
[edit | edit source]事實證明，某些類別的解析器都是單子。這使得在 Haskell 中構建解析庫非常乾淨。在本章中，我們首先在關於 一個簡單的解析單子 的部分中構建我們自己的（小型）解析庫，然後在最後一部分中介紹 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-star 運算子）
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' 函式假設我們還沒有到達列表的末尾，因此它首先解析一個 int。然後它解析列表的其餘部分。但是，它不知道我們是否已經到達末尾，因此它再次使用 mplus。一方面，它嘗試解析一個逗號，然後遞迴；另一方面，它解析一個右大括號並返回空列表。無論哪種方式，它都只是將它本身解析的 int 預先附加到開頭。
你應該注意的一件事是，你向 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”這兩個詞非常簡單，因為我們假設我們將立即讀取檔案末尾。不幸的是，如果我們不能立即消除歧義，生活就會變得更加複雜。這是解析中的一個普遍問題，與單子解析關係不大。大多數解析器庫（例如，Parsec，參見關於 Parsec 的部分）採用的解決方案是隻識別“LL(1)”語法：這意味著你必須能夠使用一個標記的預讀來消除輸入的歧義。
| 練習 |
|---|
|
編寫一個解析器 |
有了這個單子解析器，新增有關源位置的資訊就很容易了。例如，如果我們正在解析一個大型檔案，報告發生錯誤的行號可能會有所幫助。我們可以簡單地透過擴充套件 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" 的使用在某種意義上是在定義範圍之外的。但是，我們的解析器沒有注意到這一點，因為它以嚴格的從左到右的方式操作。為了解決此遺漏，需要刪除繫結（見練習）。
| 練習 |
|---|
|
修改 |