免費AI編程助手
第九章：I/O學習 —— 構建一個用于搜索文件系統(tǒng)的庫
第九章：I/O學習 —— 構建一個用于搜索文件系統(tǒng)的庫
自從電腦有了分層文件系統(tǒng)以來，“我知道有這個文件，但不知道它放在哪”這個問題就一直困擾著人們。1974年發(fā)布的Unix第五個版本引入的 find 命令，到今天仍在使用。查找文件的藝術已經走過了很長一段路：伴隨現(xiàn)代操作系統(tǒng)一起不斷發(fā)展的文件索引和搜索功能。
給程序員的工具箱里添加類似 find 這樣的功能依舊非常有價值，在本章，我們將通過編寫一個Haskell庫給我們的 find 命令添加更多功能，我們將通過一些有著不同的健壯度的方法來完成這個庫。
find命令
如果你不曾用過類Unix的系統(tǒng)，或者你不是個重度shell用戶，那么你很可能從未聽說過 find ，通過給定的一組目錄，它遞歸搜索每個目錄并且打印出每個匹配表達式的實體名稱。
-- file: ch09/RecursiveContents.hs
module RecursiveContents (getRecursiveContents) where
import Control.Monad (forM)
import System.Directory (doesDirectoryExist, getDirectoryContents)
import System.FilePath ((</>))
getRecursiveContents :: FilePath -> IO [FilePath]
getRecursiveContents topdir = do
names <- getDirectoryContents topdir
let properNames = filter (`notElem` [".", ".."]) names
paths <- forM properNames $ \name -> do
let path = topdir </> name
isDirectory <- doesDirectoryExist path
if isDirectory
then getRecursiveContents path
else return [path]
return (concat paths)
單個表達式可以識別像“符合這個全局模式的名稱”，“實體是一個文件”，“當前最后一個被修改的文件”以及其他諸如此類的表達式，通過and或or算子就可以把他們裝配起來構成更加復雜的表達式
簡單的開始：遞歸遍歷目錄
在投入設計我們的庫之前，先解決一些規(guī)模稍小的問題，我們第一個問題就是遞歸地列出一個目錄下面的所有內容和它的子目錄
filter 表達式確保一個目錄的列表不含特定的目錄名（比如代表當前目錄的 . 和上一級目錄的 .. ），如果忘記過濾這些，隨后的查找將陷入無限循環(huán)。
我們在之前的章節(jié)里完成了 forM 函數，它是參數顛倒后的 mapM 函數。
ghci> :m +Control.Monad
ghci> :type mapM
mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]
ghci> :type forM
forM :: (Monad m) => [a] -> (a -> m b) -> m [b]
循環(huán)體將檢查當前實體是否為目錄，如果是，則遞歸調用 getrecuresivacontents 函數列出這個目錄（的內容），如果否，則返回只含有當前實體名稱一個元素的列表，不要忘記 return 函數在 Haskell 中有特殊的含義，他通過monad的類型構造器包裝了一個值。
另一個值得注意的地方是變量 isDirectory 的使用，在命令式語言如 Python 中，我們通常用 ifos.path.isdir(path) 來表示，然而， doesDirectoryExist 函數是一個動作，它的返回類型是 IOBool 而非 Bool ，由于 if 表達式需要一個操作值為 bool 的表達式作為條件，我們使用 <- 來從io包裝器上得到這個動作的的 bool 返回值，這樣我們就能在 if 中使用這個干凈的無包裝的 bool 。
循環(huán)體中每一次迭代生成的結果都是名稱列表，因此 forM 的結果是 IO[[FilePath]] ，我們通過 concat 將它轉換為一個元素列表(從以列表為元素的列表轉換為不含列表元素的列表)
再次認識匿名和命名函數
在 Anonymous (lambda) functions [http://book.realworldhaskell.org/read/functional-programming.html#fp.anonymous] 這部分，我們列舉了一系列不使用匿名函數的原因，然而在這里，我們將使用它作為函數體，這是匿名函數在 Haskell 中最常見的用途之一。
我們已經在 froM 和 mapM 上看到使用函數作為參數的方式，許多循環(huán)體是程序中只出現(xiàn)一次的代碼塊。既然我們喜歡在循環(huán)中使用一個再也不會出現(xiàn)的循環(huán)體，那么為什么要給他們命名？
顯而易見，有時候我們需要在不同的循環(huán)中嵌入相同的代碼，這時候我們不應該使用匿名函數，把他們剪貼和復制進去，而是給這些匿名函數命名來調用，這樣顯得有意義一點
為什么提供 mapM 和 forM
存在兩個相同的函數看起來是有點奇怪，但接受參數的順序之間的差異使他們適用于不同的情況。
我們來考察下之前的例子，使用匿名函數作為循環(huán)體，如果我們使用 mapM 而非 forM ，我們將不得不把變量 properNames 放置到函數體的后邊，而為了讓代碼正確解析，我們就必須將整個匿名函數用括號包起來，或者用一個不必要的命名函數將它取代，自己嘗試下，拷貝上邊的代碼，用 mapM 代替 forM ，觀察代碼可讀性上有什么變化
相反，如果循環(huán)體是一個命名函數，而且我們要循環(huán)的列表是通過一個復雜表達式計算的，我們就找到了 mapM 的應用場景
這里需要遵守的代碼風格是無論通過 mapM 和 forM 都讓你寫出干凈的代碼，如果循環(huán)體或者循環(huán)中的表達式都很短，那么用哪個都無所謂，如果循環(huán)體很短，但數據很長，使用 mapM ，如果相反，則用 forM ，如果都很長，使用 let 或者 where 讓其中一個變短，通過這樣一些實踐，不同情況下那個實現(xiàn)最好就變得顯而易見
一個本地查找函數
我們可以使用 getRecursiveContents 函數作為一個內置的簡單文件查找器的基礎
-- file: ch09/SimpleFinder.hs
import RecursiveContents (getRecursiveContents)
simpleFind :: (FilePath -> Bool) -> FilePath -> IO [FilePath]
simpleFind p path = do
names <- getRecursiveContents path
return (filter p names)
上文的函數通過我們在過濾器中的謂詞來匹配 getRecursiveContents 函數返回的名字，每個通過謂詞判斷的名稱都是文件全路徑，因此如何完成一個像“查找所有擴展名以 .c 結尾的文件”的功能？
System.FilePath 模塊包含了許多有價值的函數來幫助我們操作文件名，在這個例子中，我們使用 takeExtension ：
ghci> :m +System.FilePath
ghci> :type takeExtension
takeExtension :: FilePath -> String
ghci> takeExtension "foo/bar.c"
Loading package filepath-1.1.0.0 ... linking ... done.
".c"
ghci> takeExtension "quux"
""
下面的代碼給我們一個包括獲得路徑，獲得擴展名，然后和.c進行比較的簡單功能的函數實現(xiàn)，
ghci> :load SimpleFinder
[1 of 2] Compiling RecursiveContents ( RecursiveContents.hs, interpreted )
[2 of 2] Compiling Main ( SimpleFinder.hs, interpreted )
Ok, modules loaded: RecursiveContents, Main.
ghci> :type simpleFind (\p -> takeExtension p == ".c")
simpleFind (\p -> takeExtension p == ".c") :: FilePath -> IO [FilePath]
simpleFind 在工作中有一些非常刺眼的問題，第一個就是謂詞并不能準確而完全的表達，他只關注文件夾中的實體名稱，而無法做到辨認這是個文件還是個目錄此類的事情，——而我們使用 simpleFind 的嘗試就是想列舉所文件和有和文件一樣擁有 .c 擴展名的文件夾
第二個問題是在 simpleFind 中我們無法控制它遍歷文件系統(tǒng)的方式，這是顯而易見的，想想在分布式版本控制系統(tǒng)中控制下的樹狀結構中查找一個源文件的問題吧，所有被控制的目錄都含有一個 .svn 的私有文件夾，每一個包含了許多我們毫不感興趣的子文件夾和文件，簡單的過濾所有包含 .svn 的路徑遠比僅僅在讀取時避免遍歷這些文件夾更加有效。例如，一個分布式源碼樹包含了45000個文件，30000個分布在1200個不同的.svn文件夾中，避免遍歷這1200個文件夾比過濾他們包含的30000個文件代價更低。
最后。 simpleFind 是嚴格的，因為它包含一系列IO元操作執(zhí)行構成的動作，如果我們有一百萬個文件要遍歷，我們需要等待很長一段時間才能得到一個包含一百萬個名字的巨大的返回值，這對用戶體驗和資源消耗都是噩夢，我們更需要一個只有當他們獲得結果的時才展示的結果流。
在接下來的環(huán)節(jié)里，我們將解決每個遇到的問題
謂詞在保持純粹的同時支持從貧類型到富類型
我們的謂詞只關注文件名，這將一系列有趣的操作排除在外，試想下，假如我們希望列出比某個給定值更大的文件呢？
面對這個問題的第一反應是查找 IO :我們的謂詞是 FilePath->Bool 類型，為什么不把它變成 FilePath->IOBool 類型？這將使我們所有的IO操作都成為謂詞的一部分，但這在顯而易見的好處之外引入一個潛在的問題，使用這樣一個謂詞存在各種可能的后果，比如一個有 IOa 類型返回的函數將有能力生成任何它想產生的結果。
讓我們在類型系統(tǒng)中尋找以寫出擁有更多謂詞，更少bug的代碼，我們通過避免污染IO來堅持斷言的純粹，這將確保他們不會產生任何不純的結果，同時我們給他們提供更多信息，這樣他們就可以在不必誘發(fā)潛在的危險的情況下獲得需要的表達式
Haskell 的 System.Directory 模塊提供了一個盡管受限但仍然有用的關于文件元數據的集合
ghci> :m +System.Directory
我們可以通過 doesFileExist 和 doesDirectoryExist 來判斷目錄實體是目錄還是文件，但暫時還沒有更多方式來查找這些年里出現(xiàn)的紛繁復雜的其他文件類型，比如管道，硬鏈接和軟連接。
ghci> :type doesFileExist
doesFileExist :: FilePath -> IO Bool
ghci> doesFileExist "."
Loading package old-locale-1.0.0.0 ... linking ... done.
Loading package old-time-1.0.0.0 ... linking ... done.
Loading package directory-1.0.0.0 ... linking ... done.
False
ghci> :type doesDirectoryExist
doesDirectoryExist :: FilePath -> IO Bool
ghci> doesDirectoryExist "."
True
getPermissions 函數讓我們確定當前對于文件或目錄的操作是否是合法：
ghci> :type getPermissions
getPermissions :: FilePath -> IO Permissions
ghci> :info Permissions
data Permissions
= Permissions {readable :: Bool,
writable :: Bool,
executable :: Bool,
searchable :: Bool}
-- Defined in System.Directory
instance Eq Permissions -- Defined in System.Directory
instance Ord Permissions -- Defined in System.Directory
instance Read Permissions -- Defined in System.Directory
instance Show Permissions -- Defined in System.Directory
ghci> getPermissions "."
Permissions {readable = True, writable = True, executable = False, searchable = True}
ghci> :type searchable
searchable :: Permissions -> Bool
ghci> searchable it
True
如果你無法回憶起 ghci 中變量 it 的特殊用法，回到第一章復習一下，如果我們的權限能夠列出它的內容，那么這個目錄就應該是可被搜索的，而文件則永遠是不可搜索的
最后， getModificationTime 告訴我們實體上次被修改的時間：
ghci> :type getModificationTime
getModificationTime :: FilePath -> IO System.Time.ClockTime
ghci> getModificationTime "."
Mon Aug 18 12:08:24 CDT 2008
如果我們像標準的Haskell代碼一樣對可移植性要求嚴格，這些函數就是我們手頭所有的一切(我們同樣可以通過黑客手段來獲得文件大小)，這些已經足夠讓我們明白所感興趣領域中的原則，而非讓我們浪費寶貴的時間對著一個例子冥思苦想，如果你需要寫滿足更多需求的代碼， System.Posix 和 System.Win32 模塊提供關于當代兩種計算平臺的更多文件元數據的細節(jié)。 Hackage 中同樣有一個 unix-compat 包，提供windows下的類unix的api 。
新的富類型謂詞需要關注的數據段到底有幾個？自從我們可以通過 Permissions 來判斷實體是文件還是目錄之后，我們就不再需要獲得 doesFileExist 和 doesDirectoryExist 的結果，因此一個謂詞需要關注的輸入有四個。
-- file: ch09/BetterPredicate.hs
import Control.Monad (filterM)
import System.Directory (Permissions(..), getModificationTime, getPermissions)
import System.Time (ClockTime(..))
import System.FilePath (takeExtension)
import Control.Exception (bracket, handle)
import System.IO (IOMode(..), hClose, hFileSize, openFile)
-- the function we wrote earlier
import RecursiveContents (getRecursiveContents)
type Predicate = FilePath -- path to directory entry
-> Permissions -- permissions
-> Maybe Integer -- file size (Nothing if not file)
-> ClockTime -- last modified
-> Bool
這一謂詞類型只是一個有四個參數的函數的同義詞，他將給我們節(jié)省一些鍵盤工作和屏幕空間。
注意這一返回值是 Bool 而非 IOBool ，謂詞需要保證純粹，而且不能表現(xiàn)IO，在擁有這種類型以后，我們的查找函數仍然顯得非常空白。
-- file: ch09/BetterPredicate.hs
-- soon to be defined
getFileSize :: FilePath -> IO (Maybe Integer)
betterFind :: Predicate -> FilePath -> IO [FilePath]
betterFind p path = getRecursiveContents path >>= filterM check
where check name = do
perms <- getPermissions name
size <- getFileSize name
modified <- getModificationTime name
return (p name perms size modified)
先來閱讀代碼，由于隨后將討論 getFileSize 的某些細節(jié)，因此現(xiàn)在暫時先跳過它。
我們無法使用 filter 來調用我們的謂詞，因為 p 的純粹代表他不能作為IO收集元數據的方式
這讓我們將目光轉移到一個并不熟悉的函數 filterM 上，它的動作就像普通的 filter 函數，但在這種情況下，它在 IOmonad 操作中使用它的謂詞，進而通過謂詞表現(xiàn)IO：
ghci> :m +Control.Monad
ghci> :type filterM
filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
check 謂詞是純謂詞 p 的IO功能包裝器，他執(zhí)行了所有IO發(fā)生在 p 上的可能引起負面效果的任務，因此我們可以使 p 對負面效果免疫，在收集完元數據后， check 調用 p ，通過 return 語句包裝 p 的IO返回結果
安全的獲得一個文件的大小
即使 System.Directory 不允許我們獲得一個文件的大小，我們仍可以使用 System.IO 的類似接口完成這項任務，它包含了一個名為 hFileSize 的函數，這一函數返回打開文件的字節(jié)數，下面是他的簡單調用實例：
-- file: ch09/BetterPredicate.hs
simpleFileSize :: FilePath -> IO Integer
simpleFileSize path = do
h <- openFile path ReadMode
size <- hFileSize h
hClose h
return size
當這個函數工作時，他還不能完全為我們所用，在 betterFind 中，我們在目錄下的任何實體上調用 getFileSize ，如果實體不是一個文件或者大小被 Just 包裝起來，他應當返回一個空值，而當實體不是文件或者沒有被打開時（可能是由于權限不夠），這個函數會拋出一個異常然后返回一個未包裝的大小。
下文是安全的用法：
-- file: ch09/BetterPredicate.hs
saferFileSize :: FilePath -> IO (Maybe Integer)
saferFileSize path = handle (\_ -> return Nothing) $ do
h <- openFile path ReadMode
size <- hFileSize h
hClose h
return (Just size)
函數體幾乎完全一致，除了 handle 語句。
我們的異常捕捉在忽略通過的異常的同時返回一個空值，函數體唯一的變化就是允許通過 Just 包裝文件大小
saferFileSize 函數現(xiàn)在有正確的類型簽名，并且不會拋出任何異常，但他扔未能完全的正常工作，存在 openFile 會成功的目錄實體，但 hFileSize 會拋出異常，這將和被稱作命名管道的狀況一起發(fā)生，這樣的異常會被捕捉，但卻從未發(fā)起調用 hClose 。
當發(fā)現(xiàn)不再使用文件句柄，Haskell會自動關閉它，但這只有在運行垃圾回收時才會執(zhí)行，如果無法斷言，則延遲到下一次垃圾回收。
文件句柄是稀缺資源，稀缺性是通過操作系統(tǒng)強制保證的，在linux中，一個進程只能同時擁有1024個文件句柄。
不難想象這種場景，程序調用了一個使用 saferFileSize 的 betterFind 函數，在足夠的垃圾文件句柄被關閉之前，由于 betterFind 造成文件句柄數耗盡導致了程序崩潰
這是bug危害性的一方面：通過合并起來的不同的部分使得bug不易被排查，只有在 betterFind 訪問足夠多的非文件達到進程打開文件句柄數上限的時候才會被觸發(fā)，隨后在積累的垃圾文件句柄被關閉之前返回一個嘗試打開另一個文件的調用。
任何程序內由無法獲得數據造成的后續(xù)錯誤都會讓事情變得更糟，直到垃圾回收為止。修正這樣一個bug需要程序結構本身支持，文件系統(tǒng)內容，如何關閉當前正在運行的程序以觸發(fā)垃圾回收
這種問題在開發(fā)中很容易被檢查出來，然而當他在上線之后出現(xiàn)（這些惡心的問題一向如此），就變得非常難以發(fā)覺
幸運的是，我們可以很容易避開這種錯誤，同時又能縮短我們的函數。
請求-使用-釋放循環(huán)
每當 openFile 成功之后我們就必須保證調用 hClose ， Control.Exception 模塊提供了 bracket 函數來支持這個想法：
ghci> :type bracket
bracket :: IO a -> (a -> IO b) -> (a -> IO c) -> IO c
bracket 函數需要三個動作作為參數，第一個動作需要一個資源，第二個動作釋放這個資源，第三個動作在這兩個中執(zhí)行，當資源被請求，我們稱他為操作動作，當請求動作成功，釋放動作隨后總是被調用，這保證了這個資源一直能夠被釋放，對通過的每個請求資源文件的操作，使用和釋放動作都是必要的。
如果一個異常發(fā)生在使用過程中， bracket 調用釋放動作并拋出異常，如果使用動作成功， bracket 調用釋放動作，同時返回使用動作返回的值。
我們現(xiàn)在可以寫一個完全安全的函數了，他將不會拋出異常，也不會積累可能在我們程序其他地方制造失敗的垃圾文件句柄數。
-- file: ch09/BetterPredicate.hs
getFileSize path = handle (\_ -> return Nothing) $
bracket (openFile path ReadMode) hClose $ \h -> do
size <- hFileSize h
return (Just size)
仔細觀察 bracket 的參數，首先打開文件，并且返回文件句柄，第二步關閉句柄，第三步在句柄上調用 hFileSize 并用 just 包裝結果返回
為了這個函數的正常工作，我們需要使用 bracket 和 handle ，前者保證我們不會積累垃圾文件句柄數，后者保證我們免于異常。
練習
- 調用 bracket 和 handle 的順序重要嗎，為什么
為謂詞而開發(fā)的領域特定語言
深入謂詞寫作的內部，我們的謂詞將檢查大于128kb的C++源文件：
-- file: ch09/BetterPredicate.hs
myTest path _ (Just size) _ =
takeExtension path == ".cpp" && size > 131072
myTest _ _ _ _ = False
這并不是令人感到愉快的工作，斷言需要四個參數，并且總是忽略其中的兩個，同時需要定義兩個等式，寫一些更有意義的謂詞代碼，我們可以做的更好。
有些時候，這種庫被用作嵌入式領域特定語言，我們通過編寫代碼的過程中通過編程語言的本地特性來優(yōu)雅的解決一些特定問題
第一步是寫一個返回當前函數的一個參數的函數，這個從參數中抽取路徑并傳給謂詞：
-- file: ch09/BetterPredicate.hs
pathP path _ _ _ = path
如果我們不能提供類型簽名， Haskell 將給這個函數提供一個通用類型，這在隨后會導致一個難以理解的錯誤信息，因此給 pathP 一個類型：
-- file: ch09/BetterPredicate.hs
type InfoP a = FilePath -- path to directory entry
-> Permissions -- permissions
-> Maybe Integer -- file size (Nothing if not file)
-> ClockTime -- last modified
-> a
pathP :: InfoP FilePath
我們已經創(chuàng)建了一個可以用做縮寫的類型，相似的結構函數，我們的類型代詞接受一個類型參數，如此我們可以分辨不同的結果類型：
-- file: ch09/BetterPredicate.hs
sizeP :: InfoP Integer
sizeP _ _ (Just size) _ = size
sizeP _ _ Nothing _ = -1
我們在這里做了些小動作，對那些我們無法打開的文件或者不是文件的東西我們返回的實體大小是 -1 。
事實上，瀏覽中可以看出我們在本章開始處定義謂詞類型的和 InfoPBool 一樣，因此我們可以合法的放棄謂詞類型。
pathP 和 sizeP 的用法？通過一些線索，我們發(fā)現(xiàn)可以在一個謂詞中使用它們（每個名稱中的前綴p代表斷言），從這開始事情就變得有趣起來：
-- file: ch09/BetterPredicate.hs
equalP :: (Eq a) => InfoP a -> a -> InfoP Bool
equalP f k = \w x y z -> f w x y z == k
equalP 的類型簽名值得注意，他接受一個 InfoPa ，同時兼容 pathP 和 sizeP ，他接受一個 a ，并返回一個被認為是謂詞同義詞的 InfoPBool ，換言之， equalP 構造了一個謂詞。
equalP 函數通過返回一個匿名函數工作，謂詞接受參數之后將他們轉成 f ，并將結果和 f 進行比對。
equalP 的相等強調了這一事實，我們認為它需要兩個參數，在 Haskell 柯里化處理了所有函數的情況下，通過這種方式寫 equalP 并無必要，我們可以避免匿名函數，同時通過柯里化來寫出表現(xiàn)相同的函數：
-- file: ch09/BetterPredicate.hs
equalP' :: (Eq a) => InfoP a -> a -> InfoP Bool
equalP' f k w x y z = f w x y z == k
在繼續(xù)我們的探險之前，先把寫好的模塊加載到 ghci 里去：
ghci> :load BetterPredicate
[1 of 2] Compiling RecursiveContents ( RecursiveContents.hs, interpreted )
[2 of 2] Compiling Main ( BetterPredicate.hs, interpreted )
Ok, modules loaded: RecursiveContents, Main.
讓我們來看看函數中的簡單謂詞能否正常工作：
ghci> :type betterFind (sizeP `equalP` 1024)
betterFind (sizeP `equalP` 1024) :: FilePath -> IO [FilePath]
注意我們并沒有直接調用 betterFind ，我們只是確定我們的表達式進行了類型檢查，現(xiàn)在我們需要更多的方法來列出大小為特定值的所有文件，之前的成功給了我們繼續(xù)下去的勇氣。
多用提升（lifting）少用模板
除了 equalP ，我們還將能夠編寫其他二進制函數，我們更希望不去寫他們每個的具體實現(xiàn)，因為這看起來只是重復工作：
-- file: ch09/BetterPredicate.hs
liftP :: (a -> b -> c) -> InfoP a -> b -> InfoP c
liftP q f k w x y z = f w x y z `q` k
greaterP, lesserP :: (Ord a) => InfoP a -> a -> InfoP Bool
greaterP = liftP (>)
lesserP = liftP (<)
為了完成這個，讓我們使用 Haskell 的抽象功能，定義 equalP 代替直接調用 == ，我們就可以把二進制函數作為參數傳入我們想調用的函數。
函數動作，比如 > ，以及將它轉換成另一個函數操作另一種上下文，在這里是 greaterP ，通過提升（lifting）將它引入到上下文，這解釋了當前函數名稱中l(wèi)ifting出現(xiàn)的原因，提升讓我們復用代碼并降低模板的使用，在本書的后半部分的內容中，我們將大量使用這一技術
當我們提升一個函數，我們通常將它轉換到原始類型和一個新版本——提升和未提升兩個版本
在這里，將 q 作為 liftP 的第一個參數是經過深思熟慮的，這使得我們可能寫一個對 greaterP 和 lesserP 都有意義的定義，實踐中發(fā)現(xiàn)，相較其他語言，Haskell 中參數的最佳適配成為api設計中最重要的一部分。語言內部要求參數轉換，在Haskell中放錯一個參數的位置就將失去程序的所有意義。
我們可以通過組合字（combinators）恢復一些意義，比如，直到2007年 forM 才加入 Control.Monad 模塊，在此之前，人們用的是 flipmapM 。
ghci> :m +Control.Monad
ghci> :t mapM
mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]
ghci> :t forM
forM :: (Monad m) => [a] -> (a -> m b) -> m [b]
ghci> :t flip mapM
flip mapM :: (Monad m) => [a] -> (a -> m b) -> m [b]
謂詞組合
如果我們希望組合謂詞，我們可以循著手邊最明顯的路徑來開始
-- file: ch09/BetterPredicate.hs
simpleAndP :: InfoP Bool -> InfoP Bool -> InfoP Bool
simpleAndP f g w x y z = f w x y z && g w x y z
現(xiàn)在我們知道了提升，他成為通過提升存在的布爾操作來削減代碼量的更自然的選擇。
-- file: ch09/BetterPredicate.hs
liftP2 :: (a -> b -> c) -> InfoP a -> InfoP b -> InfoP c
liftP2 q f g w x y z = f w x y z `q` g w x y z
andP = liftP2 (&&)
orP = liftP2 (||)
注意 liftP2 非常像我們之前的 liftP ，事實上，這更加通用，因為我們可以用 liftP 代替 liftP2 ：
-- file: ch09/BetterPredicate.hs
constP :: a -> InfoP a
constP k _ _ _ _ = k
liftP' q f k w x y z = f w x y z `q` constP k w x y z
Note
組合子
在Haskell中，我們更希望函數的傳入參數和返回值都是函數，就像組合子一樣
回到之前定義的 myTest 函數，現(xiàn)在我們可以使用一些幫助函數了。
-- file: ch09/BetterPredicate.hs
myTest path _ (Just size) _ =
takeExtension path == ".cpp" && size > 131072
myTest _ _ _ _ = False
在加入組合字以后這個函數會變成什么樣子：
-- file: ch09/BetterPredicate.hs
liftPath :: (FilePath -> a) -> InfoP a
liftPath f w _ _ _ = f w
myTest2 = (liftPath takeExtension `equalP` ".cpp") `andP`
(sizeP `greaterP` 131072)
由于操作文件名是如此平常的行為，我們加入了最終組合字 liftPath 。
定義并使用新算符
可以通過特定領域語言定義新的操作：
-- file: ch09/BetterPredicate.hs
(==?) = equalP
(&&?) = andP
(>?) = greaterP
myTest3 = (liftPath takeExtension ==? ".cpp") &&? (sizeP >? 131072)
這個括號在定義中是必要的，因為并未告訴Haskell有關之前和相關的操作，領域語言的操作如果沒有邊界（fixities）聲明將會被以 infixl9 之類的東西對待，計算從左到右，如果跳過這個括號，表達式將被解析成具有可怕錯誤的 (((liftPathtakeExtension)==?".cpp")&&?sizeP)>?131072 。
可以給操作添加邊界聲明，第一步是找出未提升的操作的，這樣就可以模仿他們了：
ghci> :info ==
class Eq a where
(==) :: a -> a -> Bool
...
-- Defined in GHC.Base
infix 4 ==
ghci> :info &&
(&&) :: Bool -> Bool -> Bool -- Defined in GHC.Base
infixr 3 &&
ghci> :info >
class (Eq a) => Ord a where
...
(>) :: a -> a -> Bool
...
-- Defined in GHC.Base
infix 4 >
學會這些就可以寫一個不用括號的表達式，卻和 myTest3 的解析結果一致的表達式了
控制遍歷
遍歷文件系統(tǒng)時，我們喜歡在需要遍歷的文件夾上有更多的控制權，簡便方法之一是可以在函數中允許給定文件夾的部分子文件夾通過，然后返回另一個列表，這個列表可以移除元素，也可以要求和原始列表不同，或兩者皆有，最簡單的控制函數就是id，原樣返回未修改的列表。
為了應付多種情況，我們正在嘗試改變部分表達，為了替代精心刻畫的函數類型 InfoP ，我們將使用一個普通代數數據類型來表達相同的含義
-- file: ch09/ControlledVisit.hs
data Info = Info {
infoPath :: FilePath
, infoPerms :: Maybe Permissions
, infoSize :: Maybe Integer
, infoModTime :: Maybe ClockTime
} deriving (Eq, Ord, Show)
getInfo :: FilePath -> IO Info
記錄語法給我們自由控制函數的權限，如 infoPath ， traverse 函數中的這種類型是簡單地，正如我們之前期望的那樣，如果需要一個文件或者目錄的信息，就調用 getInfo 函數：
-- file: ch09/ControlledVisit.hs
traverse :: ([Info] -> [Info]) -> FilePath -> IO [Info]
traverse 的定義很短，但很有分量：
-- file: ch09/ControlledVisit.hs
traverse order path = do
names <- getUsefulContents path
contents <- mapM getInfo (path : map (path </>) names)
liftM concat $ forM (order contents) $ \info -> do
if isDirectory info && infoPath info /= path
then traverse order (infoPath info)
else return [info]
getUsefulContents :: FilePath -> IO [String]
getUsefulContents path = do
names <- getDirectoryContents path
return (filter (`notElem` [".", ".."]) names)
isDirectory :: Info -> Bool
isDirectory = maybe False searchable . infoPerms
現(xiàn)在不再引入新技術，這就是我們遇到的最深奧的函數定義，一行行的深入他，解釋它每行為何是這樣，不過開始部分的那幾行沒什么神秘的，它們只是之前看到代碼的拷貝。
觀察變量 contents 的時候情況變得有趣起來，從左到右仔細閱讀，已經知道 names 是目錄實體的列表，同時確定當前目錄的所有元素都在這個列表中，這時通過 mapM 將 getInfo 附加到結果返回的路徑上。
接下來的這一行更深奧，繼續(xù)從左往右看，我們看到本行的最后一個元素以一個匿名函數的定義開始，并持續(xù)到這一段的結尾，給定一個Info值，函數或者遞歸訪問一個目錄（有額外的方法保證我們不在訪問這個路徑），或者返回當前值作為列表唯一元素的列表（來匹配遞歸的返回類型）。
函數通過 forM 獲得 order 返回 info 列表中的每個元素， forM 是使用者提供的遞歸控制函數。
本行的新上下文中使用提升技術， liftM 函數需要一個規(guī)則函數， concat ，并且提升到 IO 的monad操作，換言之，他需要 forM 通過 IO monad 操作的的返回值，并將 concat 附加其上（獲得一個 [Info] 類型的返回值，這也是我們所需要的）并將結果值返回給 IO monad 。
最后不要忘記定義 getInfo 函數：
-- file: ch09/ControlledVisit.hs
maybeIO :: IO a -> IO (Maybe a)
maybeIO act = handle (\_ -> return Nothing) (Just `liftM` act)
getInfo path = do
perms <- maybeIO (getPermissions path)
size <- maybeIO (bracket (openFile path ReadMode) hClose hFileSize)
modified <- maybeIO (getModificationTime path)
return (Info path perms size modified)
在此唯一值得記錄的事情是一個有用的組合字， maybeIO ，將一個可能拋出異常的 IO 操作轉換成用 Maybe 包裝的結果
練習
- 在以代數順序遍歷一個目錄樹時如何確定需要通過的內容。
- 使用 id 作為控制函數， traverseid 扮演一個前序遞歸樹，在子目錄之前他返回一個父目錄，寫一個控制函數讓 traverse 表現(xiàn)為一個后序遍歷，返回子目錄在父目錄之前。
- 使得《謂詞組合》一節(jié)里面的斷言和組合字可以處理新的 info 類型。
- 給 traverse 寫一個包裝器，讓你通過謂詞控制遞歸，并通過謂詞過濾返回結果
代碼深度，可讀性和學習過程
traverse 這樣深度的代碼在Haskell中并不多見，在這種表達方式中里學習的收獲是巨大的，同時也并不需要大量的練習才能以這種方式流利的閱讀和寫作代碼：
-- file: ch09/ControlledVisit.hs
traverseVerbose order path = do
names <- getDirectoryContents path
let usefulNames = filter (`notElem` [".", ".."]) names
contents <- mapM getEntryName ("" : usefulNames)
recursiveContents <- mapM recurse (order contents)
return (concat recursiveContents)
where getEntryName name = getInfo (path </> name)
isDirectory info = case infoPerms info of
Nothing -> False
Just perms -> searchable perms
recurse info = do
if isDirectory info && infoPath info /= path
then traverseVerbose order (infoPath info)
else return [info]
作為對比，這里有一個不那么復雜的代碼，這也許適合一個對Haskell了解不那么深入的程序員
這里所做的一切都是創(chuàng)建一個新的替代，通過部分應用（partial application）和函數組合（function composition）替代liberally，在 where 塊中我們已經定義了一些本地函數，在 maybe 組合子中，使用了 case 表達式，為了替代 liftM ，我們手動將 concat 提升。
并不是說深度是一個不好的特征， traverse 函數的每一行原始代碼都很短，我們引入一個本地變量和本地函數來保證代碼干凈且足夠短，命名注意可讀性，同時使用函數組合管道，最長的管道只含有三個元素。
編寫可維護的Haskell代碼核心是找到深度和可讀性的折中，能否做到這點取決于你的實踐層次：
- 成為Haskell程序員之前，Andrew并不知道使用標準庫的方式，為此付出的代價則是寫了一大堆不必要的重復代碼。
- Zack是一個有數月編程經驗的，并且精通通過( . )組合長管道的技巧。每當代碼需要改動，就需要重構一個管道，他無法更深入的理解已經存在的管道的意義，而這些管道也太脆弱而無法修正。
- Monica有相當時間的編程經驗，他對Haskell庫和編寫整潔的代碼非常熟悉，但他避免使用高深度的風格，她的代碼可維護，同時她還找到了一種簡單地方法來面對快速的需求變更
觀察迭代函數的另一種方法
相比原始的 betterFind 函數，迭代函數給我們更多控制權的同時仍存在一個問題，我們可以避免遞歸目錄，但我們不能過濾其他文件名直到我們獲得整個名稱樹，如果遞歸含有100000個文件的目錄的同時只關注其中三個，在獲得這三個需要的文件名之前需要給出一個含有10000個元素的表。
一個可能的方法是提供一個過濾器作為遞歸的新參數，我們將它應用到生成的名單中，這將允許我們獲得一個只包含我們需要元素的列表
然而，這個方法也存在缺點，假如說我們知道需要比三個多很多的實體組，并且這些實體組是這10000個我們需要遍歷實體中的前幾個，這種情況下就不需要訪問剩下的實體，這并不是個故弄玄虛的問題，舉個栗子，郵箱文件夾中存放了包含許多郵件信息的文件夾——就像一個有大量文件的目錄，那么代表郵箱的目錄含有數千個文件就很正常。
從另一個角度看，我們嘗試定位之前兩個遍歷函數的弱點：我們如何看待文件系統(tǒng)遍歷階級目錄下的一個文件夾？
相似的文件夾， foldr 和 foldl' ，干凈的生成遍歷并計算出一個結果，很難把這個想法從列表擴展到目錄樹，但我們仍樂于在 fold 中加入一個控制元素，我們將這個控制表達為一個代數數據類型：
-- file: ch09/FoldDir.hs
data Iterate seed = Done { unwrap :: seed }
| Skip { unwrap :: seed }
| Continue { unwrap :: seed }
deriving (Show)
type Iterator seed = seed -> Info -> Iterate seed
Iterator 類型給函數一個便于使用的別名，它需要一個種子和一個 info 值來表達這個目錄實體，并返回一個新種子和一個我們 fold 函數的說明，這個說明通過 Iterate 類型的構造器來表達：
- 如果這個構造器已經完成，遍歷將立即釋放，被 Done 包裹的值將作為結果返回。
- 如果這個說明被跳過，并且當前 info 代表一個目錄，遍歷將不在遞歸尋找這個目錄。
- 其他，這個便利仍將繼續(xù)，使用包裹值作為下一個調用 fold 函數的參數。
目錄邏輯上是左序的，因為我們開始從我們第一個遇到的實體開始 fold 操作，而每步中的種子是之前一步的結果。
-- file: ch09/FoldDir.hs
foldTree :: Iterator a -> a -> FilePath -> IO a
foldTree iter initSeed path = do
endSeed <- fold initSeed path
return (unwrap endSeed)
where
fold seed subpath = getUsefulContents subpath >>= walk seed
walk seed (name:names) = do
let path' = path </> name
info <- getInfo path'
case iter seed info of
done@(Done _) -> return done
Skip seed' -> walk seed' names
Continue seed'
| isDirectory info -> do
next <- fold seed' path'
case next of
done@(Done _) -> return done
seed'' -> walk (unwrap seed'') names
| otherwise -> walk seed' names
walk seed _ = return (Continue seed)
這部分代碼中有意思的部分很少，開始是通過 scoping 避免通過額外的參數，最高層 foldTree 函數只是 fold 的包裝器，用來揭開 fold 的最后結果的生成器。
由于 fold 是本地函數，我們不需要通過 foldTree 的 iter 變量來進入他，可以從外部進入，相似的， walk 也可以在外部看到 path 。
另一個需要指出的點是 walk 是一個尾遞歸，在我們最初的函數中用來替代一個匿名函數調用。通過外部控制，可以在任何需要的時候停止，這使得當 iterator 返回 Done 的時候就可以退出。
即使 fold 調用 walk ， walk 調用 fold 這樣的遞歸來遍歷子目錄，每個函數返回一個用 Iterate 包裝起來的種子，當 fold 被調用，并且返回， walk 檢查返回并觀察需要繼續(xù)還是退出，通過這種方式，一個 Done 的返回直接終止兩個函數中的所有遞歸調用。
實踐中一個 iterator 像什么，下面是一個觀察三個位圖文件（至多）的同時并不逆向遞歸元數據目錄的復雜例子：
-- file: ch09/FoldDir.hs
atMostThreePictures :: Iterator [FilePath]
atMostThreePictures paths info
| length paths == 3
= Done paths
| isDirectory info && takeFileName path == ".svn"
= Skip paths
| extension `elem` [".jpg", ".png"]
= Continue (path : paths)
| otherwise
= Continue paths
where extension = map toLower (takeExtension path)
path = infoPath info
為了使用這個需要調用 foldTreeatMostThreePictures[] ，它給我們一個 IO[FilePath] 類型的返回值。
當然， iterators 并不需要如此復雜，下面是個對目錄進行計數的代碼：
-- file: ch09/FoldDir.hs
countDirectories count info =
Continue (if isDirectory info
then count + 1
else count)
傳遞給 foldTree 的初始種子（seed）為數字零。
練習
- 修正 foldTree 來允許調用改變遍歷目錄實體的順序。
- foldTree 函數展示了前序遍歷，將它修正為允許調用方決定便利順序。
- 寫一個組合子的庫允許 foldTree 接收不同類型的 iterators ，你能寫出更簡潔的 iterators 嗎？
代碼指南
有許多好的Haskell程序員的習慣來自經驗，我們有一些通用的經驗給你，這樣你可以更快的寫出易于閱讀的代碼。
正如已經提到的，Haskell中永遠使用空格，而不是tab 。
如果你發(fā)現(xiàn)代碼里有個片段聰明到炸裂，停下來，然后思考下如果你離開代碼一個月是否還能懂這段代碼。
常規(guī)命名類型和變量一般是駱駝法，例如 myVariableName ，這種風格在Haskell中也同樣流行，不要去想你的其他命名習慣，如果你遵循一個不標準的慣例，那么你的代碼將會對其他人的眼睛造成折磨。
即使你已經用了Haskell一段時間，在你寫小函數之前花費幾分鐘的時間查閱庫函數，如果標準庫并沒有提供你需要的函數，你可能需要組合出一個新的函數來獲得你想要的結果。
組合函數的長管道難以閱讀，長意味著包含三個以上元素的序列，如果你有這樣一個管道，使用 let 或者 where 語句塊將它分解成若干個小部分，給每個管道元素一個有意義的名字，然后再將他們回填到代碼，如果你想不出一個有意義的名字，問下自己 能不能解釋這段代碼的功能，如果不能，簡化你的代碼。
即使在編輯器中很容易格式化長于八十列的代碼，寬度仍然是個重要問題，寬行在80行之外的內容通常會被截斷，這非常傷害可讀性，每一行不超過八十個字符，這樣你就可以寫入單獨的一行，這幫助你保持每一行代碼不那么復雜，從而更容易被人讀懂。
常用布局風格
只要你的代碼遵守布局規(guī)范，那么他并不會給人一團亂麻的感覺，因此也不會造成誤解，也就是說，有些布局風格是常用的。
in 關鍵字通常正對著 let 關鍵字，如下所示：
-- file: ch09/Style.hs
tidyLet = let foo = undefinedwei's
bar = foo * 2
in undefined
單獨列出 in 或者讓 in 在一系列等式之后跟著的寫法都是正確的，但下面這種寫法則會顯得很奇怪：
-- file: ch09/Style.hs
weirdLet = let foo = undefined
bar = foo * 2
in undefined
strangeLet = let foo = undefined
bar = foo * 2 in
undefined
與此相反，讓 do 在行尾跟著而非在行首單獨列出：
-- file: ch09/Style.hs
commonDo = do
something <- undefined
return ()
-- not seen very often
rareDo =
do something <- undefined
return ()
括號和分號即使合法也很少用到，他們的使用并不存在問題，只是讓代碼看起來奇怪，同時讓Haskell寫成的代碼不必遵守排版規(guī)則。
-- file: ch09/Style.hs
unusualPunctuation =
[ (x,y) | x <- [1..a], y <- [1..b] ] where {
b = 7;
a = 6 }
preferredLayout = [ (x,y) | x <- [1..a], y <- [1..b] ]
where b = 7
a = 6
如果等式的右側另起一行，通常在和他本行內，相關變量名或者函數定義的下方之前留出一些空格。
-- file: ch09/Style.hs
normalIndent =
undefined
strangeIndent =
undefined
空格縮進的數量有多種選擇，有時候在一個文件中，二，三，四格縮進都很正常，一個縮進也合法，但不常用，而且容易被誤讀。
寫 where 語句的縮進時，最好讓它分辨起來比較容易：
-- file: ch09/Style.hs
goodWhere = take 5 lambdas
where lambdas = []
alsoGood =
take 5 lambdas
where
lambdas = []
badWhere = -- legal, but ugly and hard to read
take 5 lambdas
where
lambdas = []
練習
即使本章內容指導你們完成文件查找代碼，但這并不意味著真正的系統(tǒng)編程，因為haskell移植的 IO 庫并不暴露足夠的消息給我們寫有趣和復雜的查詢。
- 把本章代碼移植到你使用平臺的 api 上， System.Posix 或者 System.Win32 。
- 加入查找文件所有者的功能，將這個屬性對謂詞可見。
更多建議：