再来看看更多 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 好说明我们的值在干么(有可能是为了除错)。想像有一个函数接受一个代表帮派人数的数字,然后会回传值告诉我们这是否算是一个庞大的帮派:
isBigGang :: Int -> Bool
isBigGang x = x > 9
现在我们希望他不只是回传 TrueFalse,我们还希望他能够多回传一个字串代表 log。这很容易,只要多加一个 StringBool 旁边就好了。
isBigGang :: Int -> (Bool, String)
isBigGang x = (x > 9, "Compared gang size to 9.")
我们现在回传了一个 Tuple,第一个元素是原来的布尔值,第二个元素是一个 String。现在我们的值有了一个 context。
ghci> isBigGang 3
(False,"Compared gang size to 9.")
ghci> isBigGang 30
(True,"Compared gang size to 9.")
到目前为止都还不错,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。这边我们来看一下实作:
applyLog :: (a,String) -> (a -> (b,String)) -> (b,String)
applyLog (x,log) f = let (y,newLog) = f x in (y,log ++ newLog)
当我们想把一个具有 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 运作的情形:
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")
跟之前的结果很像,只差在我们多了伴随产生的 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 的好处

请确定你了解什么是 Monoids。
到目前为止 applyLog 接受 (a,String) 型态的值,但为什么 log 一定要是 String 呢?我们使用 ++ 来附加新的 log,难道 ++ 并不能运作在任何形式的 list,而一定要限制我们在 String 上呢?我们当然可以摆脱 String,我们可以如下改变他的型态:
applyLog :: (a,[c]) -> (a -> (b,[c])) -> (b,[c])
我们用一个 List 来代表 Log。包含在 List 中的元素型态必须跟原有的 List 跟回传的 List 型态相同,否则我们没办法用 ++ 来把他们接起来。
这能够运作在 bytestring 上吗?绝对没问题。只是我们现在的型态只对 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 上。我们必须要修改型态宣告来表示这件事,同时也要在实作中把 ++ 改成 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)
由于现在包含的值可以是任何 monoid,我们不再需要把 tuple 想成包含一个值跟对应的 log,我们可以想成他包含一个值跟一个对应的 monoid。举例来说,可以说我们有一个 tuple 包含一个产品名称跟一个符合 monoid 特性的产品价格。我们可以定义一个 Sum 的 newtype 来保证我们在操作产品的时候也会把价钱跟着加起来。
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 重新定义 nIntSum,来追踪总共需要花多少钱。可以注意到我们用 mappend 来操作 Sum 的时候,价钱会被一起加起来。
ghci> Sum 3 `mappend` Sum 9
Sum {getSum = 12}
addDrink 的实作很简单,如果我们想吃豆子,他会回传 "milk" 以及伴随的 Sum 25,同样的如果我们要吃 "jerky",他就会回传 "whiskey",要吃其他东西的话,就会回传 "beer"。乍看之下这个函数没什么特别,但如果用 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。至于两个值要如何结合,那要看 monoid 中怎么定义。当我们需要的是 log 的时候,他们是串接,但这个 case 里面,数字是被加起来。
由于 addDrink 回传一个 (Food,Price),我们可以再把结果重新喂给 addDrink,这可以很容易告诉我们总共喝了多少钱:
ghci> ("dogmeat", Sum 5) `applyLog` addDrink `applyLog` addDrink
("beer",Sum {getSum = 65})
将狗食跟 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。他的定义很简单:
newtype Writer w a = Writer { runWriter :: (a, w) }
他包在一个 newtype 里面,并且可以是一个 Monad 的 instance,而且这样定义的好处是可以跟单纯 tuple 的型态区分开来。a 这个型态参数代表是包含的值的型态,而 w 则是附加的 monoid 的型态。
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')
首先,我们来看看 >>=。他的实作基本上就是 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
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 转成正常的 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 来相乘两个数。
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 接受一个数并把这个数做成一个 Writer。我们再用一串 string 来当作我们的 monoid 值,每一个数都跟着一个只有一个元素的 list,说明我们只有一个数。multWithLog 式一个 Writer,他将 35 相乘并确保相乘的纪录有写进最后的 log 中。我们用 return 来做成 a*b 的结果。我们知道 return 会接受某个值并加上某个最小的 context,我们可以确定他不会多添加额外的 log。如果我们执行程序会得到:
ghci> runWriter multWithLog
(15,["Got number: 3","Got number: 5"])
有时候我们就是想要在某个时间点放进某个 Monoid value。tell 正是我们需要的函数。他实作了 MonadWriter 这个 type class,而且在当 Writer 用的时候也能接受一个 monoid value,好比说 ["This is going on"]。我们能用他来把我们的 monoid value 接到任何一个 dummy value () 上来形成一个 Writer。当我们拿到的结果是 () 的时候,我们不会把他绑定到变量上。来看一个 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 的结果。如果我们把 tell 摆到最后,则 do 的结果则会是 ()。我们会因此丢掉乘法运算的结果。除此之外,log 的结果是不变的。
ghci> runWriter multWithLog
(15,["Got number: 3","Got number: 5","Gonna multiply these two"])

