第十章：代碼案例學習：解析二進制數(shù)據(jù)格式

本章將會討論一個常見任務(wù)：解析（parsing）二進制文件。選這個任務(wù)有兩個目的。第一個確實是想談?wù)劷馕鲞^程，但更重要的目標是談?wù)劤绦蚪M織、重構(gòu)和消除樣板代碼（boilerplate code：通常指不重要，但沒它又不行的代碼）。我們將會展示如何清理冗余代碼，并為第十四章討論 Monad 做點準備。

我們將要用到的文件格式來自于 netpbm 庫，它包含一組用來處理位圖圖像的程序及文件格式，它古老而令人尊敬。這種文件格式不但被廣泛使用，而且還非常簡單，雖然解析過程也不是完全沒有挑戰(zhàn)。對我們而言最重要的是，netpbm 文件沒有經(jīng)過壓縮。

灰度文件

netpbm 的灰度文件格式名為 PGM（”portable grey map”）。事實上它不是一個格式，而是兩個：純文本（又名P2）格式使用 ASCII 編碼，而更常用的原始（P5）格式則采用二進制表示。

每種文件格式都包含頭信息，頭信息以一個“魔法”字符串開始，指出文件格式。純文本格式是 P2，原始格式是 P5。魔法字符串之后是空格，然后是三個數(shù)字：寬度、高度、圖像的最大灰度值。這些數(shù)字用十進制 ASCII 數(shù)字表示，并用空格隔開。

最大灰度值之后便是圖像數(shù)據(jù)了。在原始文件中，這是一串二進制值。純文本文件中，這些值是用空格隔開的十進制 ASCII 數(shù)字。

原始文件可包含多個圖像，一個接一個，每個都有自己的頭信息。純文本文件只包含一個圖像。

解析原始 PGM 文件

首先我們來給原始 PGM 文件寫解析函數(shù)。PGM 解析函數(shù)是一個純函數(shù)。它不管獲取數(shù)據(jù)，只管解析。這是一種常見的 Haskell 編程方法。通過把數(shù)據(jù)的獲取和處理分開，我們可以很方便地控制從哪里獲取數(shù)據(jù)。

我們用 ByteString 類型來存儲灰度數(shù)據(jù)，因為它比較節(jié)省空間。由于 PGM 文件以 ASCII 字符串開頭，文件內(nèi)容又是二進制數(shù)據(jù)，我們同時載入兩種形式的 ByteString 模塊。

-- file: ch10/PNM.hs
import qualified Data.ByteString.Lazy.Char8 as L8
import qualified Data.ByteString.Lazy as L
import Data.Char (isSpace)

我們并不關(guān)心 ByteString 類型是惰性的還是嚴格的，因此我們隨便選了惰性的版本。

我們用一個直白的數(shù)據(jù)類型來表示 PGM 圖像。

-- file: ch10/PNM.hs
data Greymap = Greymap {
      greyWidth :: Int
    , greyHeight :: Int
    , greyMax :: Int
    , greyData :: L.ByteString
    } deriving (Eq)

通常來說，Haskell 的 Show 實例會生成數(shù)據(jù)的字符串表示，我們還可以用 read 讀回來。然而，對于一個位圖圖像文件來說，這可能會生成一個非常大的字符串，比如當你對一張照片調(diào)用 show 的時候。基于這個原因，我們不準備讓編譯器自動為我們派生 Show 實例；我們會自己實現(xiàn)，并刻意簡化它。

-- file: ch10/PNM.hs
instance Show Greymap where
    show (Greymap w h m _) = "Greymap " ++ show w ++ "x" ++ show h + " " ++ show m

我們的 Show 實例故意沒打印位圖數(shù)據(jù)，也就沒必要寫 Read 實例了，因為我們無法從 show 的結(jié)果重構(gòu) Greymap。

解析函數(shù)的類型顯而易見。

-- file: ch10/PNM.hs
parseP5 :: L.ByteString -> Maybe (Greymap, L.ByteString)

這個函數(shù)以一個 ByteString 為參數(shù)，如果解析成功的話，它返回一個被解析的 Greymap 值以及解析之后剩下的字符串，剩下的字符串以后會用到。

解析函數(shù)必須一點一點處理輸入數(shù)據(jù)。首先，我們必須確認我們正在處理的是原始 PGM 文件；然后，我們處理頭信息中的數(shù)字；最后我們處理位圖數(shù)據(jù)。下面是是一種比較初級的實現(xiàn)方法，我們會在它的基礎(chǔ)上不斷改進。

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

這段代碼非常直白，它把所有的解析放在了一個長長的梯形 case 表達式中。每個函數(shù)在處理完它所需要的部分后會把剩余的 ByteString 返回。我們再把這部分傳給下個函數(shù)。像這樣我們將結(jié)果依次解構(gòu)，如果解析失敗就返回 Nothing，否則便又向最終結(jié)邁近了一步。下面是我們在解析過程中用到的函數(shù)的定義。它們的類型被注釋掉了因為已經(jīng)寫過了。

