第十三章：數(shù)據結構
第十三章：數(shù)據結構
關聯(lián)列表
我們常常會跟一些以鍵為索引的無序數(shù)據打交道。
舉個例子，UNIX 管理猿可能需要這么一個列表，它包含系統(tǒng)中所有用戶的 UID ，以及和這個 UID 相對應的用戶名。這個列表根據 UID 而不是數(shù)據的位置來查找相應的用戶名。換句話來說， UID 就是這個數(shù)據集的鍵。
Haskell 里有幾種不同的方法來處理這種結構的數(shù)據，最常用的兩個是關聯(lián)列表（association list）和 Data.Map 模塊提供的 Map 類型。
關聯(lián)列表非常簡單，易于使用。由于關聯(lián)列表由 Haskell 列表構成，因此所有列表操作函數(shù)都可以用于處理關聯(lián)列表。
另一方面， Map 類型在處理大數(shù)據集時，性能比關聯(lián)列表要好。
本章將同時介紹這兩種數(shù)據結構。
關聯(lián)列表就是包含一個或多個 (key,value) 元組的列表， key 和 value 可以是任意類型。一個處理 UID 和用戶名映射的關聯(lián)列表的類型可能是 [(Integer,String)] 。
[注：關聯(lián)列表的 key 必須是 Eq 類型的成員。]
關聯(lián)列表的構建方式和普通列表一樣。Haskell 提供了一個 Data.List.lookup 函數(shù)，用于在關聯(lián)列表中查找數(shù)據。這個函數(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 在輸入列表為空時返回 Nothing 。如果輸入列表不為空，那么它檢查當前列表元素的 key 是否就是我們要找的 key ，如果是的話就返回和這個 key 對應的 value ，否則就繼續(xù)遞歸處理剩余的列表元素。
再來看一個稍微復雜點的例子。在 Unix/Linux 系統(tǒng)中，有一個 /etc/passwd 文件，這個文件保存了用戶名稱， UID，用戶的 HOME 目錄位置，以及其他一些數(shù)據。文件以行分割每個用戶的資料，每個數(shù)據域用冒號隔開：
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)建一個關聯(lián)列表，使得我們可以根據給定 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 函數(shù)根據給定分隔符 delimiter 將一個文本行分割為列表：
*Main> split ':' "root:x:0:0:root:/root:/bin/bash"
["root","x","0","0","root","/root","/bin/bash"]
以下是在本機執(zhí)行 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 類型的行為和關聯(lián)列表類似，但 Map 類型的性能更好。
Map 和其他語言提供的哈希表類似。不同的是， Map 的內部由平衡二叉樹實現(xiàn)，在 Haskell 這種使用不可變數(shù)據的語言中，它是一個比哈希表更高效的表示。這是一個非常明顯的例子，說明純函數(shù)式語言是如何深入地影響我們編寫程序的方式：對于一個給定的任務，我們總是選擇合適的算法和數(shù)據結構，使得解決方案盡可能地簡單和有效，但這些（純函數(shù)式的）選擇通常不同于命令式語言處理同樣問題時的選擇。
因為 Data.Map 模塊的一些函數(shù)和 Prelude 模塊的函數(shù)重名，我們通過 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 函數(shù)處理數(shù)據的方式非?！?Haskell 化』：它返回經過函數(shù)應用的輸入數(shù)據的副本。這種處理數(shù)據的方式在操作多個 Map 時非常有用，它意味著你可以像前面代碼中 mapFold 那樣使用 fold 來構建一個 Map ，又或者像 mapManual 那樣，串連起多個 Map.insert 調用。
[譯注：這里說『 Haskell 化』實際上就是『函數(shù)式化』，對于函數(shù)式語言來說，最常見的函數(shù)處理方式是接受一個輸入，然后返回一個輸出，輸出是另一個獨立的值，且原輸入不會被修改。]
現(xiàn)在，到 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 的操作方式和關聯(lián)列表類似。 Data.Map 模塊提供了一組函數(shù)，用于增刪 Map 元素，對 Map 進行過濾、修改和 fold ，以及在 Map 和關聯(lián)列表之間進行轉換。 Data.Map 模塊本身的文檔非常優(yōu)秀，因此我們在這里不會詳細講解每個函數(shù)，而是在本章的后續(xù)內容中，通過例子來介紹這些概念。
函數(shù)也是數(shù)據
Haskell 語言的威力部分在于它可以讓我們方便地創(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 域的類型：它是一個函數(shù)，接受一個 Int 類型值作為參數(shù)，并返回一個 (CustomColor,Int) 元組。
我們創(chuàng)建了兩個 FuncRec 記錄： plus5 和 always0 ，這兩個記錄的 colorCalc 域都總是返回紫色（purple）。 FuncRec 自身并沒有域去保存所使用的顏色，顏色的值被保存在函數(shù)當中 —— 我們稱這種用法為閉包。
以下是示例代碼：
*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)
上面的程序工作得很好，但我們還想做一些更有趣的事，比如說，在多個域中使用同一段數(shù)據?？梢允褂靡粋€類型構造函數(shù)來做到這一點：
-- 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ù)接受一個字符串和一個函數(shù)作為參數(shù)，返回一個新的 FuncRec 記錄。以下是對 mkFuncRecs 函數(shù)的測試：
*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 域。這就是為什么調用 name 會返回新名字，而 namedCalc 依然返回原本使用 mkFuncRecs 創(chuàng)建時設置的名字 —— 除非我們顯式地修改域，否則它們不會被改變。
擴展示例： /etc/password
以下是一個擴展示例，它展示了幾種不同的數(shù)據結構的用法，根據 /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 。有數(shù)據庫使用經驗的人可以將它們看作是兩個不同數(shù)據域的索引。
根據 /etc/passwd 文件的格式， PasswdEntry 的 Show 和 Read 實例分別用于顯示（display）和處理（parse）工作。
擴展示例：數(shù)字類型（Numeric Types）
我們已經講過 Haskell 的類型系統(tǒng)有多強大，表達能力有多強。我們已經講過很多利用這種能力的方法。現(xiàn)在我們來舉一個實際的例子看看。
在 數(shù)字類型 一節(jié)中，我們展示了 Haskell 的數(shù)字類型類?，F(xiàn)在，我們來定義一些類，然后用數(shù)字類型類把它們和 Haskell 的基本數(shù)學結合起來，看看能得到什么。
我們先來想想我們想用這些新類型在 ghci 里干什么。首先，一個不錯的選擇是把數(shù)學表達式轉成字符串，并確保它顯示了正確的優(yōu)先級。我們可以寫一個 prettyShow 函數(shù)來實現(xiàn)。稍后我們就告訴你怎么寫，先來看看怎么用它。
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* 從表達式里拿掉。寫個函數(shù)來簡化怎么樣？
ghci> prettyShow $ simplify $ 5 + 1 * 3
"5+3"
把數(shù)學表達式轉成逆波蘭表達式（RPN）怎么樣？RPN 是一種后綴表示法，它不要求括號，常見于 HP 計算器。RPN 是一種基于棧的表達式。我們把數(shù)字放進棧里，當碰到操作符時，棧頂?shù)臄?shù)字出棧，結果再被放回棧里。
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)"
跟數(shù)字打交道時，單位常常很重要。例如，當你看見數(shù)字5時，它是5米，5英尺，還是5字節(jié)？當然，當你用5米除以2秒時，系統(tǒ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
如果我們定義的表達式或函數(shù)對所有數(shù)字都合法，那我們就應該能計算出結果，或者把表達式轉成字符串。例如，如果我們定義 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 +"
既然我們能處理單位，那我們也應該能處理一些基本的三角函數(shù)，其中很多操作都是關于角的。讓我們確保角度和弧度都能被處理。
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 的類型和類型類實現(xiàn)。實際上，你看到的正是我們馬上要實現(xiàn)的 num.hs。
第一步
我們想想怎么實現(xiàn)上面提到的功能。首先，用 ghci 查看一下可知，(+) 的類型是 Numa=>a->a->a。如果我們想給加號實現(xiàn)一些自定義行為，我們就必須定義一個新類型并聲明它為 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 實現(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 類型。這個類型表示我們要支持的操作。接著，我們定義了 SymbolicManipa，由于 Numa 約束的存在，a 可替換為任何 Num 實例。我們可以有 SymbolicManipInt 這樣的具體類型。
SymbolicManip 類型可以是數(shù)字，也可以是數(shù)學運算。Arith 構造器是遞歸的，這在 Haskell 里完全合法。Arith 用一個 Op 和兩個 SymbolicManip 創(chuàng)建了一個 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 已經是一等數(shù)字（first-class number）了。就算 Integer 類型的數(shù)字字面量（numeric literals）在內部也是被包裝在 fromInteger 里的，所以 5 作為一個 SymbolicManipInt 和作為一個 Int 同樣有效。
從這兒開始，我們的任務就簡單了：擴展 SymbolicManip，使它能表示所有我們想要的操作；把它聲明為其它數(shù)字類型類的實例；為 SymbolicManip 實現(xiàn)我們自己的 Show 實例，使這棵樹在顯示時更友好。
完整代碼
這里是完整的 num.hs，我們在本節(jié)開始的 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，它和我們之前用到的類似。在這個版本中，我們開始支持一元數(shù)學操作（unary arithmetic operations）（也就是接受一個參數(shù)的操作），例如 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，但現(xiàn)在可以了，因為有了 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
{- 使用常規(guī)代數(shù)表示法，把 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 = "**"
{- 在需要的地方添加括號。這個函數(shù)比較保守，有時候不需要也會加。
Haskell 在構建 SymbolicManip 的時候已經處理好優(yōu)先級了。-}
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 函數(shù)顯示 SymbolicManip 值 -}
instance (Show a, Num a) => Show (SymbolicManip a) where
show a = prettyShow a
首先我們定義了 prettyShow 函數(shù)。它把一個表達式轉換成常規(guī)表達形式。算法相當簡單：數(shù)字和符號不做處理；二元操作是轉換后兩側的內容加上中間的操作符；當然我們也處理了一元操作。op2str 把 Op 轉為 String。在 simpleParen 里，我們加括號的算法非常保守，以確保優(yōu)先級在結果里清楚顯示。最后，我們聲明 SymbolicManip 為 Show 的實例然后用 prettyShow 來實現(xiàn)?，F(xià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 愛好者會發(fā)現(xiàn)，跟上面的算法相比，這個算法是多么簡潔。尤其是，我們根本不用關心要從哪里加括號，因為 RPN 天生只能沿著一個方向求值。接下來，我們寫個函數(shù)來實現(xià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
這個函數(shù)相當簡單。我們很輕易地就能化簡某些二元數(shù)學運算——例如，用1乘以任何值。我們首先得到操作符兩側操作數(shù)被化簡之后的版本（在這兒用到了遞歸）然后再化簡結果。對于一元操作符我們能做的不多，所以我們僅僅簡化它們作用于的表達式。
從現(xiàn)在開始，我們會增加對計量單位的支持。增加之后我們就能表示“5米”這種數(shù)量了。跟之前一樣，我們先來定義一個類型：
-- file: ch13/num.hs
{- 新數(shù)據類型：Units。Units 類型包含一個數(shù)字和一個 SymbolicManip，也就是計量單位。
計量單位符號可以是 (Symbol "m") 這個樣子。 -}
data Units a = Units a (SymbolicManip a)
deriving (Eq)
一個 Units 值包含一個數(shù)字和一個符號。符號本身是 SymbolicManip 類型。接下來，將 Units 聲明為 Num 實例。
-- file: ch13/num.hs
{- 為 Units 實現(xiàn) Num 實例。我們不知道如何轉換任意單位，因此當不同單位的數(shù)字相加時，我們報告錯誤。
對于乘法，我們生成對應的新單位。 -}
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)在，我們應該清楚為什么要用 SymbolicManip 而不是 String 來存儲計量單位了。做乘法時，計量單位也會發(fā)生改變。例如，5米乘以2米會得到10平方米。我們要求加法運算的單位必須匹配，并用加法實現(xiàn)了減法。我們再來看幾個 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"
雖然沒有實現(xiàn)所有函數(shù)，但大部分都定義了?，F(xiàn)在我們來定義幾個跟單位打交道的工具函數(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，使表達式更簡潔。units5"m" 肯定要比 Units5(Symbol"m") 省事。我們還定義了 dropUnits，它把單位去掉只返回 Num。最后，我們定義了兩個函數(shù)，用來在角度和弧度之間轉換。接下來，我們給 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 實現(xiàn)更多實例；我們引入了新類型 Units，它包含一個數(shù)字和一個單位；我們實現(xiàn)了幾個 show 函數(shù)，以便用不同的方式來轉換 SymbolicManip 和 Units。
這個例子還給了我們另外一點啟發(fā)。所有語言——即使那些包含對象和重載的——都有從某種角度看很獨特的地方。在 Haskell 里，這個“特殊”的部分很小。我們剛剛開發(fā)了一種新的表示法用來表示像數(shù)字一樣基本的東西，而且很容易就實現(xiàn)了。我們的新類型是一等類型，編譯器在編譯時就知道使用它哪個函數(shù)。Haskell 把代碼復用和互換（interchangeability）發(fā)揮到了極致。寫通用代碼很容易，而且很方便就能把它們用于多種不同類型的東西上。同樣容易的是創(chuàng)建新類型并使它們自動成為系統(tǒng)的一等功能（first-class features）。
還記得本節(jié)開頭的 ghci 例子嗎？ 我們已經實現(xiàn)了它的全部功能。你可以自己試試，看看它們是怎么工作的。
練習
- 擴展 prettyShow 函數(shù)，去掉不必要的括號。
把函數(shù)當成數(shù)據來用
在命令式語言當中，拼接兩個列表很容易。下面的 C 語言結構維護了指向列表頭尾的指針：
struct list {
struct node *head, *tail;
};
當我們想把列表 B 拼接到列表 A 的尾部時，我們將 A 的最后一個節(jié)點指向 B 的 head 節(jié)點，再把 A 的 tail 指針指向 B 的 tail 節(jié)點。
很顯然，在 Haskell 里，如果我們想保持“純”的話，這種方法是有局限性的。由于純數(shù)據是不可變的，我們無法原地修改列表。Haskell 的 (++) 操作符通過生成一個新列表來拼接列表。
-- file: ch13/Append.hs
(++) :: [a] -> [a] -> [a]
(x:xs) ++ ys = x : xs ++ ys
_ ++ ys = ys
從代碼里可以看出，創(chuàng)建新列表的開銷取決于第一個列表的長度。
我們經常需要通過重復拼接列表來創(chuàng)建一個大列表。例如，在生成網頁內容時我們可能想生成一個 String。每當有新內容添加到網頁中時，我們會很自然地想到把它拼接到已有 String 的末尾。
如果每一次拼接的開銷都正比與初始列表的長度，每一次拼接都把初始列表加的更長，那么我們將會陷入一個很糟糕的情況：所有拼接的總開銷將會正比于最終列表長度的平方。
為了更好地理解，我們來研究一下。(++) 操作符是右結合的。
ghci> :info (++)
(++) :: [a] -> [a] -> [a] -- Defined in GHC.Base
infixr 5 ++
這意味著 Haskell 在求值表達式 "a"++"b"++"c" 時會從右向左進行，就像加了括號一樣："a"++("b"++"c")。這對于提高性能非常有好處，因為它會讓左側操作數(shù)始終保持最短。
當我們重復向列表末尾拼接時，我們破壞了這種結合性。假設我們有一個列表 "a" 然后想把 "b" 拼接上去，我們把結果存儲在一個新列表里。稍后如果我們想把 "c" 拼接上去時，這時的左操作數(shù)已經變成了 "ab"。在這種情況下，每次拼接都讓左操作數(shù)變得更長。
與此同時，命令式語言的程序員卻在偷笑，因為他們重復拼接的開銷只取決于操作的次數(shù)。他們的性能是線性的，我們的是平方的。
當像重復拼接列表這種常見任務都暴露出如此嚴重的性能問題時，我們有必要從另一個角度來看看問題了。
表達式 ("a"++) 是一個 節(jié) (section)，一個部分應用的函數(shù)。它的類型是什么呢？
ghci> :type ("a" ++)
("a" ++) :: [Char] -> [Char]
由于這是一個函數(shù)，我們可以用 (.) 操作符把它和另一個節(jié)組合起來，例如 ("b"++)。
ghci> :type ("a" ++) . ("b" ++)
("a" ++) . ("b" ++) :: [Char] -> [Char]
新函數(shù)的類型和之前相同。當我們停止組合函數(shù)，并向我們創(chuàng)造的函數(shù)提供一個 String 會發(fā)生什么呢？
ghci> let f = ("a" ++) . ("b" ++)
ghci> f []
"ab"
我們實現(xiàn)了字符串拼接！我們利用這些部分應用的函數(shù)來存儲數(shù)據，并且只要提供一個空列表就可以把數(shù)據提取出來。每一個 (++) 和 (.) 部分應用都代表了一次拼接，但它們并沒有真正完成拼接。
這個方法有兩點非常有趣。第一點是部分應用的開銷是固定的，這樣多次部分應用的開銷就是線性的。第二點是當我們提供一個 [] 值來從部分應用鏈中提取最終列表時，求值會從右至左進行。這使得 (++) 的左操作數(shù)盡可能小，使得所有拼接的總開銷是線性而不是平方。
通過使用這種并不太熟悉的數(shù)據表示方式，我們避免了一個性能泥潭，并且對“把函數(shù)當成數(shù)據來用”有了新的認識。順便說一下，這個技巧并不新鮮，它通常被稱為差異列表（difference list）。
還有一點沒講。盡管從理論上看差異列表非常吸引人，但如果在實際中把 (++)、(.) 和部分應用都暴露在外的話，它并不會非常好用。我們需要把它轉成一種更好用的形式。
把差異列表轉成庫
第一步是用 newtype 聲明把底層的類型隱藏起來。我們會創(chuàng)建一個 DList 類型。類似于普通列表，它是一個參數(shù)化類型。
-- file: ch13/DList.hs
newtype DList a = DL {
unDL :: [a] -> [a]
}
unDL 是我們的析構函數(shù)，它把 DL 構造器刪除掉。我們最后導出模塊函數(shù)時會忽略掉構造函數(shù)和析構函數(shù)，這樣我們的用戶就沒必要知道 DList 類型的實現(xiàn)細節(jié)。他們只用我們導出的函數(shù)即可。
-- file: ch13/DList.hs
append :: DList a -> DList a -> DList a
append xs ys = DL (unDL xs . unDL ys)
我們的 append 函數(shù)看起來可能有點復雜，但其實它僅僅是圍繞著 (.) 操作符做了一些簿記工作，(.) 的用法和我們之前展示的完全一樣。生成函數(shù)的時候，我們必須首先用 unDL 函數(shù)把它們從 DL 構造器中取出來。然后我們在把得到的結果重新用 DL 包裝起來，確保它的類型正確。
下面是相同函數(shù)的另一種寫法，這種方法通過模式識別取出 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 []
再次聲明，跟這些函數(shù)最原始的版本相比，我們在這里做的只是一些簿記工作。
如果我們想把 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 使得拼接很廉價，但并不是所有的列表操作都容易實現(xiàn)。列表的 head 函數(shù)具有常數(shù)開銷，而對應的 DL
掃描二維碼
下載編程獅App
編程獅公眾號
更多建議：