再來看看更多 Monad
我們已經看過 Monad 是如何接受具有 context 的值,並如何用函數操作他們 還有如何用 >>=do 來減輕我們對 context 的關注,集中精神在 value 本身。
我們也看過了 Maybe 是如何把值加上一個可能會失敗的 context。我們學習到 List Monad 是如何加進多重結果的 context。我們也了解 IO Monad 如何運作,而且我們在知道什麼是 Monad 之前就已經知道他了。
在這個章節,我們會介紹一些其他的 Monad。他們可以把值變成 monadic value,因此可以讓我們的程式更簡潔清晰。多見識幾個 Monad 也可以敏銳我們對 Monad 的直覺。
我們即將要介紹的 Monad 都包含在 mtl 這個套建中。一個 Haskell package 包含了一堆模組。而 mtl 已經包含在 Haskell Platform 中,所以你可能不用另外安裝。要檢查你有沒有這套件,你可以下 ghc-pkg list。這會列出你已經安裝的套件,其中應該包含 mtl 後面接著對應的版號。

你所不知道的 Writer Monad

我們已經看過 Maybe, list 以及 IO Monad。現在我們要來看看 Writer Monad。
相對於 Maybe 是加入可能失敗的 context,list 是加入 non-deterministic 的 context,Writer 則是加進一個附加值的 context,好比 log 一般。Writer 可以讓我們在計算的同時蒐集所有 log 紀錄,並匯集成一個 log 並附加在結果上。
例如我們想要附加一個 String 好說明我們的值在幹麼(有可能是為了除錯)。想像有一個函數接受一個代表幫派人數的數字,然後會回傳值告訴我們這是否算是一個龐大的幫派:
1
isBigGang :: Int -> Bool
2
isBigGang x = x > 9
Copied!
現在我們希望他不只是回傳 TrueFalse,我們還希望他能夠多回傳一個字串代表 log。這很容易,只要多加一個 StringBool 旁邊就好了。
1
isBigGang :: Int -> (Bool, String)
2
isBigGang x = (x > 9, "Compared gang size to 9.")
Copied!
我們現在回傳了一個 Tuple,第一個元素是原來的布林值,第二個元素是一個 String。現在我們的值有了一個 context。
1
ghci> isBigGang 3
2
(False,"Compared gang size to 9.")
3
ghci> isBigGang 30
4
(True,"Compared gang size to 9.")
Copied!
到目前為止都還不錯,isBigGang 回傳一個值跟他的 context。對於正常的數值來說這樣的寫法都能運作良好。但如果我們想要把一個已經具有 context 的值,像是 (3, "Smallish gang."),餵給 isBigGang 呢?我們又面對了同樣的問題:如果我們有一個能接受正常數值並回傳一個具有 context 值的 function,那我們要如何餵給他一個具有 context 的值?
當我們在研究 Maybe monad 的時候,我們寫了一個 applyMaybe。他接受一個 Maybe a 值跟一個 a -> Maybe b 型態的函數,他會把 Maybe a 餵給這個 function,即便這個 function 其實是接受 a 而非 Maybe aapplyMaybe 有針對這樣的 context 做處理,也就是會留意有可能發生的失敗情況。但在 a -> Maybe b 裡面,我們可以只專心處理正常數值即可。因為 applyMaybe (之後變成了 >>=)會幫我們處理需要檢查 NothingJust 的情況。
我們再來寫一個接受附加 log 值的函數,也就是 (a, String) 型態的值跟 a -> (b, String) 型態的函數。我們稱呼這個函數為 applyLog。這個函數有的 context 是附加 log 值,而不是一個可能會失敗的 context,因此 applyLog 會確保原有的 log 被保留,並附上從函數產生出的新的 log。這邊我們來看一下實作:
1
applyLog :: (a,String) -> (a -> (b,String)) -> (b,String)
2
applyLog (x,log) f = let (y,newLog) = f x in (y,log ++ newLog)
Copied!
當我們想把一個具有 context 的值餵給一個函數的時候,我們會嘗試把值跟他的 context 分開,然後把值餵給函數再重新接回 context。在 Maybe monad 的情況,我們檢查值是否為 Just x,如果是,便將 x 餵給函數。而在 log 的情況,我們知道 pair 的其中一個 component 是 log 而另一個是值。所以我們先取出值 x,將 f apply 到 x,便獲取 (y,newLog),其中 y 是新的值而 newLog 則是新的 log。但如果我們回傳 newLog,舊的 log 便不會包含進去,所以我們要回傳的是 (y, log ++ newLog)。我們用 ++ 來把新的 log 接到舊的上面。
來看看 applyLog 運作的情形:
1
ghci> (3, "Smallish gang.") `applyLog` isBigGang
2
(False,"Smallish gang.Compared gang size to 9")
3
ghci> (30, "A freaking platoon.") `applyLog` isBigGang
4
(True,"A freaking platoon.Compared gang size to 9")
Copied!
跟之前的結果很像,只差在我們多了伴隨產生的 log。再來多看幾個例子:
1
ghci> ("Tobin","Got outlaw name.") `applyLog` (\x -> (length x, "Applied length."))
2
(5,"Got outlaw name.Applied length.")
3
ghci> ("Bathcat","Got outlaw name.") `applyLog` (\x -> (length x, "Applied length"))
4
(7,"Got outlaw name.Applied length")
Copied!
可以看到在 lambda 裡面 x 只是個正常的字串而不是 tuple,且 applyLog 幫我們處理掉附加 log 的動作。