-- file: ch10/PNM.hs
-- L.ByteString -> L.ByteString -> Maybe L.ByteString
matchHeader prefix str
    | prefix `L8.isPrefixOf` str
        = Just (L8.dropWhile isSpace (L.drop (L.length prefix) str))
    | otherwise
        = Nothing

-- L.ByteString -> Maybe (Int, L.ByteString)
getNat s = case L8.readInt s of
             Nothing -> Nothing
             Just (num,rest)
                 | num <= 0    -> Nothing
                 | otherwise   -> Just (num, L8.dropWhile isSpace rest)

-- Int -> L.ByteString -> Maybe (L.ByteString, L.ByteString)
getBytes n str = let count           = fromIntegral n
                     both@(prefix,_) = L.splitAt count str
                 in if L.length prefix < count
                    then Nothing
                    else Just both

消除樣板代碼

parseP5 函數(shù)雖然能用，但它的代碼風格卻并不令人滿意。它不斷挪向屏幕右側(cè)，非常明顯，再來個稍微復(fù)雜點的函數(shù)它就要橫跨屏幕了。我們不斷構(gòu)建和解構(gòu) Maybe 值，只在 Just 匹配特定值的時候才繼續(xù)。所有這些相似的 case 表達式就是“樣板代碼”，它掩蓋了我們真正要做的事情?？偠灾@段代碼需要抽象重構(gòu)。

退一步看，我們能觀察到兩種模式。第一，很多我們用到的函數(shù)都有相似的類型，它們最后一個參數(shù)都是 ByteString，返回值類型都是 Maybe。第二，parseP5 函數(shù)不斷解構(gòu) Maybe 值，然后要么失敗退出，要么把展開之后的值傳給下個函數(shù)。

我們很容易就能寫個函數(shù)來體現(xiàn)第二種模式。

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

(>>?) 函數(shù)非常簡單：它接受一個值作為左側(cè)參數(shù)，一個函數(shù) f 作為右側(cè)參數(shù)。如果值不為 Nothing，它就把函數(shù) f 應(yīng)用在 Just 構(gòu)造器中的值上。我們把這個函數(shù)定義為操作符這樣它就能把別的函數(shù)串聯(lián)在一起了。最后，我們沒給 (>>?) 定義結(jié)合度，因此它默認為 infixl9 （左結(jié)合，優(yōu)先級最高的操作符）。換言之，a>>?b>>?c 會從左向右求值，就像 (a>>?b)>>?c) 一樣。

有了這個串聯(lián)函數(shù)，我們來重寫一下解析函數(shù)。

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

理解這個函數(shù)的關(guān)鍵在于理解其中的鏈。每個 (>>?) 的左側(cè)都是一個 Maybe 值，右側(cè)都是一個返回 Maybe 值的函數(shù)。這樣，Maybe 值就可以不斷傳給后續(xù) (>>?) 表達式。

我們新增了 skipSpace 函數(shù)用來提高可讀性。通過這些改進，我們已將代碼長度減半。通過移除樣板 case 代碼，代碼變得更容易理解。

盡管在匿名（lambda）函數(shù)中我們已經(jīng)警告過不要過度使用匿名函數(shù)，在上面的函數(shù)鏈中我們還是用了一些。因為這些函數(shù)太小了，給它們命名并不能提高可讀性。

隱式狀態(tài)

到這里還沒完。我們的代碼顯式地用序?qū)鬟f結(jié)果，其中一個元素代表解析結(jié)果的中間值，另一個代表剩余的 ByteString 值。如果我們想擴展代碼，比方說記錄已經(jīng)處理過的字節(jié)數(shù)，以便在解析失敗時報告出錯位置，那我們已經(jīng)有8個地方要改了，就為了把序?qū)Ω某扇M。

這使得本來就沒多少的代碼還很難修改。問題在于用模式匹配從序?qū)χ腥≈担何覀兗僭O(shè)了我們總是會用序?qū)?，并且把這種假設(shè)編進了代碼。盡管模式匹配非常好用，但如果不慎重，我們還是會誤入歧途。

讓我們解決新代碼帶來的不便。首先，我們來修改解析狀態(tài)的類型。

-- file: ch10/Parse.hs
data ParseState = ParseState {
      string :: L.ByteString
    , offset :: Int64           -- imported from Data.Int
    } deriving (Show)

我們轉(zhuǎn)向了代數(shù)數(shù)據(jù)類型，現(xiàn)在我們既可以記錄當前剩余的字符串，也可以記錄相對于原字符串的偏移值了。更重要的改變是用了記錄語法：現(xiàn)在可以避免使用模式匹配來獲取狀態(tài)信息了，可以用 string 和 offset 訪問函數(shù)。

