第十三章：數(shù)據(jù)結(jié)構(gòu)

第十三章：數(shù)據(jù)結(jié)構(gòu)

關(guān)聯(lián)列表

我們常常會(huì)跟一些以鍵為索引的無(wú)序數(shù)據(jù)打交道。

舉個(gè)例子，UNIX 管理猿可能需要這么一個(gè)列表，它包含系統(tǒng)中所有用戶的 UID ，以及和這個(gè) UID 相對(duì)應(yīng)的用戶名。這個(gè)列表根據(jù) UID 而不是數(shù)據(jù)的位置來(lái)查找相應(yīng)的用戶名。換句話來(lái)說， UID 就是這個(gè)數(shù)據(jù)集的鍵。

Haskell 里有幾種不同的方法來(lái)處理這種結(jié)構(gòu)的數(shù)據(jù)，最常用的兩個(gè)是關(guān)聯(lián)列表（association list）和 Data.Map 模塊提供的 Map 類型。

關(guān)聯(lián)列表非常簡(jiǎn)單，易于使用。由于關(guān)聯(lián)列表由 Haskell 列表構(gòu)成，因此所有列表操作函數(shù)都可以用于處理關(guān)聯(lián)列表。

另一方面， Map 類型在處理大數(shù)據(jù)集時(shí)，性能比關(guān)聯(lián)列表要好。

本章將同時(shí)介紹這兩種數(shù)據(jù)結(jié)構(gòu)。

關(guān)聯(lián)列表就是包含一個(gè)或多個(gè) (key,value) 元組的列表， key 和 value 可以是任意類型。一個(gè)處理 UID 和用戶名映射的關(guān)聯(lián)列表的類型可能是 [(Integer,String)] 。

[注：關(guān)聯(lián)列表的 key 必須是 Eq 類型的成員。]

關(guān)聯(lián)列表的構(gòu)建方式和普通列表一樣。Haskell 提供了一個(gè) Data.List.lookup 函數(shù)，用于在關(guān)聯(lián)列表中查找數(shù)據(jù)。這個(gè)函數(shù)的類型簽名為 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 函數(shù)的定義如下：

-- 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 在輸入列表為空時(shí)返回 Nothing 。如果輸入列表不為空，那么它檢查當(dāng)前列表元素的 key 是否就是我們要找的 key ，如果是的話就返回和這個(gè) key 對(duì)應(yīng)的 value ，否則就繼續(xù)遞歸處理剩余的列表元素。

再來(lái)看一個(gè)稍微復(fù)雜點(diǎn)的例子。在 Unix/Linux 系統(tǒng)中，有一個(gè) /etc/passwd 文件，這個(gè)文件保存了用戶名稱， UID，用戶的 HOME 目錄位置，以及其他一些數(shù)據(jù)。文件以行分割每個(gè)用戶的資料，每個(gè)數(shù)據(jù)域用冒號(hào)隔開：

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 文件，它創(chuàng)建一個(gè)關(guān)聯(lián)列表，使得我們可以根據(jù)給定 UID ，獲取相應(yīng)的用戶名：

-- 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 是整個(gè)程序的核心，它逐行讀入并處理輸入，使用 lookup 從處理結(jié)果中查找給定 UID ：

*Main> findByUID "root:x:0:0:root:/root:/bin/bash" 0
Just "root"

parseline 讀入并處理一個(gè)字符串，返回一個(gè)包含 UID 和用戶名的元組：

*Main> parseline "root:x:0:0:root:/root:/bin/bash"
(0,"root")

split 函數(shù)根據(jù)給定分隔符 delimiter 將一個(gè)文本行分割為列表：

*Main> split ':' "root:x:0:0:root:/root:/bin/bash"
["root","x","0","0","root","/root","/bin/bash"]

以下是在本機(jī)執(zhí)行 passwd-al.hs 處理 /etc/passwd 的結(jié)果：

$ runghc passwd-al.hs /etc/passwd 0
root

