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 :: Food -> (Food,Price)  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"])

Adding logging to programs

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

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 319 (+) <$> (*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  addStuff :: Int -> Int  addStuff = do    a <- (*2)    b <- (+10)    return (a+b)

ghci> addStuff 3  19

addStuff :: Int -> Int  addStuff x = let      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  import Control.Monad.State  randomSt :: (RandomGen g, Random a) => State g a  randomSt = State random

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 是一個改變狀態的計算，他接受一個初始的亂數產生器，他會把他餵給 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

<$> 不過就是 fmap，而 <*> 只是一個具有下列型態的函數： (<*>) :: (Applicative f) => f (a -> b) -> f a -> f b 他有點像 fmap，只是函數本身有一個 context。我們必須把他從 context 中抽出，對 f a 做 map over 的東做，然後再放回 context 中。由於在 Haskel 中函數預設都是 curried，我們便能用 <$> 以及 <*> 來讓接受多個參數的函數也能接受 applicative 種類的值。

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

binary 函數的回傳值是 monadic，所以結果也會是 monadic。我們來試著把 list 的值用 fold 全部加起來：

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  readMaybe st = case reads st of [(x,"")] -> Just x                                  _ -> 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.Rationewtype 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  coin = Prob [(Heads,1%2),(Tails,1%2)]  loadedCoin :: Prob Coin  loadedCoin = Prob [(Heads,1%10),(Tails,9%10)]

import Data.List (all)  flipThree :: Prob Bool  flipThree = do    a <- coin    b <- coin    c <- loadedCoin    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)]