我們給解析狀態(tài)起了名字。給東西起名字方便我們推理。例如，我們現(xiàn)在可以這么看解析函數(shù)：它處理一個解析狀態(tài)，產(chǎn)生新解析狀態(tài)和一些別的信息。我們可以用 Haskell 類型直接表示。

-- file: ch10/Parse.hs
simpleParse :: ParseState -> (a, ParseState)
simpleParse = undefined

為了給用戶更多幫助，我們可以在解析失敗時報告一條錯誤信息。只需對解析器的類型稍作修改即可。

-- file: ch10/Parse.hs
betterParse :: ParseState -> Either String (a, ParseState)
betterParse = undefined

為了防患于未然，我們最好不要將解析器的實現(xiàn)暴露給用戶。早些時候我們顯式地用序?qū)肀硎緺顟B(tài)，當我們想擴展解析器的功能時，我們馬上就遇到了麻煩。為了防止這種現(xiàn)象再次發(fā)生，我們用一個 newtype 聲明來隱藏解析器的細節(jié)。

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

別忘了 newtype 只是函數(shù)在編譯時的一層包裝，它沒有運行時開銷。我們想用這個函數(shù)時，我們用 runParser 訪問器。

如果我們的模塊不導(dǎo)出 Parse 值構(gòu)造器，我們就能確保沒人會不小心創(chuàng)建一個解析器，或者通過模式匹配來觀察其內(nèi)部構(gòu)造。

identity 解析器

我們來定義一個簡單的 identity 解析器。它把輸入值轉(zhuǎn)為解析結(jié)果。從這個意義上講，它有點像 id 函數(shù)。

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

這個函數(shù)沒動解析狀態(tài)，只把它的參數(shù)當成了解析結(jié)果。我們把函數(shù)體包裝成 Parse 類型以通過類型檢查。我們該怎么用它去解析呢？

首先我們得把 Parse 包裝去掉從而得到里面的函數(shù)。這通過 runParse 函數(shù)實現(xiàn)。然后得創(chuàng)建一個 ParseState，然后對其調(diào)用解析函數(shù)。最后，我們把解析結(jié)果和最終的 ParseState 分開。

-- file: ch10/Parse.hs
parse :: Parse a -> L.ByteString -> Either String a
parse parser initState
    = case runParse parser (ParseState initState 0) of
        Left err          -> Left err
        Right (result, _) -> Right result

由于 identity 解析器和 parse 函數(shù)都沒有檢查解析狀態(tài)，我們都不用傳入字符串就可以試驗我們的代碼。

Prelude> :r
[1 of 1] Compiling Main             ( Parse.hs, interpreted )
Ok, modules loaded: Main.
*Main> :type parse (identity 1) undefined
parse (identity 1) undefined :: Num a => Either String a
*Main> parse (identity 1) undefined
Right 1
*Main> parse (identity "foo") undefined
Right "foo"

一個不檢查輸入的解析器可能有點奇怪，但很快我們就可以看到它的用處。同時，我們更加確信我們的類型是正確的，基本了解了代碼是如何工作的。

記錄語法、更新以及模式匹配

記錄語法的用處不僅僅在于訪問函數(shù)：我們可以用它來復(fù)制或部分改變已有值。就像下面這樣：

-- file: ch10/Parse.hs
modifyOffset :: ParseState -> Int64 -> ParseState
modifyOffset initState newOffset =
    initState { offset = newOffset }

這會創(chuàng)建一個跟 initState 完全一樣的 ParseState 值，除了 offset 字段會替換成 newOffset 指定的值。

*Main> let before = ParseState (L8.pack "foo") 0
*Main> let after = modifyOffset before 3
*Main> before
ParseState {string = "foo", offset = 0}
*Main> after
ParseState {string = "foo", offset = 3}

在大括號里我們可以給任意多的字段賦值，用逗號分開即可。

一個更有趣的解析器

現(xiàn)在來寫個解析器做一些有意義的事情。我們并不好高騖遠：我們只想解析單個字節(jié)而已。

-- file: ch10/Parse.hs
-- import the Word8 type from Data.Word
parseByte :: Parse Word8
parseByte =
    getState ==> \initState ->
    case L.uncons (string initState) of
      Nothing ->
          bail "no more input"
      Just (byte,remainder) ->
          putState newState ==> \_ ->
          identity byte
        where newState = initState { string = remainder,
                                     offset = newOffset }
              newOffset = offset initState + 1

定義中有幾個新函數(shù)。

L8.uncons 函數(shù)取出 ByteString 中的第一個元素。

ghci> L8.uncons (L8.pack "foo")
Just ('f',Chunk "oo" Empty)
ghci> L8.uncons L8.empty
Nothing

getState 函數(shù)得到當前解析狀態(tài)，putState 函數(shù)更新解析狀態(tài)。bail 函數(shù)終止解析并報告錯誤。(==>) 函數(shù)把解析器串聯(lián)起來。我們馬上就會詳細介紹這些函數(shù)。