$ runghc passwd-al.hs /etc/passwd 10086
Could not find that UID

Map 類型

Data.Map 模塊提供的 Map 類型的行為和關(guān)聯(lián)列表類似，但 Map 類型的性能更好。

Map 和其他語(yǔ)言提供的哈希表類似。不同的是， Map 的內(nèi)部由平衡二叉樹實(shí)現(xiàn)，在 Haskell 這種使用不可變數(shù)據(jù)的語(yǔ)言中，它是一個(gè)比哈希表更高效的表示。這是一個(gè)非常明顯的例子，說明純函數(shù)式語(yǔ)言是如何深入地影響我們編寫程序的方式：對(duì)于一個(gè)給定的任務(wù)，我們總是選擇合適的算法和數(shù)據(jù)結(jié)構(gòu)，使得解決方案盡可能地簡(jiǎn)單和有效，但這些（純函數(shù)式的）選擇通常不同于命令式語(yǔ)言處理同樣問題時(shí)的選擇。

因?yàn)?Data.Map 模塊的一些函數(shù)和 Prelude 模塊的函數(shù)重名，我們通過 importqualifiedData.MapasMap 的方式引入模塊，并使用 Map.name 的方式引用模塊中的名字。

先來(lái)看看如何用幾種不同的方式構(gòu)建 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 函數(shù)處理數(shù)據(jù)的方式非?！?Haskell 化』：它返回經(jīng)過函數(shù)應(yīng)用的輸入數(shù)據(jù)的副本。這種處理數(shù)據(jù)的方式在操作多個(gè) Map 時(shí)非常有用，它意味著你可以像前面代碼中 mapFold 那樣使用 fold 來(lái)構(gòu)建一個(gè) Map ，又或者像 mapManual 那樣，串連起多個(gè) Map.insert 調(diào)用。

[譯注：這里說『 Haskell 化』實(shí)際上就是『函數(shù)式化』，對(duì)于函數(shù)式語(yǔ)言來(lái)說，最常見的函數(shù)處理方式是接受一個(gè)輸入，然后返回一個(gè)輸出，輸出是另一個(gè)獨(dú)立的值，且原輸入不會(huì)被修改。]

現(xiàn)在，到 ghci 中驗(yàn)證一下是否所有定義都如我們所預(yù)期的那樣工作：

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 并不保證它的輸出排列和原本的輸入排列一致，對(duì)比 mapManual 的輸入和輸出可以看出這一點(diǎn)。

Map 的操作方式和關(guān)聯(lián)列表類似。 Data.Map 模塊提供了一組函數(shù)，用于增刪 Map 元素，對(duì) Map 進(jìn)行過濾、修改和 fold ，以及在 Map 和關(guān)聯(lián)列表之間進(jìn)行轉(zhuǎn)換。 Data.Map 模塊本身的文檔非常優(yōu)秀，因此我們?cè)谶@里不會(huì)詳細(xì)講解每個(gè)函數(shù)，而是在本章的后續(xù)內(nèi)容中，通過例子來(lái)介紹這些概念。

函數(shù)也是數(shù)據(jù)

Haskell 語(yǔ)言的威力部分在于它可以讓我們方便地創(chuàng)建并操作函數(shù)。

以下示例展示了怎樣將函數(shù)保存到記錄的域中：

-- 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 域的類型：它是一個(gè)函數(shù)，接受一個(gè) Int 類型值作為參數(shù)，并返回一個(gè) (CustomColor,Int) 元組。

我們創(chuàng)建了兩個(gè) FuncRec 記錄： plus5 和 always0 ，這兩個(gè)記錄的 colorCalc 域都總是返回紫色（purple）。 FuncRec 自身并沒有域去保存所使用的顏色，顏色的值被保存在函數(shù)當(dāng)中 —— 我們稱這種用法為閉包。

以下是示例代碼：

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

