第十章：代碼案例學(xué)習(xí)：解析二進(jìn)制數(shù)據(jù)格式
第十章：代碼案例學(xué)習(xí)：解析二進(jìn)制數(shù)據(jù)格式
本章將會(huì)討論一個(gè)常見任務(wù)：解析（parsing）二進(jìn)制文件。選這個(gè)任務(wù)有兩個(gè)目的。第一個(gè)確實(shí)是想談?wù)劷馕鲞^程，但更重要的目標(biāo)是談?wù)劤绦蚪M織、重構(gòu)和消除樣板代碼（boilerplate code：通常指不重要，但沒它又不行的代碼）。我們將會(huì)展示如何清理冗余代碼，并為第十四章討論 Monad 做點(diǎn)準(zhǔn)備。
我們將要用到的文件格式來自于 netpbm 庫，它包含一組用來處理位圖圖像的程序及文件格式，它古老而令人尊敬。這種文件格式不但被廣泛使用，而且還非常簡(jiǎn)單，雖然解析過程也不是完全沒有挑戰(zhàn)。對(duì)我們而言最重要的是，netpbm 文件沒有經(jīng)過壓縮。
灰度文件
netpbm 的灰度文件格式名為 PGM（”portable grey map”）。事實(shí)上它不是一個(gè)格式，而是兩個(gè)：純文本（又名P2）格式使用 ASCII 編碼，而更常用的原始（P5）格式則采用二進(jìn)制表示。
每種文件格式都包含頭信息，頭信息以一個(gè)“魔法”字符串開始，指出文件格式。純文本格式是 P2，原始格式是 P5。魔法字符串之后是空格，然后是三個(gè)數(shù)字：寬度、高度、圖像的最大灰度值。這些數(shù)字用十進(jìn)制 ASCII 數(shù)字表示，并用空格隔開。
最大灰度值之后便是圖像數(shù)據(jù)了。在原始文件中，這是一串二進(jìn)制值。純文本文件中，這些值是用空格隔開的十進(jìn)制 ASCII 數(shù)字。
原始文件可包含多個(gè)圖像，一個(gè)接一個(gè)，每個(gè)都有自己的頭信息。純文本文件只包含一個(gè)圖像。
解析原始 PGM 文件
首先我們來給原始 PGM 文件寫解析函數(shù)。PGM 解析函數(shù)是一個(gè)純函數(shù)。它不管獲取數(shù)據(jù)，只管解析。這是一種常見的 Haskell 編程方法。通過把數(shù)據(jù)的獲取和處理分開，我們可以很方便地控制從哪里獲取數(shù)據(jù)。
我們用 ByteString 類型來存儲(chǔ)灰度數(shù)據(jù)，因?yàn)樗容^節(jié)省空間。由于 PGM 文件以 ASCII 字符串開頭，文件內(nèi)容又是二進(jìn)制數(shù)據(jù)，我們同時(shí)載入兩種形式的 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 類型是惰性的還是嚴(yán)格的，因此我們隨便選了惰性的版本。
我們用一個(gè)直白的數(shù)據(jù)類型來表示 PGM 圖像。
-- file: ch10/PNM.hs
data Greymap = Greymap {
greyWidth :: Int
, greyHeight :: Int
, greyMax :: Int
, greyData :: L.ByteString
} deriving (Eq)
通常來說，Haskell 的 Show 實(shí)例會(huì)生成數(shù)據(jù)的字符串表示，我們還可以用 read 讀回來。然而，對(duì)于一個(gè)位圖圖像文件來說，這可能會(huì)生成一個(gè)非常大的字符串，比如當(dāng)你對(duì)一張照片調(diào)用 show 的時(shí)候?；谶@個(gè)原因，我們不準(zhǔn)備讓編譯器自動(dòng)為我們派生 Show 實(shí)例；我們會(huì)自己實(shí)現(xiàn)，并刻意簡(jiǎn)化它。
-- file: ch10/PNM.hs
instance Show Greymap where
show (Greymap w h m _) = "Greymap " ++ show w ++ "x" ++ show h + " " ++ show m
我們的 Show 實(shí)例故意沒打印位圖數(shù)據(jù)，也就沒必要寫 Read 實(shí)例了，因?yàn)槲覀儫o法從 show 的結(jié)果重構(gòu) Greymap。
解析函數(shù)的類型顯而易見。
-- file: ch10/PNM.hs
parseP5 :: L.ByteString -> Maybe (Greymap, L.ByteString)
這個(gè)函數(shù)以一個(gè) ByteString 為參數(shù)，如果解析成功的話，它返回一個(gè)被解析的 Greymap 值以及解析之后剩下的字符串，剩下的字符串以后會(huì)用到。
解析函數(shù)必須一點(diǎn)一點(diǎn)處理輸入數(shù)據(jù)。首先，我們必須確認(rèn)我們正在處理的是原始 PGM 文件；然后，我們處理頭信息中的數(shù)字；最后我們處理位圖數(shù)據(jù)。下面是是一種比較初級(jí)的實(shí)現(xiàn)方法，我們會(huì)在它的基礎(chǔ)上不斷改進(jìn)。
-- 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)
這段代碼非常直白，它把所有的解析放在了一個(gè)長(zhǎng)長(zhǎng)的梯形 case 表達(dá)式中。每個(gè)函數(shù)在處理完它所需要的部分后會(huì)把剩余的 ByteString 返回。我們?cè)侔堰@部分傳給下個(gè)函數(shù)。像這樣我們將結(jié)果依次解構(gòu)，如果解析失敗就返回 Nothing，否則便又向最終結(jié)邁近了一步。下面是我們?cè)诮馕鲞^程中用到的函數(shù)的定義。它們的類型被注釋掉了因?yàn)橐呀?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ù)雖然能用，但它的代碼風(fēng)格卻并不令人滿意。它不斷挪向屏幕右側(cè)，非常明顯，再來個(gè)稍微復(fù)雜點(diǎn)的函數(shù)它就要橫跨屏幕了。我們不斷構(gòu)建和解構(gòu) Maybe 值，只在 Just 匹配特定值的時(shí)候才繼續(xù)。所有這些相似的 case 表達(dá)式就是“樣板代碼”，它掩蓋了我們真正要做的事情?？偠灾?，這段代碼需要抽象重構(gòu)。
退一步看，我們能觀察到兩種模式。第一，很多我們用到的函數(shù)都有相似的類型，它們最后一個(gè)參數(shù)都是 ByteString，返回值類型都是 Maybe。第二，parseP5 函數(shù)不斷解構(gòu) Maybe 值，然后要么失敗退出，要么把展開之后的值傳給下個(gè)函數(shù)。
我們很容易就能寫個(gè)函數(shù)來體現(xiàn)第二種模式。
-- file: ch10/PNM.hs
(>>?) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>? _ = Nothing
Just v >>? f = f v
(>>?) 函數(shù)非常簡(jiǎn)單：它接受一個(gè)值作為左側(cè)參數(shù)，一個(gè)函數(shù) f 作為右側(cè)參數(shù)。如果值不為 Nothing，它就把函數(shù) f 應(yīng)用在 Just 構(gòu)造器中的值上。我們把這個(gè)函數(shù)定義為操作符這樣它就能把別的函數(shù)串聯(lián)在一起了。最后，我們沒給 (>>?) 定義結(jié)合度，因此它默認(rèn)為 infixl9 （左結(jié)合，優(yōu)先級(jí)最高的操作符）。換言之，a>>?b>>?c 會(huì)從左向右求值，就像 (a>>?b)>>?c) 一樣。
有了這個(gè)串聯(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)
理解這個(gè)函數(shù)的關(guān)鍵在于理解其中的鏈。每個(gè) (>>?) 的左側(cè)都是一個(gè) Maybe 值，右側(cè)都是一個(gè)返回 Maybe 值的函數(shù)。這樣，Maybe 值就可以不斷傳給后續(xù) (>>?) 表達(dá)式。
我們新增了 skipSpace 函數(shù)用來提高可讀性。通過這些改進(jìn)，我們已將代碼長(zhǎng)度減半。通過移除樣板 case 代碼，代碼變得更容易理解。
盡管在匿名（lambda）函數(shù)中我們已經(jīng)警告過不要過度使用匿名函數(shù)，在上面的函數(shù)鏈中我們還是用了一些。因?yàn)檫@些函數(shù)太小了，給它們命名并不能提高可讀性。
隱式狀態(tài)
到這里還沒完。我們的代碼顯式地用序?qū)鬟f結(jié)果，其中一個(gè)元素代表解析結(jié)果的中間值，另一個(gè)代表剩余的 ByteString 值。如果我們想擴(kuò)展代碼，比方說記錄已經(jīng)處理過的字節(jié)數(shù)，以便在解析失敗時(shí)報(bào)告出錯(cuò)位置，那我們已經(jīng)有8個(gè)地方要改了，就為了把序?qū)Ω某扇M。
這使得本來就沒多少的代碼還很難修改。問題在于用模式匹配從序?qū)χ腥≈担何覀兗僭O(shè)了我們總是會(huì)用序?qū)?，并且把這種假設(shè)編進(jìn)了代碼。盡管模式匹配非常好用，但如果不慎重，我們還是會(huì)誤入歧途。
讓我們解決新代碼帶來的不便。首先，我們來修改解析狀態(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)在我們既可以記錄當(dāng)前剩余的字符串，也可以記錄相對(duì)于原字符串的偏移值了。更重要的改變是用了記錄語法：現(xiàn)在可以避免使用模式匹配來獲取狀態(tài)信息了，可以用 string 和 offset 訪問函數(shù)。
我們給解析狀態(tài)起了名字。給東西起名字方便我們推理。例如，我們現(xiàn)在可以這么看解析函數(shù)：它處理一個(gè)解析狀態(tài)，產(chǎn)生新解析狀態(tài)和一些別的信息。我們可以用 Haskell 類型直接表示。
-- file: ch10/Parse.hs
simpleParse :: ParseState -> (a, ParseState)
simpleParse = undefined
為了給用戶更多幫助，我們可以在解析失敗時(shí)報(bào)告一條錯(cuò)誤信息。只需對(duì)解析器的類型稍作修改即可。
-- file: ch10/Parse.hs
betterParse :: ParseState -> Either String (a, ParseState)
betterParse = undefined
為了防患于未然，我們最好不要將解析器的實(shí)現(xiàn)暴露給用戶。早些時(shí)候我們顯式地用序?qū)肀硎緺顟B(tài)，當(dāng)我們想擴(kuò)展解析器的功能時(shí)，我們馬上就遇到了麻煩。為了防止這種現(xiàn)象再次發(fā)生，我們用一個(gè) newtype 聲明來隱藏解析器的細(xì)節(jié)。
--file: ch10/Parse.hs
newtype Parse a = Parse {
runParse :: ParseState -> Either String (a, ParseState)
}
別忘了 newtype 只是函數(shù)在編譯時(shí)的一層包裝，它沒有運(yùn)行時(shí)開銷。我們想用這個(gè)函數(shù)時(shí)，我們用 runParser 訪問器。
如果我們的模塊不導(dǎo)出 Parse 值構(gòu)造器，我們就能確保沒人會(huì)不小心創(chuàng)建一個(gè)解析器，或者通過模式匹配來觀察其內(nèi)部構(gòu)造。
identity 解析器
我們來定義一個(gè)簡(jiǎn)單的 identity 解析器。它把輸入值轉(zhuǎn)為解析結(jié)果。從這個(gè)意義上講，它有點(diǎn)像 id 函數(shù)。
-- file: ch10/Parse.hs
identity :: a -> Parse a
identity a = Parse (\s -> Right (a, s))
這個(gè)函數(shù)沒動(dòng)解析狀態(tài)，只把它的參數(shù)當(dāng)成了解析結(jié)果。我們把函數(shù)體包裝成 Parse 類型以通過類型檢查。我們?cè)撛趺从盟ソ馕瞿兀?/p>
首先我們得把 Parse 包裝去掉從而得到里面的函數(shù)。這通過 runParse 函數(shù)實(shí)現(xiàn)。然后得創(chuàng)建一個(gè) ParseState，然后對(duì)其調(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)，我們都不用傳入字符串就可以試驗(yàn)我們的代碼。
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"
一個(gè)不檢查輸入的解析器可能有點(diǎn)奇怪，但很快我們就可以看到它的用處。同時(shí)，我們更加確信我們的類型是正確的，基本了解了代碼是如何工作的。
記錄語法、更新以及模式匹配
記錄語法的用處不僅僅在于訪問函數(shù)：我們可以用它來復(fù)制或部分改變已有值。就像下面這樣：
-- file: ch10/Parse.hs
modifyOffset :: ParseState -> Int64 -> ParseState
modifyOffset initState newOffset =
initState { offset = newOffset }
這會(huì)創(chuàng)建一個(gè)跟 initState 完全一樣的 ParseState 值，除了 offset 字段會(huì)替換成 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}
在大括號(hào)里我們可以給任意多的字段賦值，用逗號(hào)分開即可。
一個(gè)更有趣的解析器
現(xiàn)在來寫個(gè)解析器做一些有意義的事情。我們并不好高騖遠(yuǎn)：我們只想解析單個(gè)字節(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
定義中有幾個(gè)新函數(shù)。
L8.uncons 函數(shù)取出 ByteString 中的第一個(gè)元素。
ghci> L8.uncons (L8.pack "foo")
Just ('f',Chunk "oo" Empty)
ghci> L8.uncons L8.empty
Nothing
getState 函數(shù)得到當(dāng)前解析狀態(tài)，putState 函數(shù)更新解析狀態(tài)。bail 函數(shù)終止解析并報(bào)告錯(cuò)誤。(==>) 函數(shù)把解析器串聯(lián)起來。我們馬上就會(huì)詳細(xì)介紹這些函數(shù)。
Note
Hanging lambdas
獲取和修改解析狀態(tài)
parseByte 函數(shù)并不接受解析狀態(tài)作為參數(shù)。相反，它必須調(diào)用 getState 來得到解析狀態(tài)的副本，然后調(diào)用 putState 將當(dāng)前狀態(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ù)的時(shí)候，記得序?qū)ψ笤貫?Parse 結(jié)果，右元素為當(dāng)前 ParseState。這樣理解起來會(huì)比較容易。
getState 將當(dāng)前解析狀態(tài)展開，這樣調(diào)用者就能訪問里面的字符串。putState 將當(dāng)前解析狀態(tài)替換為一個(gè)新狀態(tài)。(==>) 鏈中的下一個(gè)函數(shù)將會(huì)使用這個(gè)狀態(tài)。
這些函數(shù)將顯式的狀態(tài)處理移到了需要它們的函數(shù)的函數(shù)體內(nèi)。很多函數(shù)并不關(guān)心當(dāng)前狀態(tài)是什么，因而它們也不會(huì)調(diào)用 getState 或 putState。跟之前需要手動(dòng)傳遞元組的解析器相比，現(xiàn)在的代碼更加緊湊。在之后的代碼中就能看到效果。
我們將解析狀態(tài)的細(xì)節(jié)打包放入 ParseState 類型中，然后我們通過訪問器而不是模式匹配來訪問它。隱式地傳遞解析狀態(tài)給我們帶來另外的好處。如果想增加解析狀態(tài)的信息，我們只需修改 ParseState 定義，以及需要新信息的函數(shù)體即可。跟之前通過模式匹配暴露狀態(tài)的解析器相比，現(xiàn)在的代碼更加模塊化：只有需要新信息的代碼會(huì)受到影響。
報(bào)告解析錯(cuò)誤
在定義 Parse 的時(shí)候我們已經(jīng)考慮了出錯(cuò)的情況。(==>) 組合子不斷檢查解析錯(cuò)誤并在錯(cuò)誤發(fā)生時(shí)終止解析。但我們還沒來得及介紹用來報(bào)告解析錯(cuò)誤的 bail 函數(shù)。
-- file: ch10/Parse.hs
bail :: String -> Parse a
bail err = Parse $ \s -> Left $
"byte offset " ++ show (offset s) ++ ": " ++ err
調(diào)用 bail 之后，(==>) 會(huì)模式匹配包裝了錯(cuò)誤信息的 Left 構(gòu)造器，并且不會(huì)調(diào)用下一個(gè)解析器。這使得錯(cuò)誤信息可以沿著調(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ù)體很有趣，還稍微有點(diǎn)復(fù)雜。回想一下，Parse 類型表示一個(gè)被包裝的函數(shù)。既然 (==>) 函數(shù)把兩個(gè) Parse 串聯(lián)起來并產(chǎn)生第三個(gè)，它也必須返回一個(gè)被包裝的函數(shù)。
這個(gè)函數(shù)做的并不多：它僅僅創(chuàng)建了一個(gè)閉包（closure）用來記憶 firstParser 和 secondParser 的值。
Note
閉包是一個(gè)函數(shù)和它所在的環(huán)境，也就是它可以訪問的變量。閉包在 Haskell 中很常見。例如，(+5) 就是一個(gè)閉包。實(shí)現(xiàn)的時(shí)候必須將 5 記錄為 (+) 操作符的第二個(gè)參數(shù)，這樣得到的函數(shù)才能把 5 加給它的參數(shù)。
在應(yīng)用 parse 之前，這個(gè)閉包不會(huì)被展開應(yīng)用。應(yīng)用的時(shí)候，它會(huì)求值 firstParser 并檢查它的結(jié)果。如果解析失敗，閉包也會(huì)失敗。否則，它會(huì)把解析結(jié)果及 newState 傳給 secondParser。
這是非常具有想象力、非常微妙的想法：我們實(shí)際上用了一個(gè)隱藏的參數(shù)將 ParseState 在 Parse 鏈之間傳遞。（我們?cè)谥髱渍逻€會(huì)碰到這樣的代碼，所以現(xiàn)在不懂也沒有關(guān)系。）
Functor 簡(jiǎn)介
現(xiàn)在我們對(duì) map 函數(shù)已經(jīng)有了一個(gè)比較詳細(xì)的了解，它把函數(shù)應(yīng)用在列表的每一個(gè)元素上，并返回一個(gè)可能包含另一種類型元素的列表。
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ù)這種行為在別的實(shí)例中可能有用。例如，考慮一棵二叉樹。
-- file: ch10/TreeMap.hs
data Tree a = Node (Tree a) (Tree a)
| Leaf a
deriving (Show)
如果想把一個(gè)字符串樹轉(zhuǎn)成一個(gè)包含這些字符串長(zhǎng)度的樹，我們可以寫個(gè)函數(shù)來實(shí)現(xiàn)：
-- file: ch10/TreeMap.hs
treeLengths (Leaf s) = Leaf (length s)
treeLengths (Node l r) = Node (treeLengths l) (treeLengths r)
我們?cè)囍鴮ふ乙恍┛赡苻D(zhuǎn)成通用函數(shù)的模式，下面就是一個(gè)可能的模式。
-- 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 提供了一個(gè)眾所周知的類型類來進(jìn)一步一般化 treeMap。這個(gè)類型類叫做 Functor，它只定義了一個(gè)函數(shù) fmap。
-- file: ch10/TreeMap.hs
class Functor f where
fmap :: (a -> b) -> f a -> f b
我們可以把 fmap 當(dāng)做某種提升函數(shù)，就像我們?cè)?Avoiding boilerplate with lifting(fix link) 一節(jié)中介紹的那樣。它接受一個(gè)參數(shù)為普通值 a->b 的函數(shù)并把它提升為一個(gè)參數(shù)為容器 fa->fb 的函數(shù)。其中 f 是容器的類型。
舉個(gè)例子，如果我們用 Tree 替換類型變量 f，fmap 的類型就會(huì)跟 treeMap 的類型相同。事實(shí)上我們可以用 treeMap 作為 fmap 對(duì) Tree 的實(shí)現(xiàn)。
-- file: ch10/TreeMap.hs
instance Functor Tree where
fmap = treeMap
我們可以用 map 作為 fmap 對(duì)列表的實(shí)現(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 實(shí)例，如列表和 Maybe。
-- file: ch10/TreeMap.hs
instance Functor Maybe where
fmap _ Nothing = Nothing
fmap f (Just x) = Just (f x)
Maybe 的這個(gè)實(shí)例很清楚地表明了 fmap 要做什么。對(duì)于類型的每一個(gè)構(gòu)造器，它都必須給出對(duì)應(yīng)的行為。例如，如果值被包裝在 Just 里，fmap 實(shí)現(xiàn)把函數(shù)應(yīng)用在展開之后的值上，然后再用 Just 重新包裝起來。
Functor 的定義限制了我們能用 fmap 做什么。例如，如果一個(gè)類型有且僅有一個(gè)類型參數(shù)，我們才能給它實(shí)現(xiàn) Functor 實(shí)例。
舉個(gè)例子，我們不能給 Eitherab 或者 (a,b) 寫 fmap 實(shí)現(xiàn)，因?yàn)樗鼈冇袃蓚€(gè)類型參數(shù)。我們也不能給 Bool 或者 Int 寫，因?yàn)樗鼈儧]有類型參數(shù)。
另外，我們不能給類型定義添加任何約束。這是什么意思呢？為了搞清楚，我們來看一個(gè)正常的 data 定義和它的 Functor 實(shí)例。
-- file: ch10/ValidFunctor.hs
data Foo a = Foo a
instance Functor Foo where
fmap f (Foo a) = Foo (f a)
當(dāng)我們定義新類型時(shí)，我們可以在 data 關(guān)鍵字之后加一個(gè)類型約束。
-- file: ch10/ValidFunctor.hs
data Eq a => Bar a = Bar a
instance Functor Bar where
fmap f (Bar a) = Bar (f a)
這意味著只有當(dāng) a 是 Eq 類型類的成員時(shí)，它才能被放進(jìn) Foo。然而，這個(gè)約束卻讓我們無法給 Bar 寫 Functor 實(shí)例。
*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.
給類型定義加約束不好
給類型定義加約束從來就不是什么好主意。它的實(shí)質(zhì)效果是強(qiáng)迫你給每一個(gè)用到這種類型值的函數(shù)加類型約束。假設(shè)我們現(xiàn)在有一個(gè)棧數(shù)據(jù)結(jié)構(gòu)，我們想通過訪問它來看看它的元素是否按順序排列。下面是數(shù)據(jù)類型的一個(gè)簡(jiǎn)單實(shí)現(xiàn)。
-- file: ch10/TypeConstraint.hs
data (Ord a) => OrdStack a = Bottom
| Item a (OrdStack a)
deriving (Show)
如果我們想寫一個(gè)函數(shù)來看看它是不是升序的（即每個(gè)元素都比它下面的元素大），很顯然，我們需要 Ord 約束來進(jìn)行兩兩比較。
-- file: ch10/TypeConstraint.hs
isIncreasing :: (Ord a) => OrdStack a -> Bool
isIncreasing (Item a rest@(Item b _))
| a < b = isIncreasing rest
| otherwise = False
isIncreasing _ = True
然而，由于我們?cè)陬愋吐暶魃霞恿祟愋图s束，它最后也影響到了某些不需要它的地方：我們需要給 push 加上 Ord 約束，但事實(shí)上它并不關(guān)心棧里元素的順序。
-- file: ch10/TypeConstraint.hs
push :: (Ord a) => a -> OrdStack a -> OrdStack a
push a s = Item a s
如果你把 Ord 約束刪掉，push 定義便無法通過類型檢查。
正是由于這個(gè)原因，我們之前給 Bar 寫 Functor 實(shí)例沒有成功：它要求 fmap 的類型簽名加上 Eq 約束。
我們現(xiàn)在已經(jīng)嘗試性地確定了 Haskell 里給類型簽名加類型約束并不是一個(gè)好的特性，那有什么好的替代嗎？答案很簡(jiǎn)單：不要在類型定義上加類型約束，在需要它們的函數(shù)上加。
在這個(gè)例子中，我們可以刪掉 OrdStack 和 push 上的 Ord。isIncreasing 還需要，否則便無法調(diào)用 (<)?，F(xiàn)在我們只在需要的地方加類型約束了。這還有一個(gè)更深遠(yuǎn)的好處：類型簽名更準(zhǔn)確地表示了每個(gè)函數(shù)的真正需求。
大多數(shù) Haskell 容器遵循這個(gè)模式。Data.Map 模塊里的 Map 類型要求它的鍵是排序的，但類型本身卻沒有這個(gè)約束。這個(gè)約束是通過 insert 這樣的函數(shù)來表達(dá)的，因?yàn)檫@里需要它，在 size 上卻沒有，因?yàn)樵谶@里順序無關(guān)緊要。
fmap 的中綴使用
你經(jīng)常會(huì)看到 fmap 作為操作符使用：
ghci> (1+) `fmap` [1,2,3] ++ [4,5,6]
[2,3,4,4,5,6]
也許你感到奇怪，原始的 map 卻幾乎從不這樣使用。
我們這樣使用 fmap 一個(gè)可能的原因是可以省略第二個(gè)參數(shù)的括號(hào)。括號(hào)越少讀代碼也就越容易。
ghci> fmap (1+) ([1,2,3] ++ [4,5,6])
[2,3,4,5,6,7]
如果你真的想把 fmap 當(dāng)做操作符用，Control.Applicative 模塊包含了作為 fmap 別名的 (<$>) 操作符。
當(dāng)我們返回之前寫的代碼時(shí)，我們會(huì)發(fā)現(xiàn)這對(duì)解析很有用。
靈活實(shí)例
你可能想給 EitherIntb 類型實(shí)現(xiàn) Functor 實(shí)例，因?yàn)樗挥幸粋€(gè)類型參數(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)不能保證檢查這種實(shí)例的約束會(huì)終結(jié)。非終結(jié)的約束檢查會(huì)導(dǎo)致編譯器進(jìn)入死循環(huán)，所以這種形式的實(shí)例是被禁止的。
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 標(biāo)準(zhǔn)更強(qiáng)大。出于可移植性的考慮，默認(rèn)情況下，它是運(yùn)行在兼容 Haskell 98 的模式下的。 我們可以通過一個(gè)編譯命令允許更靈活的實(shí)例。
-- file: ch10/EitherIntFlexible.hs
{-# LANGUAGE FlexibleInstances #-}
instance Functor (Either Int) where
fmap _ (Left n) = Left n
fmap f (Right r) = Right (f r)
這個(gè)命令內(nèi)嵌于 LANGUAGE 編譯選項(xiàng)。
有了 Functor 實(shí)例，我們來試試 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 的思考
對(duì)于 Functor 如何工作，我們做了一些隱式的假設(shè)。把它們說清楚并當(dāng)成規(guī)則去遵守非常有用，因?yàn)檫@會(huì)讓我們把 Functor 當(dāng)成統(tǒng)一的、行為規(guī)范的對(duì)象。規(guī)則只有兩個(gè)，并且非常簡(jiǎn)單。
第一條規(guī)則是 Functor 必須保持身份（preserve identity）。也就是說，應(yīng)用 fmapid 應(yīng)該返回相同的值。
ghci> fmap id (Node (Leaf "a") (Leaf "b"))
Node (Leaf "a") (Leaf "b")
第二條規(guī)則是 Functor 必須是可組合的。也就是說，把兩個(gè) 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 的影響，只有對(duì)應(yīng)的值會(huì)改變。
ghci> fmap odd (Just 1)
Just True
ghci> fmap odd Nothing
Nothing
如果你要寫 Functor 實(shí)例，最好把這些規(guī)則記在腦子里，并且最好測(cè)試一下，因?yàn)榫幾g器不會(huì)檢查我們提到的規(guī)則。另一方面，如果你只是用 Functor，這些規(guī)則又如此自然，根本沒必要記住。它們只是把一些“照我說的做”的直覺概念形式化了。下面是期望行為的偽代碼表示。
-- file: ch10/FunctorLaws.hs
fmap id == id
fmap (f . g) == fmap f . fmap g
給 Parse 寫一個(gè) Functor 實(shí)例
對(duì)于到目前為止我們研究過的類型而言，fmap 的期望行為非常明顯。然而由于 Parse 的復(fù)雜度，對(duì)于它而言 fmap 的期望行為并沒有這么明顯。一個(gè)合理的猜測(cè)是我們要 fmap 的函數(shù)應(yīng)該應(yīng)用到當(dāng)前解析的結(jié)果上，并保持解析狀態(tài)不變。
-- file: ch10/Parse.hs
instance Functor Parse where
fmap f parser = parser ==> \result ->
identity (f result)
定義很容易理解，我們來快速做幾個(gè)實(shí)驗(yàn)看看我們是否遵守了 Functor 規(guī)則。
首先我們檢查身份是否被保持。我們?cè)谝淮螒?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"
不錯(cuò)。再來試試應(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 實(shí)例同樣遵守了第二條規(guī)則，也就是保持結(jié)構(gòu)。失敗被保持為失敗，成功被保持為成功。
最后，我們確保可組合性被保持了。
ghci> parse ((chr . fromIntegral) <$> parseByte) input
Right 'f'
ghci> parse (chr <$> fromIntegral <$> parseByte) input
Right 'f'
通過這個(gè)簡(jiǎn)單的觀察，我們的 Functor 實(shí)例看起來行為規(guī)范。
利用 Functor 解析
我們討論 Functor 是有目的的：它讓我們寫出簡(jiǎn)潔、表達(dá)能力強(qiáng)的代碼。回想早先引入的 parseByte 函數(shù)。在重構(gòu) PGM 解析器使之使用新的解析架構(gòu)的過程中，我們經(jīng)常想用 ASCII 字符而不是 Word8 值。
盡管可以寫一個(gè)類似于 parseByte 的 parseChar 函數(shù)，我們現(xiàn)在可以利用 Parse 的 Functor 屬性來避免重復(fù)代碼。我們的 functor 接受一個(gè)解析結(jié)果并將一個(gè)函數(shù)應(yīng)用于它，因此我們需要的是一個(gè)把 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 來寫一個(gè)短小的“窺視”函數(shù)。如果我們?cè)谳斎胱址哪┪?，它?huì)返回 Nothing。否則，它返回下一個(gè)字符，但不作處理（也就是說，它觀察但不打擾當(dāng)前的解析狀態(tài)）。
-- file: ch10/Parse.hs
peekByte :: Parse (Maybe Word8)
peekByte = (fmap fst . L.uncons . string) <$> getState
定義 parseChar 時(shí)用到的提升把戲同樣也可以用于定義 peekChar。
-- file: ch10/Parse.hs
peekChar :: Parse (Maybe Char)
peekChar = fmap w2c <$> peekByte
注意到 peekByte 和 peekChar 分別兩次調(diào)用了 fmap，其中一次還是 (<$>)。這么做的原因是 Parse(Maybea) 類型是嵌在 Functor 中的 Functor。我們必須提升函數(shù)兩次使它能進(jìn)入內(nèi)部 Functor。
最后，我們會(huì)寫一個(gè)通用組合子，它是 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 []
再次說明，我們?cè)诤脦讉€(gè)地方都用到了 Functor（doubled up, when necessary）用以化簡(jiǎn)函數(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 []
當(dāng)你對(duì) Functor 不熟悉的時(shí)候，冗余的定義應(yīng)該會(huì)更好讀。但是，由于 Haskell 中 Functor 非常常見，你很快就會(huì)更習(xí)慣（包括讀和寫）簡(jiǎn)潔的表達(dá)。
重構(gòu) PGM 解析器
有了新的解析代碼，原始 PGM 解析函數(shù)現(xiàn)在變成了這個(gè)樣子：
-- 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ì)，然后當(dāng)性質(zhì)為 False 時(shí)終止解析并報(bào)告錯(cuò)誤信息。
未來方向
本章的主題是抽象。我們發(fā)現(xiàn)在函數(shù)鏈中傳遞顯式狀態(tài)并不理想，因此我們把這個(gè)細(xì)節(jié)抽象出來。在寫解析器的時(shí)候發(fā)現(xiàn)要重復(fù)用到一些代碼，我們把它們抽象成函數(shù)。我們引入了 Functor，它提供了一種映射到參數(shù)化類型的通用方法。
關(guān)于解析，我們?cè)诘?6章會(huì)討論一個(gè)使用廣泛并且靈活的解析庫 Parsec。在第14章中，我們會(huì)再次討論抽象，我們會(huì)發(fā)現(xiàn)用 Monad 可以進(jìn)一步化簡(jiǎn)這章的代碼。
Hackage 數(shù)據(jù)庫中存在不少包可以用來高效解析以 ByteString 表示的二進(jìn)制數(shù)據(jù)。在寫作時(shí)，最流行的是 binary，它易用且高效。
練習(xí)
-
給“純文本” PGM 文件寫解析器。
-
在對(duì)“原始” PGM 文件的描述中，我們省略了一個(gè)細(xì)節(jié)。如果頭信息中的“最大灰度”值小于256，那每個(gè)像素都會(huì)用單個(gè)字節(jié)表示。然而，它的最大范圍可達(dá)65535，這種情況下每個(gè)像素會(huì)以大端序的形式（最高有效位字節(jié)在前）用兩個(gè)字節(jié)來表示。
重寫原始 PGM 解析器使它能夠處理單字節(jié)和雙字節(jié)形式。
-
重寫解析器使得它能夠區(qū)分“原始”和“純文本” PGM 文件，并解析對(duì)應(yīng)的文件類型。
更多建議：