第十三章 Haskell更多Monad

再來看看更多 Monad

我們已經(jīng)看過 Monad 是如何接受具有 context 的值，并如何用函數(shù)操作他們 還有如何用 >>= 跟 do 來減輕我們對(duì) context 的關(guān)注，集中精神在 value 本身。

我們也看過了 Maybe 是如何把值加上一個(gè)可能會(huì)失敗的 context。我們學(xué)習(xí)到 List Monad 是如何加進(jìn)多重結(jié)果的 context。我們也了解 IO Monad 如何運(yùn)作，而且我們?cè)谥朗裁词?Monad 之前就已經(jīng)知道他了。

在這個(gè)章節(jié)，我們會(huì)介紹一些其他的 Monad。他們可以把值變成 monadic value，因此可以讓我們的程序更簡(jiǎn)潔清晰。多見識(shí)幾個(gè) Monad 也可以敏銳我們對(duì) Monad 的直覺。

我們即將要介紹的 Monad 都包含在 mtl 這個(gè)套建中。一個(gè) Haskell package 包含了一堆模塊。而 mtl 已經(jīng)包含在 Haskell Platform 中，所以你可能不用另外安裝。要檢查你有沒有這套件，你可以下 ghc-pkg list。這會(huì)列出你已經(jīng)安裝的套件，其中應(yīng)該包含 mtl 后面接著對(duì)應(yīng)的版號(hào)。

你所不知道的 Writer Monad

我們已經(jīng)看過 Maybe, list 以及 IO Monad。現(xiàn)在我們要來看看 Writer Monad。

相對(duì)于 Maybe 是加入可能失敗的 context，list 是加入 non-deterministic 的 context，Writer 則是加進(jìn)一個(gè)附加值的 context，好比 log 一般。Writer 可以讓我們?cè)谟?jì)算的同時(shí)搜集所有 log 紀(jì)錄，并匯集成一個(gè) log 并附加在結(jié)果上。

例如我們想要附加一個(gè) String 好說明我們的值在干么（有可能是為了除錯(cuò)）。想像有一個(gè)函數(shù)接受一個(gè)代表幫派人數(shù)的數(shù)字，然后會(huì)回傳值告訴我們這是否算是一個(gè)龐大的幫派：

isBigGang :: Int -> Bool  
isBigGang x = x > 9  

現(xiàn)在我們希望他不只是回傳 True 或 False，我們還希望他能夠多回傳一個(gè)字串代表 log。這很容易，只要多加一個(gè) String 在 Bool 旁邊就好了。

isBigGang :: Int -> (Bool, String)  
isBigGang x = (x > 9, "Compared gang size to 9.")  

我們現(xiàn)在回傳了一個(gè) Tuple，第一個(gè)元素是原來的布林值，第二個(gè)元素是一個(gè) String。現(xiàn)在我們的值有了一個(gè) context。

ghci> isBigGang 3  
(False,"Compared gang size to 9.")  
ghci> isBigGang 30  
(True,"Compared gang size to 9.")  

到目前為止都還不錯(cuò)，isBigGang 回傳一個(gè)值跟他的 context。對(duì)于正常的數(shù)值來說這樣的寫法都能運(yùn)作良好。但如果我們想要把一個(gè)已經(jīng)具有 context 的值，像是 (3, "Smallish gang.")，喂給 isBigGang 呢？我們又面對(duì)了同樣的問題：如果我們有一個(gè)能接受正常數(shù)值并回傳一個(gè)具有 context 值的 function，那我們要如何喂給他一個(gè)具有 context 的值？

當(dāng)我們?cè)谘芯?nbsp;Maybe monad 的時(shí)候，我們寫了一個(gè) applyMaybe。他接受一個(gè) Maybe a 值跟一個(gè) a -> Maybe b 型態(tài)的函數(shù)，他會(huì)把 Maybe a 喂給這個(gè) function，即便這個(gè) function 其實(shí)是接受 a 而非 Maybe a。applyMaybe 有針對(duì)這樣的 context 做處理，也就是會(huì)留意有可能發(fā)生的失敗情況。但在 a -> Maybe b 里面，我們可以只專心處理正常數(shù)值即可。因?yàn)?nbsp;applyMaybe (之后變成了 >>=)會(huì)幫我們處理需要檢查 Nothing 或 Just 的情況。

我們?cè)賮韺懸粋€(gè)接受附加 log 值的函數(shù)，也就是 (a, String) 型態(tài)的值跟 a -> (b, String) 型態(tài)的函數(shù)。我們稱呼這個(gè)函數(shù)為 applyLog。這個(gè)函數(shù)有的 context 是附加 log 值，而不是一個(gè)可能會(huì)失敗的 context，因此 applyLog 會(huì)確保原有的 log 被保留，并附上從函數(shù)產(chǎn)生出的新的 log。這邊我們來看一下實(shí)作：

applyLog :: (a,String) -> (a -> (b,String)) -> (b,String)  
applyLog (x,log) f = let (y,newLog) = f x in (y,log ++ newLog)  

當(dāng)我們想把一個(gè)具有 context 的值喂給一個(gè)函數(shù)的時(shí)候，我們會(huì)嘗試把值跟他的 context 分開，然后把值喂給函數(shù)再重新接回 context。在 Maybe monad 的情況，我們檢查值是否為 Just x，如果是，便將 x 喂給函數(shù)。而在 log 的情況，我們知道 pair 的其中一個(gè) component 是 log 而另一個(gè)是值。所以我們先取出值 x，將 f apply 到 x，便獲取 (y,newLog)，其中 y 是新的值而 newLog 則是新的 log。但如果我們回傳 newLog，舊的 log 便不會(huì)包含進(jìn)去，所以我們要回傳的是 (y, log ++ newLog)。我們用 ++ 來把新的 log 接到舊的上面。

來看看 applyLog 運(yùn)作的情形：

ghci> (3, "Smallish gang.") `applyLog` isBigGang  
(False,"Smallish gang.Compared gang size to 9")  
ghci> (30, "A freaking platoon.") `applyLog` isBigGang  
(True,"A freaking platoon.Compared gang size to 9")  

跟之前的結(jié)果很像，只差在我們多了伴隨產(chǎn)生的 log。再來多看幾個(gè)例子：

ghci> ("Tobin","Got outlaw name.") `applyLog` (\x -> (length x, "Applied length."))  
(5,"Got outlaw name.Applied length.")  
ghci> ("Bathcat","Got outlaw name.") `applyLog` (\x -> (length x, "Applied length"))  
(7,"Got outlaw name.Applied length")  

可以看到在 lambda 里面 x 只是個(gè)正常的字串而不是 tuple，且 applyLog 幫我們處理掉附加 log 的動(dòng)作。

Monoids 的好處

請(qǐng)確定你了解什么是 Monoids。

到目前為止 applyLog 接受 (a,String) 型態(tài)的值，但為什么 log 一定要是 String 呢？我們使用 ++ 來附加新的 log，難道 ++ 并不能運(yùn)作在任何形式的 list，而一定要限制我們?cè)?nbsp;String 上呢？我們當(dāng)然可以擺脫 String，我們可以如下改變他的型態(tài)：

applyLog :: (a,[c]) -> (a -> (b,[c])) -> (b,[c])      

我們用一個(gè) List 來代表 Log。包含在 List 中的元素型態(tài)必須跟原有的 List 跟回傳的 List 型態(tài)相同，否則我們沒辦法用 ++ 來把他們接起來。

這能夠運(yùn)作在 bytestring 上嗎？絕對(duì)沒問題。只是我們現(xiàn)在的型態(tài)只對(duì) List 有效。我們必須要另外做一個(gè) bytestring 版本的 applyLog。但我們注意到 List 跟 bytestring 都是 monoids。因此他們都是 Monoid type class 的 instance，那代表他們都有實(shí)作 mappend。對(duì) List 以及 bytestring 而言，mappend 都是拿來串接的。

ghci> [1,2,3] `mappend` [4,5,6]  
[1,2,3,4,5,6]  
ghci> B.pack [99,104,105] `mappend` B.pack [104,117,97,104,117,97]  
Chunk "chi" (Chunk "huahua" Empty)  

修改后我們的 applyLog 可以運(yùn)作在任何 monoid 上。我們必須要修改型態(tài)宣告來表示這件事，同時(shí)也要在實(shí)作中把 ++ 改成 mappend：

applyLog :: (Monoid m) => (a,m) -> (a -> (b,m)) -> (b,m)  
applyLog (x,log) f = let (y,newLog) = f x in (y,log `mappend` newLog)  

由于現(xiàn)在包含的值可以是任何 monoid，我們不再需要把 tuple 想成包含一個(gè)值跟對(duì)應(yīng)的 log，我們可以想成他包含一個(gè)值跟一個(gè)對(duì)應(yīng)的 monoid。舉例來說，可以說我們有一個(gè) tuple 包含一個(gè)產(chǎn)品名稱跟一個(gè)符合 monoid 特性的產(chǎn)品價(jià)格。我們可以定義一個(gè) Sum 的 newtype 來保證我們?cè)诓僮鳟a(chǎn)品的時(shí)候也會(huì)把價(jià)錢跟著加起來。

import Data.Monoid  
  
type Food = String  
type Price = Sum Int  

addDrink :: Food -> (Food,Price)  
addDrink "beans" = ("milk", Sum 25)  
addDrink "jerky" = ("whiskey", Sum 99)  
addDrink _ = ("beer", Sum 30)  

我們用 string 來代表食物，用 newtype 重新定義 nInt 為 Sum，來追蹤總共需要花多少錢?？梢宰⒁獾轿覀冇?nbsp;mappend 來操作 Sum 的時(shí)候，價(jià)錢會(huì)被一起加起來。

ghci> Sum 3 `mappend` Sum 9  
Sum {getSum = 12}  

addDrink 的實(shí)作很簡(jiǎn)單，如果我們想吃豆子，他會(huì)回傳 "milk" 以及伴隨的 Sum 25，同樣的如果我們要吃 "jerky"，他就會(huì)回傳 "whiskey"，要吃其他東西的話，就會(huì)回傳 "beer"。乍看之下這個(gè)函數(shù)沒什么特別，但如果用 applyLog 的話就會(huì)有趣些。

ghci> ("beans", Sum 10) `applyLog` addDrink  
("milk",Sum {getSum = 35})  
ghci> ("jerky", Sum 25) `applyLog` addDrink  
("whiskey",Sum {getSum = 124})  
ghci> ("dogmeat", Sum 5) `applyLog` addDrink  
("beer",Sum {getSum = 35})  

牛奶價(jià)值 25 美分，但如果我們也吃了價(jià)值 10 美分的豆子的話，總共需要付 35 美分。這樣很清楚地展示了伴隨的值不一定需要是 log，他可以是任何 monoid。至于兩個(gè)值要如何結(jié)合，那要看 monoid 中怎么定義。當(dāng)我們需要的是 log 的時(shí)候，他們是串接，但這個(gè) case 里面，數(shù)字是被加起來。

由于 addDrink 回傳一個(gè) (Food,Price)，我們可以再把結(jié)果重新喂給 addDrink，這可以很容易告訴我們總共喝了多少錢：

ghci> ("dogmeat", Sum 5) `applyLog` addDrink `applyLog` addDrink  
("beer",Sum {getSum = 65})  

將狗食跟 30 美分的啤酒加在一起會(huì)得到 ("beer", Sum 35)。如果我們用 applyLog 將上面的結(jié)果再喂給 addDrink，我們會(huì)得到 ("beer", Sum 65) 這樣的結(jié)果。

The Writer type

我們認(rèn)識(shí)了一個(gè)附加 monoid 的值其實(shí)表現(xiàn)出來的是一個(gè) monad，我們來再來看看其他類似的 Monad instance。Control.Monad.Writer 這模塊含有 Writer w a 的一個(gè)型態(tài)，里面定義了他 Monad 的 instance，還有一些操作這些值的函數(shù)。

首先，我們來看一下型態(tài)。要把一個(gè) monoid 附加給一個(gè)值，只需要定義一個(gè) tuple 就好了。Writer w a 這型態(tài)其實(shí)是一個(gè) newtype wrapper。他的定義很簡(jiǎn)單：

newtype Writer w a = Writer { runWriter :: (a, w) }      