上面的程序工作得很好，但我們還想做一些更有趣的事，比如說，在多個(gè)域中使用同一段數(shù)據(jù)?？梢允褂靡粋€(gè)類型構(gòu)造函數(shù)來(lái)做到這一點(diǎn)：

-- 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 函數(shù)接受一個(gè)字符串和一個(gè)函數(shù)作為參數(shù)，返回一個(gè)新的 FuncRec 記錄。以下是對(duì) mkFuncRecs 函數(shù)的測(cè)試：

*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 的創(chuàng)建過程：我們改變了 plus5 的 name 域，但沒有修改它的 namedCalc 域。這就是為什么調(diào)用 name 會(huì)返回新名字，而 namedCalc 依然返回原本使用 mkFuncRecs 創(chuàng)建時(shí)設(shè)置的名字 —— 除非我們顯式地修改域，否則它們不會(huì)被改變。

擴(kuò)展示例： /etc/password

以下是一個(gè)擴(kuò)展示例，它展示了幾種不同的數(shù)據(jù)結(jié)構(gòu)的用法，根據(jù) /etc/passwd 文件的格式，程序處理并保存它的實(shí)體（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: "

示例程序維持兩個(gè) Map ：一個(gè)從用戶名映射到 PasswdEntry ，另一個(gè)從 UID 映射到 PasswdEntry 。有數(shù)據(jù)庫(kù)使用經(jīng)驗(yàn)的人可以將它們看作是兩個(gè)不同數(shù)據(jù)域的索引。

根據(jù) /etc/passwd 文件的格式， PasswdEntry 的 Show 和 Read 實(shí)例分別用于顯示（display）和處理（parse）工作。

擴(kuò)展示例：數(shù)字類型（Numeric Types）

我們已經(jīng)講過 Haskell 的類型系統(tǒng)有多強(qiáng)大，表達(dá)能力有多強(qiáng)。我們已經(jīng)講過很多利用這種能力的方法?，F(xiàn)在我們來(lái)舉一個(gè)實(shí)際的例子看看。

在 數(shù)字類型 一節(jié)中，我們展示了 Haskell 的數(shù)字類型類?，F(xiàn)在，我們來(lái)定義一些類，然后用數(shù)字類型類把它們和 Haskell 的基本數(shù)學(xué)結(jié)合起來(lái)，看看能得到什么。

我們先來(lái)想想我們想用這些新類型在 ghci 里干什么。首先，一個(gè)不錯(cuò)的選擇是把數(shù)學(xué)表達(dá)式轉(zhuǎn)成字符串，并確保它顯示了正確的優(yōu)先級(jí)。我們可以寫一個(gè) prettyShow 函數(shù)來(lái)實(shí)現(xiàn)。稍后我們就告訴你怎么寫，先來(lái)看看怎么用它。

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"

看起來(lái)不錯(cuò)，但還不夠聰明。我們可以很容易地把 1* 從表達(dá)式里拿掉。寫個(gè)函數(shù)來(lái)簡(jiǎn)化怎么樣？

ghci> prettyShow $ simplify $ 5 + 1 * 3
"5+3"

把數(shù)學(xué)表達(dá)式轉(zhuǎn)成逆波蘭表達(dá)式（RPN）怎么樣？RPN 是一種后綴表示法，它不要求括號(hào)，常見于 HP 計(jì)算器。RPN 是一種基于棧的表達(dá)式。我們把數(shù)字放進(jìn)棧里，當(dāng)碰到操作符時(shí)，棧頂?shù)臄?shù)字出棧，結(jié)果再被放回棧里。

ghci> rpnShow $ 5 + 1 * 3
"5 1 3 * +"
ghci> rpnShow $ simplify $ 5 + 1 * 3
"5 3 +"

能表示含有未知符號(hào)的簡(jiǎn)單表達(dá)式也很不錯(cuò)。

ghci> prettyShow $ 5 + (Symbol "x") * 3
"5+(x*3)"