Note

Hanging lambdas

獲取和修改解析狀態(tài)

parseByte 函數(shù)并不接受解析狀態(tài)作為參數(shù)。相反，它必須調(diào)用 getState 來得到解析狀態(tài)的副本，然后調(diào)用 putState 將當前狀態(tài)更新為新狀態(tài)。

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

putState :: ParseState -> Parse ()
putState s = Parse (\_ -> Right ((), s))

閱讀這些函數(shù)的時候，記得序?qū)ψ笤貫?Parse 結(jié)果，右元素為當前 ParseState。這樣理解起來會比較容易。

getState 將當前解析狀態(tài)展開，這樣調(diào)用者就能訪問里面的字符串。putState 將當前解析狀態(tài)替換為一個新狀態(tài)。(==>) 鏈中的下一個函數(shù)將會使用這個狀態(tài)。

這些函數(shù)將顯式的狀態(tài)處理移到了需要它們的函數(shù)的函數(shù)體內(nèi)。很多函數(shù)并不關(guān)心當前狀態(tài)是什么，因而它們也不會調(diào)用 getState 或 putState。跟之前需要手動傳遞元組的解析器相比，現(xiàn)在的代碼更加緊湊。在之后的代碼中就能看到效果。

我們將解析狀態(tài)的細節(jié)打包放入 ParseState 類型中，然后我們通過訪問器而不是模式匹配來訪問它。隱式地傳遞解析狀態(tài)給我們帶來另外的好處。如果想增加解析狀態(tài)的信息，我們只需修改 ParseState 定義，以及需要新信息的函數(shù)體即可。跟之前通過模式匹配暴露狀態(tài)的解析器相比，現(xiàn)在的代碼更加模塊化：只有需要新信息的代碼會受到影響。

報告解析錯誤

在定義 Parse 的時候我們已經(jīng)考慮了出錯的情況。(==>) 組合子不斷檢查解析錯誤并在錯誤發(fā)生時終止解析。但我們還沒來得及介紹用來報告解析錯誤的 bail 函數(shù)。

-- file: ch10/Parse.hs
bail :: String -> Parse a
bail err = Parse $ \s -> Left $
           "byte offset " ++ show (offset s) ++ ": " ++ err

調(diào)用 bail 之后，(==>) 會模式匹配包裝了錯誤信息的 Left 構(gòu)造器，并且不會調(diào)用下一個解析器。這使得錯誤信息可以沿著調(diào)用鏈返回。

把解析器串聯(lián)起來

(==>) 函數(shù)的功能和之前介紹的 (>>?) 函數(shù)功能類似：它可以作為“膠水”把函數(shù)串聯(lián)起來。

-- 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ù)體很有趣，還稍微有點復(fù)雜?；叵胍幌?，Parse 類型表示一個被包裝的函數(shù)。既然 (==>) 函數(shù)把兩個 Parse 串聯(lián)起來并產(chǎn)生第三個，它也必須返回一個被包裝的函數(shù)。

這個函數(shù)做的并不多：它僅僅創(chuàng)建了一個閉包（closure）用來記憶 firstParser 和 secondParser 的值。

Note

閉包是一個函數(shù)和它所在的環(huán)境，也就是它可以訪問的變量。閉包在 Haskell 中很常見。例如，(+5) 就是一個閉包。實現(xiàn)的時候必須將 5 記錄為 (+) 操作符的第二個參數(shù)，這樣得到的函數(shù)才能把 5 加給它的參數(shù)。

在應(yīng)用 parse 之前，這個閉包不會被展開應(yīng)用。應(yīng)用的時候，它會求值 firstParser 并檢查它的結(jié)果。如果解析失敗，閉包也會失敗。否則，它會把解析結(jié)果及 newState 傳給 secondParser。

這是非常具有想象力、非常微妙的想法：我們實際上用了一個隱藏的參數(shù)將 ParseState 在 Parse 鏈之間傳遞。（我們在之后幾章還會碰到這樣的代碼，所以現(xiàn)在不懂也沒有關(guān)系。）

Functor 簡介

現(xiàn)在我們對 map 函數(shù)已經(jīng)有了一個比較詳細的了解，它把函數(shù)應(yīng)用在列表的每一個元素上，并返回一個可能包含另一種類型元素的列表。

ghci> map (+1) [1,2,3]
[2,3,4]
ghci> map show [1,2,3]
["1","2","3"]
ghci> :type map show
map show :: (Show a) => [a] -> [String]

map 函數(shù)這種行為在別的實例中可能有用。例如，考慮一棵二叉樹。

-- file: ch10/TreeMap.hs
data Tree a = Node (Tree a) (Tree a)
            | Leaf a
              deriving (Show)

如果想把一個字符串樹轉(zhuǎn)成一個包含這些字符串長度的樹，我們可以寫個函數(shù)來實現(xiàn)：