他包在一個(gè) newtype 里面，并且可以是一個(gè) Monad 的 instance，而且這樣定義的好處是可以跟單純 tuple 的型態(tài)區(qū)分開來。a 這個(gè)型態(tài)參數(shù)代表是包含的值的型態(tài)，而 w 則是附加的 monoid 的型態(tài)。

他 Monad instance 的定義如下：

instance (Monoid w) => Monad (Writer w) where  
    return x = Writer (x, mempty)  
    (Writer (x,v)) >>= f = let (Writer (y, v')) = f x in Writer (y, v `mappend` v')  

首先，我們來看看 >>=。他的實(shí)作基本上就是 applyLog，只是我們的 tuple 現(xiàn)在是包在一個(gè) Writer 的 newtype 中，我們可以用 pattern matching 的方式把他給 unwrap。我們將 x 喂給 f。這會(huì)回給我們 Writer w a。接著可以用 let expression 來做 pattern matching。把結(jié)果綁定到 y 這個(gè)名字上，然后用 mappend 來結(jié)合舊的 monoid 值跟新的 monoid 值。最后把結(jié)果跟 monoid 值用 Writer constructor 包起來，形成我們最后的 Writer value。

那 return 呢？回想 return 的作用是接受一個(gè)值，并回傳一個(gè)具有意義的最小 context 來裝我們的值。那究竟什么樣的 context 可以代表我們的 Writer 呢？如果我們希望 monoid 值所造成的影響愈小愈好，那 mempty 是個(gè)合理的選擇。mempty 是被當(dāng)作 identity monoid value，像是 "" 或 Sum 0，或是空的 bytestring。當(dāng)我們對(duì) mempty 用 mappend 跟其他 monoid 值結(jié)合，結(jié)果會(huì)是其他的 monoid 值。所以如果我們用 return 來做一個(gè) Writer，然后用 >>= 來喂給其他的函數(shù)，那函數(shù)回傳的便是算出來的 monoid。下面我們?cè)囍?nbsp;return 搭配不同 context 來回傳 3：

ghci> runWriter (return 3 :: Writer String Int)  
(3,"")  
ghci> runWriter (return 3 :: Writer (Sum Int) Int)  
(3,Sum {getSum = 0})  
ghci> runWriter (return 3 :: Writer (Product Int) Int)  
(3,Product {getProduct = 1})  

因?yàn)?nbsp;Writer 并沒有定義成 Show 的 instance，我們必須用 runWriter 來把我們的 Writer 轉(zhuǎn)成正常的 tuple。對(duì)于 String，monoid 的值就是空字串。而對(duì)于 Sum 來說則是 0，因?yàn)?nbsp;0 加上其他任何值都會(huì)是對(duì)方。而對(duì) Product 來說，則是 1。

這里的 Writer instance 并沒有定義 fail，所以如果 pattern matching 失敗的話，就會(huì)調(diào)用 error。

Using do notation with Writer

既然我們定義了 Monad 的 instance，我們自然可以用 do 串接 Writer 型態(tài)的值。這在我們需要對(duì)一群 Writer 型態(tài)的值做處理時(shí)顯得特別方便。就如其他的 monad，我們可以把他們當(dāng)作具有 context 的值。在現(xiàn)在這個(gè) case 中，所有的 monoid 的值都會(huì)用 mappend 來連接起來并得到最后的結(jié)果。這邊有一個(gè)簡(jiǎn)單的范例，我們用 Writer 來相乘兩個(gè)數(shù)。

import Control.Monad.Writer  
  
logNumber :: Int -> Writer [String] Int  
logNumber x = Writer (x, ["Got number: " ++ show x])  
  
multWithLog :: Writer [String] Int  
multWithLog = do  
    a <- logNumber 3  
    b <- logNumber 5  
    return (a*b)  

logNumber 接受一個(gè)數(shù)并把這個(gè)數(shù)做成一個(gè) Writer。我們?cè)儆靡淮?string 來當(dāng)作我們的 monoid 值，每一個(gè)數(shù)都跟著一個(gè)只有一個(gè)元素的 list，說明我們只有一個(gè)數(shù)。multWithLog 式一個(gè) Writer，他將 3 跟 5 相乘并確保相乘的紀(jì)錄有寫進(jìn)最后的 log 中。我們用 return 來做成 a*b 的結(jié)果。我們知道 return 會(huì)接受某個(gè)值并加上某個(gè)最小的 context，我們可以確定他不會(huì)多添加額外的 log。如果我們執(zhí)行程序會(huì)得到：

ghci> runWriter multWithLog  
(15,["Got number: 3","Got number: 5"])  

有時(shí)候我們就是想要在某個(gè)時(shí)間點(diǎn)放進(jìn)某個(gè) Monoid value。tell 正是我們需要的函數(shù)。他實(shí)作了 MonadWriter 這個(gè) type class，而且在當(dāng) Writer 用的時(shí)候也能接受一個(gè) monoid value，好比說 ["This is going on"]。我們能用他來把我們的 monoid value 接到任何一個(gè) dummy value () 上來形成一個(gè) Writer。當(dāng)我們拿到的結(jié)果是 () 的時(shí)候，我們不會(huì)把他綁定到變量上。來看一個(gè) multWithLog 的范例：

multWithLog :: Writer [String] Int  
multWithLog = do  
    a <- logNumber 3  
    b <- logNumber 5  
    tell ["Gonna multiply these two"]  
    return (a*b)  

return (a*b) 是我們的最后一行，還記得在一個(gè) do 中的最后一行代表整個(gè) do 的結(jié)果。如果我們把 tell 擺到最后，則 do 的結(jié)果則會(huì)是 ()。我們會(huì)因此丟掉乘法運(yùn)算的結(jié)果。除此之外，log 的結(jié)果是不變的。

ghci> runWriter multWithLog  
(15,["Got number: 3","Got number: 5","Gonna multiply these two"])  

Adding logging to programs

歐幾里得算法是找出兩個(gè)數(shù)的最大公因數(shù)。Haskell 已經(jīng)提供了 gcd 的函數(shù)，但我們來實(shí)作一個(gè)具有 log 功能的 gcd：

gcd' :: Int -> Int -> Int  
gcd' a b   
    | b == 0    = a  
    | otherwise = gcd' b (a `mod` b)  

算法的內(nèi)容很簡(jiǎn)單。首先他檢查第二個(gè)數(shù)字是否為零。如果是零，那就回傳第一個(gè)數(shù)字。如果不是，那結(jié)果就是第二個(gè)數(shù)字跟將第一個(gè)數(shù)字除以第二個(gè)數(shù)字的余數(shù)兩個(gè)數(shù)字的最大公因數(shù)。舉例來說，如果我們想知道 8 跟 3 的最大公因數(shù)，首先可以注意到 3 不是 0。所以我們要求的是 3 跟 2 的最大公因數(shù)(8 除以 3 余二)。接下去我可以看到 2 不是 0，所以我們要再找 2 跟 1 的最大公因數(shù)。同樣的，第二個(gè)數(shù)不是 0，所以我們?cè)僬?1 跟 0 的最大公因數(shù)。最后第二個(gè)數(shù)終于是 0 了，所以我們得到最大公因數(shù)是 1。

ghci> gcd' 8 3  
1  

答案真的是這樣。接著我們想加進(jìn) context，context 會(huì)是一個(gè) monoid value 并且像是一個(gè) log 一樣。就像之前的范例，我們用一串 string 來當(dāng)作我們的 monoid。所以 gcd' 會(huì)長(zhǎng)成這樣：

gcd' :: Int -> Int -> Writer [String] Int  

而他的代碼會(huì)像這樣：

import Control.Monad.Writer  
  
gcd' :: Int -> Int -> Writer [String] Int  
gcd' a b  
  | b == 0 = do  
      tell ["Finished with " ++ show a]  
      return a  
  | otherwise = do  
      tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]  
      gcd' b (a `mod` b)  

這個(gè)函數(shù)接受兩個(gè) Int 并回傳一個(gè) Writer [String] Int，也就是說是一個(gè)有 log context 的 Int。當(dāng) b 等于 0 的時(shí)候，我們用一個(gè) do 來組成一個(gè) Writer 的值。我們先用 tell 來寫入我們的 log，然后用 return 來當(dāng)作 do 的結(jié)果。當(dāng)然我們也可以這樣寫：

Writer (a, ["Finished with " ++ show a])  

但我想 do 的表達(dá)方式是比較容易閱讀的。接下來我們看看當(dāng) b 不等于 0 的時(shí)候。我們會(huì)把 mod 的使用情況寫進(jìn) log。然后在 do 當(dāng)中的第二行遞歸調(diào)用 gcd'。gcd' 現(xiàn)在是回傳一個(gè) Writer 的型態(tài)，所以 gcd' b (a `mod` b) 這樣的寫法是完全沒問題的。

盡管去 trace 這個(gè) gcd' 對(duì)于理解十分有幫助，但我想了解整個(gè)大概念，把值視為具有 context 是更加有用的。

接著來試試跑我們的 gcd'，他的結(jié)果會(huì)是 Writer [String] Int，如果我們把他從 newtype 中取出來，我們會(huì)拿到一個(gè) tuple。tuple 的第一個(gè)部份就是我們要的結(jié)果：

ghci> fst $ runWriter (gcd' 8 3)  
1  

至于 log 呢，由于 log 是一連串 string，我們就用 mapM_ putStrLn 來把這些 string 印出來：

ghci> mapM_ putStrLn $ snd $ runWriter (gcd' 8 3)  
8 mod 3 = 2  
3 mod 2 = 1  
2 mod 1 = 0  
Finished with 1  

把普通的算法轉(zhuǎn)換成具有 log 是很棒的經(jīng)驗(yàn)，我們不過是把普通的 value 重寫成 Monadic value，剩下的就靠 >>= 跟 Writer 來幫我們處理一切。用這樣的方法我們幾乎可以對(duì)任何函數(shù)加上 logging 的功能。我們只要把普通的值換成 Writer，然后把一般的函數(shù)調(diào)用換成 >>= (當(dāng)然也可以用 do)

Inefficient list construction

當(dāng)制作 Writer Monad 的時(shí)候，要特別注意你是使用哪種 monoid。使用 list 的話性能有時(shí)候是沒辦法接受的。因?yàn)?list 是使用 ++ 來作為 mappend 的實(shí)現(xiàn)。而 ++ 在 list 很長(zhǎng)的時(shí)候是非常慢的。

在之前的 gcd' 中，log 并不會(huì)慢是因?yàn)?list append 的動(dòng)作實(shí)際上看起來是這樣：

a ++ (b ++ (c ++ (d ++ (e ++ f))))  

list 是建立的方向是從左到右，當(dāng)我們先建立左邊的部份，而把另一串 list 加到右邊的時(shí)候性能會(huì)不錯(cuò)。但如果我們不小心使用，而讓 Writer monad 實(shí)際在操作 list 的時(shí)候變成像這樣的話。

((((a ++ b) ++ c) ++ d) ++ e) ++ f 

這會(huì)讓我們的操作是 left associative，而不是 right associative。這非常沒有效率，因?yàn)槊看味际前延疫叺牟糠菁拥阶筮叺牟糠?，而左邊的部份又必須要從頭開始建起。

下面這個(gè)函數(shù)跟 gcd' 差不多，只是 log 的順序是相反的。他先紀(jì)錄剩下的操作，然后紀(jì)錄現(xiàn)在的步驟。

import Control.Monad.Writer  
  
gcdReverse :: Int -> Int -> Writer [String] Int  
gcdReverse a b  
  | b == 0 = do  
      tell ["Finished with " ++ show a]  
      return a  
    | otherwise = do  
      result <- gcdReverse b (a `mod` b)  
      tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]  
      return result  

他先遞歸調(diào)用，然后把結(jié)果綁定到 result。然后把目前的動(dòng)作寫到 log，在遞歸的結(jié)果之后。最后呈現(xiàn)的就是完整的 log。

ghci> mapM_ putStrLn $ snd $ runWriter (gcdReverse 8 3)  
Finished with 1  
2 mod 1 = 0  
3 mod 2 = 1  
8 mod 3 = 2  

這沒效率是因?yàn)樗?nbsp;++ 成為 left associative 而不是 right associative。

Difference lists