跟數(shù)字打交道時(shí)，單位常常很重要。例如，當(dāng)你看見數(shù)字5時(shí)，它是5米，5英尺，還是5字節(jié)？當(dāng)然，當(dāng)你用5米除以2秒時(shí)，系統(tǒng)應(yīng)該推出來(lái)正確的單位。而且，它應(yīng)該阻止你用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

如果我們定義的表達(dá)式或函數(shù)對(duì)所有數(shù)字都合法，那我們就應(yīng)該能計(jì)算出結(jié)果，或者把表達(dá)式轉(zhuǎn)成字符串。例如，如果我們定義 test 的類型為 Numa=>a，并令 test=2*5+3，那我們應(yīng)該可以：

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 +"

既然我們能處理單位，那我們也應(yīng)該能處理一些基本的三角函數(shù)，其中很多操作都是關(guān)于角的。讓我們確保角度和弧度都能被處理。

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

最后，我們應(yīng)該能把這些都放在一起，把不同類型的表達(dá)式混合使用。

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 的類型和類型類實(shí)現(xiàn)。實(shí)際上，你看到的正是我們馬上要實(shí)現(xiàn)的 num.hs。

第一步

我們想想怎么實(shí)現(xiàn)上面提到的功能。首先，用 ghci 查看一下可知，(+) 的類型是 Numa=>a->a->a。如果我們想給加號(hào)實(shí)現(xiàn)一些自定義行為，我們就必須定義一個(gè)新類型并聲明它為 Num 的實(shí)例。這個(gè)類型得用符號(hào)的形式來(lái)存儲(chǔ)表達(dá)式。我們可以從加法操作開始。我們需要存儲(chǔ)操作符本身、左側(cè)以及右側(cè)內(nèi)容。左側(cè)和右側(cè)內(nèi)容本身又可以是表達(dá)式。

我們可以把表達(dá)式想象成一棵樹。讓我們從一些簡(jiǎn)單類型開始。

-- file: ch13/numsimple.hs
-- 我們支持的操作符
data Op = Plus | Minus | Mul | Div | Pow
        deriving (Eq, Show)

{- 核心符號(hào)操作類型（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 的實(shí)例。定義 SymbolicManip 實(shí)現(xiàn) Num 的函數(shù)。如(+)等。 -}
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 類型。這個(gè)類型表示我們要支持的操作。接著，我們定義了 SymbolicManipa，由于 Numa 約束的存在，a 可替換為任何 Num 實(shí)例。我們可以有 SymbolicManipInt 這樣的具體類型。

SymbolicManip 類型可以是數(shù)字，也可以是數(shù)學(xué)運(yùn)算。Arith 構(gòu)造器是遞歸的，這在 Haskell 里完全合法。Arith 用一個(gè) Op 和兩個(gè) SymbolicManip 創(chuàng)建了一個(gè) SymbolicManip。我們來(lái)看一個(gè)例子：

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)

可以看到，我們已經(jīng)可以表示一些簡(jiǎn)單的表達(dá)式了。注意觀察 Haskell 是如何把 5*10+2 “轉(zhuǎn)換”成 SymbolicManip 值的，它甚至還正確處理了求值順序。事實(shí)上，這并不是真正意義上的轉(zhuǎn)換，因?yàn)?SymbolicManip 已經(jīng)是一等數(shù)字（first-class number）了。就算 Integer 類型的數(shù)字字面量（numeric literals）在內(nèi)部也是被包裝在 fromInteger 里的，所以 5 作為一個(gè) SymbolicManipInt 和作為一個(gè) Int 同樣有效。

從這兒開始，我們的任務(wù)就簡(jiǎn)單了：擴(kuò)展 SymbolicManip，使它能表示所有我們想要的操作；把它聲明為其它數(shù)字類型類的實(shí)例；為 SymbolicManip 實(shí)現(xiàn)我們自己的 Show 實(shí)例，使這棵樹在顯示時(shí)更友好。

完整代碼

