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

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

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

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

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")  

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")  

### Monoids 的好处

请确定你了解什么是 Monoids。

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

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 m) => (a,m) -> (a -> (b,m)) -> (b,m)
applyLog (x,log) f = let (y,newLog) = f x in (y,log mappend newLog)  

import Data.Monoid

type Food = String
type Price = Sum Int

addDrink "beans" = ("milk", Sum 25)
addDrink "jerky" = ("whiskey", Sum 99)
addDrink _ = ("beer", Sum 30)  

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})  

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

### The Writer type

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

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')  

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})  

### Using do notation with 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"])  

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"])  

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

ghci> gcd' 8 3
1  

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)  

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

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  

### Comparing Performance

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

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  

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

ghci> let f = (+) <$> (*2) <*> (+10) ghci> f 3 19 (+) <$> (*2) <*> (+10) 代表一个函数，他接受一个数值，分别把这数值交给 (*2)(+10)。然后把结果加起来。例如说，如果我们喂 3 给这个函数，他会分别对 3(*2)(+10) 的动作。而得到 613。然后呼叫 (+)，而得到 19

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

>>= 的实作看起来有点难以理解，我们可以仔细来看看。当我们使用 >>= 的时候，喂进去的是一个 monadic value，处理他的是一个函数，而吐出来的也是一个 monadic value。在这个情况下，当我们将一个函数喂进一个函数，吐出来的也是一个函数。这就是为什么我们在最外层使用了一个 lambda。在我们目前看过的实作中，>>= 几乎都是用 lambda 将内部跟外部隔开来，然后在内部来使用 f。这边也是一样的道理。要从一个函数得到一个结果，我们必须喂给他一些东西，这也是为什么我们先用 (h w) 取得结果，然后将他丢给 f。而 f 回传一个 monadic value，在这边这个 monadic value 也就是一个函数。我们再把 w 喂给他。

import Control.Monad.Instances

a <- (*2)
b <- (+10)
return (a+b)  

ghci> addStuff 3
19  

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

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

s -> (a,s) 

s 是状态的型态，而 a 是计算结果的型态。

在其他的语言中，赋值大多是被当作会改变状态的操作。举例来说，当我们在命令式语言写 x = 5，这通常代表的是把 5 指定给 x 这变数。而且这边 5 是一个 expression。

### Stack and Stones

type Stack = [Int]

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

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

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

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

stackManip 的程式有点冗长，因为我们要写得太详细，必须把状态给每个操作，然后把新的状态再喂给下一个。如果我们可以不要这样作的话，那程式应该会长得像这样：

stackManip = do
push 3
a <- pop
pop  

Control.Monad.State 这个模组提供了一个 newtype 包起来的型态。

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

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  

>>= 的实作呢？很明显的把改变状态的操作喂进 >>= 也必须要丢出另一个改变状态的操作。所以我们用 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，里面包含了最后的结果跟最终的状态。

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  

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

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

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]) 

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

Contorl.Monad.State 提供了一个 MonadState 的 typeclass，他有两个有用的函数，分别是 getput。对于 State 来说，get 的实作就像这样：

get = State $\s -> (s,s) 他只是取出现在的状态除此之外什么也不做。而 put 函数会接受一个状态并取代掉现有的状态。 put newState = State$ \s -> ((),newState)  

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

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

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

Maybe 不变是有道理的，但如果用 >>= 来把两种不同的 monad 接起来是没道理的。但对于 state monad 而言，monad 其实是 State s，所以如果 s 不一样，我们就要用 >>= 来把两个 monad 接起来。

System.Random 中的 random 函数有下列的型态：

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

import System.Random

randomSt :: (RandomGen g, Random a) => State g a
randomSt = State random  

import System.Random

threeCoins :: State StdGen (Bool,Bool,Bool)
threeCoins = do
a <- randomSt
b <- randomSt
c <- randomSt
return (a,b,c)  

threeCoins 是一个改变状态的计算，他接受一个初始的乱数产生器，他会把他喂给 randomSt，他会产生一个数字跟一个新的产生器，然后会一直传递下去。我们用 return (a,b,c) 来呈现 (a,b,c)，这样并不会改变最近一个产生器的状态。

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