-- file: ch10/TreeMap.hs
treeLengths (Leaf s) = Leaf (length s)
treeLengths (Node l r) = Node (treeLengths l) (treeLengths r)

我們試著尋找一些可能轉(zhuǎn)成通用函數(shù)的模式，下面就是一個可能的模式。

-- file: ch10/TreeMap.hs
treeMap :: (a -> b) -> Tree a -> Tree b
treeMap f (Leaf a)   = Leaf (f a)
treeMap f (Node l r) = Node (treeMap f l) (treeMap f r)

正如我們希望的那樣，treeLengths 和 treeMaplength 返回相同的結(jié)果。

ghci> let tree = Node (Leaf "foo") (Node (Leaf "x") (Leaf "quux"))
ghci> treeLengths tree
Node (Leaf 3) (Node (Leaf 1) (Leaf 4))
ghci> treeMap length tree
Node (Leaf 3) (Node (Leaf 1) (Leaf 4))
ghci> treeMap (odd . length) tree
Node (Leaf True) (Node (Leaf True) (Leaf False))

Haskell 提供了一個眾所周知的類型類來進一步一般化 treeMap。這個類型類叫做 Functor，它只定義了一個函數(shù) fmap。

-- file: ch10/TreeMap.hs
class Functor f where
    fmap :: (a -> b) -> f a -> f b

我們可以把 fmap 當做某種提升函數(shù)，就像我們在 Avoiding boilerplate with lifting(fix link) 一節(jié)中介紹的那樣。它接受一個參數(shù)為普通值 a->b 的函數(shù)并把它提升為一個參數(shù)為容器 fa->fb 的函數(shù)。其中 f 是容器的類型。

舉個例子，如果我們用 Tree 替換類型變量 f，fmap 的類型就會跟 treeMap 的類型相同。事實上我們可以用 treeMap 作為 fmap 對 Tree 的實現(xiàn)。

-- file: ch10/TreeMap.hs
instance Functor Tree where
    fmap = treeMap

我們可以用 map 作為 fmap 對列表的實現(xiàn)。

-- file: ch10/TreeMap.hs
instance Functor [] where
    fmap = map

現(xiàn)在我們可以把 fmap 用于不同類型的容器上了。

ghci> fmap length ["foo","quux"]
[3,4]
ghci> fmap length (Node (Leaf "Livingstone") (Leaf "I presume"))
Node (Leaf 11) (Leaf 9)

Prelude 定義了一些常見類型的 Functor 實例，如列表和 Maybe。

-- file: ch10/TreeMap.hs
instance Functor Maybe where
    fmap _ Nothing  = Nothing
    fmap f (Just x) = Just (f x)

Maybe 的這個實例很清楚地表明了 fmap 要做什么。對于類型的每一個構(gòu)造器，它都必須給出對應(yīng)的行為。例如，如果值被包裝在 Just 里，fmap 實現(xiàn)把函數(shù)應(yīng)用在展開之后的值上，然后再用 Just 重新包裝起來。

Functor 的定義限制了我們能用 fmap 做什么。例如，如果一個類型有且僅有一個類型參數(shù)，我們才能給它實現(xiàn) Functor 實例。

舉個例子，我們不能給 Eitherab 或者 (a,b) 寫 fmap 實現(xiàn)，因為它們有兩個類型參數(shù)。我們也不能給 Bool 或者 Int 寫，因為它們沒有類型參數(shù)。

另外，我們不能給類型定義添加任何約束。這是什么意思呢？為了搞清楚，我們來看一個正常的 data 定義和它的 Functor 實例。

-- file: ch10/ValidFunctor.hs
data Foo a = Foo a

instance Functor Foo where
    fmap f (Foo a) = Foo (f a)

當我們定義新類型時，我們可以在 data 關(guān)鍵字之后加一個類型約束。

-- file: ch10/ValidFunctor.hs
data Eq a => Bar a = Bar a

instance Functor Bar where
    fmap f (Bar a) = Bar (f a)

這意味著只有當 a 是 Eq 類型類的成員時，它才能被放進 Foo。然而，這個約束卻讓我們無法給 Bar 寫 Functor 實例。

*Main> :l ValidFunctor.hs
[1 of 1] Compiling Main             ( ValidFunctor.hs, interpreted )

ValidFunctor.hs:8:6:
    Illegal datatype context (use DatatypeContexts): Eq a =>
Failed, modules loaded: none.

給類型定義加約束不好

給類型定義加約束從來就不是什么好主意。它的實質(zhì)效果是強迫你給每一個用到這種類型值的函數(shù)加類型約束。假設(shè)我們現(xiàn)在有一個棧數(shù)據(jù)結(jié)構(gòu)，我們想通過訪問它來看看它的元素是否按順序排列。下面是數(shù)據(jù)類型的一個簡單實現(xiàn)。