這里是完整的 num.hs，我們?cè)诒竟?jié)開始的 ghci 例子中用到了它。我們來(lái)一點(diǎn)一點(diǎn)分析這段代碼。

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

我們?cè)谶@段代碼中定義了 Op，和之前我們用到的一樣。我們也定義了 SymbolicManip，它和我們之前用到的類似。在這個(gè)版本中，我們開始支持一元數(shù)學(xué)操作（unary arithmetic operations）（也就是接受一個(gè)參數(shù)的操作），例如 abs 和 cos。接下來(lái)我們來(lái)定義自己的 Num 實(shí)例。

-- 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，但現(xiàn)在可以了，因?yàn)橛辛?UnaryArith。接下來(lái)，我們?cè)俣x幾個(gè)實(shí)例。

-- file: ch13/num.hs
{- 定義 SymbolicManip 為 Fractional 實(shí)例 -}
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 實(shí)例 -}
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 實(shí)例。接下來(lái)，我們把表達(dá)式轉(zhuǎn)換字符串。

-- file: ch13/num.hs
{- 使用常規(guī)代數(shù)表示法，把 SymbolicManip 轉(zhuǎn)換為字符串 -}
prettyShow :: (Show a, Num a) => SymbolicManip a -> String

-- 顯示字符或符號(hào)
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 = "**"

{- 在需要的地方添加括號(hào)。這個(gè)函數(shù)比較保守，有時(shí)候不需要也會(huì)加。
Haskell 在構(gòu)建 SymbolicManip 的時(shí)候已經(jīng)處理好優(yōu)先級(jí)了。-}
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

{- 調(diào)用 prettyShow 函數(shù)顯示 SymbolicManip 值 -}
instance (Show a, Num a) => Show (SymbolicManip a) where
    show a = prettyShow a

首先我們定義了 prettyShow 函數(shù)。它把一個(gè)表達(dá)式轉(zhuǎn)換成常規(guī)表達(dá)形式。算法相當(dāng)簡(jiǎn)單：數(shù)字和符號(hào)不做處理；二元操作是轉(zhuǎn)換后兩側(cè)的內(nèi)容加上中間的操作符；當(dāng)然我們也處理了一元操作。op2str 把 Op 轉(zhuǎn)為 String。在 simpleParen 里，我們加括號(hào)的算法非常保守，以確保優(yōu)先級(jí)在結(jié)果里清楚顯示。最后，我們聲明 SymbolicManip 為 Show 的實(shí)例然后用 prettyShow 來(lái)實(shí)現(xiàn)?，F(xiàn)在，我們來(lái)設(shè)計(jì)一個(gè)算法把表達(dá)式轉(zhuǎn)為 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 愛好者會(huì)發(fā)現(xiàn)，跟上面的算法相比，這個(gè)算法是多么簡(jiǎn)潔。尤其是，我們根本不用關(guān)心要從哪里加括號(hào)，因?yàn)?RPN 天生只能沿著一個(gè)方向求值。接下來(lái)，我們寫個(gè)函數(shù)來(lái)實(shí)現(xiàn)一些基本的表達(dá)式化簡(jiǎn)。

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

這個(gè)函數(shù)相當(dāng)簡(jiǎn)單。我們很輕易地就能化簡(jiǎn)某些二元數(shù)學(xué)運(yùn)算——例如，用1乘以任何值。我們首先得到操作符兩側(cè)操作數(shù)被化簡(jiǎn)之后的版本（在這兒用到了遞歸）然后再化簡(jiǎn)結(jié)果。對(duì)于一元操作符我們能做的不多，所以我們僅僅簡(jiǎn)化它們作用于的表達(dá)式。

從現(xiàn)在開始，我們會(huì)增加對(duì)計(jì)量單位的支持。增加之后我們就能表示“5米”這種數(shù)量了。跟之前一樣，我們先來(lái)定義一個(gè)類型：