Either e a 则能让我们可以加入一个可能会发生错误的 context，还可以增加些有用的讯息，这样能让我们知道究竟是什么东西出错了。一个 Either e a 的值可以是代表正确的 Right，或是代表错误的 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  

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 就是建立起一个最小的 context，由于我们用 Right 代表正确的结果，所以他把值包在一个 Right constructor 里面。就像实作 Maybe 时的 return 一样。

>>= 会检查两种可能的情况：也就是 LeftRight。如果进来的是 Right，那我们就呼叫 f，就像我们在写 Just 的时候一样，只是呼叫对应的函数。而在错误的情况下，Left 会被传出来，而且里面保有描述失败的值。

Either eMonad instance 有一项额外的要求，就是包在 Left 中的型态，也就是 e，必须是 Error typeclass 的 instance。Error 这个 typeclass 描述一个可以被当作错误讯息的型态。他定义了 strMsg 这个函数，他接受一个用字串表达的错误。一个明显的范例就是 String 型态，当他是 String 的时候，strMsg 只不过回传他接受到的字串。

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

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

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 选择什么样的型态，尽管我们是要印出 Right 的值。这是因为 Error e 被限制成 Monad。把 Either 当作 Monad 使用就会碰到这样的错误，你只要明确写出 type signature 就行了：

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

## 一些实用的 Moandic functions

### liftM

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

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

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]) 

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

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

Applicative 让我们可以操作具有 context 的值就像操作一般的值一样。 就像这样：

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

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

mf 是一个 monadic value，他的结果是一个函数。由于函数跟值都是放在 context 中，假设我们从 context 取出的函数叫 f，从 context 取出的值叫 x，我们把 x 喂给 f 然后再把结果放回 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]  

liftA2 是一个方便的函数，他可以把两个 applicative 的值喂给一个函数。他的定义很简单：

liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c
liftA2 f x y = f <$> x <*> y  liftM2 也是做差不多的事情，只是多了 Monad 的限制。在函式库中其实也有 liftM3liftM4liftM5 我们看到了 monad 相较于 applicative 跟 functor 有比较强的性质。尽管 moand 有 functor 跟 applicative functor 的性质，但他们不见得有 FunctorApplicative 的 instance 定义。所以我们检视了一些在 monad 中定义，且等价于 functor 或 applicative functor 所具有的函数。 ### The join function 如果一个 monadic value 的结果是另一个 monadic value，也就是其中一个 monadic value 被包在另一个里面，你能够把他们变成一个普通的 monadic value 吗？就好像把他们打平一样。譬如说，我们有 Just (Just 9)，我们能够把他变成 Just 9 吗？事实上是可以的，这也是 monad 的一个性质。也就是我要看的 join 函数，他的型态是这样： join :: (Monad m) => m (m a) -> m a  他接受一个包在另一个 monadic value 中的 monadic value，然后会回给我们一个普通的 monadic value。这边有一些 Maybe 的范例： ghci> join (Just (Just 9)) Just 9 ghci> join (Just Nothing) Nothing ghci> join Nothing Nothing  第一行是一个计算成功的结果包在另一个计算成功的结果，他们应该要能结合成为一个比较大的计算成功的结果。第二行则是一个 Nothing 包在一个 Just 中。我们之前在处理 Maybe 型态的值时，会用 <*>>>= 把他们结合起来。输入必须都是 Just 时结果出来才会是 Just。如果中间有任何的失败，结果就会是一个失败的结果。而第三行就是这样，我们尝试把失败的结果接合起来，结果也会是一个失败。 join 一个 list 也是很简单： ghci> join [[1,2,3],[4,5,6]] [1,2,3,4,5,6]  你可以看到，对于 list 而言 join 不过就是 concat。 而要 join 一个包在 Writer 中的 Writer， 我们必须用 mappend ghci> runWriter$ join (Writer (Writer (1,"aaa"),"bbb"))
(1,"bbbaaa")  

"bbb" 先被加到 monoid 中，接着 "aaa" 被附加上去。你想要检视 Writer 中的值的话，必须先把值写进去才行。

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"  

