# 第十三章：數據結構 ## 關聯列表 我們常常會跟一些以鍵為索引的無序數據打交道。 舉個例子，UNIX 管理猿可能需要這么一個列表，它包含系統中所有用戶的 UID ，以及和這個 UID 相對應的用戶名。這個列表根據 UID 而不是數據的位置來查找相應的用戶名。換句話來說， UID 就是這個數據集的鍵。 Haskell 里有幾種不同的方法來處理這種結構的數據，最常用的兩個是關聯列表（association list）和 Data.Map 模塊提供的 Map 類型。 關聯列表非常簡單，易于使用。由于關聯列表由 Haskell 列表構成，因此所有列表操作函數都可以用于處理關聯列表。 另一方面， Map 類型在處理大數據集時，性能比關聯列表要好。 本章將同時介紹這兩種數據結構。 關聯列表就是包含一個或多個 (key,value) 元組的列表， key 和 value 可以是任意類型。一個處理 UID 和用戶名映射的關聯列表的類型可能是 [(Integer,String)] 。 [注：關聯列表的 key 必須是 Eq 類型的成員。] 關聯列表的構建方式和普通列表一樣。Haskell 提供了一個 Data.List.lookup 函數，用于在關聯列表中查找數據。這個函數的類型簽名為 Eqa=>a->[(a,b)]->Maybeb 。它的使用方式如下： ~~~ Prelude> let al = [(1, "one"), (2, "two"), (3, "three"), (4, "four")] Prelude> lookup 1 al Just "one" Prelude> lookup 5 al Nothing ~~~ lookup 函數的定義如下： ~~~ -- file: ch13/lookup.hs myLookup :: Eq a => a -> [(a, b)] -> Maybe b myLookup _ [] = Nothing myLookup key ((thiskey, thisval):rest) = if key == thiskey then Just thisval else myLookup key rest ~~~ lookup 在輸入列表為空時返回 Nothing 。如果輸入列表不為空，那么它檢查當前列表元素的 key 是否就是我們要找的 key ，如果是的話就返回和這個 key 對應的 value ，否則就繼續遞歸處理剩余的列表元素。 再來看一個稍微復雜點的例子。在 Unix/Linux 系統中，有一個 /etc/passwd 文件，這個文件保存了用戶名稱， UID，用戶的 HOME 目錄位置，以及其他一些數據。文件以行分割每個用戶的資料，每個數據域用冒號隔開： ~~~ root:x:0:0:root:/root:/bin/bash daemon:x:1:1:daemon:/usr/sbin:/bin/sh bin:x:2:2:bin:/bin:/bin/sh sys:x:3:3:sys:/dev:/bin/sh sync:x:4:65534:sync:/bin:/bin/sync games:x:5:60:games:/usr/games:/bin/sh man:x:6:12:man:/var/cache/man:/bin/sh lp:x:7:7:lp:/var/spool/lpd:/bin/sh mail:x:8:8:mail:/var/mail:/bin/sh news:x:9:9:news:/var/spool/news:/bin/sh jgoerzen:x:1000:1000:John Goerzen,,,:/home/jgoerzen:/bin/bash ~~~ 以下程序讀入并處理 /etc/passwd 文件，它創建一個關聯列表，使得我們可以根據給定 UID ，獲取相應的用戶名： ~~~ -- file: ch13/passwd-al.hs import Data.List import System.IO import Control.Monad(when) import System.Exit import System.Environment(getArgs) main = do -- Load the command-line arguments args <- getArgs -- If we don't have the right amount of args, give an error and abort when (length args /= 2) $ do putStrLn "Syntax: passwd-al filename uid" exitFailure -- Read the file lazily content <- readFile (args !! 0) -- Compute the username in pure code let username = findByUID content (read (args !! 1)) -- Display the result case username of Just x -> putStrLn x Nothing -> putStrLn "Could not find that UID" -- Given the entire input and a UID, see if we can find a username. findByUID :: String -> Integer -> Maybe String findByUID content uid = let al = map parseline . lines $ content in lookup uid al -- Convert a colon-separated line into fields parseline :: String -> (Integer, String) parseline input = let fields = split ':' input in (read (fields !! 2), fields !! 0) -- Takes a delimiter and a list. -- Break up the list based on the delimiter. split :: Eq a => a -> [a] -> [[a]] -- If the input is empty, the result is a list of empty lists. split _ [] = [[]] split delimiter str = let -- Find the part of the list before delimiter and put it in "before". -- The result of the list, including the leading delimiter, goes in "remainder". (before, remainder) = span (/= delimiter) str in before : case remainder of [] -> [] x -> -- If there is more data to process, -- call split recursively to process it split delimiter (tail x) ~~~ findByUID 是整個程序的核心，它逐行讀入并處理輸入，使用 lookup 從處理結果中查找給定 UID ： ~~~ *Main> findByUID "root:x:0:0:root:/root:/bin/bash" 0 Just "root" ~~~ parseline 讀入并處理一個字符串，返回一個包含 UID 和用戶名的元組： ~~~ *Main> parseline "root:x:0:0:root:/root:/bin/bash" (0,"root") ~~~ split 函數根據給定分隔符 delimiter 將一個文本行分割為列表： ~~~ *Main> split ':' "root:x:0:0:root:/root:/bin/bash" ["root","x","0","0","root","/root","/bin/bash"] ~~~ 以下是在本機執行 passwd-al.hs 處理 /etc/passwd 的結果： ~~~ $ runghc passwd-al.hs /etc/passwd 0 root $ runghc passwd-al.hs /etc/passwd 10086 Could not find that UID ~~~ ## Map 類型 Data.Map 模塊提供的 Map 類型的行為和關聯列表類似，但 Map 類型的性能更好。 Map 和其他語言提供的哈希表類似。不同的是， Map 的內部由平衡二叉樹實現，在 Haskell 這種使用不可變數據的語言中，它是一個比哈希表更高效的表示。這是一個非常明顯的例子，說明純函數式語言是如何深入地影響我們編寫程序的方式：對于一個給定的任務，我們總是選擇合適的算法和數據結構，使得解決方案盡可能地簡單和有效，但這些（純函數式的）選擇通常不同于命令式語言處理同樣問題時的選擇。 因為 Data.Map 模塊的一些函數和 Prelude 模塊的函數重名，我們通過 importqualifiedData.MapasMap 的方式引入模塊，并使用 Map.name 的方式引用模塊中的名字。 先來看看如何用幾種不同的方式構建 Map ： ~~~ -- file: ch13/buildmap.hs import qualified Data.Map as Map -- Functions to generate a Map that represents an association list -- as a map al = [(1, "one"), (2, "two"), (3, "three"), (4, "four")] -- Create a map representation of 'al' by converting the association -- list using Map.fromList mapFromAL = Map.fromList al -- Create a map representation of 'al' by doing a fold mapFold = foldl (\map (k, v) -> Map.insert k v map) Map.empty al -- Manually create a map with the elements of 'al' in it mapManual = Map.insert 2 "two" . Map.insert 4 "four" . Map.insert 1 "one" . Map.insert 3 "three" $ Map.empty ~~~ Map.insert 函數處理數據的方式非常『 Haskell 化』：它返回經過函數應用的輸入數據的副本。這種處理數據的方式在操作多個 Map 時非常有用，它意味著你可以像前面代碼中 mapFold 那樣使用 fold 來構建一個 Map ，又或者像 mapManual 那樣，串連起多個 Map.insert 調用。 [譯注：這里說『 Haskell 化』實際上就是『函數式化』，對于函數式語言來說，最常見的函數處理方式是接受一個輸入，然后返回一個輸出，輸出是另一個獨立的值，且原輸入不會被修改。] 現在，到 ghci 中驗證一下是否所有定義都如我們所預期的那樣工作： ~~~ Prelude> :l buildmap.hs [1 of 1] Compiling Main ( buildmap.hs, interpreted ) Ok, modules loaded: Main. *Main> al Loading package array-0.4.0.0 ... linking ... done. Loading package deepseq-1.3.0.0 ... linking ... done. Loading package containers-0.4.2.1 ... linking ... done. [(1,"one"),(2,"two"),(3,"three"),(4,"four")] *Main> mapFromAL fromList [(1,"one"),(2,"two"),(3,"three"),(4,"four")] *Main> mapFold fromList [(1,"one"),(2,"two"),(3,"three"),(4,"four")] *Main> mapManual fromList [(1,"one"),(2,"two"),(3,"three"),(4,"four")] ~~~ 注意， Map 并不保證它的輸出排列和原本的輸入排列一致，對比 mapManual 的輸入和輸出可以看出這一點。 Map 的操作方式和關聯列表類似。 Data.Map 模塊提供了一組函數，用于增刪 Map 元素，對 Map 進行過濾、修改和 fold ，以及在 Map 和關聯列表之間進行轉換。 Data.Map 模塊本身的文檔非常優秀，因此我們在這里不會詳細講解每個函數，而是在本章的后續內容中，通過例子來介紹這些概念。 ## 函數也是數據 Haskell 語言的威力部分在于它可以讓我們方便地創建并操作函數。 以下示例展示了怎樣將函數保存到記錄的域中： ~~~ -- file: ch13/funcrecs.hs -- Our usual CustomColor type to play with data CustomColor = CustomColor {red :: Int, green :: Int, blue :: Int} deriving (Eq, Show, Read) -- A new type that stores a name and a function. -- The function takes an Int, applies some computation to it, -- and returns an Int along with a CustomColor data FuncRec = FuncRec {name :: String, colorCalc :: Int -> (CustomColor, Int)} plus5func color x = (color, x + 5) purple = CustomColor 255 0 255 plus5 = FuncRec {name = "plus5", colorCalc = plus5func purple} always0 = FuncRec {name = "always0", colorCalc = \_ -> (purple, 0)} ~~~ 注意 colorCalc 域的類型：它是一個函數，接受一個 Int 類型值作為參數，并返回一個 (CustomColor,Int) 元組。 我們創建了兩個 FuncRec 記錄： plus5 和 always0 ，這兩個記錄的 colorCalc 域都總是返回紫色（purple）。 FuncRec 自身并沒有域去保存所使用的顏色，顏色的值被保存在函數當中 —— 我們稱這種用法為*閉包*。 以下是示例代碼： ~~~ *Main> :l funcrecs.hs [1 of 1] Compiling Main ( funcrecs.hs, interpreted ) Ok, modules loaded: Main. *Main> :t plus5 plus5 :: FuncRec *Main> name plus5 "plus5" *Main> :t colorCalc plus5 colorCalc plus5 :: Int -> (CustomColor, Int) *Main> (colorCalc plus5) 7 (CustomColor {red = 255, green = 0, blue = 255},12) *Main> :t colorCalc always0 colorCalc always0 :: Int -> (CustomColor, Int) *Main> (colorCalc always0) 7 (CustomColor {red = 255, green = 0, blue = 255},0) ~~~ 上面的程序工作得很好，但我們還想做一些更有趣的事，比如說，在多個域中使用同一段數據。可以使用一個類型構造函數來做到這一點： ~~~ -- file: ch13/funcrecs2.hs data FuncRec = FuncRec {name :: String, calc :: Int -> Int, namedCalc :: Int -> (String, Int)} mkFuncRec :: String -> (Int -> Int) -> FuncRec mkFuncRec name calcfunc = FuncRec {name = name, calc = calcfunc, namedCalc = \x -> (name, calcfunc x)} plus5 = mkFuncRec "plus5" (+ 5) always0 = mkFuncRec "always0" (\_ -> 0) ~~~ mkFuncRecs 函數接受一個字符串和一個函數作為參數，返回一個新的 FuncRec 記錄。以下是對 mkFuncRecs 函數的測試： ~~~ *Main> :l funcrecs2.hs [1 of 1] Compiling Main ( funcrecs2.hs, interpreted ) Ok, modules loaded: Main. *Main> :t plus5 plus5 :: FuncRec *Main> name plus5 "plus5" *Main> (calc plus5) 5 10 *Main> (namedCalc plus5) 5 ("plus5",10) *Main> let plus5a = plus5 {name = "PLUS5A"} *Main> name plus5a "PLUS5A" *Main> (namedCalc plus5a) 5 ("plus5",10) ~~~ 注意 plus5a 的創建過程：我們改變了 plus5 的 name 域，但沒有修改它的 namedCalc 域。這就是為什么調用 name 會返回新名字，而 namedCalc 依然返回原本使用 mkFuncRecs 創建時設置的名字 —— 除非我們顯式地修改域，否則它們不會被改變。 ## 擴展示例： /etc/password 以下是一個擴展示例，它展示了幾種不同的數據結構的用法，根據 /etc/passwd 文件的格式，程序處理并保存它的實體（entry）： ~~~ -- file: ch13/passwdmap.hs import Data.List import qualified Data.Map as Map import System.IO import Text.Printf(printf) import System.Environment(getArgs) import System.Exit import Control.Monad(when) {- | The primary piece of data this program will store. It represents the fields in a POSIX /etc/passwd file -} data PasswdEntry = PasswdEntry { userName :: String, password :: String, uid :: Integer, gid :: Integer, gecos :: String, homeDir :: String, shell :: String} deriving (Eq, Ord) {- | Define how we get data to a 'PasswdEntry'. -} instance Show PasswdEntry where show pe = printf "%s:%s:%d:%d:%s:%s:%s" (userName pe) (password pe) (uid pe) (gid pe) (gecos pe) (homeDir pe) (shell pe) {- | Converting data back out of a 'PasswdEntry'. -} instance Read PasswdEntry where readsPrec _ value = case split ':' value of [f1, f2, f3, f4, f5, f6, f7] -> -- Generate a 'PasswdEntry' the shorthand way: -- using the positional fields. We use 'read' to convert -- the numeric fields to Integers. [(PasswdEntry f1 f2 (read f3) (read f4) f5 f6 f7, [])] x -> error $ "Invalid number of fields in input: " ++ show x where {- | Takes a delimiter and a list. Break up the list based on the - delimiter. -} split :: Eq a => a -> [a] -> [[a]] -- If the input is empty, the result is a list of empty lists. split _ [] = [[]] split delim str = let -- Find the part of the list before delim and put it in -- "before". The rest of the list, including the leading -- delim, goes in "remainder". (before, remainder) = span (/= delim) str in before : case remainder of [] -> [] x -> -- If there is more data to process, -- call split recursively to process it split delim (tail x) -- Convenience aliases; we'll have two maps: one from UID to entries -- and the other from username to entries type UIDMap = Map.Map Integer PasswdEntry type UserMap = Map.Map String PasswdEntry {- | Converts input data to maps. Returns UID and User maps. -} inputToMaps :: String -> (UIDMap, UserMap) inputToMaps inp = (uidmap, usermap) where -- fromList converts a [(key, value)] list into a Map uidmap = Map.fromList . map (\pe -> (uid pe, pe)) $ entries usermap = Map.fromList . map (\pe -> (userName pe, pe)) $ entries -- Convert the input String to [PasswdEntry] entries = map read (lines inp) main = do -- Load the command-line arguments args <- getArgs -- If we don't have the right number of args, -- give an error and abort when (length args /= 1) $ do putStrLn "Syntax: passwdmap filename" exitFailure -- Read the file lazily content <- readFile (head args) let maps = inputToMaps content mainMenu maps mainMenu maps@(uidmap, usermap) = do putStr optionText hFlush stdout sel <- getLine -- See what they want to do. For every option except 4, -- return them to the main menu afterwards by calling -- mainMenu recursively case sel of "1" -> lookupUserName >> mainMenu maps "2" -> lookupUID >> mainMenu maps "3" -> displayFile >> mainMenu maps "4" -> return () _ -> putStrLn "Invalid selection" >> mainMenu maps where lookupUserName = do putStrLn "Username: " username <- getLine case Map.lookup username usermap of Nothing -> putStrLn "Not found." Just x -> print x lookupUID = do putStrLn "UID: " uidstring <- getLine case Map.lookup (read uidstring) uidmap of Nothing -> putStrLn "Not found." Just x -> print x displayFile = putStr . unlines . map (show . snd) . Map.toList $ uidmap optionText = "\npasswdmap options:\n\ \\n\ \1 Look up a user name\n\ \2 Look up a UID\n\ \3 Display entire file\n\ \4 Quit\n\n\ \Your selection: " ~~~ 示例程序維持兩個 Map ：一個從用戶名映射到 PasswdEntry ，另一個從 UID 映射到 PasswdEntry 。有數據庫使用經驗的人可以將它們看作是兩個不同數據域的索引。 根據 /etc/passwd 文件的格式， PasswdEntry 的 Show 和 Read 實例分別用于顯示（display）和處理（parse）工作。 ## 擴展示例：數字類型（Numeric Types） 我們已經講過 Haskell 的類型系統有多強大，表達能力有多強。我們已經講過很多利用這種能力的方法。現在我們來舉一個實際的例子看看。 在 [*數字類型*](#) 一節中，我們展示了 Haskell 的數字類型類。現在，我們來定義一些類，然后用數字類型類把它們和 Haskell 的基本數學結合起來，看看能得到什么。 我們先來想想我們想用這些新類型在 **ghci** 里干什么。首先，一個不錯的選擇是把數學表達式轉成字符串，并確保它顯示了正確的優先級。我們可以寫一個 prettyShow 函數來實現。稍后我們就告訴你怎么寫，先來看看怎么用它。 ~~~ ghci> :l num.hs [1 of 1] Compiling Main ( num.hs, interpreted ) Ok, modules loaded: Main. ghci> 5 + 1 * 3 8 ghci> prettyShow $ 5 + 1 * 3 "5+(1*3)" ghci> prettyShow $ 5 * 1 + 3 "(5*1)+3" ~~~ 看起來不錯，但還不夠聰明。我們可以很容易地把 1* 從表達式里拿掉。寫個函數來簡化怎么樣？ ~~~ ghci> prettyShow $ simplify $ 5 + 1 * 3 "5+3" ~~~ 把數學表達式轉成逆波蘭表達式（RPN）怎么樣？RPN 是一種后綴表示法，它不要求括號，常見于 HP 計算器。RPN 是一種基于棧的表達式。我們把數字放進棧里，當碰到操作符時，棧頂的數字出棧，結果再被放回棧里。 ~~~ ghci> rpnShow $ 5 + 1 * 3 "5 1 3 * +" ghci> rpnShow $ simplify $ 5 + 1 * 3 "5 3 +" ~~~ 能表示含有未知符號的簡單表達式也很不錯。 ~~~ ghci> prettyShow $ 5 + (Symbol "x") * 3 "5+(x*3)" ~~~ 跟數字打交道時，單位常常很重要。例如，當你看見數字5時，它是5米，5英尺，還是5字節？當然，當你用5米除以2秒時，系統應該推出來正確的單位。而且，它應該阻止你用2秒加上5米。 ~~~ ghci> 5 / 2 2.5 ghci> (units 5 "m") / (units 2 "s") 2.5_m/s ghci> (units 5 "m") + (units 2 "s") *** Exception: Mis-matched units in add ghci> (units 5 "m") + (units 2 "m") 7_m ghci> (units 5 "m") / 2 2.5_m ghci> 10 * (units 5 "m") / (units 2 "s") 25.0_m/s ~~~ 如果我們定義的表達式或函數對所有數字都合法，那我們就應該能計算出結果，或者把表達式轉成字符串。例如，如果我們定義 test 的類型為 Numa=>a，并令 test=2*5+3，那我們應該可以： ~~~ ghci> test 13 ghci> rpnShow test "2 5 * 3 +" ghci> prettyShow test "(2*5)+3" ghci> test + 5 18 ghci> prettyShow (test + 5) "((2*5)+3)+5" ghci> rpnShow (test + 5) "2 5 * 3 + 5 +" ~~~ 既然我們能處理單位，那我們也應該能處理一些基本的三角函數，其中很多操作都是關于角的。讓我們確保角度和弧度都能被處理。 ~~~ ghci> sin (pi / 2) 1.0 ghci> sin (units (pi / 2) "rad") 1.0_1.0 ghci> sin (units 90 "deg") 1.0_1.0 ghci> (units 50 "m") * sin (units 90 "deg") 50.0_m ~~~ 最后，我們應該能把這些都放在一起，把不同類型的表達式混合使用。 ~~~ ghci> ((units 50 "m") * sin (units 90 "deg")) :: Units (SymbolicManip Double) 50.0*sin(((2.0*pi)*90.0)/360.0)_m ghci> prettyShow $ dropUnits $ (units 50 "m") * sin (units 90 "deg") "50.0*sin(((2.0*pi)*90.0)/360.0)" ghci> rpnShow $ dropUnits $ (units 50 "m") * sin (units 90 "deg") "50.0 2.0 pi * 90.0 * 360.0 / sin *" ghci> (units (Symbol "x") "m") * sin (units 90 "deg") x*sin(((2.0*pi)*90.0)/360.0)_m ~~~ 你剛才看到的一切都可以用 Haskell 的類型和類型類實現。實際上，你看到的正是我們馬上要實現的 num.hs。 ## 第一步 我們想想怎么實現上面提到的功能。首先，用 **ghci** 查看一下可知，(+) 的類型是 Numa=>a->a->a。如果我們想給加號實現一些自定義行為，我們就必須定義一個新類型并聲明它為 Num 的實例。這個類型得用符號的形式來存儲表達式。我們可以從加法操作開始。我們需要存儲操作符本身、左側以及右側內容。左側和右側內容本身又可以是表達式。 我們可以把表達式想象成一棵樹。讓我們從一些簡單類型開始。 ~~~ -- file: ch13/numsimple.hs -- 我們支持的操作符 data Op = Plus | Minus | Mul | Div | Pow deriving (Eq, Show) {- 核心符號操作類型（core symbolic manipulation type） -} data SymbolicManip a = Number a -- Simple number, such as 5 | Arith Op (SymbolicManip a) (SymbolicManip a) deriving (Eq, Show) {- SymbolicManip 是 Num 的實例。定義 SymbolicManip 實現 Num 的函數。如(+)等。 -} instance Num a => Num (SymbolicManip a) where a + b = Arith Plus a b a - b = Arith Minus a b a * b = Arith Mul a b negate a = Arith Mul (Number (-1)) a abs a = error "abs is unimplemented" signum _ = error "signum is unimplemented" fromInteger i = Number (fromInteger i) ~~~ 首先我們定義了 Op 類型。這個類型表示我們要支持的操作。接著，我們定義了 SymbolicManipa，由于 Numa 約束的存在，a 可替換為任何 Num 實例。我們可以有 SymbolicManipInt 這樣的具體類型。 SymbolicManip 類型可以是數字，也可以是數學運算。Arith 構造器是遞歸的，這在 Haskell 里完全合法。Arith 用一個 Op 和兩個 SymbolicManip 創建了一個 SymbolicManip。我們來看一個例子： ~~~ Prelude> :l numsimple.hs [1 of 1] Compiling Main ( numsimple.hs, interpreted ) Ok, modules loaded: Main. *Main> Number 5 Number 5 *Main> :t Number 5 Number 5 :: Num a => SymbolicManip a *Main> :t Number (5::Int) Number (5::Int) :: SymbolicManip Int *Main> Number 5 * Number 10 Arith Mul (Number 5) (Number 10) *Main> (5 * 10)::SymbolicManip Int Arith Mul (Number 5) (Number 10) *Main> (5 * 10 + 2)::SymbolicManip Int Arith Plus (Arith Mul (Number 5) (Number 10)) (Number 2) ~~~ 可以看到，我們已經可以表示一些簡單的表達式了。注意觀察 Haskell 是如何把 5*10+2 “轉換”成 SymbolicManip 值的，它甚至還正確處理了求值順序。事實上，這并不是真正意義上的轉換，因為 SymbolicManip 已經是一等數字（first-class number）了。就算 Integer 類型的數字字面量（numeric literals）在內部也是被包裝在 fromInteger 里的，所以 5 作為一個 SymbolicManipInt 和作為一個 Int 同樣有效。 從這兒開始，我們的任務就簡單了：擴展 SymbolicManip，使它能表示所有我們想要的操作；把它聲明為其它數字類型類的實例；為 SymbolicManip 實現我們自己的 Show 實例，使這棵樹在顯示時更友好。 ## 完整代碼 這里是完整的 num.hs，我們在本節開始的 **ghci** 例子中用到了它。我們來一點一點分析這段代碼。 ~~~ -- file: ch13/num.hs import Data.List -------------------------------------------------- -- Symbolic/units manipulation -------------------------------------------------- -- The "operators" that we're going to support data Op = Plus | Minus | Mul | Div | Pow deriving (Eq, Show) {- The core symbolic manipulation type. It can be a simple number, a symbol, a binary arithmetic operation (such as +), or a unary arithmetic operation (such as cos) Notice the types of BinaryArith and UnaryArith: it's a recursive type. So, we could represent a (+) over two SymbolicManips. -} data SymbolicManip a = Number a -- Simple number, such as 5 | Symbol String -- A symbol, such as x | BinaryArith Op (SymbolicManip a) (SymbolicManip a) | UnaryArith String (SymbolicManip a) deriving (Eq) ~~~ 我們在這段代碼中定義了 Op，和之前我們用到的一樣。我們也定義了 SymbolicManip，它和我們之前用到的類似。在這個版本中，我們開始支持一元數學操作（unary arithmetic operations）（也就是接受一個參數的操作），例如 abs 和 cos。接下來我們來定義自己的 Num 實例。 ~~~ -- file: ch13/num.hs {- SymbolicManip will be an instance of Num. Define how the Num operations are handled over a SymbolicManip. This will implement things like (+) for SymbolicManip. -} instance Num a => Num (SymbolicManip a) where a + b = BinaryArith Plus a b a - b = BinaryArith Minus a b a * b = BinaryArith Mul a b negate a = BinaryArith Mul (Number (-1)) a abs a = UnaryArith "abs" a signum _ = error "signum is unimplemented" fromInteger i = Number (fromInteger i) ~~~ 非常直觀，和之前的代碼很像。注意之前我們不支持 abs，但現在可以了，因為有了 UnaryArith。接下來，我們再定義幾個實例。 ~~~ -- file: ch13/num.hs {- 定義 SymbolicManip 為 Fractional 實例 -} instance (Fractional a) => Fractional (SymbolicManip a) where a / b = BinaryArith Div a b recip a = BinaryArith Div (Number 1) a fromRational r = Number (fromRational r) {- 定義 SymbolicManip 為 Floating 實例 -} instance (Floating a) => Floating (SymbolicManip a) where pi = Symbol "pi" exp a = UnaryArith "exp" a log a = UnaryArith "log" a sqrt a = UnaryArith "sqrt" a a ** b = BinaryArith Pow a b sin a = UnaryArith "sin" a cos a = UnaryArith "cos" a tan a = UnaryArith "tan" a asin a = UnaryArith "asin" a acos a = UnaryArith "acos" a atan a = UnaryArith "atan" a sinh a = UnaryArith "sinh" a cosh a = UnaryArith "cosh" a tanh a = UnaryArith "tanh" a asinh a = UnaryArith "asinh" a acosh a = UnaryArith "acosh" a atanh a = UnaryArith "atanh" a ~~~ 這段代碼直觀地定義了 Fractional 和 Floating 實例。接下來，我們把表達式轉換字符串。 ~~~ -- file: ch13/num.hs {- 使用常規代數表示法，把 SymbolicManip 轉換為字符串 -} prettyShow :: (Show a, Num a) => SymbolicManip a -> String -- 顯示字符或符號 prettyShow (Number x) = show x prettyShow (Symbol x) = x prettyShow (BinaryArith op a b) = let pa = simpleParen a pb = simpleParen b pop = op2str op in pa ++ pop ++ pb prettyShow (UnaryArith opstr a) = opstr ++ "(" ++ show a ++ ")" op2str :: Op -> String op2str Plus = "+" op2str Minus = "-" op2str Mul = "*" op2str Div = "/" op2str Pow = "**" {- 在需要的地方添加括號。這個函數比較保守，有時候不需要也會加。 Haskell 在構建 SymbolicManip 的時候已經處理好優先級了。-} simpleParen :: (Show a, Num a) => SymbolicManip a -> String simpleParen (Number x) = prettyShow (Number x) simpleParen (Symbol x) = prettyShow (Symbol x) simpleParen x@(BinaryArith _ _ _) = "(" ++ prettyShow x ++ ")" simpleParen x@(UnaryArith _ _) = prettyShow x {- 調用 prettyShow 函數顯示 SymbolicManip 值 -} instance (Show a, Num a) => Show (SymbolicManip a) where show a = prettyShow a ~~~ 首先我們定義了 prettyShow 函數。它把一個表達式轉換成常規表達形式。算法相當簡單：數字和符號不做處理；二元操作是轉換后兩側的內容加上中間的操作符；當然我們也處理了一元操作。op2str 把 Op 轉為 String。在 simpleParen 里，我們加括號的算法非常保守，以確保優先級在結果里清楚顯示。最后，我們聲明 SymbolicManip 為 Show 的實例然后用 prettyShow 來實現。現在，我們來設計一個算法把表達式轉為 RPN 形式的字符串。 ~~~ -- file: ch13/num.hs {- Show a SymbolicManip using RPN. HP calculator users may find this familiar. -} rpnShow :: (Show a, Num a) => SymbolicManip a -> String rpnShow i = let toList (Number x) = [show x] toList (Symbol x) = [x] toList (BinaryArith op a b) = toList a ++ toList b ++ [op2str op] toList (UnaryArith op a) = toList a ++ [op] join :: [a] -> [[a]] -> [a] join delim l = concat (intersperse delim l) in join " " (toList i) ~~~ RPN 愛好者會發現，跟上面的算法相比，這個算法是多么簡潔。尤其是，我們根本不用關心要從哪里加括號，因為 RPN 天生只能沿著一個方向求值。接下來，我們寫個函數來實現一些基本的表達式化簡。 ~~~ -- file: ch13/num.hs {- Perform some basic algebraic simplifications on a SymbolicManip. -} simplify :: (Eq a, Num a) => SymbolicManip a -> SymbolicManip a simplify (BinaryArith op ia ib) = let sa = simplify ia sb = simplify ib in case (op, sa, sb) of (Mul, Number 1, b) -> b (Mul, a, Number 1) -> a (Mul, Number 0, b) -> Number 0 (Mul, a, Number 0) -> Number 0 (Div, a, Number 1) -> a (Plus, a, Number 0) -> a (Plus, Number 0, b) -> b (Minus, a, Number 0) -> a _ -> BinaryArith op sa sb simplify (UnaryArith op a) = UnaryArith op (simplify a) simplify x = x ~~~ 這個函數相當簡單。我們很輕易地就能化簡某些二元數學運算——例如，用1乘以任何值。我們首先得到操作符兩側操作數被化簡之后的版本（在這兒用到了遞歸）然后再化簡結果。對于一元操作符我們能做的不多，所以我們僅僅簡化它們作用于的表達式。 從現在開始，我們會增加對計量單位的支持。增加之后我們就能表示“5米”這種數量了。跟之前一樣，我們先來定義一個類型： ~~~ -- file: ch13/num.hs {- 新數據類型：Units。Units 類型包含一個數字和一個 SymbolicManip，也就是計量單位。 計量單位符號可以是 (Symbol "m") 這個樣子。 -} data Units a = Units a (SymbolicManip a) deriving (Eq) ~~~ 一個 Units 值包含一個數字和一個符號。符號本身是 SymbolicManip 類型。接下來，將 Units 聲明為 Num 實例。 ~~~ -- file: ch13/num.hs {- 為 Units 實現 Num 實例。我們不知道如何轉換任意單位，因此當不同單位的數字相加時，我們報告錯誤。 對于乘法，我們生成對應的新單位。 -} instance (Eq a, Num a) => Num (Units a) where (Units xa ua) + (Units xb ub) | ua == ub = Units (xa + xb) ua | otherwise = error "Mis-matched units in add or subtract" (Units xa ua) - (Units xb ub) = (Units xa ua) + (Units (xb * (-1)) ub) (Units xa ua) * (Units xb ub) = Units (xa * xb) (ua * ub) negate (Units xa ua) = Units (negate xa) ua abs (Units xa ua) = Units (abs xa) ua signum (Units xa _) = Units (signum xa) (Number 1) fromInteger i = Units (fromInteger i) (Number 1) ~~~ 現在，我們應該清楚為什么要用 SymbolicManip 而不是 String 來存儲計量單位了。做乘法時，計量單位也會發生改變。例如，5米乘以2米會得到10平方米。我們要求加法運算的單位必須匹配，并用加法實現了減法。我們再來看幾個 Units 的類型類實例。 ~~~ -- file: ch13/num.hs {- Make Units an instance of Fractional -} instance (Eq a, Fractional a) => Fractional (Units a) where (Units xa ua) / (Units xb ub) = Units (xa / xb) (ua / ub) recip a = 1 / a fromRational r = Units (fromRational r) (Number 1) {- Floating implementation for Units. Use some intelligence for angle calculations: support deg and rad -} instance (Eq a, Floating a) => Floating (Units a) where pi = (Units pi (Number 1)) exp _ = error "exp not yet implemented in Units" log _ = error "log not yet implemented in Units" (Units xa ua) ** (Units xb ub) | ub == Number 1 = Units (xa ** xb) (ua ** Number xb) | otherwise = error "units for RHS of ** not supported" sqrt (Units xa ua) = Units (sqrt xa) (sqrt ua) sin (Units xa ua) | ua == Symbol "rad" = Units (sin xa) (Number 1) | ua == Symbol "deg" = Units (sin (deg2rad xa)) (Number 1) | otherwise = error "Units for sin must be deg or rad" cos (Units xa ua) | ua == Symbol "rad" = Units (cos xa) (Number 1) | ua == Symbol "deg" = Units (cos (deg2rad xa)) (Number 1) | otherwise = error "Units for cos must be deg or rad" tan (Units xa ua) | ua == Symbol "rad" = Units (tan xa) (Number 1) | ua == Symbol "deg" = Units (tan (deg2rad xa)) (Number 1) | otherwise = error "Units for tan must be deg or rad" asin (Units xa ua) | ua == Number 1 = Units (rad2deg $ asin xa) (Symbol "deg") | otherwise = error "Units for asin must be empty" acos (Units xa ua) | ua == Number 1 = Units (rad2deg $ acos xa) (Symbol "deg") | otherwise = error "Units for acos must be empty" atan (Units xa ua) | ua == Number 1 = Units (rad2deg $ atan xa) (Symbol "deg") | otherwise = error "Units for atan must be empty" sinh = error "sinh not yet implemented in Units" cosh = error "cosh not yet implemented in Units" tanh = error "tanh not yet implemented in Units" asinh = error "asinh not yet implemented in Units" acosh = error "acosh not yet implemented in Units" atanh = error "atanh not yet implemented in Units" ~~~ 雖然沒有實現所有函數，但大部分都定義了。現在我們來定義幾個跟單位打交道的工具函數。 ~~~ -- file: ch13/num.hs {- A simple function that takes a number and a String and returns an appropriate Units type to represent the number and its unit of measure -} units :: (Num z) => z -> String -> Units z units a b = Units a (Symbol b) {- Extract the number only out of a Units type -} dropUnits :: (Num z) => Units z -> z dropUnits (Units x _) = x {- Utilities for the Unit implementation -} deg2rad x = 2 * pi * x / 360 rad2deg x = 360 * x / (2 * pi) ~~~ 首先我們定義了 units，使表達式更簡潔。units5"m" 肯定要比 Units5(Symbol"m") 省事。我們還定義了 dropUnits，它把單位去掉只返回 Num。最后，我們定義了兩個函數，用來在角度和弧度之間轉換。接下來，我們給 Units 定義 Show 實例。 ~~~ -- file: ch13/num.hs {- Showing units: we show the numeric component, an underscore, then the prettyShow version of the simplified units -} instance (Eq a, Show a, Num a) => Show (Units a) where show (Units xa ua) = show xa ++ "_" ++ prettyShow (simplify ua) ~~~ 很簡單。最后我們定義 test 變量用來測試。 ~~~ -- file: ch13/num.hs test :: (Num a) => a test = 2 * 5 + 3 ~~~ 回頭看看這些代碼，我們已經完成了既定目標：給 SymbolicManip 實現更多實例；我們引入了新類型 Units，它包含一個數字和一個單位；我們實現了幾個 show 函數，以便用不同的方式來轉換 SymbolicManip 和 Units。 這個例子還給了我們另外一點啟發。所有語言——即使那些包含對象和重載的——都有從某種角度看很獨特的地方。在 Haskell 里，這個“特殊”的部分很小。我們剛剛開發了一種新的表示法用來表示像數字一樣基本的東西，而且很容易就實現了。我們的新類型是一等類型，編譯器在編譯時就知道使用它哪個函數。Haskell 把代碼復用和互換（interchangeability）發揮到了極致。寫通用代碼很容易，而且很方便就能把它們用于多種不同類型的東西上。同樣容易的是創建新類型并使它們自動成為系統的一等功能（first-class features）。 還記得本節開頭的 **ghci** 例子嗎？ 我們已經實現了它的全部功能。你可以自己試試，看看它們是怎么工作的。 ## 練習 1. 擴展 prettyShow 函數，去掉不必要的括號。 ## 把函數當成數據來用 在命令式語言當中，拼接兩個列表很容易。下面的 C 語言結構維護了指向列表頭尾的指針： ~~~ struct list { struct node *head, *tail; }; ~~~ 當我們想把列表 B 拼接到列表 A 的尾部時，我們將 A 的最后一個節點指向 B 的 head 節點，再把 A 的 tail 指針指向 B 的 tail 節點。 很顯然，在 Haskell 里，如果我們想保持“純”的話，這種方法是有局限性的。由于純數據是不可變的，我們無法原地修改列表。Haskell 的 (++) 操作符通過生成一個新列表來拼接列表。 ~~~ -- file: ch13/Append.hs (++) :: [a] -> [a] -> [a] (x:xs) ++ ys = x : xs ++ ys _ ++ ys = ys ~~~ 從代碼里可以看出，創建新列表的開銷取決于第一個列表的長度。 我們經常需要通過重復拼接列表來創建一個大列表。例如，在生成網頁內容時我們可能想生成一個 String。每當有新內容添加到網頁中時，我們會很自然地想到把它拼接到已有 String 的末尾。 如果每一次拼接的開銷都正比與初始列表的長度，每一次拼接都把初始列表加的更長，那么我們將會陷入一個很糟糕的情況：所有拼接的總開銷將會正比于最終列表長度的平方。 為了更好地理解，我們來研究一下。(++) 操作符是右結合的。 ~~~ ghci> :info (++) (++) :: [a] -> [a] -> [a] -- Defined in GHC.Base infixr 5 ++ ~~~ 這意味著 Haskell 在求值表達式 "a"++"b"++"c" 時會從右向左進行，就像加了括號一樣："a"++("b"++"c")。這對于提高性能非常有好處，因為它會讓左側操作數始終保持最短。 當我們重復向列表末尾拼接時，我們破壞了這種結合性。假設我們有一個列表 "a" 然后想把 "b" 拼接上去，我們把結果存儲在一個新列表里。稍后如果我們想把 "c" 拼接上去時，這時的左操作數已經變成了 "ab"。在這種情況下，每次拼接都讓左操作數變得更長。 與此同時，命令式語言的程序員卻在偷笑，因為他們重復拼接的開銷只取決于操作的次數。他們的性能是線性的，我們的是平方的。 當像重復拼接列表這種常見任務都暴露出如此嚴重的性能問題時，我們有必要從另一個角度來看看問題了。 表達式 ("a"++) 是一個 [*節*](#) (section)，一個部分應用的函數。它的類型是什么呢？ ~~~ ghci> :type ("a" ++) ("a" ++) :: [Char] -> [Char] ~~~ 由于這是一個函數，我們可以用 (.) 操作符把它和另一個節組合起來，例如 ("b"++)。 ~~~ ghci> :type ("a" ++) . ("b" ++) ("a" ++) . ("b" ++) :: [Char] -> [Char] ~~~ 新函數的類型和之前相同。當我們停止組合函數，并向我們創造的函數提供一個 String 會發生什么呢？ ~~~ ghci> let f = ("a" ++) . ("b" ++) ghci> f [] "ab" ~~~ 我們實現了字符串拼接！我們利用這些部分應用的函數來存儲數據，并且只要提供一個空列表就可以把數據提取出來。每一個 (++) 和 (.) 部分應用都代表了一次拼接，但它們并沒有真正完成拼接。 這個方法有兩點非常有趣。第一點是部分應用的開銷是固定的，這樣多次部分應用的開銷就是線性的。第二點是當我們提供一個 [] 值來從部分應用鏈中提取最終列表時，求值會從右至左進行。這使得 (++) 的左操作數盡可能小，使得所有拼接的總開銷是線性而不是平方。 通過使用這種并不太熟悉的數據表示方式，我們避免了一個性能泥潭，并且對“把函數當成數據來用”有了新的認識。順便說一下，這個技巧并不新鮮，它通常被稱為*差異列表*（difference list）。 還有一點沒講。盡管從理論上看差異列表非常吸引人，但如果在實際中把 (++)、(.) 和部分應用都暴露在外的話，它并不會非常好用。我們需要把它轉成一種更好用的形式。 ## 把差異列表轉成庫 第一步是用 newtype 聲明把底層的類型隱藏起來。我們會創建一個 DList 類型。類似于普通列表，它是一個參數化類型。 ~~~ -- file: ch13/DList.hs newtype DList a = DL { unDL :: [a] -> [a] } ~~~ unDL 是我們的析構函數，它把 DL 構造器刪除掉。我們最后導出模塊函數時會忽略掉構造函數和析構函數，這樣我們的用戶就沒必要知道 DList 類型的實現細節。他們只用我們導出的函數即可。 ~~~ -- file: ch13/DList.hs append :: DList a -> DList a -> DList a append xs ys = DL (unDL xs . unDL ys) ~~~ 我們的 append 函數看起來可能有點復雜，但其實它僅僅是圍繞著 (.) 操作符做了一些簿記工作，(.) 的用法和我們之前展示的完全一樣。生成函數的時候，我們必須首先用 unDL 函數把它們從 DL 構造器中取出來。然后我們在把得到的結果重新用 DL 包裝起來，確保它的類型正確。 下面是相同函數的另一種寫法，這種方法通過模式識別取出 xs 和 ys。 ~~~ -- file: ch13/DList.hs append' :: DList a -> DList a -> DList a append' (DL xs) (DL ys) = DL (xs . ys) ~~~ 我們需要在 DList 類型和普通列表之間來回轉換。 ~~~ -- file: ch13/DList.hs fromList :: [a] -> DList a fromList xs = DL (xs ++) toList :: DList a -> [a] toList (DL xs) = xs [] ~~~ 再次聲明，跟這些函數最原始的版本相比，我們在這里做的只是一些簿記工作。 如果我們想把 DList 作為普通列表的替代品，我們還需要提供一些常用的列表操作。 ~~~ -- file: ch13/DList.hs empty :: DList a empty = DL id -- equivalent of the list type's (:) operator cons :: a -> DList a -> DList a cons x (DL xs) = DL ((x:) . xs) infixr `cons` dfoldr :: (a -> b -> b) -> b -> DList a -> b dfoldr f z xs = foldr f z (toList xs) ~~~ 盡管 DList 使得拼接很廉價，但并不是所有的列表操作都容易實現。列表的 head 函數具有常數開銷，而對應的 DList 實現卻需要將整個 DList 轉為普通列表，因此它比普通列表的實現昂貴得多：它的開銷正比于構造 DList 所需的拼接次數。 ~~~ -- file: ch13/DList.hs safeHead :: DList a -> Maybe a safeHead xs = case toList xs of (y:_) -> Just y _ -> Nothing ~~~ 為了實現對應的 map 函數，我們可以把 DList 類型聲明為一個 Functor（函子）。 ~~~ -- file: ch13/DList.hs dmap :: (a -> b) -> DList a -> DList b dmap f = dfoldr go empty where go x xs = cons (f x) xs instance Functor DList where fmap = dmap ~~~ 當我們實現了足夠多的列表操作時，我們回到源文件頂部增加一個模塊頭。 ~~~ -- file: ch13/DList.hs module DList ( DList , fromList , toList , empty , append , cons , dfoldr ) where ~~~ ## 列表、差異列表和幺半群（monoids） 在抽象代數中，有一類簡單的抽象結構被稱為*幺半群*。許多數學結構都是幺半群，因為成為幺半群的要求非常低。一個結構只要滿足兩個性質便可稱為幺半群： - 一個滿足結合律的二元操作符。我們稱之為 (*)：表達式 a*(b*c) 和 (a*b)*c 結果必須相同。 - 一個單位元素。我們稱之為 e，它必須遵守兩條法則：a*e==a 和 e*a==a。 幺半群并不要求這個二元操作符做什么，它只要求這個二元操作符必須存在。因此很多數學結構都是幺半群。如果我們把加號作為二元操作符，0作為單位元素，那么整數就是一個幺半群。把乘號作為二元操作符，1作為單位元素，整數就形成了另一個幺半群。 Haskell 中幺半群無所不在。Data.Monoid 模塊定義了 Monoid 類型類。 ~~~ -- file: ch13/Monoid.hs class Monoid a where mempty :: a -- the identity mappend :: a -> a -> a -- associative binary operator ~~~ 如果我們把 (++) 當做二元操作符，[] 當做單位元素，列表就形成了一個幺半群。 ~~~ -- file: ch13/Monoid.hs instance Monoid [a] where mempty = [] mappend = (++) ~~~ 由于列表和 DLists 關系如此緊密，DList 類型也必須是一個幺半群。 ~~~ -- file: ch13/DList.hs instance Monoid (DList a) where mempty = empty mappend = append ~~~ 在 **ghci** 里試試 Monoid 類型類的函數。 ~~~ ghci> "foo" `mappend` "bar" "foobar" ghci> toList (fromList [1,2] `mappend` fromList [3,4]) [1,2,3,4] ghci> mempty `mappend` [1] [1] ~~~ Note 盡管從數學的角度看，整數可以以兩種不同的方式作為幺半群，但在 Haskell 里，我們卻不能給 Int 寫兩個不同的 Monoid 實例：編譯器會報告重復實例錯誤。 如果我們真的需要在同一個類型上實現多個 Monoid 實例，我們可以用 newtype 創建不同的類型來達到目的。 ~~~ -- file: ch13/Monoid.hs {-# LANGUAGE GeneralizedNewtypeDeriving #-} newtype AInt = A { unA :: Int } deriving (Show, Eq, Num) -- monoid under addition instance Monoid AInt where mempty = 0 mappend = (+) newtype MInt = M { unM :: Int } deriving (Show, Eq, Num) -- monoid under multiplication instance Monoid MInt where mempty = 1 mappend = (*) ~~~ 這樣，根據使用類型的不同，我們就能得到不同的行為。 ~~~ ghci> 2 `mappend` 5 :: MInt M {unM = 10} ghci> 2 `mappend` 5 :: AInt A {unA = 7} ~~~ 在這一節（The writer monad and lists）中，我們還會繼續討論差異列表和它的幺半群性質。 Note 跟 functor 規則一樣，Haskell 沒法替我們檢查幺半群的規則。如果我們定義了一個 Monoid 實例，我們可以很容易地寫一些 QuickCheck 性質來得到一個較高的統計推斷，確保代碼遵守了幺半群規則。 ## 通用序列 不論是 Haskell 內置的列表，還是我們前面定義的 DList ，這些數據結構在不同的地方都有自己的性能短板。為此， Data.Sequence 模塊定義了 Seq 容器類型，對于大多數操作，這種類型能都提供良好的效率保證。 為了避免命名沖突， Data.Sequence 模塊通常以 qualified 的方式引入： ~~~ Prelude> import qualified Data.Sequence as Seq Prelude Seq> ~~~ empty 函數用于創建一個空 Seq ， singleton 用于創建只包含單個元素的 Seq ： ~~~ Prelude Seq> Seq.empty fromList [] Prelude Seq> Seq.singleton 1 fromList [1] ~~~ 還可以使用 fromList 函數，通過列表創建出相應的 Seq ： ~~~ Prelude Seq> let a = Seq.fromList [1, 2, 3] Prelude Seq> a fromList [1,2,3] ~~~ Data.Sequence 模塊還提供了幾種操作符形式的構造函數。但是，在使用 qualified 形式載入模塊的情況下調用它們會非常難看： [譯注：操作符形式指的是那種放在兩個操作對象之間的函數，比如 2*2 中的 * 函數。] ~~~ Prelude Seq> 1 Seq.<| Seq.singleton 2 fromList [1,2] ~~~ 可以通過直接載入這幾個函數來改善可讀性： ~~~ Prelude Seq> import Data.Sequence((><), (<|), (|>)) ~~~ 現在好多了： ~~~ Prelude Seq Data.Sequence> Seq.singleton 1 |> 2 fromList [1,2] ~~~ 一個幫助記憶 (<|) 和 (|>) 函數的方法是，函數的『箭頭』總是指向被添加的元素： (<|) 函數要添加的元素在左邊，而 (|>) 函數要添加的元素在右邊： ~~~ Prelude Seq Data.Sequence> 1 <| Seq.singleton 2 fromList [1,2] Prelude Seq Data.Sequence> Seq.singleton 1 |> 2 fromList [1,2] ~~~ 不管是從左邊添加元素，還是從右邊添加元素，添加操作都可以在常數時間內完成。對兩個 Seq 進行追加（append）操作同樣非常廉價，復雜度等同于兩個 Seq 中較短的那個 Seq 的長度的對數。 追加操作由 (><) 函數完成： ~~~ Prelude Seq Data.Sequence> let left = Seq.fromList [1, 3, 3] Prelude Seq Data.Sequence> let right = Seq.fromList [7, 1] Prelude Seq Data.Sequence> left >< right fromList [1,3,3,7,1] ~~~ 反過來，如果我們想將 Seq 轉換回列表，那么就需要 Data.Foldable 模塊的幫助： ~~~ Prelude Seq Data.Sequence> import qualified Data.Foldable as Foldable Prelude Seq Data.Sequence Foldable> ~~~ 這個模塊定義了一個類型， Foldable ，而 Seq 實現了這個類型： ~~~ Prelude Seq Data.Sequence Foldable> Foldable.toList (Seq.fromList [1, 2, 3]) [1,2,3] ~~~ Data.Foldable 中的 fold 函數可以用于對 Seq 進行 fold 操作： ~~~ Prelude Seq Data.Sequence Foldable> Foldable.foldl' (+) 0 (Seq.fromList [1, 2, 3]) 6 ~~~ Data.Sequence 模塊還提供了大量有用的函數，這些函數都和 Haskell 列表的函數類似。模塊的文檔也非常齊全，還提供了函數的時間復雜度信息。 最后的疑問是，既然 Seq 的效率這么好，那為什么它不是 Haskell 默認的序列類型呢？答案是，列表類型更簡單，消耗更低，對于大多數應用程序來說，列表已經足夠滿足需求了。除此之外，列表可以很好地處理惰性環境，而 Seq 在這方面做得還不夠好。