第十四章：Monads

回顧之前代碼?

-- file: ch10/PNM.hs
matchHeader :: L.ByteString -> L.ByteString -> Maybe L.ByteString

-- "nat" here is short for "natural number"
getNat :: L.ByteString -> Maybe (Int, L.ByteString)

getBytes :: Int -> L.ByteString
         -> Maybe (L.ByteString, L.ByteString)

    parseP5 s =
      case matchHeader (L8.pack "P5") s of
        Nothing -> Nothing
        Just s1 ->
          case getNat s1 of
            Nothing -> Nothing
            Just (width, s2) ->
              case getNat (L8.dropWhile isSpace s2) of
                Nothing -> Nothing
                Just (height, s3) ->
                  case getNat (L8.dropWhile isSpace s3) of
                    Nothing -> Nothing
                    Just (maxGrey, s4)
                      | maxGrey > 255 -> Nothing
                      | otherwise ->
                          case getBytes 1 s4 of
                            Nothing -> Nothing
                            Just (_, s5) ->
                              case getBytes (width * height) s5 of
                                Nothing -> Nothing
                                Just (bitmap, s6) ->
                                  Just (Greymap width height maxGrey bitmap, s6)

-- file: ch10/PNM.hs
(>>?) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>? _ = Nothing
Just v  >>? f = f v

-- file: ch10/PNM.hs
parseP5_take2 :: L.ByteString -> Maybe (Greymap, L.ByteString)
parseP5_take2 s =
    matchHeader (L8.pack "P5") s       >>?
    \s -> skipSpace ((), s)           >>?
    (getNat . snd)                    >>?
    skipSpace                         >>?
    \(width, s) ->   getNat s         >>?
    skipSpace                         >>?
    \(height, s) ->  getNat s         >>?
    \(maxGrey, s) -> getBytes 1 s     >>?
    (getBytes (width * height) . snd) >>?
    \(bitmap, s) -> Just (Greymap width height maxGrey bitmap, s)

skipSpace :: (a, L.ByteString) -> Maybe (a, L.ByteString)
skipSpace (a, s) = Just (a, L8.dropWhile isSpace s)

-- file: ch10/Parse.hs
(==>) :: Parse a -> (a -> Parse b) -> Parse b

firstParser ==> secondParser  =  Parse chainedParser
  where chainedParser initState   =
          case runParse firstParser initState of
            Left errMessage ->
                Left errMessage
            Right (firstResult, newState) ->
                runParse (secondParser firstResult) newState

尋找共同特征?

如果我們仔細分析上面的例子，它們好像沒有什么共同特點。不過有一點比較明顯，它們都想把函數(shù)串聯(lián)起來并試圖隱藏細節(jié)以便我們寫出整潔的代碼。然后，我們先不管那些細節(jié)，從更粗略的層面去思考一下。

首先，我們看一看類型聲明：

-- file: ch14/Maybe.hs
data Maybe a = Nothing
             | Just a

-- file: ch11/Parse.hs
newtype Parse a = Parse {
      runParse :: ParseState -> Either String (a, ParseState)
    }

這兩個類型的共同特點是它們都有一個類型參數(shù)，因此它們都是范型，對具體的類型一無所知。

然后看一看我們給兩個類型寫的串聯(lián)函數(shù)：

ghci> :type (>>?)
(>>?) :: Maybe a -> (a -> Maybe b) -> Maybe b

ghci> :type (==>)
(==>) :: Parse a -> (a -> Parse b) -> Parse b

這兩個函數(shù)的類型非常相似，如果我們把它們的類型構造器替換為一個類型變量，我們會得到一個更加抽象的類型。

-- file: ch14/Maybe.hs
chain :: m a -> (a -> m b) -> m b

最終，在兩種情況下，我們都得到了一個獲取一個普通的值，然后把它“注入”到一個目標類型里面去的函數(shù)。對于 Maybe 類型，這個函數(shù)就是它的一個值構造器 Just ，``Parse``的注入函數(shù)就略微復雜一些。

-- file: ch10/Parse.hs
identity :: a -> Parse a
identity a = Parse (\s -> Right (a, s))

我們不用關心它的實現(xiàn)細節(jié)，也不管它有多么復雜；重要的是，這些類型都有一個“注入器”函數(shù)，它大致長這樣：