ghci> runState (join (State $\s -> (push 10,1:2:s))) [0,0,0] ((),[10,1,2,0,0,0])  这边的 lambda 函数接受一个状态，并把 21 放到堆叠中，并把 push 10 当作他的结果。当对整个东西做 join 的时候，他会先把 21 放到堆叠上，然后进行 push 10 的计算，因而把 10 放到堆叠的顶端。 join 的实作像是这样： join :: (Monad m) => m (m a) -> m a join mm = do m <- mm m  因为 mm 的结果会是一个 monadic value，我们单独用 m <- mm 拿取他的结果。这也可以说明 Maybe 只有当外层跟内层的值都是 Just 的时候才会是 Just。如果把 mm 的值设成 Just (Just 8) 的话，他看起来会是这样： joinedMaybes :: Maybe Int joinedMaybes = do m <- Just (Just 8) m  最有趣的是对于一个 monadic value 而言，用 >>= 把他喂进一个函数其实等价于对 monad 做 mapping over 的动作，然后用 join 来把值从 nested 的状态变成扁平的状态。也就是说 m >>= f 其实就是 join (fmap f m)。如果你仔细想想的话其实很明显。>>= 的使用方式是，把一个 monadic value 喂进一个接受普通值的函数，但他却会回传 monadic value。如果我们 map over 一个 monadic value，我们会做成一个 monadic value 包了另外一个 monadic value。例如说，我们现在手上有 Just 9\x -> Just (x+1)。如果我们把这个函数 map over Just 9，我们会得到 Just (Just 10) 事实上 m >>= f 永远等价于 join (fmap f m) 这性质非常有用。如果我们要定义自己的 Monad instance，要知道怎么把 nested monadic value 变成扁平比起要定义 >>= 是比较容易的一件事。 ### filterM filter 函数是 Haskell 中不可或缺的要素。他接受一个断言(predicate)跟一个 list 来过滤掉断言为否的部份并回传一个新的 list。他的型态是这样： filter :: (a -> Bool) -> [a] -> [a]  predicate 能接 list 中的一个元素并回传一个 Bool 型态的值。但如果 Bool 型态其实是一个 monadic value 呢？也就是他有一个 context。例如说除了 TrueFalse 之外还伴随一个 monoid，像是 ["Accepted the number 5"]，或 ["3 is too small"]。照前面所学的听起来是没问题，而且产出的 list 也会跟随 context，在这个例子中就是 log。所以如果 Bool 会回传伴随 context 的布林值，我们会认为最终的结果也会具有 context。要不然这些 context 都会在处理过程中遗失。 Control.Monad 中的 filterM 函数正是我们所需要的，他的型态如下： filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]  predicate 会回传一个 monadic value，他的结果会是 Bool 型态，由于他是 monadic value，他的 context 有可能会是任何 context，譬如说可能的失败，non-determinism，甚至其他的 context。一旦我们能保证 context 也会被保存在最后的结果中，结果也就是一个 monadic value。 我们来写一个接受 list 然后过滤掉小于 4 的函数。先尝试使用 filter 函数： ghci> filter (\x -> x < 4) [9,1,5,2,10,3] [1,2,3]  很简单吧。接着我们在做个 predicate，除了表达 TrueFalse 之外，还提供了一个 log。我们会用 Writer monad 来表达这件事： 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  这个函数会回传 Writer [String] Bool 而不是一个单纯的 Bool。他是一个 monadic predicate。如果扫到的数字小于 4 的话，我们就会回报要保存他，而且回传 return True 接着，我们把他跟一个 list 喂给 filterM。由于 predicate 会回传 Writer，所以结果仍会是一个 Writer 值。 ghci> fst$ runWriter $filterM keepSmall [9,1,5,2,10,3] [1,2,3]  要检查 Writer 的结果，我们想要印出 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  

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

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

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

### foldM