-- file: ch13/num.hs
{- 新數(shù)據(jù)類型：Units。Units 類型包含一個(gè)數(shù)字和一個(gè) SymbolicManip，也就是計(jì)量單位。
計(jì)量單位符號(hào)可以是 (Symbol "m") 這個(gè)樣子。 -}
data Units a = Units a (SymbolicManip a)
             deriving (Eq)

一個(gè) Units 值包含一個(gè)數(shù)字和一個(gè)符號(hào)。符號(hào)本身是 SymbolicManip 類型。接下來(lái)，將 Units 聲明為 Num 實(shí)例。

-- file: ch13/num.hs
{- 為 Units 實(shí)現(xiàn) Num 實(shí)例。我們不知道如何轉(zhuǎn)換任意單位，因此當(dāng)不同單位的數(shù)字相加時(shí)，我們報(bào)告錯(cuò)誤。
對(duì)于乘法，我們生成對(duì)應(yīng)的新單位。 -}
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)

現(xiàn)在，我們應(yīng)該清楚為什么要用 SymbolicManip 而不是 String 來(lái)存儲(chǔ)計(jì)量單位了。做乘法時(shí)，計(jì)量單位也會(huì)發(fā)生改變。例如，5米乘以2米會(huì)得到10平方米。我們要求加法運(yùn)算的單位必須匹配，并用加法實(shí)現(xiàn)了減法。我們?cè)賮?lái)看幾個(gè) Units 的類型類實(shí)例。

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

雖然沒有實(shí)現(xiàn)所有函數(shù)，但大部分都定義了?，F(xiàn)在我們來(lái)定義幾個(gè)跟單位打交道的工具函數(shù)。

-- 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，使表達(dá)式更簡(jiǎn)潔。units5"m" 肯定要比 Units5(Symbol"m") 省事。我們還定義了 dropUnits，它把單位去掉只返回 Num。最后，我們定義了兩個(gè)函數(shù)，用來(lái)在角度和弧度之間轉(zhuǎn)換。接下來(lái)，我們給 Units 定義 Show 實(shí)例。

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

很簡(jiǎn)單。最后我們定義 test 變量用來(lái)測(cè)試。

-- file: ch13/num.hs
test :: (Num a) => a
test = 2 * 5 + 3

回頭看看這些代碼，我們已經(jīng)完成了既定目標(biāo)：給 SymbolicManip 實(shí)現(xiàn)更多實(shí)例；我們引入了新類型 Units，它包含一個(gè)數(shù)字和一個(gè)單位；我們實(shí)現(xiàn)了幾個(gè) show 函數(shù)，以便用不同的方式來(lái)轉(zhuǎn)換 SymbolicManip 和 Units。

這個(gè)例子還給了我們另外一點(diǎn)啟發(fā)。所有語(yǔ)言——即使那些包含對(duì)象和重載的——都有從某種角度看很獨(dú)特的地方。在 Haskell 里，這個(gè)“特殊”的部分很小。我們剛剛開發(fā)了一種新的表示法用來(lái)表示像數(shù)字一樣基本的東西，而且很容易就實(shí)現(xiàn)了。我們的新類型是一等類型，編譯器在編譯時(shí)就知道使用它哪個(gè)函數(shù)。Haskell 把代碼復(fù)用和互換（interchangeability）發(fā)揮到了極致。寫通用代碼很容易，而且很方便就能把它們用于多種不同類型的東西上。同樣容易的是創(chuàng)建新類型并使它們自動(dòng)成為系統(tǒng)的一等功能（first-class features）。

還記得本節(jié)開頭的 ghci 例子嗎？ 我們已經(jīng)實(shí)現(xiàn)了它的全部功能。你可以自己試試，看看它們是怎么工作的。

練習(xí)

1. 擴(kuò)展 prettyShow 函數(shù)，去掉不必要的括號(hào)。

把函數(shù)當(dāng)成數(shù)據(jù)來(lái)用

在命令式語(yǔ)言當(dāng)中，拼接兩個(gè)列表很容易。下面的 C 語(yǔ)言結(jié)構(gòu)維護(hù)了指向列表頭尾的指針：