由于 list 在重復(fù) append 的時(shí)候顯得低效，我們最好能使用一種支持高效 appending 的數(shù)據(jù)結(jié)構(gòu)。其中一種就是 difference list。difference list 很類似 list，只是他是一個(gè)函數(shù)。他接受一個(gè) list 并 prepend 另一串 list 到他前面。一個(gè)等價(jià)于 [1,2,3] 的 difference list 是這樣一個(gè)函數(shù) \xs -> [1,2,3] ++ xs。一個(gè)等價(jià)于 [] 的 difference list 則是 \xs -> [] ++ xs。

Difference list 最酷的地方在于他支持高效的 appending。當(dāng)我們用 ++ 來實(shí)現(xiàn) appending 的時(shí)候，他必須要走到左邊的 list 的尾端，然后把右邊的 list 一個(gè)個(gè)從這邊接上。那 difference list 是怎么作的呢？appending 兩個(gè) difference list 就像這樣

f `append` g = \xs -> f (g xs)  

f 跟 g 這邊是兩個(gè)函數(shù)，他們都接受一個(gè) list 并 prepend 另一串 list。舉例來說，如果 f 代表 ("dog"++)（可以寫成 \xs -> "dog" ++ xs）而 g 是 ("meat"++)，那 f `append` g 就會(huì)做成一個(gè)新的函數(shù)，等價(jià)于：

\xs -> "dog" ++ ("meat" ++ xs)  

append 兩個(gè) difference list 其實(shí)就是用一個(gè)函數(shù)，這函數(shù)先喂一個(gè) list 給第一個(gè) difference list，然后再把結(jié)果喂給第二個(gè) difference list。

我們可以用一個(gè) newtype 來包起來

newtype DiffList a = DiffList { getDiffList :: [a] -> [a] }  

我們包起來的型態(tài)是 [a] -> [a]，因?yàn)?difference list 不過就是一個(gè)轉(zhuǎn)換一個(gè) list 到另一個(gè) list 的函數(shù)。要把普通 list 轉(zhuǎn)換成 difference list 也很容易。

toDiffList :: [a] -> DiffList a  
toDiffList xs = DiffList (xs++)  
  
fromDiffList :: DiffList a -> [a]  
fromDiffList (DiffList f) = f []  

要把一個(gè)普通 list 轉(zhuǎn)成 difference list 不過就是照之前定義的，作一個(gè) prepend 另一個(gè) list 的函數(shù)。由于 difference list 只是一個(gè) prepend 另一串 list 的一個(gè)函數(shù)，假如我們要轉(zhuǎn)回來的話，只要喂給他空的 list 就行了。

這邊我們給一個(gè) difference list 的 Monoid 定義

instance Monoid (DiffList a) where  
    mempty = DiffList (\xs -> [] ++ xs)  
    (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))  

我們可以看到 mempty 不過就是 id，而 mappend 其實(shí)是 function composition。

ghci> fromDiffList (toDiffList [1,2,3,4] `mappend` toDiffList [1,2,3])  
[1,2,3,4,1,2,3]  

現(xiàn)在我們可以用 difference list 來加速我們的 gcdReverse

import Control.Monad.Writer  
  
gcd' :: Int -> Int -> Writer (DiffList String) Int  
gcd' a b  
  | b == 0 = do  
      tell (toDiffList ["Finished with " ++ show a])  
      return a  
  | otherwise = do  
      result <- gcd' b (a `mod` b)  
      tell (toDiffList [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)])  
      return result  

我們只要把 monoid 的型態(tài)從 [String] 改成 DiffList String，并在使用 tell 的時(shí)候把普通的 list 用 toDiffList 轉(zhuǎn)成 difference list 就可以了。

ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ gcdReverse 110 34  
Finished with 2  
8 mod 2 = 0  
34 mod 8 = 2  
110 mod 34 = 8  

我們用 runWriter 來取出 gcdReverse 110 34 的結(jié)果，然后用 snd 取出 log，并用 fromDiffList 轉(zhuǎn)回普通的 list 印出來。

Comparing Performance

要體會(huì) Difference List 能如何增進(jìn)效率，考慮一個(gè)從某數(shù)數(shù)到零的 case。我們紀(jì)錄的時(shí)候就像 gcdReverse 一樣是反過來記的，所以在 log 中實(shí)際上是從零數(shù)到某個(gè)數(shù)。

finalCountDown :: Int -> Writer (DiffList String) ()  
finalCountDown 0 = do  
    tell (toDiffList ["0"])  
finalCountDown x = do  
    finalCountDown (x-1)  
    tell (toDiffList [show x])  

如果我們喂 0，他就只 log 0。如果喂其他正整數(shù)，他會(huì)先倒數(shù)到 0 然后 append 那些數(shù)到 log 中，所以如果我們調(diào)用 finalCountDown 并喂給他 100，那 log 的最后一筆就會(huì)是 "100"。

如果你把這個(gè)函數(shù) load 進(jìn) GHCi 中并喂給他一個(gè)比較大的整數(shù) 500000，你會(huì)看到他無停滯地從 0 開始數(shù)起：

ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ finalCountDown 500000  
0  
1  
2  

但如果我們用普通的 list 而不用 difference list

finalCountDown :: Int -> Writer [String] ()  
finalCountDown 0 = do  
    tell ["0"]  
finalCountDown x = do  
    finalCountDown (x-1)  
    tell [show x]  

并下同樣的指令

ghci> mapM_ putStrLn . snd . runWriter $ finalCountDown 500000  

我們會(huì)看到整個(gè)運(yùn)算卡卡的。

當(dāng)然這不是一個(gè)嚴(yán)謹(jǐn)?shù)臏y(cè)試方法，但足以表顯出 difference list 是比較有效率的寫法。

Reader Monad

在講 Applicative 的章節(jié)中，我們說過了 (->) r 的型態(tài)只是 Functor 的一個(gè) instance。要將一個(gè)函數(shù) f map over 一個(gè)函數(shù) g，基本上等價(jià)于一個(gè)函數(shù)，他可以接受原本 g 接受的參數(shù)，先套用 g 然后再把其結(jié)果丟給 f。

ghci> let f = (*5)  
ghci> let g = (+3)
ghci> (fmap f g) 8

我們已經(jīng)見識(shí)過函數(shù)當(dāng)作 applicative functors 的例子。這樣能讓我們對(duì)函數(shù)的結(jié)果直接進(jìn)行操作。

ghci> let f = (+) <$> (*2) <*> (+10)
ghci> f 3
19

(+) <$> (*2) <*> (+10) 代表一個(gè)函數(shù)，他接受一個(gè)數(shù)值，分別把這數(shù)值交給 (*2) 跟 (+10)。然后把結(jié)果加起來。例如說，如果我們喂 3 給這個(gè)函數(shù)，他會(huì)分別對(duì) 3 做 (*2) 跟 (+10) 的動(dòng)作。而得到 6 跟 13。然后調(diào)用 (+)，而得到 19。

其實(shí) (->) r 不只是一個(gè) functor 跟一個(gè) applicative functor，他也是一個(gè) monad。就如其他 monadic value 一般，一個(gè)函數(shù)也可以被想做是包含一個(gè) context 的。這個(gè) context 是說我們期待某個(gè)值，他還沒出現(xiàn)，但我們知道我們會(huì)把他當(dāng)作函數(shù)的參數(shù)，調(diào)用函數(shù)來得到結(jié)果。

我們已經(jīng)見識(shí)到函數(shù)是怎樣可以看作 functor 或是 applicative functors 了。再來讓我們看看當(dāng)作 Monad 的一個(gè) instance 時(shí)會(huì)是什么樣子。你可以在 Control.Monad.Instances 里面找到，他看起來像這樣：

instance Monad ((->) r) where  
    return x = \_ -> x  
    h >>= f = \w -> f (h w) w  

我們之前已經(jīng)看過函數(shù)的 pure 實(shí)作了，而 return 差不多就是 pure。他接受一個(gè)值并把他放進(jìn)一個(gè) minimal context 里面。而要讓一個(gè)函數(shù)能夠是某個(gè)定值的唯一方法就是讓他完全忽略他的參數(shù)。

而 >>= 的實(shí)作看起來有點(diǎn)難以理解，我們可以仔細(xì)來看看。當(dāng)我們使用 >>= 的時(shí)候，喂進(jìn)去的是一個(gè) monadic value，處理他的是一個(gè)函數(shù)，而吐出來的也是一個(gè) monadic value。在這個(gè)情況下，當(dāng)我們將一個(gè)函數(shù)喂進(jìn)一個(gè)函數(shù)，吐出來的也是一個(gè)函數(shù)。這就是為什么我們?cè)谧钔鈱邮褂昧艘粋€(gè) lambda。在我們目前看過的實(shí)作中，>>= 幾乎都是用 lambda 將內(nèi)部跟外部隔開來，然后在內(nèi)部來使用 f。這邊也是一樣的道理。要從一個(gè)函數(shù)得到一個(gè)結(jié)果，我們必須喂給他一些東西，這也是為什么我們先用 (h w) 取得結(jié)果，然后將他丟給 f。而 f 回傳一個(gè) monadic value，在這邊這個(gè) monadic value 也就是一個(gè)函數(shù)。我們?cè)侔?nbsp;w 喂給他。

如果你還不太懂 >>= 怎么寫出來的，不要擔(dān)心，因?yàn)榻酉聛淼姆独龝?huì)讓你曉得這真的是一個(gè)簡(jiǎn)單的 Monad。我們?cè)煲粋€(gè) do expression 來使用這個(gè) Monad。

import Control.Monad.Instances  
  
addStuff :: Int -> Int  
addStuff = do  
  a <- (*2)  
  b <- (+10)  
  return (a+b)  

這跟我們之前寫的 applicative expression 差不多，只差在他是運(yùn)作在 monad 上。一個(gè) do expression 的結(jié)果永遠(yuǎn)會(huì)是一個(gè) monadic vlaue，這個(gè)也不例外。而這個(gè) monadic value 其實(shí)是一個(gè)函數(shù)。只是在這邊他接受一個(gè)數(shù)字，然后套用 (*2)，把結(jié)果綁定到 a 上面。而 (+10) 也同用被套用到同樣的參數(shù)。結(jié)果被綁定到 b 上。return 就如其他 monad 一樣，只是制作一個(gè)簡(jiǎn)單的 monadic value 而不會(huì)作多余的事情。這讓整個(gè)函數(shù)的結(jié)果是 a+b。如果我們?cè)囍芘芸?，?huì)得到之前的結(jié)果。

ghci> addStuff 3  
19  

其中 3 會(huì)被喂給 (*2) 跟 (+10)。而且他也會(huì)被喂給 return (a+b)，只是他會(huì)忽略掉 3 而永遠(yuǎn)回傳 a+b 正因?yàn)槿绱?，function monad 也被稱作 reader monad。所有函數(shù)都從一個(gè)固定的地方讀取。要寫得更清楚一些，可以把 addStuff 改寫如下：

addStuff :: Int -> Int  
addStuff x = let  
    a = (*2) x  
    b = (+10) x  
    in a+b  

我們見識(shí)了把函數(shù)視作具有 context 的值很自然的可以表達(dá)成 reader monad。只要我們當(dāng)作我們知道函數(shù)會(huì)回傳什么值就好。他作的就是把所有的函數(shù)都黏在一起做成一個(gè)大的函數(shù)，然后把這個(gè)函數(shù)的參數(shù)都喂給全部組成的函數(shù)，這有點(diǎn)取出他們未來的值的意味。實(shí)作做完了然后 >>= 就會(huì)保證一切都能正常運(yùn)作。

State Monad

Haskell 是一個(gè)純粹的語言，正因?yàn)槿绱?，我們的程序是有一堆沒辦法改變?nèi)驙顟B(tài)或變量的函數(shù)所組成，他們只會(huì)作些處理并回傳結(jié)果。這樣的性質(zhì)讓我們很容易思考我們的程序在干嘛，因?yàn)槲覀儾恍枰獡?dān)心變量在某一個(gè)時(shí)間點(diǎn)的值是什么。然而，有一些領(lǐng)域的問題根本上就是依賴于隨著時(shí)間而改變的狀態(tài)。雖然我們也可以用 Haskell 寫出這樣的程序，但有時(shí)候?qū)懫饋硇U痛苦的。這也是為什么 Haskell 要加進(jìn) State Monad 這個(gè)特性。這讓我們?cè)?Haskell 中可以容易地處理狀態(tài)性的問題，并讓其他部份的程序還是保持純粹性。