Adding logging to programs

欧几里得算法是找出两个数的最大公因数。Haskell 已经提供了 gcd 的函数,但我们来实作一个具有 log 功能的 gcd:
gcd' :: Int -> Int -> Int
gcd' a b
| b == 0 = a
| otherwise = gcd' b (a `mod` b)
算法的内容很简单。首先他检查第二个数字是否为零。如果是零,那就回传第一个数字。如果不是,那结果就是第二个数字跟将第一个数字除以第二个数字的余数两个数字的最大公因数。举例来说,如果我们想知道 8 跟 3 的最大公因数,首先可以注意到 3 不是 0。所以我们要求的是 3 跟 2 的最大公因数(8 除以 3 余二)。接下去我可以看到 2 不是 0,所以我们要再找 2 跟 1 的最大公因数。同样的,第二个数不是 0,所以我们再找 1 跟 0 的最大公因数。最后第二个数终于是 0 了,所以我们得到最大公因数是 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)
这个函数接受两个 Int 并回传一个 Writer [String] Int,也就是说是一个有 log context 的 Int。当 b 等于 0 的时候,我们用一个 do 来组成一个 Writer 的值。我们先用 tell 来写入我们的 log,然后用 return 来当作 do 的结果。当然我们也可以这样写:
Writer (a, ["Finished with " ++ show a])
但我想 do 的表达方式是比较容易阅读的。接下来我们看看当 b 不等于 0 的时候。我们会把 mod 的使用情况写进 log。然后在 do 当中的第二行递归调用 gcd'gcd' 现在是回传一个 Writer 的型态,所以 gcd' b (a `mod` b) 这样的写法是完全没问题的。
尽管去 trace 这个 gcd' 对于理解十分有帮助,但我想了解整个大概念,把值视为具有 context 是更加有用的。
接着来试试跑我们的 gcd',他的结果会是 Writer [String] Int,如果我们把他从 newtype 中取出来,我们会拿到一个 tuple。tuple 的第一个部份就是我们要的结果:
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
把普通的算法转换成具有 log 是很棒的经验,我们不过是把普通的 value 重写成 Monadic value,剩下的就靠 >>=Writer 来帮我们处理一切。用这样的方法我们几乎可以对任何函数加上 logging 的功能。我们只要把普通的值换成 Writer,然后把一般的函数调用换成 >>= (当然也可以用 do)

Inefficient list construction

