第十章：代碼案例學習：解析二進制數據格式 · Real World Haskell 中文版

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