當(dāng)我們處理亂數(shù)的時(shí)候，我們的函數(shù)接受一個(gè) random generator 并回傳一個(gè)新的亂數(shù)跟一個(gè)新的 random generator。如果我們需要很多個(gè)亂數(shù)，我們可以用前一個(gè)函數(shù)回傳的 random generator 繼續(xù)做下去。當(dāng)我們要寫一個(gè)接受 StdGen 的函數(shù)并產(chǎn)生丟三個(gè)硬幣結(jié)果的函數(shù)，我們會(huì)這樣寫：

threeCoins :: StdGen -> (Bool, Bool, Bool)  
threeCoins gen =   
    let (firstCoin, newGen) = random gen  
        (secondCoin, newGen') = random newGen  
        (thirdCoin, newGen''') = random newGen'  
    in  (firstCoin, secondCoin, thirdCoin)  

他接受一個(gè) gen 然后用 random gen 產(chǎn)生一個(gè) Bool 型態(tài)的值以及新的 generator。要仿真丟第二個(gè)硬幣的話，便使用新的 generator。在其他語言中，多半除了亂數(shù)之外不需要多回傳一個(gè) generator。那是因?yàn)槲覀兛梢詫?duì)現(xiàn)有的進(jìn)行修改。但 Haskell 是純粹的語言，我們沒辦法那么做，所以我們必須要接受一個(gè)狀態(tài)，產(chǎn)生結(jié)果然后回傳一個(gè)新的狀態(tài)，然后用新的狀態(tài)來繼續(xù)做下去。

一般來講你應(yīng)該不會(huì)喜歡這么寫，在程序中有赤裸裸的狀態(tài)，但我們又不想放棄 Haskell 的純粹性質(zhì)。這就是 State Monad 的好處了，他可以幫我們處理這些瑣碎的事情，又讓我們保持 Haskell 的純粹性。

為了深入理解狀態(tài)性的計(jì)算，我們先來看看應(yīng)該給他們什么樣的型態(tài)。我們會(huì)說一個(gè)狀態(tài)性的計(jì)算是一個(gè)函數(shù)，他接受一個(gè)狀態(tài)，回傳一個(gè)值跟一個(gè)新的狀態(tài)。寫起來會(huì)像這樣：

s -> (a,s) 

s 是狀態(tài)的型態(tài)，而 a 是計(jì)算結(jié)果的型態(tài)。

在其他的語言中，賦值大多是被當(dāng)作會(huì)改變狀態(tài)的操作。舉例來說，當(dāng)我們?cè)诿钍秸Z言寫 ``x = 5``，這通常代表的是把 ``5`` 指定給 ``x`` 這變量。而且這邊 ``5`` 是一個(gè) expression。

如果你用函數(shù)語言的角度去思考，你可以把他想做是一個(gè)函數(shù)，接受一個(gè)狀態(tài)，并回傳結(jié)果跟新的狀態(tài)。那新的狀態(tài)代表所有已指定的值與新加入的變量。

這種改變狀態(tài)的計(jì)算，除了想做是一個(gè)接受狀態(tài)并回傳結(jié)果跟新狀態(tài)的函數(shù)外，也可以想做是具有 context 的值。 實(shí)際的值是結(jié)果。然而要得到結(jié)果，我們必須要給一個(gè)初始的狀態(tài)，才能得到結(jié)果跟最后的狀態(tài)。

Stack and Stones

考慮現(xiàn)在我們要對(duì)一個(gè)堆疊的操作建立模型。你可以把東西推上堆疊頂端，或是把東西從頂端拿下來。如果你要的元素是在堆疊的底層的話，你必須要把他上面的東西都拿下來才能拿到他。

我們用一個(gè) list 來代表我們的堆疊。而我們把 list 的頭當(dāng)作堆疊的頂端。為了正確的建立模型，我們要寫兩個(gè)函數(shù)：pop 跟 push。pop 會(huì)接受一個(gè)堆疊，取下一個(gè)元素并回傳一個(gè)新的堆疊，這個(gè)新的堆疊不包含取下的元素。push 會(huì)接受一個(gè)元素，把他堆到堆疊中，并回傳一個(gè)新的堆疊，其包含這個(gè)新的元素。

type Stack = [Int]  
  
pop :: Stack -> (Int,Stack)  
pop (x:xs) = (x,xs)  

push :: Int -> Stack -> ((),Stack)  
push a xs = ((),a:xs)  

我們用 () 來當(dāng)作 pushing 的結(jié)果，畢竟推上堆疊并不需要什么回傳值，他的重點(diǎn)是在改變堆疊。注意到 push 跟 pop 都是改變狀態(tài)的計(jì)算，可以從他們的型態(tài)看出來。

我們來寫一段程序來仿真一個(gè)堆疊的操作。我們接受一個(gè)堆疊，把 3 推上去，然后取出兩個(gè)元素。

stackManip :: Stack -> (Int, Stack)  
stackManip stack = let  
    ((),newStack1) = push 3 stack  
    (a ,newStack2) = pop newStack1  
    in pop newStack2 

我們拿一個(gè) stack 來作 push 3 stack 的動(dòng)作，其結(jié)果是一個(gè) tuple。tuple 的第一個(gè)部份是 ()，而第二個(gè)部份是新的堆疊，我們把他命名成 newStack1。然后我們從 newStack1 上 pop 出一個(gè)數(shù)字。其結(jié)果是我們之前 push 上去的一個(gè)數(shù)字 a，然后把這個(gè)更新的堆疊叫做 newStack2。然后我們從 newStack2 上再 pop 出一個(gè)數(shù)字 b，并得到 newStack3。我們回傳一個(gè) tuple 跟最終的堆疊。

ghci> stackManip [5,8,2,1]  
(5,[8,2,1])  

結(jié)果就是 5 跟新的堆疊 [8,2,1]。注意到 stackManip 是一個(gè)會(huì)改變狀態(tài)的操作。我們把一堆會(huì)改變狀態(tài)的操作綁在一起操作，有沒有覺得很耳熟的感覺。

stackManip 的程序有點(diǎn)冗長(zhǎng)，因?yàn)槲覀円獙懙锰敿?xì)，必須把狀態(tài)給每個(gè)操作，然后把新的狀態(tài)再喂給下一個(gè)。如果我們可以不要這樣作的話，那程序應(yīng)該會(huì)長(zhǎng)得像這樣：

stackManip = do  
    push 3  
    a <- pop  
    pop  

這就是 State Monad 在做的事。有了他，我們便可以免除于要把狀態(tài)操作寫得太明白的窘境。

The State Monad

Control.Monad.State 這個(gè)模塊提供了一個(gè) newtype 包起來的型態(tài)。

newtype State s a = State { runState :: s -> (a,s) }  

一個(gè) State s a 代表的是一個(gè)改變狀態(tài)的操作，他操縱的狀態(tài)為型態(tài) s，而產(chǎn)生的結(jié)果是 a。

我們已經(jīng)見識(shí)過什么是改變狀態(tài)的操作，以及他們是可以被看成具有 context 的值。接著來看看他們 Monad 的 instance：

instance Monad (State s) where  
    return x = State $ \s -> (x,s)  
    (State h) >>= f = State $ \s -> let (a, newState) = h s  
                                        (State g) = f a  
                                    in  g newState  

我們先來看看 return 那一行。我們 return 要作的事是接受一個(gè)值，并做出一個(gè)改變狀態(tài)的操作，讓他永遠(yuǎn)回傳那個(gè)值。所以我們才做了一個(gè) lambda 函數(shù)，\s -> (x,s)。我們把 x 當(dāng)成是結(jié)果，并且狀態(tài)仍然是 s。這就是 return 要完成的 minimal context。

那 >>= 的實(shí)作呢？很明顯的把改變狀態(tài)的操作喂進(jìn) >>= 也必須要丟出另一個(gè)改變狀態(tài)的操作。所以我們用 State 這個(gè) newtype wrapper 來把一個(gè) lambda 函數(shù)包住。這個(gè) lambda 會(huì)是新的一個(gè)改變狀態(tài)的操作。但里面的內(nèi)容是什么？首先我們應(yīng)該要從接受的操作取出結(jié)果。由于 lambda 是在一個(gè)大的操作中，所以我們可以喂給 h 我們現(xiàn)在的狀態(tài)，也就是 s。那會(huì)產(chǎn)生 (a, newState)。到目前為止每次我們?cè)趯?shí)作 >>= 的時(shí)候，我們都會(huì)先從 monadic value 中取出結(jié)果，然后喂給 f 來得到新的 monadic value。在寫 Writer 的時(shí)候，我們除了這樣作還要確保 context 是用 mappend 把舊的 monoid value 跟新的接起來。在這邊我們則是用 f a 得到一個(gè)新的操作 g?，F(xiàn)在我們有了新的操作跟新的狀態(tài)（叫做 newState），我們就把 newState 喂給 g。結(jié)果便是一個(gè) tuple，里面包含了最后的結(jié)果跟最終的狀態(tài)。

有了 >>=，我們便可以把兩個(gè)操作黏在一起，只是第二個(gè)被放在一個(gè)函數(shù)中，專門接受第一個(gè)的結(jié)果。由于 pop 跟 push 已經(jīng)是改變狀態(tài)的操作了，我們可以把他們包在 State 中

import Control.Monad.State  
  
pop :: State Stack Int  
pop = State $ \(x:xs) -> (x,xs)  

push :: Int -> State Stack ()  
push a = State $ \xs -> ((),a:xs)  

pop 已經(jīng)滿足我們的條件，而 push 要先接受一個(gè) Int 才會(huì)回傳我們要的操作。所以我們可以改寫先前的范例如下：

import Control.Monad.State  
  
stackManip :: State Stack Int  
stackManip = do  
  push 3  
  a <- pop  
  pop  

看到我們是怎么把一個(gè) push 跟兩個(gè) pop 黏成一個(gè)操作嗎？當(dāng)我們將他們從一個(gè) newtype 取出，其實(shí)就是需要一個(gè)能喂進(jìn)初始狀態(tài)的函數(shù)：

ghci> runState stackManip [5,8,2,1]  
(5,[8,2,1])  

我們不須綁定第二個(gè) pop，因?yàn)槲覀兏静粫?huì)用到 a，所以可以寫成下面的樣子：

stackManip :: State Stack Int  
stackManip = do  
    push 3  
    pop  
    pop  

再來嘗試另外一種方式，先從堆疊上取下一個(gè)數(shù)字，看看他是不是 5，如果是的話就把他放回堆疊上，如果不是的話就堆上 3 跟 8。

stackStuff :: State Stack ()  
stackStuff = do  
    a <- pop  
    if a == 5  
        then push 5  
        else do  
            push 3  
            push 8 

很直覺吧！我們來看看初始的堆疊的樣子。

ghci> runState stackStuff [9,0,2,1,0]  
((),[8,3,0,2,1,0]) 

還記得我們說過 do 的結(jié)果會(huì)是一個(gè) monadic value，而在 State monad 的 case，do 也就是一個(gè)改變狀態(tài)的函數(shù)。而由于 stackManip 跟 stackStuff 都是改變狀態(tài)的計(jì)算，因此我們可以把他們黏在一起：

moreStack :: State Stack ()  
moreStack = do  
    a <- stackManip  
    if a == 100  
        then stackStuff  
        else return ()  

如果 stackManip 的結(jié)果是 100，我們就會(huì)跑 stackStuff，如果不是的話就什么都不做。return () 不過就是什么是都不做，全部保持原樣。

Contorl.Monad.State 提供了一個(gè) MonadState 的 typeclass，他有兩個(gè)有用的函數(shù)，分別是 get 跟 put。對(duì)于 State 來說，get 的實(shí)作就像這樣：

get = State $ \s -> (s,s)

他只是取出現(xiàn)在的狀態(tài)除此之外什么也不做。而 put 函數(shù)會(huì)接受一個(gè)狀態(tài)并取代掉現(xiàn)有的狀態(tài)。

put newState = State $ \s -> ((),newState)  

有了這兩個(gè)狀態(tài)，我們便可以看到現(xiàn)在堆疊中有什么，或是把整個(gè)堆疊中的元素?fù)Q掉。

stackyStack :: State Stack ()  
stackyStack = do  
    stackNow <- get  
    if stackNow == [1,2,3]  
        then put [8,3,1]  
        else put [9,2,1]  

我們可以看看對(duì)于 State 而言，>>= 的型態(tài)會(huì)是什么：

(>>=) :: State s a -> (a -> State s b) -> State s b  

我們可以看到狀態(tài)的型態(tài)都是 s，而結(jié)果從型態(tài) a 變成型態(tài) b。這代表我們可以把好幾個(gè)改變狀態(tài)的計(jì)算黏在一起，這些計(jì)算的結(jié)果可以都不一樣，但狀態(tài)的型態(tài)會(huì)是一樣的。舉例來說，對(duì)于 Maybe 而言，>>= 的型態(tài)會(huì)是：

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b  

Maybe 不變是有道理的，但如果用 >>= 來把兩種不同的 monad 接起來是沒道理的。但對(duì)于 state monad 而言，monad 其實(shí)是 State s，所以如果 s 不一樣，我們就要用 >>= 來把兩個(gè) monad 接起來。

隨機(jī)性與 state monad

在章節(jié)的一開始，我們知道了在 Haskell 中要產(chǎn)生亂數(shù)的不方便。我們要拿一個(gè)產(chǎn)生器，并回傳一個(gè)亂數(shù)跟一個(gè)新的產(chǎn)生器。接下來我們還一定要用新的產(chǎn)生器不可。但 State Monad 讓我們可以方便一些。

System.Random 中的 random 函數(shù)有下列的型態(tài)：

random :: (RandomGen g, Random a) => g -> (a, g)  

代表他接受一個(gè)亂數(shù)產(chǎn)生器，并產(chǎn)生一個(gè)亂數(shù)跟一個(gè)新的產(chǎn)生器。很明顯他是一個(gè)會(huì)改變狀態(tài)的計(jì)算，所以我們可以用 newtype 把他包在一個(gè) State 中，然后把他當(dāng)作 monadic value 來操作。

import System.Random  
import Control.Monad.State  
  
randomSt :: (RandomGen g, Random a) => State g a  
randomSt = State random  

這樣我們要丟三個(gè)硬幣的結(jié)果可以改寫成這樣：

import System.Random  
import Control.Monad.State  
  
threeCoins :: State StdGen (Bool,Bool,Bool)  
threeCoins = do  
  a <- randomSt  
  b <- randomSt  
  c <- randomSt  
  return (a,b,c)  

threeCoins 是一個(gè)改變狀態(tài)的計(jì)算，他接受一個(gè)初始的亂數(shù)產(chǎn)生器，他會(huì)把他喂給 randomSt，他會(huì)產(chǎn)生一個(gè)數(shù)字跟一個(gè)新的產(chǎn)生器，然后會(huì)一直傳遞下去。我們用 return (a,b,c) 來呈現(xiàn) (a,b,c)，這樣并不會(huì)改變最近一個(gè)產(chǎn)生器的狀態(tài)。

ghci> runState threeCoins (mkStdGen 33)  
((True,False,True),680029187 2103410263)

要完成像這樣要改變狀態(tài)的任務(wù)便因此變得輕松了很多。

Error Monad

我們知道 Maybe 是拿來賦予一個(gè)值具有可能失敗的 context。一個(gè)值可能會(huì)是 Just something 或是一個(gè) Nothing。盡管這很有用，但當(dāng)我們拿到了一個(gè) Nothing，我們只知道他失敗了，但我們沒辦法塞進(jìn)一些有用的信息，告訴我們究竟是在什么樣的情況下失敗了。

而 Either e a 則能讓我們可以加入一個(gè)可能會(huì)發(fā)生錯(cuò)誤的 context，還可以增加些有用的消息，這樣能讓我們知道究竟是什么東西出錯(cuò)了。一個(gè) Either e a 的值可以是代表正確的 Right，或是代表錯(cuò)誤的 Left，例如說：

ghci> :t Right 4  
Right 4 :: (Num t) => Either a t  
ghci> :t Left "out of cheese error"  
Left "out of cheese error" :: Either [Char] b  

這就像是加強(qiáng)版的 Maybe，他看起來實(shí)在很像一個(gè) monad，畢竟他也可以當(dāng)作是一個(gè)可能會(huì)發(fā)生錯(cuò)誤的 context，只是多了些消息罷了。

在 Control.Monad.Error 里面有他的 Monad instance。

instance (Error e) => Monad (Either e) where  
    return x = Right x   
    Right x >>= f = f x  
    Left err >>= f = Left err  
    fail msg = Left (strMsg msg)  

return 就是建立起一個(gè)最小的 context，由于我們用 Right 代表正確的結(jié)果，所以他把值包在一個(gè) Right constructor 里面。就像實(shí)作 Maybe 時(shí)的 return 一樣。

>>= 會(huì)檢查兩種可能的情況：也就是 Left 跟 Right。如果進(jìn)來的是 Right，那我們就調(diào)用 f，就像我們?cè)趯?nbsp;Just 的時(shí)候一樣，只是調(diào)用對(duì)應(yīng)的函數(shù)。而在錯(cuò)誤的情況下，Left 會(huì)被傳出來，而且里面保有描述失敗的值。

Either e 的 Monad instance 有一項(xiàng)額外的要求，就是包在 Left 中的型態(tài)，也就是 e，必須是 Error typeclass 的 instance。Error 這個(gè) typeclass 描述一個(gè)可以被當(dāng)作錯(cuò)誤消息的型態(tài)。他定義了 strMsg 這個(gè)函數(shù)，他接受一個(gè)用字串表達(dá)的錯(cuò)誤。一個(gè)明顯的范例就是 String 型態(tài)，當(dāng)他是 String 的時(shí)候，strMsg 只不過回傳他接受到的字串。

ghci> :t strMsg  
strMsg :: (Error a) => String -> a  
ghci> strMsg "boom!" :: String  
"boom!"  

但因?yàn)槲覀兺ǔＴ谟?nbsp;Either 來描述錯(cuò)誤的時(shí)候，是用 String 來裝錯(cuò)誤消息，所以我們也不用擔(dān)心這一點(diǎn)。當(dāng)在 do 里面做 pattern match 失敗的時(shí)候，Left 的值會(huì)拿來代表失敗。

總之來看看一個(gè)范例吧：

ghci> Left "boom" >>= \x -> return (x+1)  
Left "boom"  
ghci> Right 100 >>= \x -> Left "no way!"  
Left "no way!" 

當(dāng)我們用 >>= 來把一個(gè) Left 喂進(jìn)一個(gè)函數(shù)，函數(shù)的運(yùn)算會(huì)被忽略而直接回傳丟進(jìn)去的 Left 值。當(dāng)我們喂 Right 值給函數(shù)，函數(shù)就會(huì)被計(jì)算而得到結(jié)果，但函數(shù)還是產(chǎn)生了一個(gè) Left 值。

當(dāng)我們?cè)囍挂粋€(gè) Right 值給函數(shù)，而且函數(shù)也成功地計(jì)算，我們卻碰到了一個(gè)奇怪的 type error。

ghci> Right 3 >>= \x -> return (x + 100)  
  
<interactive>:1:0:  
  Ambiguous type variable `a' in the constraints:  
    `Error a' arising from a use of `it' at <interactive>:1:0-33  
    `Show a' arising from a use of `print' at <interactive>:1:0-33  
  Probable fix: add a type signature that fixes these type variable(s)  

Haskell 警告說他不知道要為 e 選擇什么樣的型態(tài)，盡管我們是要印出 Right 的值。這是因?yàn)?nbsp;Error e 被限制成 Monad。把 Either 當(dāng)作 Monad 使用就會(huì)碰到這樣的錯(cuò)誤，你只要明確寫出 type signature 就行了：

ghci> Right 3 >>= \x -> return (x + 100) :: Either String Int  
Right 103  

這樣就沒問題了。

撇除這個(gè)小毛病，把 Either 當(dāng) Monad 使用就像使用 Maybe 一樣。在前一章中，我們展示了 Maybe 的使用方式。你可以把前一章的范例用 Either 重寫當(dāng)作練習(xí)。

一些實(shí)用的 Moandic functions

在這個(gè)章節(jié)，我們會(huì)看看一些操作 monadic value 的函數(shù)。這樣的函數(shù)通常我們稱呼他們?yōu)?monadic function。其中有些你是第一次見到，但有些不過是 filter 或 foldl 的變形。讓我們來看看吧！

liftM

當(dāng)我們開始學(xué)習(xí) Monad 的時(shí)候，我們是先學(xué)習(xí) functors，他代表可以被 map over 的事物。接著我們學(xué)了 functors 的加強(qiáng)版，也就是 applicative functors，他可以對(duì) applicative values 做函數(shù)的套用，也可以把一個(gè)一般值放到一個(gè)缺省的 context 中。最后，我們介紹在 applicative functors 上更進(jìn)一步的 monad，他讓這些具有 context 的值可以被喂進(jìn)一般函數(shù)中。

也就是說每一個(gè) monad 都是個(gè) applicative functor，而每一個(gè) applicative functor 也都是一個(gè) functor。Applicative typeclass 中有加入限制，讓每一個(gè) Applicative 都是 Functor。但 Monad 卻沒有這樣的限制，讓每個(gè) Monad 都是 Applicative。這是因?yàn)?nbsp;Monad 這個(gè) typeclass 是在 Applicative 引入前就存在的緣故。

但即使每個(gè) monad 都是一個(gè) functor，但我們不需要依賴 Functor 的定義。那是因?yàn)槲覀冇?nbsp;liftM 這個(gè)函數(shù)。他會(huì)接受一個(gè)函數(shù)跟一個(gè) monadic value，然后把函數(shù) map over 那些 monadic value。所以他其實(shí)就是 fmap，以下是他的型態(tài)：

liftM :: (Monad m) => (a -> b) -> m a -> m b  

而這是 fmap 的型態(tài)：

fmap :: (Functor f) => (a -> b) -> f a -> f b

如果 Functor 跟 Monad 的 instance 遵守 functor 跟 monad 的法則（到目前為止我們看過的 monad 都遵守），那這兩個(gè)函數(shù)其實(shí)是等價(jià)的。這就像 pure 跟 return 其實(shí)是同一件事，只是一個(gè)在 Applicative 中，而另外一個(gè)在 Monad 里面，我們來試試看 liftM 吧：

ghci> liftM (*3) (Just 8)  
Just 24  
ghci> fmap (*3) (Just 8)  
Just 24  
ghci> runWriter $ liftM not $ Writer (True, "chickpeas")  
(False,"chickpeas")  
ghci> runWriter $ fmap not $ Writer (True, "chickpeas")  
(False,"chickpeas")  
ghci> runState (liftM (+100) pop) [1,2,3,4]  
(101,[2,3,4])  
ghci> runState (fmap (+100) pop) [1,2,3,4]  
(101,[2,3,4]) 

我們已經(jīng)知道 fmap 是如何運(yùn)作在 Maybe 上。而 liftM 又跟 fmap 等價(jià)。對(duì)于 Writer 型態(tài)的值而言，函數(shù)只有對(duì)他的第一個(gè) component 做處理。而對(duì)于改變狀態(tài)的計(jì)算，fmap 跟 liftM 也都是產(chǎn)生另一個(gè)改變狀態(tài)的計(jì)算。我們也看過了 (+100) 當(dāng)作用在 pop 上會(huì)產(chǎn)生 (1, [2,3,4])。

來看看 liftM 是如何被實(shí)作的：

liftM :: (Monad m) => (a -> b) -> m a -> m b  
liftM f m = m >>= (\x -> return (f x)) 

或者用 do 來表示得清楚些

liftM :: (Monad m) => (a -> b) -> m a -> m b  
liftM f m = do  
    x <- m  
    return (f x)  

我們喂一個(gè) monadic value m 給函數(shù)，我們套用那個(gè)函數(shù)然后把結(jié)果放進(jìn)一個(gè)缺省的 context。由于遵守 monad laws，這保證這操作不會(huì)改變 context，只會(huì)呈現(xiàn)最后的結(jié)果。我們可以看到實(shí)作中 liftM 也沒有用到 Functor 的性質(zhì)。這代表我們能只用 monad 提供給我們的就實(shí)作完 fmap。這特性讓我們可以得到 monad 比 functor 性質(zhì)要強(qiáng)的結(jié)論。

Applicative 讓我們可以操作具有 context 的值就像操作一般的值一樣。 就像這樣：

ghci> (+) <$> Just 3 <*> Just 5  
Just 8  
ghci> (+) <$> Just 3 <*> Nothing  
Nothing  

使用 applicative 的特性讓事情變得很精簡(jiǎn)。 <$> 不過就是 fmap，而 <*> 只是一個(gè)具有下列型態(tài)的函數(shù)：

(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b  

他有點(diǎn)像 fmap，只是函數(shù)本身有一個(gè) context。我們必須把他從 context 中抽出，對(duì) f a 做 map over 的東做，然后再放回 context 中。由于在 Haskel 中函數(shù)缺省都是 curried，我們便能用 <$> 以及 <*> 來讓接受多個(gè)參數(shù)的函數(shù)也能接受 applicative 種類的值。

總之 <*> 跟 fmap 很類似，他也能只用 Monad 保證的性質(zhì)實(shí)作出來。ap 這個(gè)函數(shù)基本上就是 <*>，只是他是限制在 Monad 上而不是 Applicative 上。這邊是他的定義：

ap :: (Monad m) => m (a -> b) -> m a -> m b  
ap mf m = do  
    f <- mf  
    x <- m  
    return (f x)  

mf 是一個(gè) monadic value，他的結(jié)果是一個(gè)函數(shù)。由于函數(shù)跟值都是放在 context 中，假設(shè)我們從 context 取出的函數(shù)叫 f，從 context 取出的值叫 x，我們把 x 喂給 f 然后再把結(jié)果放回 context。像這樣：

ghci> Just (+3) <*> Just 4  
Just 7  
ghci> Just (+3) `ap` Just 4  
Just 7  
ghci> [(+1),(+2),(+3)] <*> [10,11]  
[11,12,12,13,13,14]  
ghci> [(+1),(+2),(+3)] `ap` [10,11]  
[11,12,12,13,13,14]  

由于我們能用 Monad 提供的函數(shù)實(shí)作出 Applicative 的函數(shù)，因此我們看到 Monad 有比 applicative 強(qiáng)的性質(zhì)。事實(shí)上，當(dāng)我們知道一個(gè)型態(tài)是 monad 的時(shí)候，大多數(shù)會(huì)先定義出 Monad 的 instance，然后才定義 Applicative 的 instance。而且只要把 pure 定義成 return，<*> 定義成 ap 就行了。同樣的，如果你已經(jīng)有了 Monad 的 instance，你也可以簡(jiǎn)單的定義出 Functor，只要把 fmap 定義成 liftM 就行了。

liftA2 是一個(gè)方便的函數(shù)，他可以把兩個(gè) applicative 的值喂給一個(gè)函數(shù)。他的定義很簡(jiǎn)單：

liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c  
liftA2 f x y = f <$> x <*> y  

liftM2 也是做差不多的事情，只是多了 Monad 的限制。在函式庫中其實(shí)也有 liftM3，liftM4 跟 liftM5。

我們看到了 monad 相較于 applicative 跟 functor 有比較強(qiáng)的性質(zhì)。盡管 moand 有 functor 跟 applicative functor 的性質(zhì)，但他們不見得有 Functor 跟 Applicative 的 instance 定義。所以我們查看了一些在 monad 中定義，且等價(jià)于 functor 或 applicative functor 所具有的函數(shù)。

The join function

如果一個(gè) monadic value 的結(jié)果是另一個(gè) monadic value，也就是其中一個(gè) monadic value 被包在另一個(gè)里面，你能夠把他們變成一個(gè)普通的 monadic value 嗎？就好像把他們打平一樣。譬如說，我們有 Just (Just 9)，我們能夠把他變成 Just 9 嗎？事實(shí)上是可以的，這也是 monad 的一個(gè)性質(zhì)。也就是我要看的 join 函數(shù)，他的型態(tài)是這樣：

join :: (Monad m) => m (m a) -> m a  

他接受一個(gè)包在另一個(gè) monadic value 中的 monadic value，然后會(huì)回給我們一個(gè)普通的 monadic value。這邊有一些 Maybe 的范例：

ghci> join (Just (Just 9))  
Just 9  
ghci> join (Just Nothing)  
Nothing  
ghci> join Nothing  
Nothing  

第一行是一個(gè)計(jì)算成功的結(jié)果包在另一個(gè)計(jì)算成功的結(jié)果，他們應(yīng)該要能結(jié)合成為一個(gè)比較大的計(jì)算成功的結(jié)果。第二行則是一個(gè) Nothing 包在一個(gè) Just 中。我們之前在處理 Maybe 型態(tài)的值時(shí)，會(huì)用 <*> 或 >>= 把他們結(jié)合起來。輸入必須都是 Just 時(shí)結(jié)果出來才會(huì)是 Just。如果中間有任何的失敗，結(jié)果就會(huì)是一個(gè)失敗的結(jié)果。而第三行就是這樣，我們嘗試把失敗的結(jié)果接合起來，結(jié)果也會(huì)是一個(gè)失敗。

要 join 一個(gè) list 也是很簡(jiǎn)單：

ghci> join [[1,2,3],[4,5,6]]  
[1,2,3,4,5,6]  

你可以看到，對(duì)于 list 而言 join 不過就是 concat。 而要 join 一個(gè)包在 Writer 中的 Writer， 我們必須用 mappend：

ghci> runWriter $ join (Writer (Writer (1,"aaa"),"bbb"))  
(1,"bbbaaa")  

"bbb" 先被加到 monoid 中，接著 "aaa" 被附加上去。你想要查看 Writer 中的值的話，必須先把值寫進(jìn)去才行。

要對(duì) Either 做 join 跟對(duì) Maybe 做 join 是很類似的：

ghci> join (Right (Right 9)) :: Either String Int  
Right 9  
ghci> join (Right (Left "error")) :: Either String Int  
Left "error"  
ghci> join (Left "error") :: Either String Int  
Left "error"  

如果我們對(duì)一個(gè)包了另外一個(gè)改變狀態(tài)的計(jì)算的進(jìn)行改變狀態(tài)的計(jì)算，要作 join 的動(dòng)作會(huì)讓外面的先被計(jì)算，然后才是計(jì)算里面的：

ghci> runState (join (State $ \s -> (push 10,1:2:s))) [0,0,0]  
((),[10,1,2,0,0,0])  

這邊的 lambda 函數(shù)接受一個(gè)狀態(tài)，并把 2 跟 1 放到堆疊中，并把 push 10 當(dāng)作他的結(jié)果。當(dāng)對(duì)整個(gè)東西做 join 的時(shí)候，他會(huì)先把 2 跟 1 放到堆疊上，然后進(jìn)行 push 10 的計(jì)算，因而把 10 放到堆疊的頂端。

join 的實(shí)作像是這樣：

join :: (Monad m) => m (m a) -> m a  
join mm = do  
    m <- mm  
    m  

因?yàn)?nbsp;mm 的結(jié)果會(huì)是一個(gè) monadic value，我們單獨(dú)用 m <- mm 拿取他的結(jié)果。這也可以說明 Maybe 只有當(dāng)外層跟內(nèi)層的值都是 Just 的時(shí)候才會(huì)是 Just。如果把 mm 的值設(shè)成 Just (Just 8) 的話，他看起來會(huì)是這樣：

joinedMaybes :: Maybe Int  
joinedMaybes = do  
    m <- Just (Just 8)  
    m  

最有趣的是對(duì)于一個(gè) monadic value 而言，用 >>= 把他喂進(jìn)一個(gè)函數(shù)其實(shí)等價(jià)于對(duì) monad 做 mapping over 的動(dòng)作，然后用 join 來把值從 nested 的狀態(tài)變成扁平的狀態(tài)。也就是說 m >>= f 其實(shí)就是 join (fmap f m)。如果你仔細(xì)想想的話其實(shí)很明顯。>>= 的使用方式是，把一個(gè) monadic value 喂進(jìn)一個(gè)接受普通值的函數(shù)，但他卻會(huì)回傳 monadic value。如果我們 map over 一個(gè) monadic value，我們會(huì)做成一個(gè) monadic value 包了另外一個(gè) monadic value。例如說，我們現(xiàn)在手上有 Just 9 跟 \x -> Just (x+1)。如果我們把這個(gè)函數(shù) map over Just 9，我們會(huì)得到 Just (Just 10)

事實(shí)上 m >>= f 永遠(yuǎn)等價(jià)于 join (fmap f m) 這性質(zhì)非常有用。如果我們要定義自己的 Monad instance，要知道怎么把 nested monadic value 變成扁平比起要定義 >>= 是比較容易的一件事。

filterM

filter 函數(shù)是 Haskell 中不可或缺的要素。他接受一個(gè)斷言(predicate)跟一個(gè) list 來過濾掉斷言為否的部份并回傳一個(gè)新的 list。他的型態(tài)是這樣：

filter :: (a -> Bool) -> [a] -> [a]  

predicate 能接 list 中的一個(gè)元素并回傳一個(gè) Bool 型態(tài)的值。但如果 Bool 型態(tài)其實(shí)是一個(gè) monadic value 呢？也就是他有一個(gè) context。例如說除了 True 跟 False 之外還伴隨一個(gè) monoid，像是 ["Accepted the number 5"]，或 ["3 is too small"]。照前面所學(xué)的聽起來是沒問題，而且產(chǎn)出的 list 也會(huì)跟隨 context，在這個(gè)例子中就是 log。所以如果 Bool 會(huì)回傳伴隨 context 的布林值，我們會(huì)認(rèn)為最終的結(jié)果也會(huì)具有 context。要不然這些 context 都會(huì)在處理過程中遺失。

在 Control.Monad 中的 filterM 函數(shù)正是我們所需要的，他的型態(tài)如下：

filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]  

predicate 會(huì)回傳一個(gè) monadic value，他的結(jié)果會(huì)是 Bool 型態(tài)，由于他是 monadic value，他的 context 有可能會(huì)是任何 context，譬如說可能的失敗，non-determinism，甚至其他的 context。一旦我們能保證 context 也會(huì)被保存在最后的結(jié)果中，結(jié)果也就是一個(gè) monadic value。

我們來寫一個(gè)接受 list 然后過濾掉小于 4 的函數(shù)。先嘗試使用 filter 函數(shù)：

ghci> filter (\x -> x < 4) [9,1,5,2,10,3]  
[1,2,3] 

很簡(jiǎn)單吧。接著我們?cè)谧鰝€(gè) predicate，除了表達(dá) True 或 False 之外，還提供了一個(gè) log。我們會(huì)用 Writer monad 來表達(dá)這件事：

keepSmall :: Int -> Writer [String] Bool  
keepSmall x  
    | x < 4 = do  
        tell ["Keeping " ++ show x]  
        return True  
    | otherwise = do  
        tell [show x ++ " is too large, throwing it away"]  
        return False  

這個(gè)函數(shù)會(huì)回傳 Writer [String] Bool 而不是一個(gè)單純的 Bool。他是一個(gè) monadic predicate。如果掃到的數(shù)字小于 4 的話，我們就會(huì)回報(bào)要保存他，而且回傳 return True。

接著，我們把他跟一個(gè) list 喂給 filterM。由于 predicate 會(huì)回傳 Writer，所以結(jié)果仍會(huì)是一個(gè) Writer 值。

ghci> fst $ runWriter $ filterM keepSmall [9,1,5,2,10,3]  
[1,2,3]  

要檢查 Writer 的結(jié)果，我們想要印出 log 看看里面有什么東西：

ghci> mapM_ putStrLn $ snd $ runWriter $ filterM keepSmall [9,1,5,2,10,3]  
9 is too large, throwing it away  
Keeping 1  
5 is too large, throwing it away  
Keeping 2  
10 is too large, throwing it away  
Keeping 3  

提供 monadic predicate 給 filterM，我們便能夠做 filter 的動(dòng)作，同時(shí)還能保有 monadic context。

一個(gè)比較炫的技巧是用 filterM 來產(chǎn)生一個(gè) list 的 powerset。一個(gè) powerset 就是一個(gè)集合所有子集所形成的集合。如果說我們的 list 是 [1,2,3]，那他個(gè) powerset 就會(huì)是：

[1,2,3]  
[1,2]  
[1,3]  
[1]  
[2,3]  
[2]  
[3]  
[]  

換句話說，要產(chǎn)生一個(gè) powerset 就是要列出所有要丟掉跟保留的組合。[2,3] 只不過代表我們把 1 給丟掉而已。

我們要依賴 non-determinism 來寫我們這產(chǎn)生 powerset 的函數(shù)。我們接受一個(gè) list [1,2,3] 然后查看第一個(gè)元素，這個(gè)例子中是 1，我們會(huì)問：我們要保留他呢？還是丟掉他呢？答案是我們都要做。所以我們會(huì)用一個(gè) non-determinism 的 predicate 來過濾我的 list。也就是我們的 powerset 函數(shù)：

powerset :: [a] -> [[a]]  
powerset xs = filterM (\x -> [True, False]) xs 

等等，我們已經(jīng)寫完了嗎？沒錯(cuò)，就這么簡(jiǎn)單，我們可以同時(shí)丟掉跟保留每個(gè)元素。只要我們用 non-deterministic predicate，那結(jié)果也就是一個(gè) non-deterministic value，也便是一個(gè) list 的 list。試著跑跑看：

ghci> powerset [1,2,3]  
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]  

這樣的寫法需要讓你好好想一下，但如果你能接受 list 其實(shí)就是 non-deterministic value 的話，那要想通會(huì)比較容易一些。

foldM

foldl 的 monadic 的版本叫做 foldM。如果你還有印象的話，foldl 會(huì)接受一個(gè) binary 函數(shù)，一個(gè)起始累加值跟一串 list，他會(huì)從左邊開始用 binary 函數(shù)每次帶進(jìn)一個(gè)值來 fold。foldM 也是做同樣的事，只是他接受的這個(gè) binary 函數(shù)會(huì)產(chǎn)生 monadic value。不意外的，他的結(jié)果也會(huì)是 monadic value。foldl 的型態(tài)是：

foldl :: (a -> b -> a) -> a -> [b] -> a 

而 foldM 的型態(tài)則是：

foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a  

binary 函數(shù)的回傳值是 monadic，所以結(jié)果也會(huì)是 monadic。我們來試著把 list 的值用 fold 全部加起來：

ghci> foldl (\acc x -> acc + x) 0 [2,8,3,1]  
14  

這邊起始的累加值是 0，首先 2 會(huì)被加進(jìn)去，變成 2。然后 8 被加進(jìn)去變成 10，直到我們沒有值可以再加，那便是最終的結(jié)果。

但如果我們想額外加一個(gè)條件，也就是當(dāng)碰到一個(gè)數(shù)字大于 9 時(shí)候，整個(gè)運(yùn)算就算失敗呢？一種合理的修改就是用一個(gè) binary 函數(shù)，他會(huì)檢查現(xiàn)在這個(gè)數(shù)是否大于 9，如果是便引發(fā)失敗，如果不是就繼續(xù)。由于有失敗的可能性，我們便需要這個(gè) binary 函數(shù)回傳一個(gè) Maybe，而不是一個(gè)普通的值。我們來看看這個(gè)函數(shù)：

binSmalls :: Int -> Int -> Maybe Int  
binSmalls acc x  
    | x > 9     = Nothing  
    | otherwise = Just (acc + x)  

由于這邊的 binary 函數(shù)是 monadic function，我們不能用普通的 foldl，我們必須用 foldM：

ghci> foldM binSmalls 0 [2,8,3,1]  
Just 14  
ghci> foldM binSmalls 0 [2,11,3,1]  
Nothing  

由于這串 list 中有一個(gè)數(shù)值大于 9，所以整個(gè)結(jié)果會(huì)是 Nothing。另外你也可以嘗試 fold 一個(gè)回傳 Writer 的 binary 函數(shù)，他會(huì)在 fold 的過程中紀(jì)錄你想紀(jì)錄的信息。

Making a safe RPN calculator

之前的章節(jié)我們實(shí)作了一個(gè) RPN 計(jì)算機(jī)，但我們沒有做錯(cuò)誤的處理。他只有在輸入是合法的時(shí)候才會(huì)運(yùn)算正確。假如有東西出錯(cuò)了，整個(gè)程序便會(huì)當(dāng)?shù)?。我們?cè)谶@章看到了要怎樣把代碼轉(zhuǎn)換成 monadic 的版本，我們先嘗適用 Maybe monad 來幫我們的 RPN 計(jì)算機(jī)加上些錯(cuò)誤處理。

我們的 RPN 計(jì)算機(jī)接受一個(gè)像 "1 3 + 2 *" 這樣的字串，把他斷成 word，變成 ["1","3","+","2","*"] 這樣。然后用一個(gè) binary 函數(shù)，跟一個(gè)空的堆疊，從左邊開始或是將數(shù)值推進(jìn)堆疊中，或是操作堆疊最上層的兩個(gè)元素。

以下便是程序的核心部份：

import Data.List  
  
solveRPN :: String -> Double  
solveRPN = head . foldl foldingFunction [] . words  

我們把輸入變成一個(gè)字串的 list，從左邊開始 fold，當(dāng)堆疊中只剩下一個(gè)元素的時(shí)候，他便是我們要的答案。以下是我們的 folding 函數(shù)：

foldingFunction :: [Double] -> String -> [Double]  
foldingFunction (x:y:ys) "*" = (x * y):ys  
foldingFunction (x:y:ys) "+" = (x + y):ys  
foldingFunction (x:y:ys) "-" = (y - x):ys  
foldingFunction xs numberString = read numberString:xs  

這邊我們的累加元素是一個(gè)堆疊，我們用一個(gè) Double 的 list 來表示他。當(dāng)我們?cè)谧?folding 的過程，如果當(dāng)前的元素是一個(gè) operator，他會(huì)從堆疊上拿下兩個(gè)元素，用 operator 施行運(yùn)算然后把結(jié)果放回堆疊。如果當(dāng)前的元素是一個(gè)表示成字串的數(shù)字，他會(huì)把字串轉(zhuǎn)換成數(shù)字，并回傳一個(gè)新的堆疊包含了轉(zhuǎn)換后的數(shù)字。

我們首先把我們的 folding 函數(shù)加上處理錯(cuò)誤的 case，所以他的型態(tài)會(huì)變成這樣：

foldingFunction :: [Double] -> String -> Maybe [Double]  

他不是回傳一個(gè) Just 的堆疊就是回傳 Nothing。

reads 函數(shù)就像 read 一樣，差別在于他回傳一個(gè) list。在成功讀取的情況下 list 中只包含讀取的那個(gè)元素。如果他失敗了，他會(huì)回傳一個(gè)空的 list。除了回傳讀取的元素，他也回傳剩下讀取失敗的元素。他必須要看完整串輸入，我們想把他弄成一個(gè) readMaybe 的函數(shù)，好方便我們進(jìn)行。

readMaybe :: (Read a) => String -> Maybe a  
readMaybe st = case reads st of [(x,"")] -> Just x  
                                _ -> Nothing  

測(cè)試結(jié)果如下：

ghci> readMaybe "1" :: Maybe Int  
Just 1  
ghci> readMaybe "GO TO HELL" :: Maybe Int  
Nothing  

看起來運(yùn)作正常。我們?cè)侔阉兂梢粋€(gè)可以處理失敗情況的 monadic 函數(shù)

foldingFunction :: [Double] -> String -> Maybe [Double]  
foldingFunction (x:y:ys) "*" = return ((x * y):ys)  
foldingFunction (x:y:ys) "+" = return ((x + y):ys)  
foldingFunction (x:y:ys) "-" = return ((y - x):ys)  
foldingFunction xs numberString = liftM (:xs) (readMaybe numberString)  

前三種 case 跟前面的很像，只差在堆疊現(xiàn)在是包在 Just 里面（我們常常是用 return 來做到這件事，但其實(shí)我們也可以用 Just）。在最后一種情況，我們用 readMaybe numberString 然后我們用 (:xs) map over 他。所以如果堆疊 xs 是 [1.0,2.0] 且 readMaybe numberString 產(chǎn)生 Just 3.0，那結(jié)果便是 Just [3.0,1.0,2.0]。如果 readyMaybe numberString 產(chǎn)生 Nothing 那結(jié)果便是 Nothing。我們來試著跑跑看 folding 函數(shù)

ghci> foldingFunction [3,2] "*"  
Just [6.0]  
ghci> foldingFunction [3,2] "-"  
Just [-1.0]  
ghci> foldingFunction [] "*"  
Nothing  
ghci> foldingFunction [] "1"  
Just [1.0]  
ghci> foldingFunction [] "1 wawawawa"  
Nothing  

看起來正常運(yùn)作。我們可以用他來寫一個(gè)新的 solveRPN。

import Data.List  
  
solveRPN :: String -> Maybe Double  
solveRPN st = do  
  [result] <- foldM foldingFunction [] (words st)  
  return result  

我們?nèi)允墙邮芤粋€(gè)字串把他斷成一串 word。然后我們用一個(gè)空的堆疊來作 folding 的動(dòng)作，只差在我們用的是 foldM 而不是 foldl。foldM 的結(jié)果會(huì)是 Maybe，Maybe 里面包含了一個(gè)只有一個(gè)元素的 list。我們用 do expression 來取出值，把他綁定到 result 上。當(dāng) foldM 回傳 Nothing 的時(shí)候，整個(gè)結(jié)果就變成 Nothing。也特別注意我們有在 do 里面做 pattern match 的動(dòng)作，所以如果 list 中不是只有一個(gè)元素的話，最后結(jié)果便會(huì)是 Nothing。最后一行我們用 return result 來展示 RPN 計(jì)算的結(jié)果，把他包在一個(gè) Maybe 里面。

ghci> solveRPN "1 2 * 4 +"  
Just 6.0  
ghci> solveRPN "1 2 * 4 + 5 *"  
Just 30.0  
ghci> solveRPN "1 2 * 4"  
Nothing  
ghci> solveRPN "1 8 wharglbllargh"  
Nothing  

第一個(gè)例子會(huì)失敗是因?yàn)?list 中不是只有一個(gè)元素，所以 do 里面的 pattern matching 失敗了。第二個(gè)例子會(huì)失敗是因?yàn)?nbsp;readMaybe 回傳了 Nothing。

Composing monadic functions

當(dāng)我們介紹 monad law 的時(shí)候，我們說過 <=< 就像是函數(shù)合成一樣，只差在一個(gè)是作用在普通函數(shù) a -> b。一個(gè)是作用在 monadic 函數(shù) a -> m b。

ghci> let f = (+1) . (*100)  
ghci> f 4  
401  
ghci> let g = (\x -> return (x+1)) <=< (\x -> return (x*100))  
ghci> Just 4 >>= g  
Just 401  

在這個(gè)例子中我們合成了兩個(gè)普通的函數(shù)，并喂給給他 4。我們也合成了兩個(gè) monadic 函數(shù)并用 >>= 喂給他 Just 4。

如果我們?cè)?list 中有一大堆函數(shù)，我們可以把他們合成一個(gè)巨大的函數(shù)。用 id 當(dāng)作累加的起點(diǎn)，. 當(dāng)作 binary 函數(shù)，用 fold 來作這件事。

ghci> let f = foldr (.) id [(+1),(*100),(+1)]  
ghci> f 1  
201  

f 接受一個(gè)數(shù)字，然后會(huì)幫他加 1，乘以 100，再加 1。我們也可以將 monadic 函數(shù)用同樣的方式做合成，只是不用 . 而用 <=<，不用 id 而用 return。我們不需要 foldM，由于 <=< 只用 foldr 就足夠了。

當(dāng)我們?cè)谥暗恼鹿?jié)介紹 list monad 的時(shí)候， 我們用他來解決一個(gè)騎士是否能在三步內(nèi)走到另一點(diǎn)的問題。 那個(gè)函數(shù)叫做 moveKnight， 他接受一個(gè)座標(biāo)然后回傳所有可能的下一步。 然后產(chǎn)生出所有可能三步的移動(dòng)。

in3 start = return start >>= moveKnight >>= moveKnight >>= moveKnight   

要檢查我們是否能只用三步從 start 走到 end，我們用下列函數(shù)

canReachIn3 :: KnightPos -> KnightPos -> Bool  
canReachIn3 start end = end `elem` in3 start  

如果使用 monadic 版本的合成的話，我們也可以做一個(gè)類似的 in3，但我們希望他不只有三步的版本，而希望有任意步的版本。如果你仔細(xì)觀察 in3，他只不過用 >>= 跟 moveKnight 把之前所有可能結(jié)果喂到下一步。把他一般化，就會(huì)像下面的樣子：

import Data.List  
  
inMany :: Int -> KnightPos -> [KnightPos]  
inMany x start = return start >>= foldr (<=<) return (replicate x moveKnight)  

首先我們用 replicate 來做出一個(gè) list，里面有 x 份的 moveKnight。然后我們把所有函數(shù)都合成起來，就會(huì)給我們從起點(diǎn)走 x 步內(nèi)所有可能的的位置。然后我們只需要把起始位置喂給他就好了。

我們也可以一般化我們的 canReachIn3：

canReachIn :: Int -> KnightPos -> KnightPos -> Bool  
canReachIn x start end = end `elem` inMany x start  

定義自己的 Monad

在這一章節(jié)，我們會(huì)帶你看看究竟一個(gè)型態(tài)是怎么被辨認(rèn)，確認(rèn)是一個(gè) monad 而且正確定義出 Monad 的 instance。我們通常不會(huì)為了定義 monad 而定義。比較常發(fā)生的是，我們想要針對(duì)一個(gè)問題建立模型，卻稍后發(fā)現(xiàn)我們定義的型態(tài)其實(shí)是一個(gè) Monad，所以就定義一個(gè) Monad 的 instance。

正如我們看到的，list 是被拿來當(dāng)作 non-deterministic values。對(duì)于 [3,5,9]，我們可以看作是一個(gè) non-deterministic value，我們不能知道究竟是哪一個(gè)。當(dāng)我們把一個(gè) list 用 >>= 喂給一個(gè)函數(shù)，他就是把一串可能的選擇都丟給函數(shù)，函數(shù)一個(gè)個(gè)去計(jì)算在那種情況下的結(jié)果，結(jié)果也便是一個(gè) list。

如果我們把 [3,5,9] 看作是 3,5,9 各出現(xiàn)一次，但這邊沒有每一種數(shù)字出現(xiàn)的機(jī)率。如果我們把 non-deterministic 的值看作是 [3,5,9]，但 3 出現(xiàn)的機(jī)率是 50%，5 跟 9 出現(xiàn)的機(jī)率各是 25%呢？我們來試著用 Haskell 描述看看。

如果說 list 中的每一個(gè)元素都伴隨著他出現(xiàn)的機(jī)率。那下面的形式就蠻合理的：

[(3,0.5),(5,0.25),(9,0.25)]  

在數(shù)學(xué)上，機(jī)率通常不是用百分比表示，而是用介于 0 跟 1 的實(shí)數(shù)表示。0 代表不可能會(huì)發(fā)生，而 1 代表絕對(duì)會(huì)發(fā)生。但浮點(diǎn)數(shù)很有可能很快隨著運(yùn)算失去精準(zhǔn)度，所以 Haskell 有提供有理數(shù)。他的型態(tài)是擺在 Data.Ratio 中，叫做 Rational。要?jiǎng)?chuàng)造出一個(gè) Rational，我們會(huì)把他寫成一個(gè)分?jǐn)?shù)的形式。分子跟分母用 % 分隔。這邊有幾個(gè)例子：

ghci> 1%4  
1 % 4  
ghci> 1%2 + 1%2  
1 % 1  
ghci> 1%3 + 5%4  
19 % 12  

第一行代表四分之一，第二行代表兩個(gè)二分之一加起來變成一。而第三行我們把三分之一跟四分之五加起來變成十二分之十九。所以我們來用 Rational 取代浮點(diǎn)數(shù)來當(dāng)作我們的機(jī)率值吧。

ghci> [(3,1%2),(5,1%4),(9,1%4)]  
[(3,1 % 2),(5,1 % 4),(9,1 % 4)]  

所以 3 有二分之一的機(jī)會(huì)出現(xiàn)，而 5 跟 9 有四分之一的機(jī)會(huì)出現(xiàn)。

可以看到我們幫 list 加上了一些額外的 context。再我們繼續(xù)深入之前，我們用一個(gè) newtype 把他包起來，好讓我們幫他寫 instance。

import Data.Ratio

newtype Prob a = Prob { getProb :: [(a,Rational)] } deriving Show  

接著我們想問，這是一個(gè) functor 嗎？list 是一個(gè) functor，所以很有可能他也是一個(gè) functor，畢竟我們只是在 list 上多加一些東西而已。在 list 的情況下，我們可以針對(duì)每個(gè)元素用函數(shù)做處理。這邊我們也是用函數(shù)針對(duì)每個(gè)元素做處理，只是我們是輸出機(jī)率值。所以我們就來寫個(gè) functor 的 instance 吧。

instance Functor Prob where  
    fmap f (Prob xs) = Prob $ map (\(x,p) -> (f x,p)) xs 

我們可以用 pattern matching 的方式把 newtype 解開來，套用函數(shù) f 之后再包回去。過程中不會(huì)動(dòng)到機(jī)率值。

ghci> fmap negate (Prob [(3,1%2),(5,1%4),(9,1%4)])  
Prob {getProb = [(-3,1 % 2),(-5,1 % 4),(-9,1 % 4)]}  

要注意機(jī)率的和永遠(yuǎn)是 1。如果我們沒有漏掉某種情形的話，沒有道理他們加起來的值不為 1。一個(gè)有 75% 機(jī)率是正面以及 50% 機(jī)率是反面的硬幣根本沒什么道理。

接著要問一個(gè)重要的問題，他是一個(gè) monad 嗎？我們知道 list 是一個(gè) monad，所以他很有可能也是一個(gè) monad。首先來想想 return。他在 list 是怎么運(yùn)作的？他接受一個(gè)普通的值并把他放到一個(gè) list 中變成只有一個(gè)元素的 list。那在這邊又如何？由于他是一個(gè)最小的 context，他也應(yīng)該是一個(gè)元素的 list。那機(jī)率值呢？return x 的值永遠(yuǎn)都是 x，所以機(jī)率值不應(yīng)該是 0，而應(yīng)該是 1。

至于 >>= 呢？看起來有點(diǎn)復(fù)雜，所以我們換種方式來思考，我們知道 m >>= f 會(huì)等價(jià)于 join (fmap f m)，所以我們來想要怎么把一串包含 probability list 的 list 弄平。舉個(gè)例子，考慮一個(gè) list，'a' 跟 'b' 恰出現(xiàn)其中一個(gè)的機(jī)率為 25%，兩個(gè)出現(xiàn)的機(jī)率相等。而 'c' 跟 'd' 恰出現(xiàn)其中一個(gè)的機(jī)率為 75%，兩個(gè)出現(xiàn)的機(jī)率也是相等。這邊有一個(gè)圖將情形畫出來。

每個(gè)字母發(fā)生的機(jī)率有多高呢？如果我們用四個(gè)盒子來代表每個(gè)字母，那每個(gè)盒子的機(jī)率為何？每個(gè)盒子的機(jī)率是他們所裝有的機(jī)率值相乘的結(jié)果。'a' 的機(jī)率是八分之一，'b' 同樣也是八分之一。八分之一是因?yàn)槲覀儼讯种桓姆种幌喑说玫降慕Y(jié)果。而 'c' 發(fā)生的機(jī)率是八分之三，是因?yàn)槎种怀松纤姆种?d' 同樣也是八分之三。如果把所有的機(jī)率加起來，就會(huì)得到一，符合機(jī)率的規(guī)則。

來看看怎么用一個(gè) list 表達(dá)我們要說明的東西：

thisSituation :: Prob (Prob Char)  
thisSituation = Prob  
    [( Prob [('a',1%2),('b',1%2)] , 1%4 )  
    ,( Prob [('c',1%2),('d',1%2)] , 3%4 )  
    ]

注意到這邊的型態(tài)是 Prob (Prob Char)。所以我們要思考的是如何把一串包含機(jī)率 list 的 list 打平。如果能成功寫出這樣的邏輯，>>= 不過就是 join (fmap f m)，我們便得到了一個(gè) monad。我們這邊寫了一個(gè) flatten 來做這件事。

flatten :: Prob (Prob a) -> Prob a  
flatten (Prob xs) = Prob $ concat $ map multAll xs  
    where multAll (Prob innerxs,p) = map (\(x,r) -> (x,p*r)) innerxs  

multAll 接受一個(gè) tuple，里面包含一個(gè) probability list 跟一個(gè)伴隨的機(jī)率值 p，所以我們要作的事是把 list 里面的機(jī)率值都乘以 p，并回傳一個(gè)新的 tuple 包含新的 list 跟新的機(jī)率值。我們將 multAll map over 到我們的 probability list 上，我們就成功地打平了我們的 list。

現(xiàn)在我們就能定義我們的 Monad instance。

instance Monad Prob where  
    return x = Prob [(x,1%1)]  
    m >>= f = flatten (fmap f m)  
    fail _ = Prob []  

由于我們已經(jīng)把所有苦工的做完了，定義這個(gè) instance 顯得格外輕松。我們也定義了 fail，我們定義他的方式跟定義 list 一樣。如果在 do 中發(fā)生了失敗的 pattern match，那就會(huì)調(diào)用 fail。

檢查我們定義的 instance 是否遵守 monad law 也是很重要的。monad law 的第一個(gè)定律是 return x >>= f 應(yīng)該要等價(jià)于 f x。要寫出嚴(yán)格的證明會(huì)很麻煩，但我們可以觀察到下列事實(shí)：首先用 return 做一個(gè)最小的 context，然后用 fmap 將一個(gè)函數(shù) map over 這個(gè) context，再將他打平。這樣做出來的 probability list，每一個(gè)機(jī)率值都相當(dāng)于將我們最初放到 minimal context 中的值乘上 1%1。同樣的邏輯，也可以看出 m >>= return 是等價(jià)于 m。第三個(gè)定律是 f <=< (g <=< h) 應(yīng)該要等價(jià)于 (f <=< g) <=< h。我們可以從乘法有結(jié)合律的性質(zhì)，以及 list monad 的特性上推出 probability monad 也符合這個(gè)定律。1%2 * (1%3 * 1%5) 等于 (1%2 * 1%3) * 1%5。

現(xiàn)在我們有了一個(gè) monad，這樣有什么好處呢？他可以幫助我們計(jì)算機(jī)率值。我們可以把機(jī)率事件看作是具有 context 的 value，而 probability monad 可以保證機(jī)率值能正確地被計(jì)算成最終的結(jié)果。

好比說我們現(xiàn)在有兩個(gè)普通的硬幣以及一個(gè)灌鉛的硬幣。灌鉛的硬幣十次中有九次會(huì)出現(xiàn)正面，只有一次會(huì)出現(xiàn)反面。如果我們一次丟擲這三個(gè)硬幣，有多大的機(jī)會(huì)他們都會(huì)出現(xiàn)正面呢？讓我們先來表達(dá)丟擲硬幣這件事，分別丟的是灌鉛的跟普通的硬幣。

data Coin = Heads | Tails deriving (Show, Eq)  

coin :: Prob Coin  
coin = Prob [(Heads,1%2),(Tails,1%2)]  

loadedCoin :: Prob Coin  
loadedCoin = Prob [(Heads,1%10),(Tails,9%10)]  

最后，來看看擲硬幣的函數(shù)：

import Data.List (all)  
  
flipThree :: Prob Bool  
flipThree = do  
  a <- coin  
  b <- coin  
  c <- loadedCoin  
  return (all (==Tails) [a,b,c])  

試著跑一下的話，我們會(huì)看到盡管我們用了不公平的硬幣，三個(gè)反面的機(jī)率還是不高。

ghci> getProb flipThree  
[(False,1 % 40),(False,9 % 40),(False,1 % 40),(False,9 % 40),  
 (False,1 % 40),(False,9 % 40),(False,1 % 40),(True,9 % 40)]  

同時(shí)出現(xiàn)正面的機(jī)率是四十分之九，差不多是 25%的機(jī)會(huì)。我們的 monad 并沒有辦法 join 所有都是 False 的情形，也就是所有硬幣都是出現(xiàn)反面的情況。不過那不是個(gè)嚴(yán)重的問題，可以寫個(gè)函數(shù)來將同樣的結(jié)果變成一種結(jié)果，這就留給讀者當(dāng)作習(xí)題。

在這章節(jié)中，我們從提出問題到真的寫出型態(tài)，并確認(rèn)這個(gè)型態(tài)是一個(gè) monad，寫出他的 instance 并實(shí)際操作他。這是個(gè)很棒的經(jīng)驗(yàn)。現(xiàn)在讀者們應(yīng)該對(duì)于 monad 有不少的了解才是。