http://wiki.jikexueyuan.com/project/haskell-guide/images/clint.png" alt="" />
我們已經(jīng)看過 Monad 是如何接受具有 context 的值，并如何用函數(shù)操作他們 還有如何用 >>= 跟 do 來減輕我們對 context 的關(guān)注，集中精神在 value 本身。
我們也看過了 Maybe 是如何把值加上一個可能會失敗的 context。我們學習到 List Monad 是如何加進多重結(jié)果的 context。我們也了解 IO Monad 如何運作，而且我們在知道什么是 Monad 之前就已經(jīng)知道他了。
在這個章節(jié)，我們會介紹一些其他的 Monad。他們可以把值變成 monadic value，因此可以讓我們的程式更簡潔清晰。多見識幾個 Monad 也可以敏銳我們對 Monad 的直覺。
我們即將要介紹的 Monad 都包含在 mtl 這個套建中。一個 Haskell package 包含了一堆模組。而 mtl 已經(jīng)包含在 Haskell Platform 中，所以你可能不用另外安裝。要檢查你有沒有這套件，你可以下 ghc-pkg list。這會列出你已經(jīng)安裝的套件，其中應該包含 mtl 后面接著對應的版號。
我們已經(jīng)看過 Maybe, list 以及 IO Monad?，F(xiàn)在我們要來看看 Writer Monad。
相對于 Maybe 是加入可能失敗的 context，list 是加入 non-deterministic 的 context，Writer 則是加進一個附加值的 context，好比 log 一般。Writer 可以讓我們在計算的同時搜集所有 log 紀錄，并匯集成一個 log 并附加在結(jié)果上。
例如我們想要附加一個 String 好說明我們的值在干么（有可能是為了除錯）。想像有一個函數(shù)接受一個代表幫派人數(shù)的數(shù)字，然后會回傳值告訴我們這是否算是一個龐大的幫派：
isBigGang :: Int -> Bool
isBigGang x = x > 9 現(xiàn)在我們希望他不只是回傳 True 或 False，我們還希望他能夠多回傳一個字串代表 log。這很容易，只要多加一個 String 在 Bool 旁邊就好了。
isBigGang :: Int -> (Bool, String)
isBigGang x = (x > 9, "Compared gang size to 9.") 我們現(xiàn)在回傳了一個 Tuple，第一個元素是原來的布林值，第二個元素是一個 String。現(xiàn)在我們的值有了一個 context。
ghci> isBigGang 3
(False,"Compared gang size to 9.")
ghci> isBigGang 30
(True,"Compared gang size to 9.") http://wiki.jikexueyuan.com/project/haskell-guide/images/tuco.png" alt="" />
到目前為止都還不錯，isBigGang 回傳一個值跟他的 context。對于正常的數(shù)值來說這樣的寫法都能運作良好。但如果我們想要把一個已經(jīng)具有 context 的值，像是 (3, "Smallish gang.")，喂給 isBigGang 呢？我們又面對了同樣的問題：如果我們有一個能接受正常數(shù)值并回傳一個具有 context 值的 function，那我們要如何喂給他一個具有 context 的值？
當我們在研究 Maybe monad 的時候，我們寫了一個 applyMaybe。他接受一個 Maybe a 值跟一個 a -> Maybe b 型態(tài)的函數(shù)，他會把 Maybe a 喂給這個 function，即便這個 function 其實是接受 a 而非 Maybe a。applyMaybe 有針對這樣的 context 做處理，也就是會留意有可能發(fā)生的失敗情況。但在 a -> Maybe b 里面，我們可以只專心處理正常數(shù)值即可。因為 applyMaybe (之后變成了 >>=)會幫我們處理需要檢查 Nothing 或 Just 的情況。
我們再來寫一個接受附加 log 值的函數(shù)，也就是 (a, String) 型態(tài)的值跟 a -> (b, String) 型態(tài)的函數(shù)。我們稱呼這個函數(shù)為 applyLog。這個函數(shù)有的 context 是附加 log 值，而不是一個可能會失敗的 context，因此 applyLog 會確保原有的 log 被保留，并附上從函數(shù)產(chǎn)生出的新的 log。這邊我們來看一下實作：
applyLog :: (a,String) -> (a -> (b,String)) -> (b,String)
applyLog (x,log) f = let (y,newLog) = f x in (y,log ++ newLog) 當我們想把一個具有 context 的值喂給一個函數(shù)的時候，我們會嘗試把值跟他的 context 分開，然后把值喂給函數(shù)再重新接回 context。在 Maybe monad 的情況，我們檢查值是否為 Just x，如果是，便將 x 喂給函數(shù)。而在 log 的情況，我們知道 pair 的其中一個 component 是 log 而另一個是值。所以我們先取出值 x，將 f apply 到 x，便獲取 (y,newLog)，其中 y 是新的值而 newLog 則是新的 log。但如果我們回傳 newLog，舊的 log 便不會包含進去，所以我們要回傳的是 (y, log ++ newLog)。我們用 ++ 來把新的 log 接到舊的上面。
來看看 applyLog 運作的情形：
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。再來多看幾個例子：
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 只是個正常的字串而不是 tuple，且 applyLog 幫我們處理掉附加 log 的動作。
請確定你了解什么是 Monoids。到目前為止 applyLog 接受 (a,String) 型態(tài)的值，但為什么 log 一定要是 String 呢？我們使用 ++ 來附加新的 log，難道 ++ 并不能運作在任何形式的 list，而一定要限制我們在 String 上呢？我們當然可以擺脫 String，我們可以如下改變他的型態(tài)：
applyLog :: (a,[c]) -> (a -> (b,[c])) -> (b,[c]) 我們用一個 List 來代表 Log。包含在 List 中的元素型態(tài)必須跟原有的 List 跟回傳的 List 型態(tài)相同，否則我們沒辦法用 ++ 來把他們接起來。
這能夠運作在 bytestring 上嗎？絕對沒問題。只是我們現(xiàn)在的型態(tài)只對 List 有效。我們必須要另外做一個 bytestring 版本的 applyLog。但我們注意到 List 跟 bytestring 都是 monoids。因此他們都是 Monoid type class 的 instance，那代表他們都有實作 mappend。對 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 可以運作在任何 monoid 上。我們必須要修改型態(tài)宣告來表示這件事，同時也要在實作中把 ++ 改成 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 想成包含一個值跟對應的 log，我們可以想成他包含一個值跟一個對應的 monoid。舉例來說，可以說我們有一個 tuple 包含一個產(chǎn)品名稱跟一個符合 monoid 特性的產(chǎn)品價格。我們可以定義一個 Sum 的 newtype 來保證我們在操作產(chǎn)品的時候也會把價錢跟著加起來。
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，來追蹤總共需要花多少錢。可以注意到我們用 mappend 來操作 Sum 的時候，價錢會被一起加起來。
ghci> Sum 3 `mappend` Sum 9
Sum {getSum = 12} addDrink 的實作很簡單，如果我們想吃豆子，他會回傳 "milk" 以及伴隨的 Sum 25，同樣的如果我們要吃 "jerky"，他就會回傳 "whiskey"，要吃其他東西的話，就會回傳 "beer"。乍看之下這個函數(shù)沒什么特別，但如果用 applyLog 的話就會有趣些。
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}) 牛奶價值 25 美分，但如果我們也吃了價值 10 美分的豆子的話，總共需要付 35 美分。這樣很清楚地展示了伴隨的值不一定需要是 log，他可以是任何 monoid。至于兩個值要如何結(jié)合，那要看 monoid 中怎么定義。當我們需要的是 log 的時候，他們是串接，但這個 case 里面，數(shù)字是被加起來。
由于 addDrink 回傳一個 (Food,Price)，我們可以再把結(jié)果重新喂給 addDrink，這可以很容易告訴我們總共喝了多少錢：
ghci> ("dogmeat", Sum 5) `applyLog` addDrink `applyLog` addDrink
("beer",Sum {getSum = 65}) 將狗食跟 30 美分的啤酒加在一起會得到 ("beer", Sum 35)。如果我們用 applyLog 將上面的結(jié)果再喂給 addDrink，我們會得到 ("beer", Sum 65) 這樣的結(jié)果。
我們認識了一個附加 monoid 的值其實表現(xiàn)出來的是一個 monad，我們來再來看看其他類似的 Monad instance。Control.Monad.Writer 這模組含有 Writer w a 的一個型態(tài)，里面定義了他 Monad 的 instance，還有一些操作這些值的函數(shù)。
首先，我們來看一下型態(tài)。要把一個 monoid 附加給一個值，只需要定義一個 tuple 就好了。Writer w a 這型態(tài)其實是一個 newtype wrapper。他的定義很簡單：
newtype Writer w a = Writer { runWriter :: (a, w) } 他包在一個 newtype 里面，并且可以是一個 Monad 的 instance，而且這樣定義的好處是可以跟單純 tuple 的型態(tài)區(qū)分開來。a 這個型態(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') http://wiki.jikexueyuan.com/project/haskell-guide/images/angeleyes.png" alt="" />
首先，我們來看看 >>=。他的實作基本上就是 applyLog，只是我們的 tuple 現(xiàn)在是包在一個 Writer 的 newtype 中，我們可以用 pattern matching 的方式把他給 unwrap。我們將 x 喂給 f。這會回給我們 Writer w a。接著可以用 let expression 來做 pattern matching。把結(jié)果綁定到 y 這個名字上，然后用 mappend 來結(jié)合舊的 monoid 值跟新的 monoid 值。最后把結(jié)果跟 monoid 值用 Writer constructor 包起來，形成我們最后的 Writer value。
那 return 呢？回想 return 的作用是接受一個值，并回傳一個具有意義的最小 context 來裝我們的值。那究竟什么樣的 context 可以代表我們的 Writer 呢？如果我們希望 monoid 值所造成的影響愈小愈好，那 mempty 是個合理的選擇。mempty 是被當作 identity monoid value，像是 "" 或 Sum 0，或是空的 bytestring。當我們對 mempty 用 mappend 跟其他 monoid 值結(jié)合，結(jié)果會是其他的 monoid 值。所以如果我們用 return 來做一個 Writer，然后用 >>= 來喂給其他的函數(shù)，那函數(shù)回傳的便是算出來的 monoid。下面我們試著用 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}) 因為 Writer 并沒有定義成 Show 的 instance，我們必須用 runWriter 來把我們的 Writer 轉(zhuǎn)成正常的 tuple。對于 String，monoid 的值就是空字串。而對于 Sum 來說則是 0，因為 0 加上其他任何值都會是對方。而對 Product 來說，則是 1。
這里的 Writer instance 并沒有定義 fail，所以如果 pattern matching 失敗的話，就會呼叫 error。
既然我們定義了 Monad 的 instance，我們自然可以用 do 串接 Writer 型態(tài)的值。這在我們需要對一群 Writer 型態(tài)的值做處理時顯得特別方便。就如其他的 monad，我們可以把他們當作具有 context 的值。在現(xiàn)在這個 case 中，所有的 monoid 的值都會用 mappend 來連接起來并得到最后的結(jié)果。這邊有一個簡單的范例，我們用 Writer 來相乘兩個數(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 接受一個數(shù)并把這個數(shù)做成一個 Writer。我們再用一串 string 來當作我們的 monoid 值，每一個數(shù)都跟著一個只有一個元素的 list，說明我們只有一個數(shù)。multWithLog 式一個 Writer，他將 3 跟 5 相乘并確保相乘的紀錄有寫進最后的 log 中。我們用 return 來做成 a*b 的結(jié)果。我們知道 return 會接受某個值并加上某個最小的 context，我們可以確定他不會多添加額外的 log。如果我們執(zhí)行程式會得到：
ghci> runWriter multWithLog
(15,["Got number: 3","Got number: 5"]) 有時候我們就是想要在某個時間點放進某個 Monoid value。tell 正是我們需要的函數(shù)。他實作了 MonadWriter 這個 type class，而且在當 Writer 用的時候也能接受一個 monoid value，好比說 ["This is going on"]。我們能用他來把我們的 monoid value 接到任何一個 dummy value () 上來形成一個 Writer。當我們拿到的結(jié)果是 () 的時候，我們不會把他綁定到變數(shù)上。來看一個 multWithLog 的范例：
multWithLog :: Writer [String] Int
multWithLog = do
a <- logNumber 3
b <- logNumber 5
tell ["Gonna multiply these two"]
return (a*b) return (a*b) 是我們的最后一行，還記得在一個 do 中的最后一行代表整個 do 的結(jié)果。如果我們把 tell 擺到最后，則 do 的結(jié)果則會是 ()。我們會因此丟掉乘法運算的結(jié)果。除此之外，log 的結(jié)果是不變的。
ghci> runWriter multWithLog
(15,["Got number: 3","Got number: 5","Gonna multiply these two"]) 歐幾里得算法是找出兩個數(shù)的最大公因數(shù)。Haskell 已經(jīng)提供了 gcd 的函數(shù)，但我們來實作一個具有 log 功能的 gcd：
gcd' :: Int -> Int -> Int
gcd' a b
| b == 0 = a
| otherwise = gcd' b (a `mod` b) 演算法的內(nèi)容很簡單。首先他檢查第二個數(shù)字是否為零。如果是零，那就回傳第一個數(shù)字。如果不是，那結(jié)果就是第二個數(shù)字跟將第一個數(shù)字除以第二個數(shù)字的余數(shù)兩個數(shù)字的最大公因數(shù)。舉例來說，如果我們想知道 8 跟 3 的最大公因數(shù)，首先可以注意到 3 不是 0。所以我們要求的是 3 跟 2 的最大公因數(shù)(8 除以 3 余二)。接下去我可以看到 2 不是 0，所以我們要再找 2 跟 1 的最大公因數(shù)。同樣的，第二個數(shù)不是 0，所以我們再找 1 跟 0 的最大公因數(shù)。最后第二個數(shù)終于是 0 了，所以我們得到最大公因數(shù)是 1。
ghci> gcd' 8 3
1 答案真的是這樣。接著我們想加進 context，context 會是一個 monoid value 并且像是一個 log 一樣。就像之前的范例，我們用一串 string 來當作我們的 monoid。所以 gcd' 會長成這樣：
gcd' :: Int -> Int -> Writer [String] Int 而他的程式碼會像這樣：
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) 這個函數(shù)接受兩個 Int 并回傳一個 Writer [String] Int，也就是說是一個有 log context 的 Int。當 b 等于 0 的時候，我們用一個 do 來組成一個 Writer 的值。我們先用 tell 來寫入我們的 log，然后用 return 來當作 do 的結(jié)果。當然我們也可以這樣寫：
Writer (a, ["Finished with " ++ show a]) 但我想 do 的表達方式是比較容易閱讀的。接下來我們看看當 b 不等于 0 的時候。我們會把 mod 的使用情況寫進 log。然后在 do 當中的第二行遞回呼叫 gcd'。gcd' 現(xiàn)在是回傳一個 Writer 的型態(tài)，所以 gcd' b (a `mod` b) 這樣的寫法是完全沒問題的。
盡管去 trace 這個 gcd' 對于理解十分有幫助，但我想了解整個大概念，把值視為具有 context 是更加有用的。
接著來試試跑我們的 gcd'，他的結(jié)果會是 Writer [String] Int，如果我們把他從 newtype 中取出來，我們會拿到一個 tuple。tuple 的第一個部份就是我們要的結(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)驗，我們不過是把普通的 value 重寫成 Monadic value，剩下的就靠 >>= 跟 Writer 來幫我們處理一切。用這樣的方法我們幾乎可以對任何函數(shù)加上 logging 的功能。我們只要把普通的值換成 Writer，然后把一般的函數(shù)呼叫換成 >>= (當然也可以用 do)
當制作 Writer Monad 的時候，要特別注意你是使用哪種 monoid。使用 list 的話效能有時候是沒辦法接受的。因為 list 是使用 ++ 來作為 mappend 的實現(xiàn)。而 ++ 在 list 很長的時候是非常慢的。
在之前的 gcd' 中，log 并不會慢是因為 list append 的動作實際上看起來是這樣：
a ++ (b ++ (c ++ (d ++ (e ++ f)))) list 是建立的方向是從左到右，當我們先建立左邊的部份，而把另一串 list 加到右邊的時候效能會不錯。但如果我們不小心使用，而讓 Writer monad 實際在操作 list 的時候變成像這樣的話。
((((a ++ b) ++ c) ++ d) ++ e) ++ f 這會讓我們的操作是 left associative，而不是 right associative。這非常沒有效率，因為每次都是把右邊的部份加到左邊的部份，而左邊的部份又必須要從頭開始建起。
下面這個函數(shù)跟 gcd' 差不多，只是 log 的順序是相反的。他先紀錄剩下的操作，然后紀錄現(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 他先遞回呼叫，然后把結(jié)果綁定到 result。然后把目前的動作寫到 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 這沒效率是因為他讓 ++ 成為 left associative 而不是 right associative。
http://wiki.jikexueyuan.com/project/haskell-guide/images/cactus.png" alt="" />
由于 list 在重復 append 的時候顯得低效，我們最好能使用一種支援高效 appending 的資料結(jié)構(gòu)。其中一種就是 difference list。difference list 很類似 list，只是他是一個函數(shù)。他接受一個 list 并 prepend 另一串 list 到他前面。一個等價于 [1,2,3] 的 difference list 是這樣一個函數(shù) \xs -> [1,2,3] ++ xs。一個等價于 [] 的 difference list 則是 \xs -> [] ++ xs。
Difference list 最酷的地方在于他支援高效的 appending。當我們用 ++ 來實現(xiàn) appending 的時候，他必須要走到左邊的 list 的尾端，然后把右邊的 list 一個個從這邊接上。那 difference list 是怎么作的呢？appending 兩個 difference list 就像這樣
f `append` g = \xs -> f (g xs) f 跟 g 這邊是兩個函數(shù)，他們都接受一個 list 并 prepend 另一串 list。舉例來說，如果 f 代表 ("dog"++)（可以寫成 \xs -> "dog" ++ xs）而 g 是 ("meat"++)，那 f `append` g 就會做成一個新的函數(shù)，等價于：
\xs -> "dog" ++ ("meat" ++ xs) append 兩個 difference list 其實就是用一個函數(shù)，這函數(shù)先喂一個 list 給第一個 difference list，然后再把結(jié)果喂給第二個 difference list。
我們可以用一個 newtype 來包起來
newtype DiffList a = DiffList { getDiffList :: [a] -> [a] } 我們包起來的型態(tài)是 [a] -> [a]，因為 difference list 不過就是一個轉(zhuǎn)換一個 list 到另一個 list 的函數(shù)。要把普通 list 轉(zhuǎn)換成 difference list 也很容易。
toDiffList :: [a] -> DiffList a
toDiffList xs = DiffList (xs++)
fromDiffList :: DiffList a -> [a]
fromDiffList (DiffList f) = f [] 要把一個普通 list 轉(zhuǎn)成 difference list 不過就是照之前定義的，作一個 prepend 另一個 list 的函數(shù)。由于 difference list 只是一個 prepend 另一串 list 的一個函數(shù)，假如我們要轉(zhuǎn)回來的話，只要喂給他空的 list 就行了。
這邊我們給一個 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 其實是 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 的時候把普通的 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 印出來。
要體會 Difference List 能如何增進效率，考慮一個從某數(shù)數(shù)到零的 case。我們紀錄的時候就像 gcdReverse 一樣是反過來記的，所以在 log 中實際上是從零數(shù)到某個數(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ù)，他會先倒數(shù)到 0 然后 append 那些數(shù)到 log 中，所以如果我們呼叫 finalCountDown 并喂給他 100，那 log 的最后一筆就會是 "100"。
如果你把這個函數(shù) load 進 GHCi 中并喂給他一個比較大的整數(shù) 500000，你會看到他無停滯地從 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 我們會看到整個運算卡卡的。
當然這不是一個嚴謹?shù)臏y試方法，但足以表顯出 difference list 是比較有效率的寫法。
http://wiki.jikexueyuan.com/project/haskell-guide/images/revolver.png" alt="" />
在講 Applicative 的章節(jié)中，我們說過了 (->) r 的型態(tài)只是 Functor 的一個 instance。要將一個函數(shù) f map over 一個函數(shù) g，基本上等價于一個函數(shù)，他可以接受原本 g 接受的參數(shù)，先套用 g 然后再把其結(jié)果丟給 f。
ghci> let f = (*5)
ghci> let g = (+3)
ghci> (fmap f g) 8我們已經(jīng)見識過函數(shù)當作 applicative functors 的例子。這樣能讓我們對函數(shù)的結(jié)果直接進行操作。
ghci> let f = (+) <$> (*2) <*> (+10)
ghci> f 3
19(+) <$> (*2) <*> (+10) 代表一個函數(shù)，他接受一個數(shù)值，分別把這數(shù)值交給 (*2) 跟 (+10)。然后把結(jié)果加起來。例如說，如果我們喂 3 給這個函數(shù)，他會分別對 3 做 (*2) 跟 (+10) 的動作。而得到 6 跟 13。然后呼叫 (+)，而得到 19。
其實 (->) r 不只是一個 functor 跟一個 applicative functor，他也是一個 monad。就如其他 monadic value 一般，一個函數(shù)也可以被想做是包含一個 context 的。這個 context 是說我們期待某個值，他還沒出現(xiàn)，但我們知道我們會把他當作函數(shù)的參數(shù)，呼叫函數(shù)來得到結(jié)果。
我們已經(jīng)見識到函數(shù)是怎樣可以看作 functor 或是 applicative functors 了。再來讓我們看看當作 Monad 的一個 instance 時會是什么樣子。你可以在 Control.Monad.Instances 里面找到，他看起來像這樣：
instance Monad ((->) r) where
return x = \_ -> x
h >>= f = \w -> f (h w) w 我們之前已經(jīng)看過函數(shù)的 pure 實作了，而 return 差不多就是 pure。他接受一個值并把他放進一個 minimal context 里面。而要讓一個函數(shù)能夠是某個定值的唯一方法就是讓他完全忽略他的參數(shù)。
而 >>= 的實作看起來有點難以理解，我們可以仔細來看看。當我們使用 >>= 的時候，喂進去的是一個 monadic value，處理他的是一個函數(shù)，而吐出來的也是一個 monadic value。在這個情況下，當我們將一個函數(shù)喂進一個函數(shù)，吐出來的也是一個函數(shù)。這就是為什么我們在最外層使用了一個 lambda。在我們目前看過的實作中，>>= 幾乎都是用 lambda 將內(nèi)部跟外部隔開來，然后在內(nèi)部來使用 f。這邊也是一樣的道理。要從一個函數(shù)得到一個結(jié)果，我們必須喂給他一些東西，這也是為什么我們先用 (h w) 取得結(jié)果，然后將他丟給 f。而 f 回傳一個 monadic value，在這邊這個 monadic value 也就是一個函數(shù)。我們再把 w 喂給他。
如果你還不太懂 >>= 怎么寫出來的，不要擔心，因為接下來的范例會讓你曉得這真的是一個簡單的 Monad。我們造一個 do expression 來使用這個 Monad。
import Control.Monad.Instances
addStuff :: Int -> Int
addStuff = do
a <- (*2)
b <- (+10)
return (a+b) 這跟我們之前寫的 applicative expression 差不多，只差在他是運作在 monad 上。一個 do expression 的結(jié)果永遠會是一個 monadic vlaue，這個也不例外。而這個 monadic value 其實是一個函數(shù)。只是在這邊他接受一個數(shù)字，然后套用 (*2)，把結(jié)果綁定到 a 上面。而 (+10) 也同用被套用到同樣的參數(shù)。結(jié)果被綁定到 b 上。return 就如其他 monad 一樣，只是制作一個簡單的 monadic value 而不會作多余的事情。這讓整個函數(shù)的結(jié)果是 a+b。如果我們試著跑跑看，會得到之前的結(jié)果。
ghci> addStuff 3
19 其中 3 會被喂給 (*2) 跟 (+10)。而且他也會被喂給 return (a+b)，只是他會忽略掉 3 而永遠回傳 a+b 正因為如此，function monad 也被稱作 reader monad。所有函數(shù)都從一個固定的地方讀取。要寫得更清楚一些，可以把 addStuff 改寫如下：
addStuff :: Int -> Int
addStuff x = let
a = (*2) x
b = (+10) x
in a+b 我們見識了把函數(shù)視作具有 context 的值很自然的可以表達成 reader monad。只要我們當作我們知道函數(shù)會回傳什么值就好。他作的就是把所有的函數(shù)都黏在一起做成一個大的函數(shù)，然后把這個函數(shù)的參數(shù)都喂給全部組成的函數(shù)，這有點取出他們未來的值的意味。實作做完了然后 >>= 就會保證一切都能正常運作。
http://wiki.jikexueyuan.com/project/haskell-guide/images/texas.png" alt="" />
Haskell 是一個純粹的語言，正因為如此，我們的程式是有一堆沒辦法改變?nèi)驙顟B(tài)或變數(shù)的函數(shù)所組成，他們只會作些處理并回傳結(jié)果。這樣的性質(zhì)讓我們很容易思考我們的程式在干嘛，因為我們不需要擔心變數(shù)在某一個時間點的值是什么。然而，有一些領(lǐng)域的問題根本上就是依賴于隨著時間而改變的狀態(tài)。雖然我們也可以用 Haskell 寫出這樣的程式，但有時候?qū)懫饋硇U痛苦的。這也是為什么 Haskell 要加進 State Monad 這個特性。這讓我們在 Haskell 中可以容易地處理狀態(tài)性的問題，并讓其他部份的程式還是保持純粹性。
當我們處理亂數(shù)的時候，我們的函數(shù)接受一個 random generator 并回傳一個新的亂數(shù)跟一個新的 random generator。如果我們需要很多個亂數(shù)，我們可以用前一個函數(shù)回傳的 random generator 繼續(xù)做下去。當我們要寫一個接受 StdGen 的函數(shù)并產(chǎn)生丟三個硬幣結(jié)果的函數(shù)，我們會這樣寫：
threeCoins :: StdGen -> (Bool, Bool, Bool)
threeCoins gen =
let (firstCoin, newGen) = random gen
(secondCoin, newGen') = random newGen
(thirdCoin, newGen''') = random newGen'
in (firstCoin, secondCoin, thirdCoin) 他接受一個 gen 然后用 random gen 產(chǎn)生一個 Bool 型態(tài)的值以及新的 generator。要模擬丟第二個硬幣的話，便使用新的 generator。在其他語言中，多半除了亂數(shù)之外不需要多回傳一個 generator。那是因為我們可以對現(xiàn)有的進行修改。但 Haskell 是純粹的語言，我們沒辦法那么做，所以我們必須要接受一個狀態(tài)，產(chǎn)生結(jié)果然后回傳一個新的狀態(tài)，然后用新的狀態(tài)來繼續(xù)做下去。
一般來講你應該不會喜歡這么寫，在程式中有赤裸裸的狀態(tài)，但我們又不想放棄 Haskell 的純粹性質(zhì)。這就是 State Monad 的好處了，他可以幫我們處理這些瑣碎的事情，又讓我們保持 Haskell 的純粹性。
為了深入理解狀態(tài)性的計算，我們先來看看應該給他們什么樣的型態(tài)。我們會說一個狀態(tài)性的計算是一個函數(shù)，他接受一個狀態(tài)，回傳一個值跟一個新的狀態(tài)。寫起來會像這樣：
s -> (a,s) s 是狀態(tài)的型態(tài)，而 a 是計算結(jié)果的型態(tài)。
在其他的語言中，賦值大多是被當作會改變狀態(tài)的操作。舉例來說，當我們在命令式語言寫 ``x = 5``，這通常代表的是把 ``5`` 指定給 ``x`` 這變數(shù)。而且這邊 ``5`` 是一個 expression。
如果你用函數(shù)語言的角度去思考，你可以把他想做是一個函數(shù)，接受一個狀態(tài)，并回傳結(jié)果跟新的狀態(tài)。那新的狀態(tài)代表所有已指定的值與新加入的變數(shù)。這種改變狀態(tài)的計算，除了想做是一個接受狀態(tài)并回傳結(jié)果跟新狀態(tài)的函數(shù)外，也可以想做是具有 context 的值。 實際的值是結(jié)果。然而要得到結(jié)果，我們必須要給一個初始的狀態(tài)，才能得到結(jié)果跟最后的狀態(tài)。
考慮現(xiàn)在我們要對一個堆疊的操作建立模型。你可以把東西推上堆疊頂端，或是把東西從頂端拿下來。如果你要的元素是在堆疊的底層的話，你必須要把他上面的東西都拿下來才能拿到他。
我們用一個 list 來代表我們的堆疊。而我們把 list 的頭當作堆疊的頂端。為了正確的建立模型，我們要寫兩個函數(shù)：pop 跟 push。pop 會接受一個堆疊，取下一個元素并回傳一個新的堆疊，這個新的堆疊不包含取下的元素。push 會接受一個元素，把他堆到堆疊中，并回傳一個新的堆疊，其包含這個新的元素。
type Stack = [Int]
pop :: Stack -> (Int,Stack)
pop (x:xs) = (x,xs)
push :: Int -> Stack -> ((),Stack)
push a xs = ((),a:xs) 我們用 () 來當作 pushing 的結(jié)果，畢竟推上堆疊并不需要什么回傳值，他的重點是在改變堆疊。注意到 push 跟 pop 都是改變狀態(tài)的計算，可以從他們的型態(tài)看出來。
我們來寫一段程式來模擬一個堆疊的操作。我們接受一個堆疊，把 3 推上去，然后取出兩個元素。
stackManip :: Stack -> (Int, Stack)
stackManip stack = let
((),newStack1) = push 3 stack
(a ,newStack2) = pop newStack1
in pop newStack2 我們拿一個 stack 來作 push 3 stack 的動作，其結(jié)果是一個 tuple。tuple 的第一個部份是 ()，而第二個部份是新的堆疊，我們把他命名成 newStack1。然后我們從 newStack1 上 pop 出一個數(shù)字。其結(jié)果是我們之前 push 上去的一個數(shù)字 a，然后把這個更新的堆疊叫做 newStack2。然后我們從 newStack2 上再 pop 出一個數(shù)字 b，并得到 newStack3。我們回傳一個 tuple 跟最終的堆疊。
ghci> stackManip [5,8,2,1]
(5,[8,2,1]) 結(jié)果就是 5 跟新的堆疊 [8,2,1]。注意到 stackManip 是一個會改變狀態(tài)的操作。我們把一堆會改變狀態(tài)的操作綁在一起操作，有沒有覺得很耳熟的感覺。
stackManip 的程式有點冗長，因為我們要寫得太詳細，必須把狀態(tài)給每個操作，然后把新的狀態(tài)再喂給下一個。如果我們可以不要這樣作的話，那程式應該會長得像這樣：
stackManip = do
push 3
a <- pop
pop 這就是 State Monad 在做的事。有了他，我們便可以免除于要把狀態(tài)操作寫得太明白的窘境。
Control.Monad.State 這個模組提供了一個 newtype 包起來的型態(tài)。
newtype State s a = State { runState :: s -> (a,s) } 一個 State s a 代表的是一個改變狀態(tài)的操作，他操縱的狀態(tài)為型態(tài) s，而產(chǎn)生的結(jié)果是 a。
我們已經(jīng)見識過什么是改變狀態(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 要作的事是接受一個值，并做出一個改變狀態(tài)的操作，讓他永遠回傳那個值。所以我們才做了一個 lambda 函數(shù)，\s -> (x,s)。我們把 x 當成是結(jié)果，并且狀態(tài)仍然是 s。這就是 return 要完成的 minimal context。
http://wiki.jikexueyuan.com/project/haskell-guide/images/badge.png" alt="" />
那 >>= 的實作呢？很明顯的把改變狀態(tài)的操作喂進 >>= 也必須要丟出另一個改變狀態(tài)的操作。所以我們用 State 這個 newtype wrapper 來把一個 lambda 函數(shù)包住。這個 lambda 會是新的一個改變狀態(tài)的操作。但里面的內(nèi)容是什么？首先我們應該要從接受的操作取出結(jié)果。由于 lambda 是在一個大的操作中，所以我們可以喂給 h 我們現(xiàn)在的狀態(tài)，也就是 s。那會產(chǎn)生 (a, newState)。到目前為止每次我們在實作 >>= 的時候，我們都會先從 monadic value 中取出結(jié)果，然后喂給 f 來得到新的 monadic value。在寫 Writer 的時候，我們除了這樣作還要確保 context 是用 mappend 把舊的 monoid value 跟新的接起來。在這邊我們則是用 f a 得到一個新的操作 g?，F(xiàn)在我們有了新的操作跟新的狀態(tài)（叫做 newState），我們就把 newState 喂給 g。結(jié)果便是一個 tuple，里面包含了最后的結(jié)果跟最終的狀態(tài)。
有了 >>=，我們便可以把兩個操作黏在一起，只是第二個被放在一個函數(shù)中，專門接受第一個的結(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 要先接受一個 Int 才會回傳我們要的操作。所以我們可以改寫先前的范例如下：
import Control.Monad.State
stackManip :: State Stack Int
stackManip = do
push 3
a <- pop
pop 看到我們是怎么把一個 push 跟兩個 pop 黏成一個操作嗎？當我們將他們從一個 newtype 取出，其實就是需要一個能喂進初始狀態(tài)的函數(shù)：
ghci> runState stackManip [5,8,2,1]
(5,[8,2,1]) 我們不須綁定第二個 pop，因為我們根本不會用到 a，所以可以寫成下面的樣子：
stackManip :: State Stack Int
stackManip = do
push 3
pop
pop 再來嘗試另外一種方式，先從堆疊上取下一個數(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é)果會是一個 monadic value，而在 State monad 的 case，do 也就是一個改變狀態(tài)的函數(shù)。而由于 stackManip 跟 stackStuff 都是改變狀態(tài)的計算，因此我們可以把他們黏在一起：
moreStack :: State Stack ()
moreStack = do
a <- stackManip
if a == 100
then stackStuff
else return () 如果 stackManip 的結(jié)果是 100，我們就會跑 stackStuff，如果不是的話就什么都不做。return () 不過就是什么是都不做，全部保持原樣。
Contorl.Monad.State 提供了一個 MonadState 的 typeclass，他有兩個有用的函數(shù)，分別是 get 跟 put。對于 State 來說，get 的實作就像這樣：
get = State $ \s -> (s,s)他只是取出現(xiàn)在的狀態(tài)除此之外什么也不做。而 put 函數(shù)會接受一個狀態(tài)并取代掉現(xiàn)有的狀態(tài)。
put newState = State $ \s -> ((),newState) 有了這兩個狀態(tài)，我們便可以看到現(xiàn)在堆疊中有什么，或是把整個堆疊中的元素換掉。
stackyStack :: State Stack ()
stackyStack = do
stackNow <- get
if stackNow == [1,2,3]
then put [8,3,1]
else put [9,2,1] 我們可以看看對于 State 而言，>>= 的型態(tài)會是什么：
(>>=) :: State s a -> (a -> State s b) -> State s b 我們可以看到狀態(tài)的型態(tài)都是 s，而結(jié)果從型態(tài) a 變成型態(tài) b。這代表我們可以把好幾個改變狀態(tài)的計算黏在一起，這些計算的結(jié)果可以都不一樣，但狀態(tài)的型態(tài)會是一樣的。舉例來說，對于 Maybe 而言，>>= 的型態(tài)會是：
(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b Maybe 不變是有道理的，但如果用 >>= 來把兩種不同的 monad 接起來是沒道理的。但對于 state monad 而言，monad 其實是 State s，所以如果 s 不一樣，我們就要用 >>= 來把兩個 monad 接起來。
在章節(jié)的一開始，我們知道了在 Haskell 中要產(chǎn)生亂數(shù)的不方便。我們要拿一個產(chǎn)生器，并回傳一個亂數(shù)跟一個新的產(chǎn)生器。接下來我們還一定要用新的產(chǎn)生器不可。但 State Monad 讓我們可以方便一些。
System.Random 中的 random 函數(shù)有下列的型態(tài)：
random :: (RandomGen g, Random a) => g -> (a, g) 代表他接受一個亂數(shù)產(chǎn)生器，并產(chǎn)生一個亂數(shù)跟一個新的產(chǎn)生器。很明顯他是一個會改變狀態(tài)的計算，所以我們可以用 newtype 把他包在一個 State 中，然后把他當作 monadic value 來操作。
import System.Random
import Control.Monad.State
randomSt :: (RandomGen g, Random a) => State g a
randomSt = State random 這樣我們要丟三個硬幣的結(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 是一個改變狀態(tài)的計算，他接受一個初始的亂數(shù)產(chǎn)生器，他會把他喂給 randomSt，他會產(chǎn)生一個數(shù)字跟一個新的產(chǎn)生器，然后會一直傳遞下去。我們用 return (a,b,c) 來呈現(xiàn) (a,b,c)，這樣并不會改變最近一個產(chǎn)生器的狀態(tài)。
ghci> runState threeCoins (mkStdGen 33)
((True,False,True),680029187 2103410263)要完成像這樣要改變狀態(tài)的任務便因此變得輕松了很多。
我們知道 Maybe 是拿來賦予一個值具有可能失敗的 context。一個值可能會是 Just something 或是一個 Nothing。盡管這很有用，但當我們拿到了一個 Nothing，我們只知道他失敗了，但我們沒辦法塞進一些有用的資訊，告訴我們究竟是在什么樣的情況下失敗了。
而 Either e a 則能讓我們可以加入一個可能會發(fā)生錯誤的 context，還可以增加些有用的訊息，這樣能讓我們知道究竟是什么東西出錯了。一個 Either e a 的值可以是代表正確的 Right，或是代表錯誤的 Left，例如說：
掃碼關(guān)注鍍金池微信號
手機訂課，優(yōu)惠多多