-- file: ch10/TypeConstraint.hs
data (Ord a) => OrdStack a = Bottom
                           | Item a (OrdStack a)
                             deriving (Show)

如果我們想寫一個函數(shù)來看看它是不是升序的（即每個元素都比它下面的元素大），很顯然，我們需要 Ord 約束來進行兩兩比較。

-- file: ch10/TypeConstraint.hs
isIncreasing :: (Ord a) => OrdStack a -> Bool
isIncreasing (Item a rest@(Item b _))
    | a < b     = isIncreasing rest
    | otherwise = False
isIncreasing _  = True

然而，由于我們在類型聲明上加了類型約束，它最后也影響到了某些不需要它的地方：我們需要給 push 加上 Ord 約束，但事實上它并不關(guān)心棧里元素的順序。

-- file: ch10/TypeConstraint.hs
push :: (Ord a) => a -> OrdStack a -> OrdStack a
push a s = Item a s

如果你把 Ord 約束刪掉，push 定義便無法通過類型檢查。

正是由于這個原因，我們之前給 Bar 寫 Functor 實例沒有成功：它要求 fmap 的類型簽名加上 Eq 約束。

我們現(xiàn)在已經(jīng)嘗試性地確定了 Haskell 里給類型簽名加類型約束并不是一個好的特性，那有什么好的替代嗎？答案很簡單：不要在類型定義上加類型約束，在需要它們的函數(shù)上加。

在這個例子中，我們可以刪掉 OrdStack 和 push 上的 Ord。isIncreasing 還需要，否則便無法調(diào)用 (<)。現(xiàn)在我們只在需要的地方加類型約束了。這還有一個更深遠的好處：類型簽名更準確地表示了每個函數(shù)的真正需求。

大多數(shù) Haskell 容器遵循這個模式。Data.Map 模塊里的 Map 類型要求它的鍵是排序的，但類型本身卻沒有這個約束。這個約束是通過 insert 這樣的函數(shù)來表達的，因為這里需要它，在 size 上卻沒有，因為在這里順序無關(guān)緊要。

fmap 的中綴使用

你經(jīng)常會看到 fmap 作為操作符使用：

ghci> (1+) `fmap` [1,2,3] ++ [4,5,6]
[2,3,4,4,5,6]

也許你感到奇怪，原始的 map 卻幾乎從不這樣使用。

我們這樣使用 fmap 一個可能的原因是可以省略第二個參數(shù)的括號。括號越少讀代碼也就越容易。

ghci> fmap (1+) ([1,2,3] ++ [4,5,6])
[2,3,4,5,6,7]

如果你真的想把 fmap 當做操作符用，Control.Applicative 模塊包含了作為 fmap 別名的 (<$>) 操作符。

當我們返回之前寫的代碼時，我們會發(fā)現(xiàn)這對解析很有用。

靈活實例

你可能想給 EitherIntb 類型實現(xiàn) Functor 實例，因為它只有一個類型參數(shù)。

-- file: ch10/EitherInt.hs
instance Functor (Either Int) where
    fmap _ (Left n) = Left n
    fmap f (Right r) = Right (f r)

然而，Haskell 98 類型系統(tǒng)不能保證檢查這種實例的約束會終結(jié)。非終結(jié)的約束檢查會導(dǎo)致編譯器進入死循環(huán)，所以這種形式的實例是被禁止的。

Prelude> :l EitherInt.hs
[1 of 1] Compiling Main             ( EitherInt.hs, interpreted )

EitherInt.hs:2:10:
    Illegal instance declaration for ‘Functor (Either Int)’
      (All instance types must be of the form (T a1 ... an)
       where a1 ... an are *distinct type variables*,
       and each type variable appears at most once in the instance head.
       Use FlexibleInstances if you want to disable this.)
    In the instance declaration for ‘Functor (Either Int)’
Failed, modules loaded: none.

GHC 的類型系統(tǒng)比 Haskell 98 標準更強大。出于可移植性的考慮，默認情況下，它是運行在兼容 Haskell 98 的模式下的。 我們可以通過一個編譯命令允許更靈活的實例。