-- file: ch14/Maybe.hs
inject :: a -> m a

在Haskell里面，正是這三個屬性和一些如何使用它們的規(guī)則定義了monad。我們集中總結一下：

1. 一個類型構造器 m
2. 一個用于把某個函數(shù)的輸出串聯(lián)到另外一個函數(shù)輸入上的函數(shù)，它的類型是 m a -> (a -> m b) -> m b
3. 一個類型是 a -> m a 類型的函數(shù)，它把普通值注入到調用鏈里面，也就是說，它把類型 a 用類型構造器 m 包裝起來。

Maybe 類型的類型構造器 Maybe a ,串聯(lián)函數(shù) (>>?) 以及注入函數(shù) Just 使Maybe成為一個monad。對于 Parse 類型，對應的是類型構造器 Parse a ,串聯(lián)函數(shù) Parse a 以及注入函數(shù) identify 。

對于Monad的串聯(lián)函數(shù)和注入函數(shù)具體應該干什么我們刻意只字未提，因為它幾乎不重要。事實上，正是因為Monad如此簡單，它在Haskell里面無處不在。許多常見的編程模式都用到了monad結構：傳遞隱式數(shù)據(jù)，或是短路求值鏈。

Monad 類型類?

在Haskell里面我們可以使用一個類型類(typeclass)來表示“串聯(lián)”以及“注入”的概念以及它們的類型。標準庫的Predule模塊已經(jīng)包含了這樣一個類型類，也就是 Monad 。

-- file: ch14/Maybe.hs
class Monad m where
    -- chain
    (>>=)  :: m a -> (a -> m b) -> m b
    -- inject
    return :: a -> m a

在這里，(>>=) 就是我們的串聯(lián)函數(shù)。 在 串聯(lián)化（Sequencing） 中我們已經(jīng)介紹了它。通常將這個操作符稱呼為“綁定”，因為它把左側運算的結果綁定到右側運算的參數(shù)上。

我們的注入函數(shù)是 return ,在 Return的本色 中講過，選用 return 這個名字有點倒霉。這個關鍵字在命令式語言中被廣泛使用并且有一個非常容易理解的含義。但是在Haskell里面它的含義完全不同；具體來說，在函數(shù)調用鏈中間使用 return 并不會導致調用鏈提前中止；我們可以這樣理解它：它把純值( a 類型)放進(returns)monads( m a 類型)里。

(>>=) 和 return 是 Monad 這個類型類的核心函數(shù)；除此之外，它還定義了另外兩個函數(shù)。一個函數(shù)是 (>>) ，類似于 (>>=) ，它的作用也是串聯(lián)，但是它忽略左側的值。

-- file: ch14/Maybe.hs
    (>>) :: m a -> m b -> m b
        a >> f = a >>= \_ -> f

當我們需要按順序執(zhí)行一系列操作的，并且不關心先前的計算結果的時候，可以使用這操作符。這樣也許看起來讓人覺得費解：為什么我們會忽略一個函數(shù)的返回值呢，這樣有什么意義？回想一下，我們之前定義了一個 (==>&) 組合子來專門表達這個概念。另外，考慮一下 print 這樣的函數(shù)，它的返回結果是一個占位符，我們沒有必要關心它返回值是什么。

ghci> :type print "foo"
print "foo" :: IO ()

如果我們使用普通的 (>>=) 來串聯(lián)調用，我們必須提供一個新的函數(shù)來忽略參數(shù)（這個參數(shù)是前一個 print 的返回值。)

ghci> print "foo" >>= \_ -> print "bar"
"foo"
"bar"

但是，如果我們使用 (>>) 操作符，那么就可以去掉那個沒什么用的函數(shù)了：

ghci> print "baz" >> print "quux"
"baz"
"quux"

正如我們上面看到的一樣， (>>) 的默認實現(xiàn)是通過 (>>=) 完成的。

Monad類型類另外一個非核心函數(shù)是 fail ,這個函數(shù)接受一個錯誤消息然后讓函數(shù)調用鏈失敗。

回顧一下我們在 第 10 章：代碼案例學習：解析二進制數(shù)據(jù)格式 寫的parse, 里面有一個 Monad 的實例：

-- file: ch10/Parse.hs
instance Monad Parse where
    return = identity
    (>>=) = (==>)
    fail = bail