foldl 的 monadic 的版本叫做 foldM。如果你还有印象的话，foldl 会接受一个 binary 函数，一个起始累加值跟一串 list，他会从左边开始用 binary 函数每次带进一个值来 fold。foldM 也是做同样的事，只是他接受的这个 binary 函数会产生 monadic value。不意外的，他的结果也会是 monadic value。foldl 的型态是：

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

foldM 的型态则是：

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

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

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

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

### Making a safe RPN calculator

import Data.List

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

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  

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

reads 函数就像 read 一样，差别在于他回传一个 list。在成功读取的情况下 list 中只包含读取的那个元素。如果他失败了，他会回传一个空的 list。除了回传读取的元素，他也回传剩下读取失败的元素。他必须要看完整串输入，我们想把他弄成一个 readMaybe 的函数，好方便我们进行。

readMaybe :: (Read a) => String -> Maybe a
_ -> Nothing  

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

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)  

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  

import Data.List

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

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  

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  

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

f 接受一个数字，然后会帮他加 1，乘以 100，再加 1。我们也可以将 monadic 函数用同样的方式做合成，只是不用 . 而用 <=<，不用 id 而用 return。我们不需要 foldM，由于 <=< 只用 foldr 就足够了。

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

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

import Data.List

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

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

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

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

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

import Data.Ratio

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

instance Functor Prob where
fmap f (Prob xs) = Prob $map (\(x,p) -> (f x,p)) xs  我们可以用 pattern matching 的方式把 newtype 解开来，套用函数 f 之后再包回去。过程中不会动到机率值。 ghci> fmap negate (Prob [(3,1%2),(5,1%4),(9,1%4)]) Prob {getProb = [(-3,1 % 2),(-5,1 % 4),(-9,1 % 4)]}  要注意机率的和永远是 1。如果我们没有漏掉某种情形的话，没有道理他们加起来的值不为 1。一个有 75% 机率是正面以及 50% 机率是反面的硬币根本没什么道理。 接着要问一个重要的问题，他是一个 monad 吗？我们知道 list 是一个 monad，所以他很有可能也是一个 monad。首先来想想 return。他在 list 是怎么运作的？他接受一个普通的值并把他放到一个 list 中变成只有一个元素的 list。那在这边又如何？由于他是一个最小的 context，他也应该是一个元素的 list。那机率值呢？return x 的值永远都是 x，所以机率值不应该是 0，而应该是 1 至于 >>= 呢？看起来有点复杂，所以我们换种方式来思考，我们知道 m >>= f 会等价于 join (fmap f m)，所以我们来想要怎么把一串包含 probability list 的 list 弄平。举个例子，考虑一个 list，'a''b' 恰出现其中一个的机率为 25%，两个出现的机率相等。而 'c''d' 恰出现其中一个的机率为 75%，两个出现的机率也是相等。这边有一个图将情形画出来。 每个字母发生的机率有多高呢？如果我们用四个盒子来代表每个字母，那每个盒子的机率为何？每个盒子的机率是他们所装有的机率值相乘的结果。'a' 的机率是八分之一，'b' 同样也是八分之一。八分之一是因为我们把二分之一跟四分之一相乘得到的结果。而 'c' 发生的机率是八分之三，是因为二分之一乘上四分之三。'd' 同样也是八分之三。如果把所有的机率加起来，就会得到一，符合机率的规则。 来看看怎么用一个 list 表达我们要说明的东西： thisSituation :: Prob (Prob Char) thisSituation = Prob [( Prob [('a',1%2),('b',1%2)] , 1%4 ) ,( Prob [('c',1%2),('d',1%2)] , 3%4 ) ] 注意到这边的型态是 Prob (Prob Char)。所以我们要思考的是如何把一串包含机率 list 的 list 打平。如果能成功写出这样的逻辑，>>= 不过就是 join (fmap f m)，我们便得到了一个 monad。我们这边写了一个 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 接受一个 tuple，里面包含一个 probability list 跟一个伴随的机率值 p，所以我们要作的事是把 list 里面的机率值都乘以 p，并回传一个新的 tuple 包含新的 list 跟新的机率值。我们将 multAll map over 到我们的 probability list 上，我们就成功地打平了我们的 list。

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

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

coin :: Prob Coin

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

import Data.List (all)

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

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)]