-- file: ch10/EitherIntFlexible.hs
{-# LANGUAGE FlexibleInstances #-}

instance Functor (Either Int) where
    fmap _ (Left n)  = Left n
    fmap f (Right r) = Right (f r)

這個命令內(nèi)嵌于 LANGUAGE 編譯選項。

有了 Functor 實例，我們來試試 EitherInt 的 fmap 函數(shù)。

ghci> :load EitherIntFlexible
[1 of 1] Compiling Main             ( EitherIntFlexible.hs, interpreted )
Ok, modules loaded: Main.
ghci> fmap (== "cheeseburger") (Left 1 :: Either Int String)
Left 1
ghci> fmap (== "cheeseburger") (Right "fries" :: Either Int String)
Right False

更多關(guān)于 Functor 的思考

對于 Functor 如何工作，我們做了一些隱式的假設(shè)。把它們說清楚并當成規(guī)則去遵守非常有用，因為這會讓我們把 Functor 當成統(tǒng)一的、行為規(guī)范的對象。規(guī)則只有兩個，并且非常簡單。

第一條規(guī)則是 Functor 必須保持身份（preserve identity）。也就是說，應(yīng)用 fmapid 應(yīng)該返回相同的值。

ghci> fmap id (Node (Leaf "a") (Leaf "b"))
Node (Leaf "a") (Leaf "b")

第二條規(guī)則是 Functor 必須是可組合的。也就是說，把兩個 fmap 組合使用效果應(yīng)該和把函數(shù)組合起來再用 fmap 相同。

ghci> (fmap even . fmap length) (Just "twelve")
Just True
ghci> fmap (even . length) (Just "twelve")
Just True

另一種看待這兩條規(guī)則的方式是 Functor 必須保持結(jié)構(gòu)（shape）。集合的結(jié)構(gòu)不應(yīng)該受到 Functor 的影響，只有對應(yīng)的值會改變。

ghci> fmap odd (Just 1)
Just True
ghci> fmap odd Nothing
Nothing

如果你要寫 Functor 實例，最好把這些規(guī)則記在腦子里，并且最好測試一下，因為編譯器不會檢查我們提到的規(guī)則。另一方面，如果你只是用 Functor，這些規(guī)則又如此自然，根本沒必要記住。它們只是把一些“照我說的做”的直覺概念形式化了。下面是期望行為的偽代碼表示。

-- file: ch10/FunctorLaws.hs
fmap id       ==  id
fmap (f . g)  ==  fmap f . fmap g

給 Parse 寫一個 Functor 實例

對于到目前為止我們研究過的類型而言，fmap 的期望行為非常明顯。然而由于 Parse 的復(fù)雜度，對于它而言 fmap 的期望行為并沒有這么明顯。一個合理的猜測是我們要 fmap 的函數(shù)應(yīng)該應(yīng)用到當前解析的結(jié)果上，并保持解析狀態(tài)不變。

-- file: ch10/Parse.hs
instance Functor Parse where
    fmap f parser = parser ==> \result ->
                    identity (f result)

定義很容易理解，我們來快速做幾個實驗看看我們是否遵守了 Functor 規(guī)則。

首先我們檢查身份是否被保持。我們在一次應(yīng)該失敗的解析上試試：從空字符串中解析字節(jié)（別忘了 (<$>) 就是 fmap）。

ghci> parse parseByte L.empty
Left "byte offset 0: no more input"
ghci> parse (id <$> parseByte) L.empty
Left "byte offset 0: no more input"

不錯。再來試試應(yīng)該成功的解析。

ghci> let input = L8.pack "foo"
ghci> L.head input
102
ghci> parse parseByte input
Right 102
ghci> parse (id <$> parseByte) input
Right 102

通過觀察上面的結(jié)果，可以看到我們的 Functor 實例同樣遵守了第二條規(guī)則，也就是保持結(jié)構(gòu)。失敗被保持為失敗，成功被保持為成功。

最后，我們確?？山M合性被保持了。

ghci> parse ((chr . fromIntegral) <$> parseByte) input
Right 'f'
ghci> parse (chr <$> fromIntegral <$> parseByte) input
Right 'f'

通過這個簡單的觀察，我們的 Functor 實例看起來行為規(guī)范。

利用 Functor 解析

我們討論 Functor 是有目的的：它讓我們寫出簡潔、表達能力強的代碼。回想早先引入的 parseByte 函數(shù)。在重構(gòu) PGM 解析器使之使用新的解析架構(gòu)的過程中，我們經(jīng)常想用 ASCII 字符而不是 Word8 值。

盡管可以寫一個類似于 parseByte 的 parseChar 函數(shù)，我們現(xiàn)在可以利用 Parse 的 Functor 屬性來避免重復(fù)代碼。我們的 functor 接受一個解析結(jié)果并將一個函數(shù)應(yīng)用于它，因此我們需要的是一個把 Word8 轉(zhuǎn)成 Char 的函數(shù)。

-- file: ch10/Parse.hs
w2c :: Word8 -> Char
w2c = chr . fromIntegral

-- import Control.Applicative
parseChar :: Parse Char
parseChar = w2c <$> parseByte

我們也可以利用 Functor 來寫一個短小的“窺視”函數(shù)。如果我們在輸入字符串的末尾，它會返回 Nothing。否則，它返回下一個字符，但不作處理（也就是說，它觀察但不打擾當前的解析狀態(tài)）。

-- file: ch10/Parse.hs
peekByte :: Parse (Maybe Word8)
peekByte = (fmap fst . L.uncons . string) <$> getState

定義 parseChar 時用到的提升把戲同樣也可以用于定義 peekChar。

-- file: ch10/Parse.hs
peekChar :: Parse (Maybe Char)
peekChar = fmap w2c <$> peekByte

注意到 peekByte 和 peekChar 分別兩次調(diào)用了 fmap，其中一次還是 (<$>)。這么做的原因是 Parse(Maybea) 類型是嵌在 Functor 中的 Functor。我們必須提升函數(shù)兩次使它能進入內(nèi)部 Functor。

最后，我們會寫一個通用組合子，它是 Parse 中的 takeWhile：它在謂詞為 True 是處理輸入。

-- file: ch10/Parse.hs
parseWhile :: (Word8 -> Bool) -> Parse [Word8]
parseWhile p = (fmap p <$> peekByte) ==> \mp ->
               if mp == Just True
               then parseByte ==> \b ->
                    (b:) <$> parseWhile p
               else identity []

再次說明，我們在好幾個地方都用到了 Functor（doubled up, when necessary）用以化簡函數(shù)。下面是相同函數(shù)不用 Functor 的版本。

-- file: ch10/Parse.hs
parseWhileVerbose p =
    peekByte ==> \mc ->
    case mc of
      Nothing -> identity []
      Just c | p c ->
                 parseByte ==> \b ->
                 parseWhileVerbose p ==> \bs ->
                 identity (b:bs)
             | otherwise ->
                 identity []

當你對 Functor 不熟悉的時候，冗余的定義應(yīng)該會更好讀。但是，由于 Haskell 中 Functor 非常常見，你很快就會更習慣（包括讀和寫）簡潔的表達。

重構(gòu) PGM 解析器

有了新的解析代碼，原始 PGM 解析函數(shù)現(xiàn)在變成了這個樣子：

-- file: ch10/Parse.hs
parseRawPGM =
    parseWhileWith w2c notWhite ==> \header -> skipSpaces ==>&
    assert (header == "P5") "invalid raw header" ==>&
    parseNat ==> \width -> skipSpaces ==>&
    parseNat ==> \height -> skipSpaces ==>&
    parseNat ==> \maxGrey ->
    parseByte ==>&
    parseBytes (width * height) ==> \bitmap ->
    identity (Greymap width height maxGrey bitmap)
  where notWhite = (`notElem` " \r\n\t")

下面是定義中用到的輔助函數(shù)，其中一些模式現(xiàn)在應(yīng)該已經(jīng)非常熟悉了：

-- file: ch10/Parse.hs
parseWhileWith :: (Word8 -> a) -> (a -> Bool) -> Parse [a]
parseWhileWith f p = fmap f <$> parseWhile (p . f)

parseNat :: Parse Int
parseNat = parseWhileWith w2c isDigit ==> \digits ->
           if null digits
           then bail "no more input"
           else let n = read digits
                in if n < 0
                   then bail "integer overflow"
                   else identity n

(==>&) :: Parse a -> Parse b -> Parse b
p ==>& f = p ==> \_ -> f

skipSpaces :: Parse ()
skipSpaces = parseWhileWith w2c isSpace ==>& identity ()

assert :: Bool -> String -> Parse ()
assert True  _   = identity ()
assert False err = bail err

類似于 (==>)，(==>&) 組合子將解析器串聯(lián)起來。但右側(cè)忽略左側(cè)的結(jié)果。assert 使得我們可以檢查性質(zhì)，然后當性質(zhì)為 False 時終止解析并報告錯誤信息。

未來方向

本章的主題是抽象。我們發(fā)現(xiàn)在函數(shù)鏈中傳遞顯式狀態(tài)并不理想，因此我們把這個細節(jié)抽象出來。在寫解析器的時候發(fā)現(xiàn)要重復(fù)用到一些代碼，我們把它們抽象成函數(shù)。我們引入了 Functor，它提供了一種映射到參數(shù)化類型的通用方法。

關(guān)于解析，我們在第16章會討論一個使用廣泛并且靈活的解析庫 Parsec。在第14章中，我們會再次討論抽象，我們會發(fā)現(xiàn)用 Monad 可以進一步化簡這章的代碼。

Hackage 數(shù)據(jù)庫中存在不少包可以用來高效解析以 ByteString 表示的二進制數(shù)據(jù)。在寫作時，最流行的是 binary，它易用且高效。

練習

1. 給“純文本” PGM 文件寫解析器。

2. 在對“原始” PGM 文件的描述中，我們省略了一個細節(jié)。如果頭信息中的“最大灰度”值小于256，那每個像素都會用單個字節(jié)表示。然而，它的最大范圍可達65535，這種情況下每個像素會以大端序的形式（最高有效位字節(jié)在前）用兩個字節(jié)來表示。

重寫原始 PGM 解析器使它能夠處理單字節(jié)和雙字節(jié)形式。

1. 重寫解析器使得它能夠區(qū)分“原始”和“純文本” PGM 文件，并解析對應(yīng)的文件類型。