struct list {
    struct node *head, *tail;
};

當(dāng)我們想把列表 B 拼接到列表 A 的尾部時(shí)，我們將 A 的最后一個(gè)節(jié)點(diǎn)指向 B 的 head 節(jié)點(diǎn)，再把 A 的 tail 指針指向 B 的 tail 節(jié)點(diǎn)。

很顯然，在 Haskell 里，如果我們想保持“純”的話，這種方法是有局限性的。由于純數(shù)據(jù)是不可變的，我們無(wú)法原地修改列表。Haskell 的 (++) 操作符通過生成一個(gè)新列表來(lái)拼接列表。

-- file: ch13/Append.hs
(++) :: [a] -> [a] -> [a]
(x:xs) ++ ys = x : xs ++ ys
_      ++ ys = ys

從代碼里可以看出，創(chuàng)建新列表的開銷取決于第一個(gè)列表的長(zhǎng)度。

我們經(jīng)常需要通過重復(fù)拼接列表來(lái)創(chuàng)建一個(gè)大列表。例如，在生成網(wǎng)頁(yè)內(nèi)容時(shí)我們可能想生成一個(gè) String。每當(dāng)有新內(nèi)容添加到網(wǎng)頁(yè)中時(shí)，我們會(huì)很自然地想到把它拼接到已有 String 的末尾。

如果每一次拼接的開銷都正比與初始列表的長(zhǎng)度，每一次拼接都把初始列表加的更長(zhǎng)，那么我們將會(huì)陷入一個(gè)很糟糕的情況：所有拼接的總開銷將會(huì)正比于最終列表長(zhǎng)度的平方。

為了更好地理解，我們來(lái)研究一下。(++) 操作符是右結(jié)合的。

ghci> :info (++)
(++) :: [a] -> [a] -> [a]   -- Defined in GHC.Base
infixr 5 ++

這意味著 Haskell 在求值表達(dá)式 "a"++"b"++"c" 時(shí)會(huì)從右向左進(jìn)行，就像加了括號(hào)一樣："a"++("b"++"c")。這對(duì)于提高性能非常有好處，因?yàn)樗鼤?huì)讓左側(cè)操作數(shù)始終保持最短。

當(dāng)我們重復(fù)向列表末尾拼接時(shí)，我們破壞了這種結(jié)合性。假設(shè)我們有一個(gè)列表 "a" 然后想把 "b" 拼接上去，我們把結(jié)果存儲(chǔ)在一個(gè)新列表里。稍后如果我們想把 "c" 拼接上去時(shí)，這時(shí)的左操作數(shù)已經(jīng)變成了 "ab"。在這種情況下，每次拼接都讓左操作數(shù)變得更長(zhǎng)。

與此同時(shí)，命令式語(yǔ)言的程序員卻在偷笑，因?yàn)樗麄冎貜?fù)拼接的開銷只取決于操作的次數(shù)。他們的性能是線性的，我們的是平方的。

當(dāng)像重復(fù)拼接列表這種常見任務(wù)都暴露出如此嚴(yán)重的性能問題時(shí)，我們有必要從另一個(gè)角度來(lái)看看問題了。

表達(dá)式 ("a"++) 是一個(gè) 節(jié) (section)，一個(gè)部分應(yīng)用的函數(shù)。它的類型是什么呢？

ghci> :type ("a" ++)
("a" ++) :: [Char] -> [Char]

由于這是一個(gè)函數(shù)，我們可以用 (.) 操作符把它和另一個(gè)節(jié)組合起來(lái)，例如 ("b"++)。

ghci> :type ("a" ++) . ("b" ++)
("a" ++) . ("b" ++) :: [Char] -> [Char]

新函數(shù)的類型和之前相同。當(dāng)我們停止組合函數(shù)，并向我們創(chuàng)造的函數(shù)提供一個(gè) String 會(huì)發(fā)生什么呢？