Monoids 的好處

1
請確定你了解什麼是 Monoids。
Copied!
到目前為止 applyLog 接受 (a,String) 型態的值,但為什麼 log 一定要是 String 呢?我們使用 ++ 來附加新的 log,難道 ++ 並不能運作在任何形式的 list,而一定要限制我們在 String 上呢?我們當然可以擺脫 String,我們可以如下改變他的型態:
1
applyLog :: (a,[c]) -> (a -> (b,[c])) -> (b,[c])
Copied!
我們用一個 List 來代表 Log。包含在 List 中的元素型態必須跟原有的 List 跟回傳的 List 型態相同,否則我們沒辦法用 ++ 來把他們接起來。
這能夠運作在 bytestring 上嗎?絕對沒問題。只是我們現在的型態只對 List 有效。我們必須要另外做一個 bytestring 版本的 applyLog。但我們注意到 List 跟 bytestring 都是 monoids。因此他們都是 Monoid type class 的 instance,那代表他們都有實作 mappend。對 List 以及 bytestring 而言,mappend 都是拿來串接的。
1
ghci> [1,2,3] `mappend` [4,5,6]
2
[1,2,3,4,5,6]
3
ghci> B.pack [99,104,105] `mappend` B.pack [104,117,97,104,117,97]
4
Chunk "chi" (Chunk "huahua" Empty)
Copied!
修改後我們的 applyLog 可以運作在任何 monoid 上。我們必須要修改型態宣告來表示這件事,同時也要在實作中把 ++ 改成 mappend
1
applyLog :: (Monoid m) => (a,m) -> (a -> (b,m)) -> (b,m)
2
applyLog (x,log) f = let (y,newLog) = f x in (y,log `mappend` newLog)
Copied!
由於現在包含的值可以是任何 monoid,我們不再需要把 tuple 想成包含一個值跟對應的 log,我們可以想成他包含一個值跟一個對應的 monoid。舉例來說,可以說我們有一個 tuple 包含一個產品名稱跟一個符合 monoid 特性的產品價格。我們可以定義一個 Sum 的 newtype 來保證我們在操作產品的時候也會把價錢跟著加起來。
1
import Data.Monoid
2
3
type Food = String
4
type Price = Sum Int
5
6
addDrink :: Food -> (Food,Price)
7
addDrink "beans" = ("milk", Sum 25)
8
addDrink "jerky" = ("whiskey", Sum 99)
9
addDrink _ = ("beer", Sum 30)
Copied!
我們用 string 來代表食物,用 newtype 重新定義 nIntSum,來追蹤總共需要花多少錢。可以注意到我們用 mappend 來操作 Sum 的時候,價錢會被一起加起來。
1
ghci> Sum 3 `mappend` Sum 9
2
Sum {getSum = 12}
Copied!
addDrink 的實作很簡單,如果我們想吃豆子,他會回傳 "milk" 以及伴隨的 Sum 25,同樣的如果我們要吃 "jerky",他就會回傳 "whiskey",要吃其他東西的話,就會回傳 "beer"。乍看之下這個函數沒什麼特別,但如果用 applyLog 的話就會有趣些。
1
ghci> ("beans", Sum 10) `applyLog` addDrink
2
("milk",Sum {getSum = 35})
3
ghci> ("jerky", Sum 25) `applyLog` addDrink
4
("whiskey",Sum {getSum = 124})
5
ghci> ("dogmeat", Sum 5) `applyLog` addDrink
6
("beer",Sum {getSum = 35})
Copied!
牛奶價值 25 美分,但如果我們也吃了價值 10 美分的豆子的話,總共需要付 35 美分。這樣很清楚地展示了伴隨的值不一定需要是 log,他可以是任何 monoid。至於兩個值要如何結合,那要看 monoid 中怎麼定義。當我們需要的是 log 的時候,他們是串接,但這個 case 裡面,數字是被加起來。
由於 addDrink 回傳一個 (Food,Price),我們可以再把結果重新餵給 addDrink,這可以很容易告訴我們總共喝了多少錢:
1
ghci> ("dogmeat", Sum 5) `applyLog` addDrink `applyLog` addDrink
2
("beer",Sum {getSum = 65})
Copied!
將狗食跟 30 美分的啤酒加在一起會得到 ("beer", Sum 35)。如果我們用 applyLog 將上面的結果再餵給 addDrink,我們會得到 ("beer", Sum 65) 這樣的結果。

The Writer type

我們認識了一個附加 monoid 的值其實表現出來的是一個 monad,我們來再來看看其他類似的 Monad instance。Control.Monad.Writer 這模組含有 Writer w a 的一個型態,裏面定義了他 Monad 的 instance,還有一些操作這些值的函數。
首先,我們來看一下型態。要把一個 monoid 附加給一個值,只需要定義一個 tuple 就好了。Writer w a 這型態其實是一個 newtype wrapper。他的定義很簡單:
1
newtype Writer w a = Writer { runWriter :: (a, w) }
Copied!
他包在一個 newtype 裏面,並且可以是一個 Monad 的 instance,而且這樣定義的好處是可以跟單純 tuple 的型態區分開來。a 這個型態參數代表是包含的值的型態,而 w 則是附加的 monoid 的型態。
Monad instance 的定義如下:
1
instance (Monoid w) => Monad (Writer w) where
2
return x = Writer (x, mempty)
3
(Writer (x,v)) >>= f = let (Writer (y, v')) = f x in Writer (y, v `mappend` v')
Copied!
首先,我們來看看 >>=。他的實作基本上就是 applyLog,只是我們的 tuple 現在是包在一個 Writernewtype 中,我們可以用 pattern matching 的方式把他給 unwrap。我們將 x 餵給 f。這會回給我們 Writer w a。接著可以用 let expression 來做 pattern matching。把結果綁定到 y 這個名字上,然後用 mappend 來結合舊的 monoid 值跟新的 monoid 值。最後把結果跟 monoid 值用 Writer constructor 包起來,形成我們最後的 Writer value。
return 呢?回想 return 的作用是接受一個值,並回傳一個具有意義的最小 context 來裝我們的值。那究竟什麼樣的 context 可以代表我們的 Writer 呢?如果我們希望 monoid 值所造成的影響愈小愈好,那 mempty 是個合理的選擇。mempty 是被當作 identity monoid value,像是 ""Sum 0,或是空的 bytestring。當我們對 memptymappend 跟其他 monoid 值結合,結果會是其他的 monoid 值。所以如果我們用 return 來做一個 Writer,然後用 >>= 來餵給其他的函數,那函數回傳的便是算出來的 monoid。下面我們試著用 return 搭配不同 context 來回傳 3
1
ghci> runWriter (return 3 :: Writer String Int)
2
(3,"")
3
ghci> runWriter (return 3 :: Writer (Sum Int) Int)
4
(3,Sum {getSum = 0})
5
ghci> runWriter (return 3 :: Writer (Product Int) Int)
6
(3,Product {getProduct = 1})
Copied!
因為 Writer 並沒有定義成 Show 的 instance,我們必須用 runWriter 來把我們的 Writer 轉成正常的 tuple。對於 String,monoid 的值就是空字串。而對於 Sum 來說則是 0,因為 0 加上其他任何值都會是對方。而對 Product 來說,則是 1
這裡的 Writer instance 並沒有定義 fail,所以如果 pattern matching 失敗的話,就會呼叫 error

Using do notation with Writer

既然我們定義了 Monad 的 instance,我們自然可以用 do 串接 Writer 型態的值。這在我們需要對一群 Writer 型態的值做處理時顯得特別方便。就如其他的 monad,我們可以把他們當作具有 context 的值。在現在這個 case 中,所有的 monoid 的值都會用 mappend 來連接起來並得到最後的結果。這邊有一個簡單的範例,我們用 Writer 來相乘兩個數。
1
import Control.Monad.Writer
2
3
logNumber :: Int -> Writer [String] Int
4
logNumber x = Writer (x, ["Got number: " ++ show x])
5
6
multWithLog :: Writer [String] Int
7
multWithLog = do
8
a <- logNumber 3
9
b <- logNumber 5
10
return (a*b)
Copied!
logNumber 接受一個數並把這個數做成一個 Writer。我們再用一串 string 來當作我們的 monoid 值,每一個數都跟著一個只有一個元素的 list,說明我們只有一個數。multWithLog 式一個 Writer,他將 35 相乘並確保相乘的紀錄有寫進最後的 log 中。我們用 return 來做成 a*b 的結果。我們知道 return 會接受某個值並加上某個最小的 context,我們可以確定他不會多添加額外的 log。如果我們執行程式會得到:
1
ghci> runWriter multWithLog
2
(15,["Got number: 3","Got number: 5"])
Copied!
有時候我們就是想要在某個時間點放進某個 Monoid value。tell 正是我們需要的函數。他實作了 MonadWriter 這個 type class,而且在當 Writer 用的時候也能接受一個 monoid value,好比說 ["This is going on"]。我們能用他來把我們的 monoid value 接到任何一個 dummy value () 上來形成一個 Writer。當我們拿到的結果是 () 的時候,我們不會把他綁定到變數上。來看一個 multWithLog 的範例:
1
multWithLog :: Writer [String] Int
2
multWithLog = do
3
a <- logNumber 3
4
b <- logNumber 5
5
tell ["Gonna multiply these two"]
6
return (a*b)
Copied!
return (a*b) 是我們的最後一行,還記得在一個 do 中的最後一行代表整個 do 的結果。如果我們把 tell 擺到最後,則 do 的結果則會是 ()。我們會因此丟掉乘法運算的結果。除此之外,log 的結果是不變的。
1
ghci> runWriter multWithLog
2
(15,["Got number: 3","Got number: 5","Gonna multiply these two"])
Copied!

Adding logging to programs

歐幾里得算法是找出兩個數的最大公因數。Haskell 已經提供了 gcd 的函數,但我們來實作一個具有 log 功能的 gcd:
1
gcd' :: Int -> Int -> Int
2
gcd' a b
3
| b == 0 = a
4
| otherwise = gcd' b (a `mod` b)
Copied!
演算法的內容很簡單。首先他檢查第二個數字是否為零。如果是零,那就回傳第一個數字。如果不是,那結果就是第二個數字跟將第一個數字除以第二個數字的餘數兩個數字的最大公因數。舉例來說,如果我們想知道 8 跟 3 的最大公因數,首先可以注意到 3 不是 0。所以我們要求的是 3 跟 2 的最大公因數(8 除以 3 餘二)。接下去我可以看到 2 不是 0,所以我們要再找 2 跟 1 的最大公因數。同樣的,第二個數不是 0,所以我們再找 1 跟 0 的最大公因數。最後第二個數終於是 0 了,所以我們得到最大公因數是 1。
1
ghci> gcd' 8 3
2
1
Copied!
答案真的是這樣。接著我們想加進 context,context 會是一個 monoid value 並且像是一個 log 一樣。就像之前的範例,我們用一串 string 來當作我們的 monoid。所以 gcd' 會長成這樣:
1
gcd' :: Int -> Int -> Writer [String] Int
Copied!
而他的程式碼會像這樣:
1
import Control.Monad.Writer
2
3
gcd' :: Int -> Int -> Writer [String] Int
4
gcd' a b
5
| b == 0 = do
6
tell ["Finished with " ++ show a]
7
return a
8
| otherwise = do
9
tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
10
gcd' b (a `mod` b)
Copied!
這個函數接受兩個 Int 並回傳一個 Writer [String] Int,也就是說是一個有 log context 的 Int。當 b 等於 0 的時候,我們用一個 do 來組成一個 Writer 的值。我們先用 tell 來寫入我們的 log,然後用 return 來當作 do 的結果。當然我們也可以這樣寫:
1
Writer (a, ["Finished with " ++ show a])
Copied!
但我想 do 的表達方式是比較容易閱讀的。接下來我們看看當 b 不等於 0 的時候。我們會把 mod 的使用情況寫進 log。然後在 do 當中的第二行遞迴呼叫 gcd'gcd' 現在是回傳一個 Writer 的型態,所以 gcd' b (a `mod` b) 這樣的寫法是完全沒問題的。
儘管去 trace 這個 gcd' 對於理解十分有幫助,但我想了解整個大概念,把值視為具有 context 是更加有用的。
接著來試試跑我們的 gcd',他的結果會是 Writer [String] Int,如果我們把他從 newtype 中取出來,我們會拿到一個 tuple。tuple 的第一個部份就是我們要的結果:
1
ghci> fst $ runWriter (gcd' 8 3)
2
1
Copied!
至於 log 呢,由於 log 是一連串 string,我們就用 mapM_ putStrLn 來把這些 string 印出來:
1
ghci> mapM_ putStrLn $ snd $ runWriter (gcd' 8 3)
2
8 mod 3 = 2
3
3 mod 2 = 1
4
2 mod 1 = 0
5
Finished with 1
Copied!
把普通的演算法轉換成具有 log 是很棒的經驗,我們不過是把普通的 value 重寫成 Monadic value,剩下的就靠 >>=Writer 來幫我們處理一切。用這樣的方法我們幾乎可以對任何函數加上 logging 的功能。我們只要把普通的值換成 Writer,然後把一般的函數呼叫換成 >>= (當然也可以用 do)

Inefficient list construction

當製作 Writer Monad 的時候,要特別注意你是使用哪種 monoid。使用 list 的話效能有時候是沒辦法接受的。因為 list 是使用 ++ 來作為 mappend 的實現。而 ++ 在 list 很長的時候是非常慢的。
在之前的 gcd' 中,log 並不會慢是因為 list append 的動作實際上看起來是這樣:
1
a ++ (b ++ (c ++ (d ++ (e ++ f))))
Copied!
list 是建立的方向是從左到右,當我們先建立左邊的部份,而把另一串 list 加到右邊的時候效能會不錯。但如果我們不小心使用,而讓 Writer monad 實際在操作 list 的時候變成像這樣的話。
1
((((a ++ b) ++ c) ++ d) ++ e) ++ f
Copied!
這會讓我們的操作是 left associative,而不是 right associative。這非常沒有效率,因為每次都是把右邊的部份加到左邊的部份,而左邊的部份又必須要從頭開始建起。
下面這個函數跟 gcd' 差不多,只是 log 的順序是相反的。他先紀錄剩下的操作,然後紀錄現在的步驟。
1
import Control.Monad.Writer
2
3
gcdReverse :: Int -> Int -> Writer [String] Int
4
gcdReverse a b
5
| b == 0 = do
6
tell ["Finished with " ++ show a]
7
return a
8
| otherwise = do
9
result <- gcdReverse b (a `mod` b)
10
tell [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)]
11
return result
Copied!
他先遞迴呼叫,然後把結果綁定到 result。然後把目前的動作寫到 log,在遞迴的結果之後。最後呈現的就是完整的 log。
1
ghci> mapM_ putStrLn $ snd $ runWriter (gcdReverse 8 3)
2
Finished with 1
3
2 mod 1 = 0
4
3 mod 2 = 1
5
8 mod 3 = 2
Copied!
這沒效率是因為他讓 ++ 成為 left associative 而不是 right associative。

Difference lists

由於 list 在重複 append 的時候顯得低效,我們最好能使用一種支援高效 appending 的資料結構。其中一種就是 difference list。difference list 很類似 list,只是他是一個函數。他接受一個 list 並 prepend 另一串 list 到他前面。一個等價於 [1,2,3] 的 difference list 是這樣一個函數 \xs -> [1,2,3] ++ xs。一個等價於 [] 的 difference list 則是 \xs -> [] ++ xs
Difference list 最酷的地方在於他支援高效的 appending。當我們用 ++ 來實現 appending 的時候,他必須要走到左邊的 list 的尾端,然後把右邊的 list 一個個從這邊接上。那 difference list 是怎麼作的呢?appending 兩個 difference list 就像這樣
1
f `append` g = \xs -> f (g xs)
Copied!
fg 這邊是兩個函數,他們都接受一個 list 並 prepend 另一串 list。舉例來說,如果 f 代表 ("dog"++)(可以寫成 \xs -> "dog" ++ xs)而 g("meat"++),那 f `append` g 就會做成一個新的函數,等價於:
1
\xs -> "dog" ++ ("meat" ++ xs)
Copied!
append 兩個 difference list 其實就是用一個函數,這函數先餵一個 list 給第一個 difference list,然後再把結果餵給第二個 difference list。
我們可以用一個 newtype 來包起來
1
newtype DiffList a = DiffList { getDiffList :: [a] -> [a] }
Copied!
我們包起來的型態是 [a] -> [a],因為 difference list 不過就是一個轉換一個 list 到另一個 list 的函數。要把普通 list 轉換成 difference list 也很容易。
1
toDiffList :: [a] -> DiffList a
2
toDiffList xs = DiffList (xs++)
3
4
fromDiffList :: DiffList a -> [a]
5
fromDiffList (DiffList f) = f []
Copied!
要把一個普通 list 轉成 difference list 不過就是照之前定義的,作一個 prepend 另一個 list 的函數。由於 difference list 只是一個 prepend 另一串 list 的一個函數,假如我們要轉回來的話,只要餵給他空的 list 就行了。
這邊我們給一個 difference list 的 Monoid 定義
1
instance Monoid (DiffList a) where
2
mempty = DiffList (\xs -> [] ++ xs)
3
(DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))
Copied!
我們可以看到 mempty 不過就是 id,而 mappend 其實是 function composition。
1
ghci> fromDiffList (toDiffList [1,2,3,4] `mappend` toDiffList [1,2,3])
2
[1,2,3,4,1,2,3]
Copied!
現在我們可以用 difference list 來加速我們的 gcdReverse
1
import Control.Monad.Writer
2
3
gcd' :: Int -> Int -> Writer (DiffList String) Int
4
gcd' a b
5
| b == 0 = do
6
tell (toDiffList ["Finished with " ++ show a])
7
return a
8
| otherwise = do
9
result <- gcd' b (a `mod` b)
10
tell (toDiffList [show a ++ " mod " ++ show b ++ " = " ++ show (a `mod` b)])
11
return result
Copied!
我們只要把 monoid 的型態從 [String] 改成 DiffList String,並在使用 tell 的時候把普通的 list 用 toDiffList 轉成 difference list 就可以了。
1
ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ gcdReverse 110 34
2
Finished with 2
3
8 mod 2 = 0
4
34 mod 8 = 2
5
110 mod 34 = 8
Copied!
我們用 runWriter 來取出 gcdReverse 110 34 的結果,然後用 snd 取出 log,並用 fromDiffList 轉回普通的 list 印出來。

Comparing Performance

要體會 Difference List 能如何增進效率,考慮一個從某數數到零的 case。我們紀錄的時候就像 gcdReverse 一樣是反過來記的,所以在 log 中實際上是從零數到某個數。
1
finalCountDown :: Int -> Writer (DiffList String) ()
2
finalCountDown 0 = do
3
tell (toDiffList ["0"])
4
finalCountDown x = do
5
finalCountDown (x-1)
6
tell (toDiffList [show x])
Copied!
如果我們餵 0,他就只 log 0。如果餵其他正整數,他會先倒數到 0 然後 append 那些數到 log 中,所以如果我們呼叫 finalCountDown 並餵給他 100,那 log 的最後一筆就會是 "100"
如果你把這個函數 load 進 GHCi 中並餵給他一個比較大的整數 500000,你會看到他無停滯地從 0 開始數起:
1
ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ finalCountDown 500000
2
0
3
1
4
2
Copied!
但如果我們用普通的 list 而不用 difference list
1
finalCountDown :: Int -> Writer [String] ()
2
finalCountDown 0 = do
3
tell ["0"]
4
finalCountDown x = do
5
finalCountDown (x-1)
6
tell [show x]
Copied!
並下同樣的指令
1
ghci> mapM_ putStrLn . snd . runWriter $ finalCountDown 500000
Copied!
我們會看到整個運算卡卡的。
當然這不是一個嚴謹的測試方法,但足以表顯出 difference list 是比較有效率的寫法。

Reader Monad

在講 Applicative 的章節中,我們說過了 (->) r 的型態只是 Functor 的一個 instance。要將一個函數 f map over 一個函數 g,基本上等價於一個函數,他可以接受原本 g 接受的參數,先套用 g 然後再把其結果丟給 f
1
ghci> let f = (*5)
2
ghci> let g = (+3)
3
ghci> (fmap f g) 8
Copied!
我們已經見識過函數當作 applicative functors 的例子。這樣能讓我們對函數的結果直接進行操作。
1
ghci> let f = (+) <gt; (*2) <*> (+10)
2
ghci> f 3
3
19
Copied!
(+) <gt; (*2) <*> (+10) 代表一個函數,他接受一個數值,分別把這數值交給 (*2)(+10)。然後把結果加起來。例如說,如果我們餵 3 給這個函數,他會分別對 3(*2)(+10) 的動作。而得到 613。然後呼叫 (+),而得到 19
其實 (->) r 不只是一個 functor 跟一個 applicative functor,他也是一個 monad。就如其他 monadic value 一般,一個函數也可以被想做是包含一個 context 的。這個 context 是說我們期待某個值,他還沒出現,但我們知道我們會把他當作函數的參數,呼叫函數來得到結果。
我們已經見識到函數是怎樣可以看作 functor 或是 applicative functors 了。再來讓我們看看當作 Monad 的一個 instance 時會是什麼樣子。你可以在 Control.Monad.Instances 裡面找到,他看起來像這樣:
1
instance Monad ((->) r) where
2
return x = \_ -> x
3
h >>= f = \w -> f (h w) w
Copied!
我們之前已經看過函數的 pure 實作了,而 return 差不多就是 pure。他接受一個值並把他放進一個 minimal context 裡面。而要讓一個函數能夠是某個定值的唯一方法就是讓他完全忽略他的參數。
>>= 的實作看起來有點難以理解,我們可以仔細來看看。當我們使用 >>= 的時候,餵進去的是一個 monadic value,處理他的是一個函數,而吐出來的也是一個 monadic value。在這個情況下,當我們將一個函數餵進一個函數,吐出來的也是一個函數。這就是為什麼我們在最外層使用了一個 lambda。在我們目前看過的實作中,>>= 幾乎都是用 lambda 將內部跟外部隔開來,然後在內部來使用 f。這邊也是一樣的道理。要從一個函數得到一個結果,我們必須餵給他一些東西,這也是為什麼我們先用 (h w) 取得結果,然後將他丟給 f。而 f 回傳一個 monadic value,在這邊這個 monadic value 也就是一個函數。我們再把 w 餵給他。
如果你還不太懂 >>= 怎麼寫出來的,不要擔心,因為接下來的範例會讓你曉得這真的是一個簡單的 Monad。我們造一個 do expression 來使用這個 Monad。
1
import Control.Monad.Instances
2
3
addStuff :: Int -> Int
4
addStuff = do
5
a <- (*2)
6
b <- (+10)
7
return (a+b)
Copied!
這跟我們之前寫的 applicative expression 差不多,只差在他是運作在 monad 上。一個 do expression 的結果永遠會是一個 monadic vlaue,這個也不例外。而這個 monadic value 其實是一個函數。只是在這邊他接受一個數字,然後套用 (*2),把結果綁定到 a 上面。而 (+10) 也同用被套用到同樣的參數。結果被綁定到 b 上。return 就如其他 monad 一樣,只是製作一個簡單的 monadic value 而不會作多餘的事情。這讓整個函數的結果是 a+b。如果我們試著跑跑看,會得到之前的結果。
1
ghci> addStuff 3
2
19
Copied!
其中 3 會被餵給 (*2)(+10)。而且他也會被餵給 return (a+b),只是他會忽略掉 3 而永遠回傳 a+b 正因為如此,function monad 也被稱作 reader monad。所有函數都從一個固定的地方讀取。要寫得更清楚一些,可以把 addStuff 改寫如下:
1
addStuff :: Int -> Int
2
addStuff x = let
3
a = (*2) x
4
b = (+10) x
5
in a+b
Copied!
我們見識了把函數視作具有 context 的值很自然的可以表達成 reader monad。只要我們當作我們知道函數會回傳什麼值就好。他作的就是把所有的函數都黏在一起做成一個大的函數,然後把這個函數的參數都餵給全部組成的函數,這有點取出他們未來的值的意味。實作做完了然後 >>= 就會保證一切都能正常運作。

State Monad

Haskell 是一個純粹的語言,正因為如此,我們的程式是有一堆沒辦法改變全域狀態或變數的函數所組成,他們只會作些處理並回傳結果。這樣的性質讓我們很容易思考我們的程式在幹嘛,因為我們不需要擔心變數在某一個時間點的值是什麼。然而,有一些領域的問題根本上就是依賴於隨著時間而改變的狀態。雖然我們也可以用 Haskell 寫出這樣的程式,但有時候寫起來蠻痛苦的。這也是為什麼 Haskell 要加進 State Monad 這個特性。這讓我們在 Haskell 中可以容易地處理狀態性的問題,並讓其他部份的程式還是保持純粹性。
當我們處理亂數的時候,我們的函數接受一個 random generator 並回傳一個新的亂數跟一個新的 random generator。如果我們需要很多個亂數,我們可以用前一個函數回傳的 random generator 繼續做下去。當我們要寫一個接受 StdGen 的函數並產生丟三個硬幣結果的函數,我們會這樣寫:
1
threeCoins :: StdGen -> (Bool, Bool, Bool)
2
threeCoins gen =
3
let (firstCoin, newGen) = random gen
4
(secondCoin, newGen') = random newGen
5
(thirdCoin, newGen''') = random newGen'
6
in (firstCoin, secondCoin, thirdCoin)
Copied!
他接受一個 gen 然後用 random gen 產生一個 Bool 型態的值以及新的 generator。要模擬丟第二個硬幣的話,便使用新的 generator。在其他語言中,多半除了亂數之外不需要多回傳一個 generator。那是因為我們可以對現有的進行修改。但 Haskell 是純粹的語言,我們沒辦法那麼做,所以我們必須要接受一個狀態,產生結果然後回傳一個新的狀態,然後用新的狀態來繼續做下去。
一般來講你應該不會喜歡這麼寫,在程式中有赤裸裸的狀態,但我們又不想放棄 Haskell 的純粹性質。這就是 State Monad 的好處了,他可以幫我們處理這些瑣碎的事情,又讓我們保持 Haskell 的純粹性。
為了深入理解狀態性的計算,我們先來看看應該給他們什麼樣的型態。我們會說一個狀態性的計算是一個函數,他接受一個狀態,回傳一個值跟一個新的狀態。寫起來會像這樣:
1
s -> (a,s)
Copied!
s 是狀態的型態,而 a 是計算結果的型態。
1
在其他的語言中,賦值大多是被當作會改變狀態的操作。舉例來說,當我們在命令式語言寫 ``x = 5``,這通常代表的是把 ``5`` 指定給 ``x`` 這變數。而且這邊 ``5`` 是一個 expression。
2
3
如果你用函數語言的角度去思考,你可以把他想做是一個函數,接受一個狀態,並回傳結果跟新的狀態。那新的狀態代表所有已指定的值與新加入的變數。
Copied!
這種改變狀態的計算,除了想做是一個接受狀態並回傳結果跟新狀態的函數外,也可以想做是具有 context 的值。 實際的值是結果。然而要得到結果,我們必須要給一個初始的狀態,才能得到結果跟最後的狀態。

Stack and Stones

考慮現在我們要對一個堆疊的操作建立模型。你可以把東西推上堆疊頂端,或是把東西從頂端拿下來。如果你要的元素是在堆疊的底層的話,你必須要把他上面的東西都拿下來才能拿到他。
我們用一個 list 來代表我們的堆疊。而我們把 list 的頭當作堆疊的頂端。為了正確的建立模型,我們要寫兩個函數:poppushpop 會接受一個堆疊,取下一個元素並回傳一個新的堆疊,這個新的堆疊不包含取下的元素。push 會接受一個元素,把他堆到堆疊中,並回傳一個新的堆疊,其包含這個新的元素。
1
type Stack = [Int]
2
3
pop :: Stack -> (Int,Stack)
4
pop (x:xs) = (x,xs)
5
6
push :: Int -> Stack -> ((),Stack)
7
push a xs = ((),a:xs)
Copied!
我們用 () 來當作 pushing 的結果,畢竟推上堆疊並不需要什麼回傳值,他的重點是在改變堆疊。注意到 pushpop 都是改變狀態的計算,可以從他們的型態看出來。
我們來寫一段程式來模擬一個堆疊的操作。我們接受一個堆疊,把 3 推上去,然後取出兩個元素。
1
stackManip :: Stack -> (Int, Stack)
2
stackManip stack = let
3
((),newStack1) = push 3 stack
4
(a ,newStack2) = pop newStack1
5
in pop newStack2
Copied!
我們拿一個 stack 來作 push 3 stack 的動作,其結果是一個 tuple。tuple 的第一個部份是 (),而第二個部份是新的堆疊,我們把他命名成 newStack1。然後我們從 newStack1 上 pop 出一個數字。其結果是我們之前 push 上去的一個數字 a,然後把這個更新的堆疊叫做 newStack2。然後我們從 newStack2 上再 pop 出一個數字 b,並得到 newStack3。我們回傳一個 tuple 跟最終的堆疊。
1
ghci> stackManip [5,8,2,1]
2
(5,[8,2,1])
Copied!
結果就是 5 跟新的堆疊 [8,2,1]。注意到 stackManip 是一個會改變狀態的操作。我們把一堆會改變狀態的操作綁在一起操作,有沒有覺得很耳熟的感覺。
stackManip 的程式有點冗長,因為我們要寫得太詳細,必須把狀態給每個操作,然後把新的狀態再餵給下一個。如果我們可以不要這樣作的話,那程式應該會長得像這樣:
1
stackManip = do
2
push 3
3
a <- pop
4
pop
Copied!
這就是 State Monad 在做的事。有了他,我們便可以免除於要把狀態操作寫得太明白的窘境。

The State Monad

Control.Monad.State 這個模組提供了一個 newtype 包起來的型態。
1
newtype State s a = State { runState :: s -> (a,s) }
Copied!
一個 State s a 代表的是一個改變狀態的操作,他操縱的狀態為型態 s,而產生的結果是 a
我們已經見識過什麼是改變狀態的操作,以及他們是可以被看成具有 context 的值。接著來看看他們 Monad 的 instance:
1
instance Monad (State s) where
2
return x = State $ \s -> (x,s)
3
(State h) >>= f = State $ \s -> let (a, newState) = h s
4
(State g) = f a
5
in g newState
Copied!
我們先來看看 return 那一行。我們 return 要作的事是接受一個值,並做出一個改變狀態的操作,讓他永遠回傳那個值。所以我們才做了一個 lambda 函數,\s -> (x,s)。我們把 x 當成是結果,並且狀態仍然是 s。這就是 return 要完成的 minimal context。
>>= 的實作呢?很明顯的把改變狀態的操作餵進 >>= 也必須要丟出另一個改變狀態的操作。所以我們用 State 這個 newtype wrapper 來把一個 lambda 函數包住。這個 lambda 會是新的一個改變狀態的操作。但裡面的內容是什麼?首先我們應該要從接受的操作取出結果。由於 lambda 是在一個大的操作中,所以我們可以餵給 h 我們現在的狀態,也就是 s。那會產生 (a, newState)。到目前為止每次我們在實作 >>= 的時候,我們都會先從 monadic value 中取出結果,然後餵給 f 來得到新的 monadic value。在寫 Writer 的時候,我們除了這樣作還要確保 context 是用 mappend 把舊的 monoid value 跟新的接起來。在這邊我們則是用 f a 得到一個新的操作 g。現在我們有了新的操作跟新的狀態(叫做 newState),我們就把 newState 餵給 g。結果便是一個 tuple,裡面包含了最後的結果跟最終的狀態。
有了 >>=,我們便可以把兩個操作黏在一起,只是第二個被放在一個函數中,專門接受第一個的結果。由於 poppush 已經是改變狀態的操作了,我們可以把他們包在 State
1
import Control.Monad.State
2
3
pop :: State Stack Int
4
pop = State $ \(x:xs) -> (x,xs)
5
6
push :: Int -> State Stack ()
7
push a = State $ \xs -> ((),a:xs)
Copied!
pop 已經滿足我們的條件,而 push 要先接受一個 Int 才會回傳我們要的操作。所以我們可以改寫先前的範例如下:
1
import Control.Monad.State
2
3
stackManip :: State Stack Int
4
stackManip = do
5
push 3
6
a <- pop
7
pop
Copied!
看到我們是怎麼把一個 push 跟兩個 pop 黏成一個操作嗎?當我們將他們從一個 newtype 取出,其實就是需要一個能餵進初始狀態的函數:
1
ghci> runState stackManip [5,8,2,1]
2
(5,[8,2,1])
Copied!
我們不須綁定第二個 pop,因為我們根本不會用到 a,所以可以寫成下面的樣子:
1
stackManip :: State Stack Int
2
stackManip = do
3
push 3
4
pop
5
pop
Copied!
再來嘗試另外一種方式,先從堆疊上取下一個數字,看看他是不是 5,如果是的話就把他放回堆疊上,如果不是的話就堆上 38
1
stackStuff :: State Stack ()
2
stackStuff = do
3
a <- pop
4
if a == 5
5
then push 5
6
else do
7
push 3
8
push 8
Copied!
很直覺吧!我們來看看初始的堆疊的樣子。
1
ghci> runState stackStuff [9,0,2,1,0]
2
((),[8,3,0,2,1,0])
Copied!
還記得我們說過 do 的結果會是一個 monadic value,而在 State monad 的 case,do 也就是一個改變狀態的函數。而由於 stackManipstackStuff 都是改變狀態的計算,因此我們可以把他們黏在一起:
1
moreStack :: State Stack ()
2
moreStack = do
3
a <- stackManip
4
if a == 100
5
then stackStuff
6
else return ()
Copied!
如果 stackManip 的結果是 100,我們就會跑 stackStuff,如果不是的話就什麼都不做。return () 不過就是什麼是都不做,全部保持原樣。
Contorl.Monad.State 提供了一個 MonadState 的 typeclass,他有兩個有用的函數,分別是 getput。對於 State 來說,get 的實作就像這樣:
1
get = State $ \s -> (s,s)
Copied!
他只是取出現在的狀態除此之外什麼也不做。而 put 函數會接受一個狀態並取代掉現有的狀態。
1
put newState = State $ \s -> ((),newState)
Copied!
有了這兩個狀態,我們便可以看到現在堆疊中有什麼,或是把整個堆疊中的元素換掉。
1
stackyStack :: State Stack ()
2
stackyStack = do
3
stackNow <- get
4
if stackNow == [1,2,3]
5
then put [8,3,1]
6
else put [9,2,1]
Copied!
我們可以看看對於 State 而言,>>= 的型態會是什麼:
1
(>>=) :: State s a -> (a -> State s b) -> State s b
Copied!
我們可以看到狀態的型態都是 s,而結果從型態 a 變成型態 b。這代表我們可以把好幾個改變狀態的計算黏在一起,這些計算的結果可以都不一樣,但狀態的型態會是一樣的。舉例來說,對於 Maybe 而言,>>= 的型態會是:
1
(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Copied!
Maybe 不變是有道理的,但如果用 >>= 來把兩種不同的 monad 接起來是沒道理的。但對於 state monad 而言,monad 其實是 State s,所以如果 s 不一樣,我們就要用 >>= 來把兩個 monad 接起來。

隨機性與 state monad

在章節的一開始,我們知道了在 Haskell 中要產生亂數的不方便。我們要拿一個產生器,並回傳一個亂數跟一個新的產生器。接下來我們還一定要用新的產生器不可。但 State Monad 讓我們可以方便一些。
System.Random 中的 random 函數有下列的型態:
1
random :: (RandomGen g, Random a) => g -> (a, g)
Copied!
代表他接受一個亂數產生器,並產生一個亂數跟一個新的產生器。很明顯他是一個會改變狀態的計算,所以我們可以用 newtype 把他包在一個 State 中,然後把他當作 monadic value 來操作。
1
import System.Random
2
import Control.Monad.State
3
4
randomSt :: (RandomGen g, Random a) => State g a
5
randomSt = State random