術語解釋?

可能你對monad的某些慣用語并不熟悉，雖然他們不是正式術語，但是很常見；因此有必要了解一下。

• “Monadic”僅僅表示“和Monad相關的”。一個monadic 類型就是一個Monad 類型類的實例；一個monadic值就是一個具有monadic類型的值。
• 當我們說某個東西“是一個monad”的時候，我們其實表達的意思是“這個類型是Monad這個類型類的實例”；作為Monad的實例就有三要素：類型構造器，注入函數(shù)，串聯(lián)函數(shù)。
• 同樣，當我們談到“Foo這個monad”的時候，我們實際上指的是Foo這個類型，只不過Foo是Monad這個類型類的實例。
• Monadic值的一個別稱是“動作”；這個說法可能源自 I/O Monad 的引入， print "foo" 這樣的monad值會導致副作用。返回類型是monadic值的函數(shù)有時候也被稱之為動作，雖然這樣并不太常見。

使用新的Monad?

我們在介紹Monad的時候，展示了一些之前的代碼，并說明它們其實就是Monad。既然我們慢慢知道m(xù)onad是什么，而且已經(jīng)見識過 Monad 這個類型類；現(xiàn)在就讓我們用學到的知識來寫一個Monad吧。我們先定義它的接口，然后使用它；一旦完成了這些，我們就寫出了自己的Monad！

純粹的Haskell代碼寫起來非常簡潔，但是它不能執(zhí)行IO操作；有時候，我們想記下我們程序的一些操作，但是又不想直接把日志信息寫入文件；就這些需求，我們開發(fā)一個小型庫。

回憶一下我們在 將 glob 模式翻譯為正則表達式 中定義的 globToRegex 函數(shù)；我們修改它讓它能夠記住每次它翻譯過的句子。我們又回到了熟悉的恐怖場景：比較同一份代碼的Monadic版本和非Monadic版。

首先，我們可以使用一個 Logger 類型類把處理結果的類型包裝起來。

-- file: ch14/Logger.hs
globToRegex :: String -> Logger String

-- file: ch14/Logger.hs
module Logger
    (
      Logger
    , Log
    , runLogger
    , record
    ) where

-- file: ch14/Logger.hs
type Log = [String]

-- file: ch14/Logger.hs
runLogger :: Logger a -> (a, Log)

-- file: ch14/Logger.hs
record :: String -> Logger ()

ghci> let simple = return True :: Logger Bool
ghci> runLogger simple
(True,[])

ghci> runLogger (record "hi mom!" >> return 3.1337)
(3.1337,["hi mom!"])

-- file: ch14/Logger.hs
globToRegex cs =
    globToRegex' cs >>= \ds ->
    return ('^':ds)