ghci> let f = ("a" ++) . ("b" ++)
ghci> f []
"ab"

我們實(shí)現(xiàn)了字符串拼接！我們利用這些部分應(yīng)用的函數(shù)來(lái)存儲(chǔ)數(shù)據(jù)，并且只要提供一個(gè)空列表就可以把數(shù)據(jù)提取出來(lái)。每一個(gè) (++) 和 (.) 部分應(yīng)用都代表了一次拼接，但它們并沒有真正完成拼接。

這個(gè)方法有兩點(diǎn)非常有趣。第一點(diǎn)是部分應(yīng)用的開銷是固定的，這樣多次部分應(yīng)用的開銷就是線性的。第二點(diǎn)是當(dāng)我們提供一個(gè) [] 值來(lái)從部分應(yīng)用鏈中提取最終列表時(shí)，求值會(huì)從右至左進(jìn)行。這使得 (++) 的左操作數(shù)盡可能小，使得所有拼接的總開銷是線性而不是平方。

通過使用這種并不太熟悉的數(shù)據(jù)表示方式，我們避免了一個(gè)性能泥潭，并且對(duì)“把函數(shù)當(dāng)成數(shù)據(jù)來(lái)用”有了新的認(rèn)識(shí)。順便說一下，這個(gè)技巧并不新鮮，它通常被稱為差異列表（difference list）。

還有一點(diǎn)沒講。盡管從理論上看差異列表非常吸引人，但如果在實(shí)際中把 (++)、(.) 和部分應(yīng)用都暴露在外的話，它并不會(huì)非常好用。我們需要把它轉(zhuǎn)成一種更好用的形式。

把差異列表轉(zhuǎn)成庫(kù)

第一步是用 newtype 聲明把底層的類型隱藏起來(lái)。我們會(huì)創(chuàng)建一個(gè) DList 類型。類似于普通列表，它是一個(gè)參數(shù)化類型。

-- file: ch13/DList.hs
newtype DList a = DL {
    unDL :: [a] -> [a]
    }

unDL 是我們的析構(gòu)函數(shù)，它把 DL 構(gòu)造器刪除掉。我們最后導(dǎo)出模塊函數(shù)時(shí)會(huì)忽略掉構(gòu)造函數(shù)和析構(gòu)函數(shù)，這樣我們的用戶就沒必要知道 DList 類型的實(shí)現(xiàn)細(xì)節(jié)。他們只用我們導(dǎo)出的函數(shù)即可。

-- file: ch13/DList.hs
append :: DList a -> DList a -> DList a
append xs ys = DL (unDL xs . unDL ys)

我們的 append 函數(shù)看起來(lái)可能有點(diǎn)復(fù)雜，但其實(shí)它僅僅是圍繞著 (.) 操作符做了一些簿記工作，(.) 的用法和我們之前展示的完全一樣。生成函數(shù)的時(shí)候，我們必須首先用 unDL 函數(shù)把它們從 DL 構(gòu)造器中取出來(lái)。然后我們?cè)诎训玫降慕Y(jié)果重新用 DL 包裝起來(lái)，確保它的類型正確。

下面是相同函數(shù)的另一種寫法，這種方法通過模式識(shí)別取出 xs 和 ys。

-- file: ch13/DList.hs
append' :: DList a -> DList a -> DList a
append' (DL xs) (DL ys) = DL (xs . ys)

我們需要在 DList 類型和普通列表之間來(lái)回轉(zhuǎn)換。

-- file: ch13/DList.hs
fromList :: [a] -> DList a
fromList xs = DL (xs ++)

toList :: DList a -> [a]
toList (DL xs) = xs []

再次聲明，跟這些函數(shù)最原始的版本相比，我們?cè)谶@里做的只是一些簿記工作。

如果我們想把 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 使得拼接很廉價(jià)，但并不是所有的列表操作都容易實(shí)現(xiàn)。列表的 head 函數(shù)具有常數(shù)開銷，而對(duì)應(yīng)的 DL