当制作 Writer Monad 的时候,要特别注意你是使用哪种 monoid。使用 list 的话性能有时候是没办法接受的。因为 list 是使用 ++ 来作为 mappend 的实现。而 ++ 在 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。这非常没有效率,因为每次都是把右边的部份加到左边的部份,而左边的部份又必须要从头开始建起。
下面这个函数跟 gcd' 差不多,只是 log 的顺序是相反的。他先纪录剩下的操作,然后纪录现在的步骤。
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
他先递归调用,然后把结果绑定到 result。然后把目前的动作写到 log,在递归的结果之后。最后呈现的就是完整的 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。

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 就像这样
f `append` g = \xs -> f (g xs)
fg 这边是两个函数,他们都接受一个 list 并 prepend 另一串 list。举例来说,如果 f 代表 ("dog"++)(可以写成 \xs -> "dog" ++ xs)而 g("meat"++),那 f `append` g 就会做成一个新的函数,等价于:
\xs -> "dog" ++ ("meat" ++ xs)
append 两个 difference list 其实就是用一个函数,这函数先喂一个 list 给第一个 difference list,然后再把结果喂给第二个 difference list。
我们可以用一个 newtype 来包起来
newtype DiffList a = DiffList { getDiffList :: [a] -> [a] }
我们包起来的型态是 [a] -> [a],因为 difference list 不过就是一个转换一个 list 到另一个 list 的函数。要把普通 list 转换成 difference list 也很容易。
toDiffList :: [a] -> DiffList a
toDiffList xs = DiffList (xs++)
fromDiffList :: DiffList a -> [a]
fromDiffList (DiffList f) = f []
要把一个普通 list 转成 difference list 不过就是照之前定义的,作一个 prepend 另一个 list 的函数。由于 difference list 只是一个 prepend 另一串 list 的一个函数,假如我们要转回来的话,只要喂给他空的 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]
现在我们可以用 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 的型态从 [String] 改成 DiffList String,并在使用 tell 的时候把普通的 list 用 toDiffList 转成 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 的结果,然后用 snd 取出 log,并用 fromDiffList 转回普通的 list 印出来。

Comparing Performance

要体会 Difference List 能如何增进效率,考虑一个从某数数到零的 case。我们纪录的时候就像 gcdReverse 一样是反过来记的,所以在 log 中实际上是从零数到某个数。
finalCountDown :: Int -> Writer (DiffList String) ()
finalCountDown 0 = do
tell (toDiffList ["0"])
finalCountDown x = do
finalCountDown (x-1)
tell (toDiffList [show x])
如果我们喂 0,他就只 log 0。如果喂其他正整数,他会先倒数到 0 然后 append 那些数到 log 中,所以如果我们调用 finalCountDown 并喂给他 100,那 log 的最后一笔就会是 "100"
如果你把这个函数 load 进 GHCi 中并喂给他一个比较大的整数 500000,你会看到他无停滞地从 0 开始数起:
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
我们会看到整个运算卡卡的。
当然这不是一个严谨的测试方法,但足以表显出 difference list 是比较有效率的写法。

Reader Monad