ghci> :type (>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
ghci> :type (globToRegex "" >>=)
(globToRegex "" >>=) :: (String -> Logger b) -> Logger b

-- file: ch14/Logger.hs
globToRegex' :: String -> Logger String
globToRegex' "" = return "$"

-- file: ch14/Logger.hs
globToRegex' ('?':cs) =
    record "any" >>
    globToRegex' cs >>= \ds ->
    return ('.':ds)

-- file: ch14/Logger.hs
globToRegex' ('*':cs) = do
    record "kleene star"
    ds <- globToRegex' cs
    return (".*" ++ ds)

-- file: ch14/Logger.hs
globToRegex' ('[':'!':c:cs) =
    record "character class, negative" >>
    charClass cs >>= \ds ->
    return ("[^" ++ c : ds)
globToRegex' ('[':c:cs) =
    record "character class" >>
    charClass cs >>= \ds ->
    return ("[" ++ c : ds)
globToRegex' ('[':_) =
    fail "unterminated character class"

同時使用puer和monadic代碼?

迄今為止我們看到的Monad好像有一個非常明顯的缺陷：Monad的類型構造器把一個值包裝成一個monadic的值，這樣導致在monad里面使用普通的純函數(shù)有點困難。舉個例子，假設我們有一段運行在monad里面的代碼，它所做的就是返回一個字符串：

ghci> let m = return "foo" :: Logger String

如果我們想知道字符串的長度是多少，我們不能直接調用 length 函數(shù)：因為這個字符串被 Logger 這個monad包裝起來了，因此類型并不匹配。

ghci> length m

<interactive>:1:7:
    Couldn't match expected type `[a]'
           against inferred type `Logger String'
    In the first argument of `length', namely `m'
    In the expression: length m
    In the definition of `it': it = length m

我們能做的事情就是下面這樣：

ghci> :type   m >>= \s -> return (length s)
m >>= \s -> return (length s) :: Logger Int

我們使用 (>>=) 把字符串從monad里面取出來，然后使用一個匿名函數(shù)調用 length 接著用 return 把這個字符串重新包裝成 Logger 。

由于這種形式的代碼經(jīng)常在Haskell里面出現(xiàn)，因此已經(jīng)有一個類似的操作符存在了。在 Functor 簡介 里面我們介紹了 lifting 這種技術；把一個純函數(shù) Lift 為一個函子通常意味著從一個帶有上下文的特殊值里面取出那個值，然后使用這個普通的值調用純函數(shù)，得到結果之后用特定的類型構造器包裝成原來有著上下文的特殊值。

在monad里面，我們需要干同樣的一件事。由于 Monad 這個類型類已經(jīng)提供了 (>>=) 和 return 這兩個函數(shù)處理monadic的值和普通值之間的轉換，因此 liftM 函數(shù)不需要知道m(xù)onad的任何實現(xiàn)細節(jié)。

-- file: ch14/Logger.hs
liftM :: (Monad m) => (a -> b) -> m a -> m b
liftM f m = m >>= \i ->
            return (f i)

當我們把一個類型聲明為 Functor 這個類型類的實例之后，我們必須根據(jù)這個特定的類型實現(xiàn)對應的 fmap 函數(shù)；但是， 由于 (>>=) 和 return 對monad的進行了抽象，因此``liftM`` 不需要知道任何monad的任何實現(xiàn)細節(jié)。我們只需要實現(xiàn)一次并配上合適的類型簽名即可。

在標準庫的 Control.Monad 模塊里面已經(jīng)為我們定義好了 liftM 函數(shù)。

我們來看看使用 liftM 對于提升我們代碼可讀性有什么作用；先看看沒有使用 liftM 的代碼：

-- file: ch14/Logger.hs
charClass_wordy (']':cs) =
    globToRegex' cs >>= \ds ->
    return (']':ds)
charClass_wordy (c:cs) =
    charClass_wordy cs >>= \ds ->
    return (c:ds)

然后我們用 liftM 去掉那些 (>>=)) 和匿名函數(shù)：

-- file: ch14/Logger.hs
charClass (']':cs) = (']':) `liftM` globToRegex' cs
charClass (c:cs) = (c:) `liftM` charClass cs

正如 fmap 一樣，我們通常用中綴的方式調用 liftM 。可以用這種方式來閱讀這個表達式：把右邊操作得到的monadic的值應用到左邊的純函數(shù)上。

liftM 函數(shù)實在是太有用了，因此 Control.Monad 定義了它的幾個變種，這些變種可以處理更長的參數(shù)；我們可以看一看 globToRegex 這個函數(shù)的最后一個分句：

-- file: ch14/Logger.hs
globToRegex' (c:cs) = liftM2 (++) (escape c) (globToRegex' cs)

escape :: Char -> Logger String
escape c
    | c `elem` regexChars = record "escape" >> return ['\\',c]
    | otherwise           = return [c]
  where regexChars = "\\+()^$.{}]|"

上面這段代碼用到的 liftM2 函數(shù)的定義如下：

-- file: ch14/Logger.hs
liftM2 :: (Monad m) => (a -> b -> c) -> m a -> m b -> m c
liftM2 f m1 m2 =
    m1 >>= \a ->
    m2 >>= \b ->
    return (f a b)

它首先執(zhí)行第一個動作，接著執(zhí)行第二個操作，然后把這兩個操作的結果組合起來應用到那個純函數(shù)上并包裝返回的結果。 Control.Monad 里面定義了 liftM liftM2 直到 liftM5 。

關于Monad的一些誤解?

我們已經(jīng)見識過很多Monad的例子并且對monad也有一些感覺了；在繼續(xù)探討monad之前，有一些廣為流傳的關于monad的觀念需要澄清。你肯定經(jīng)常聽到這些說法，因此你可能已經(jīng)有一些很好的理由來反駁這些謬論了。

• Monads很難理解 我們已經(jīng)從好幾個實例的問題來說明Monad是如何工作的了，并且我們已經(jīng)知道理解monad最好的方式就是先通過一些具體的例子來進行解釋，然后抽象出這些這些例子共同的東西。
• Monads僅僅用于 I/O 操作和命令式代碼 雖然我們在Haskell的IO里面使用Monad，但是Monad在其他的地方也非常有用。我們已經(jīng)通過monad串聯(lián)簡單的計算，隱藏復雜的狀態(tài)以及紀錄日志了；然而，Monad的作用我們還只看到冰山一角。
• 只有Haskell才有Monad Haskell有可能是顯式使用Monad最多的語言，但是在別的語言里面也存在，從C++到OCaml。由于Haskell的 do 表示法，強大的類型系統(tǒng)以及語言的語法使得Monad在Haskell里面非常容易處理。
• Monads使用來控制求值順序的

創(chuàng)建Logger Monad?

Logger 類的定義非常簡單：

-- file: ch14/Logger.hs
newtype Logger a = Logger { execLogger :: (a, Log) }

它其實就是一個二元組，第一個元素是執(zhí)行動作的結果，第二元素是我們執(zhí)行動作的時候紀錄的日志信息列表。

我們使用 newtype 關鍵字把二元組進行了包裝使它的類型更加清晰易讀。 runLogger 函數(shù)可以從這個Monad里面取出這個元組里面的值；這個函數(shù)其實是 execLogger 的一個別名。

-- file: ch14/Logger.hs
runLogger = execLogger

record 這個函數(shù)將為接收到的日志信息創(chuàng)建一個只包含單個元素的列表。

-- file: ch14/Logger.hs
record s = Logger ((), [s])

這個動作的結果是 () 。

讓我們以 return 開始，構建 Monad 實例；先嘗試一下：它什么都不記錄，然后把結果存放在二元組里面。

-- file: ch14/Logger.hs
instance Monad Logger where
    return a = Logger (a, [])

(>>=) 的定義更有趣，當然它也是monad的核心。 (>>=) 把一個普通的值和一個monadic的函數(shù)結合起來，得到新的運算結果和一個新的日志信息。

-- file: ch14/Logger.hs
    -- (>>=) :: Logger a -> (a -> Logger b) -> Logger b
    m >>= k = let (a, w) = execLogger m
                  n      = k a
                  (b, x) = execLogger n
              in Logger (b, w ++ x)

我們看看這段代碼里面發(fā)生了什么。首先使用 runLogger 函數(shù)從動作 m 取出結果 a ,然后把它傳遞給monadic函數(shù) k; 接著我們又取出 b ；最后把 w 和 x 拼接得到一個新的日志。

Maybe monad?

Maybe 應該是最簡單的Monad了。它代表了一種可能不會產(chǎn)生計算結果的計算過程。

-- file: ch14/Maybe.hs
instance Monad Maybe where
    Just x >>= k  =  k x
    Nothing >>= _ =  Nothing

    Just _ >> k   =  k
    Nothing >> _  =  Nothing

    return x      =  Just x

    fail _        =  Nothing

當我們使用 (>>=) 或者 (>>) 串聯(lián)一些 Maybe 計算的時候，如果這些計算中的任何一個返回了 Nothing ， (>>=) 和 (>>) 就不會對余下的任何計算進行求值。

值得一提的是，整個調用鏈并不是完全短路的。每一個 (>>=) 或者 (>>) 仍然會匹配它左邊的 Nothing 然后給右邊的函數(shù)一個 Nothing, 直到達到調用鏈的末端。這一點很容易被遺忘：當調用鏈中某個計算失敗的時候，之前計算的結果，余下的調用鏈以及使用的 Nothing 值在運行時的開銷是廉價的，但并不是完全沒有開銷。

-- file: ch14/Maybe.hs
maybe :: b -> (a -> b) -> Maybe a -> b
maybe n _ Nothing  = n
maybe _ f (Just x) = f x

-- file: ch14/Carrier.hs
import qualified Data.Map as M

type PersonName = String
type PhoneNumber = String
type BillingAddress = String
data MobileCarrier = Honest_Bobs_Phone_Network
                   | Morrisas_Marvelous_Mobiles
                   | Petes_Plutocratic_Phones
                     deriving (Eq, Ord)

findCarrierBillingAddress :: PersonName
                          -> M.Map PersonName PhoneNumber
                          -> M.Map PhoneNumber MobileCarrier
                          -> M.Map MobileCarrier BillingAddress
                          -> Maybe BillingAddress

-- file: ch14/Carrier.hs
variation1 person phoneMap carrierMap addressMap =
    case M.lookup person phoneMap of
      Nothing -> Nothing
      Just number ->
          case M.lookup number carrierMap of
            Nothing -> Nothing
            Just carrier -> M.lookup carrier addressMap

ghci> :module +Data.Map
ghci> :type Data.Map.lookup
Data.Map.lookup :: (Ord k, Monad m) => k -> Map k a -> m a

-- file: ch14/Carrier.hs
variation2 person phoneMap carrierMap addressMap = do
  number <- M.lookup person phoneMap
  carrier <- M.lookup number carrierMap
  address <- M.lookup carrier addressMap
  return address

-- file: ch14/Carrier.hs
variation2a person phoneMap carrierMap addressMap = do
  number <- M.lookup person phoneMap
  carrier <- M.lookup number carrierMap
  M.lookup carrier addressMap

List Monad?

Maybe 類型代表有可能有值也可能沒有值的計算；也有的情況下希望計算會返回一系列的結果，顯然，List正適合這個目的。List的類型帶有一個參數(shù)，這暗示它有可能能作為一個monad使用；事實上，我們確實能把它當作monad使用。

先不看標準庫的 Prelude 對于List monad的實現(xiàn)，我們自己來看看一個 List 的monad應該是什么樣的。這個過程很簡單：首先看 (>>=) 和 return 的類型，然后進行一些替換操作，看看我們能不能使用一些熟悉的list函數(shù)。

return 和 (>>=) 這兩個函數(shù)里面顯然 return 比較簡單。我們已經(jīng)知道 return 函數(shù)接受一個類型，然后把它用類型構造器 m 包裝一下然后產(chǎn)生一個新的類型 m a. 在List這種情況下，這個類型構造器就是 []. 把這個類型構造器使用List的類型構造器替換掉我們就得到了類型 [] a (當然，這樣寫是非法的！）；可以把它寫成更加熟悉的形式 [a].

現(xiàn)在我們知道list的 return 函數(shù)的類型應該是 a -> [a] 。對于這種類型的函數(shù)，只有少數(shù)那么幾種實現(xiàn)的可能：要么它返回一個空列表，要么返回一個單個元素的列表，或者一個無窮長度的列表?；谖覀儸F(xiàn)在對于Monad的理解，最有可能的實現(xiàn)方式應該是返回單個元素的列表：它不會丟失已有信息，也不會無限重復。

-- file: ch14/ListMonad.hs
returnSingleton :: a -> [a]
returnSingleton x = [x]

如果我們對 (>>=) 的類型簽名進行和 return 類似的替換，我們會得到： [a] -> (a -> [b]) -> [b] . 這看起來和 map 非常相似。

ghci> :type (>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
ghci> :type map
map :: (a -> b) -> [a] -> [b]

map 函數(shù)的參數(shù)順序和它有點不對應，我們可以改成這樣：

ghci> :type (>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
ghci> :type flip map
flip map :: [a] -> (a -> b) -> [b]

但是還是有一點小問題： flip map 的第二個參數(shù)的類型是 a -> b ，但是 (>>=) 的第二個參數(shù)的類型是 a -> [b] ,應該怎么辦呢？

我們對類型進行更多的替換，看看會發(fā)生什么。 flip map 這個函數(shù)能把任何類型 b 作為返回結果；如果我們使用 [b] 來替換 b ，這個函數(shù)的類型就成了 a -> (a -> [n]) -> [[b]]. 換句話說，如果我們使用 map ，將一個列表與一個返回列表的函數(shù)進行映射，我們會得到一個包含列表的列表。

ghci> flip map [1,2,3] (\a -> [a,a+100])
[[1,101],[2,102],[3,103]]

有趣的是，我們這么做并沒有讓 flip map 和 (>>=) 的類型更加匹配一點； (>>=) 的類型是 [a] -> (a -> [b]) -> [b] ；然而，flip map 如果對返回列表的函數(shù)進行map那么它的類型簽名是 [a] -> (a -> [b]) -> [[b]] .在類型上依然是不匹配的，我們僅僅是把不匹配的類型從中間轉移到了末尾。但是，我們的努力并沒有白費：我們現(xiàn)在其實只需要一個能把 [[b]] 轉化成 [b] 的函數(shù)就好了。很明顯 concat 符合我們的要求。

ghci> :type concat
concat :: [[a]] -> [a]

(>>=) 的類型告訴我們應該把 map 的參數(shù)進行翻轉，然后使用 concat 進行處理得到單個列表。

ghci> :type \xs f -> concat (map f xs)
\xs f -> concat (map f xs) :: [a] -> (a -> [a1]) -> [a1]

事實上lists的 (>>=) 定義就是這樣：

-- file: ch14/ListMonad.hs
instance Monad [] where
    return x = [x]
        xs >>= f = concat (map f xs)

它使用函數(shù) f 對列表 xs 的每一個元素 x 進行處理，然后把得到的結果拼接起來得到單個列表。

現(xiàn)在我們已經(jīng)搞定了List這個Monad的兩個核心函數(shù)，另外兩個非核心函數(shù)實現(xiàn)起來就很容易了：

-- file: ch14/ListMonad.hs
    xs >> f = concat (map (\_ -> f) xs)
    fail _ = []

-- file: ch14/CartesianProduct.hs
comprehensive xs ys = [(x,y) | x <- xs, y <- ys]

-- file: ch14/CartesianProduct.hs
monadic xs ys = do { x <- xs; y <- ys; return (x,y) }

ghci> comprehensive [1,2] "bar"
[(1,'b'),(1,'a'),(1,'r'),(2,'b'),(2,'a'),(2,'r')]
ghci> comprehensive [1,2] "bar" == monadic [1,2] "bar"
True

-- file: ch14/CartesianProduct.hs
blockyDo xs ys = do
    x <- xs
    y <- ys
    return (x, y)

-- file: ch14/CartesianProduct.hs
blockyPlain xs ys =
    xs >>=
    \x -> ys >>=
    \y -> return (x, y)

blockyPlain_reloaded xs ys =
    concat (map (\x ->
                 concat (map (\y ->
                              return (x, y))
                         ys))
            xs)

-- file: ch14/MultiplyTo.hs
guarded :: Bool -> [a] -> [a]
guarded True  xs = xs
guarded False _  = []

multiplyTo :: Int -> [(Int, Int)]
multiplyTo n = do
  x <- [1..n]
  y <- [x..n]
  guarded (x * y == n) $
    return (x, y)

ghci> multiplyTo 8
[(1,8),(2,4)]
ghci> multiplyTo 100
[(1,100),(2,50),(4,25),(5,20),(10,10)]
ghci> multiplyTo 891
[(1,891),(3,297),(9,99),(11,81),(27,33)]

還原do的本質?

Haskell的 do 表示法實際上是個語法糖：它給我們提供了一種不使用 (>>=) 和匿名函數(shù)來寫monadic代碼的方式。去除do語法糖的過程就是把它翻譯為 (>>=) 和匿名函數(shù)。

去除do語法糖的規(guī)則非常簡單。我們可以簡單的把編譯器想象為機械重復地對這些do語句塊執(zhí)行這些規(guī)則直到?jīng)]有任何do關鍵字為止。

do 關鍵字后面接單個動作（action）直接翻譯為動作本身。

-- file: ch14/Do.hs
doNotation1 =
    do act

-- file: ch14/Do.hs
translated1 =
    act

do 后面包含多個動作（action）的表示是這樣的：首先是第一個動作，但是接一個 (>>) 操作符，然后一個 do 關鍵字；最后接剩下的動作。當我們對do語句塊重復應用這條規(guī)則的時候，整個do語句快就會被 (>>) 串聯(lián)起來。

-- file: ch14/Do.hs
doNotation2 =
    do act1
       act2
       {- ... etc. -}
       actN

-- file: ch14/Do.hs
translated2 =
    act1 >>
    do act2
       {- ... etc. -}
       actN

finalTranslation2 =
    act1 >>
    act2 >>
    {- ... etc. -}
    actN

<- 標記需