在讲 Applicative 的章节中,我们说过了 (->) r 的型态只是 Functor 的一个 instance。要将一个函数 f map over 一个函数 g,基本上等价于一个函数,他可以接受原本 g 接受的参数,先套用 g 然后再把其结果丢给 f
ghci> let f = (*5)
ghci> let g = (+3)
ghci> (fmap f g) 8
我们已经见识过函数当作 applicative functors 的例子。这样能让我们对函数的结果直接进行操作。
ghci> let f = (+) <$> (*2) <*> (+10)
ghci> f 3
19
(+) <$> (*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 里面找到,他看起来像这样:
instance Monad ((->) r) where
return x = \_ -> x
h >>= f = \w -> f (h w) w
我们之前已经看过函数的 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。
import Control.Monad.Instances
addStuff :: Int -> Int
addStuff = do
a <- (*2)
b <- (+10)
return (a+b)
这跟我们之前写的 applicative expression 差不多,只差在他是运作在 monad 上。一个 do expression 的结果永远会是一个 monadic vlaue,这个也不例外。而这个 monadic value 其实是一个函数。只是在这边他接受一个数字,然后套用 (*2),把结果绑定到 a 上面。而 (+10) 也同用被套用到同样的参数。结果被绑定到 b 上。return 就如其他 monad 一样,只是制作一个简单的 monadic value 而不会作多余的事情。这让整个函数的结果是 a+b。如果我们试着跑跑看,会得到之前的结果。
ghci> addStuff 3
19
其中 3 会被喂给 (*2)(+10)。而且他也会被喂给 return (a+b),只是他会忽略掉 3 而永远回传 a+b 正因为如此,function monad 也被称作 reader monad。所有函数都从一个固定的地方读取。要写得更清楚一些,可以把 addStuff 改写如下:
addStuff :: Int -> Int
addStuff x = let
a = (*2) x
b = (+10) x
in a+b
我们见识了把函数视作具有 context 的值很自然的可以表达成 reader monad。只要我们当作我们知道函数会回传什么值就好。他作的就是把所有的函数都黏在一起做成一个大的函数,然后把这个函数的参数都喂给全部组成的函数,这有点取出他们未来的值的意味。实作做完了然后 >>= 就会保证一切都能正常运作。

State Monad

Haskell 是一个纯粹的语言,正因为如此,我们的程序是有一堆没办法改变全域状态或变量的函数所组成,他们只会作些处理并回传结果。这样的性质让我们很容易思考我们的程序在干嘛,因为我们不需要担心变量在某一个时间点的值是什么。然而,有一些领域的问题根本上就是依赖于随着时间而改变的状态。虽然我们也可以用 Haskell 写出这样的程序,但有时候写起来蛮痛苦的。这也是为什么 Haskell 要加进 State Monad 这个特性。这让我们在 Haskell 中可以容易地处理状态性的问题,并让其他部份的程序还是保持纯粹性。
当我们处理乱数的时候,我们的函数接受一个 random generator 并回传一个新的乱数跟一个新的 random generator。如果我们需要很多个乱数,我们可以用前一个函数回传的 random generator 继续做下去。当我们要写一个接受 StdGen 的函数并产生丢三个硬币结果的函数,我们会这样写:
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 产生一个 Bool 型态的值以及新的 generator。要仿真丢第二个硬币的话,便使用新的 generator。在其他语言中,多半除了乱数之外不需要多回传一个 generator。那是因为我们可以对现有的进行修改。但 Haskell 是纯粹的语言,我们没办法那么做,所以我们必须要接受一个状态,产生结果然后回传一个新的状态,然后用新的状态来继续做下去。
一般来讲你应该不会喜欢这么写,在程序中有赤裸裸的状态,但我们又不想放弃 Haskell 的纯粹性质。这就是 State Monad 的好处了,他可以帮我们处理这些琐碎的事情,又让我们保持 Haskell 的纯粹性。
为了深入理解状态性的计算,我们先来看看应该给他们什么样的型态。我们会说一个状态性的计算是一个函数,他接受一个状态,回传一个值跟一个新的状态。写起来会像这样:
s -> (a,s)
s 是状态的型态,而 a 是计算结果的型态。
在其他的语言中,赋值大多是被当作会改变状态的操作。举例来说,当我们在命令式语言写 ``x = 5``,这通常代表的是把 ``5`` 指定给 ``x`` 这变量。而且这边 ``5`` 是一个 expression。
如果你用函数语言的角度去思考,你可以把他想做是一个函数,接受一个状态,并回传结果跟新的状态。那新的状态代表所有已指定的值与新加入的变量。
这种改变状态的计算,除了想做是一个接受状态并回传结果跟新状态的函数外,也可以想做是具有 context 的值。 实际的值是结果。然而要得到结果,我们必须要给一个初始的状态,才能得到结果跟最后的状态。

Stack and Stones

考虑现在我们要对一个堆叠的操作建立模型。你可以把东西推上堆叠顶端,或是把东西从顶端拿下来。如果你要的元素是在堆叠的底层的话,你必须要把他上面的东西都拿下来才能拿到他。
我们用一个 list 来代表我们的堆叠。而我们把 list 的头当作堆叠的顶端。为了正确的建立模型,我们要写两个函数:poppushpop 会接受一个堆叠,取下一个元素并回传一个新的堆叠,这个新的堆叠不包含取下的元素。push 会接受一个元素,把他堆到堆叠中,并回传一个新的堆叠,其包含这个新的元素。
type Stack = [Int]
pop :: Stack -> (Int,Stack)
pop (x:xs) = (x,xs)
push :: Int -> Stack -> ((),Stack)
push a xs = ((),a:xs)
我们用 () 来当作 pushing 的结果,毕竟推上堆叠并不需要什么回传值,他的重点是在改变堆叠。注意到 pushpop 都是改变状态的计算,可以从他们的型态看出来。
我们来写一段程序来仿真一个堆叠的操作。我们接受一个堆叠,把 3 推上去,然后取出两个元素。
stackManip :: Stack -> (Int, Stack)
stackManip stack = let
((),newStack1) = push 3 stack
(a ,newStack2) = pop newStack1
in pop newStack2
我们拿一个 stack 来作 push 3 stack 的动作,其结果是一个 tuple。tuple 的第一个部份是 (),而第二个部份是新的堆叠,我们把他命名成 newStack1。然后我们从 newStack1 上 pop 出一个数字。其结果是我们之前 push 上去的一个数字 a,然后把这个更新的堆叠叫做 newStack2。然后我们从 newStack2 上再 pop 出一个数字 b,并得到 newStack3。我们回传一个 tuple 跟最终的堆叠。
ghci> stackManip [5,8,2,1]
(5,[8,2,1])
结果就是 5 跟新的堆叠 [8,2,1]。注意到 stackManip 是一个会改变状态的操作。我们把一堆会改变状态的操作绑在一起操作,有没有觉得很耳熟的感觉。
stackManip 的程序有点冗长,因为我们要写得太详细,必须把状态给每个操作,然后把新的状态再喂给下一个。如果我们可以不要这样作的话,那程序应该会长得像这样:
stackManip = do
push 3
a <- pop
pop
这就是 State Monad 在做的事。有了他,我们便可以免除于要把状态操作写得太明白的窘境。

The State Monad

Control.Monad.State 这个模块提供了一个 newtype 包起来的型态。
newtype State s a = State { runState :: s -> (a,s) }
一个 State s a 代表的是一个改变状态的操作,他操纵的状态为型态 s,而产生的结果是 a
我们已经见识过什么是改变状态的操作,以及他们是可以被看成具有 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 要作的事是接受一个值,并做出一个改变状态的操作,让他永远回传那个值。所以我们才做了一个 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
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 已经满足我们的条件,而 push 要先接受一个 Int 才会回传我们要的操作。所以我们可以改写先前的范例如下:
import Control.Monad.State
stackManip :: State Stack Int
stackManip = do
push 3
a <- pop
pop
看到我们是怎么把一个 push 跟两个 pop 黏成一个操作吗?当我们将他们从一个 newtype 取出,其实就是需要一个能喂进初始状态的函数:
ghci> runState stackManip [5,8,2,1]
(5,[8,2,1])
我们不须绑定第二个 pop,因为我们根本不会用到 a,所以可以写成下面的样子:
stackManip :: State Stack Int
stackManip = do
push 3
pop
pop
再来尝试另外一种方式,先从堆叠上取下一个数字,看看他是不是 5,如果是的话就把他放回堆叠上,如果不是的话就堆上 38
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 的结果会是一个 monadic value,而在 State monad 的 case,do 也就是一个改变状态的函数。而由于 stackManipstackStuff 都是改变状态的计算,因此我们可以把他们黏在一起:
moreStack :: State Stack ()
moreStack = do
a <- stackManip
if a == 100
then stackStuff
else return ()
如果 stackManip 的结果是 100,我们就会跑 stackStuff,如果不是的话就什么都不做。return () 不过就是什么是都不做,全部保持原样。
Contorl.Monad.State 提供了一个 MonadState 的 typeclass,他有两个有用的函数,分别是 getput。对于 State 来说,get 的实作就像这样: