Haskell/庫/資料結構入門

本章介紹了庫中提供的一些資料結構。我們將重點關注一些常見且特別有用的示例，每個 Haskell 程式設計師都應該瞭解這些示例。

權衡

本章不斷強調列表的缺點，但這並不意味著你應該停止使用它們！列表是 Haskell 中預設的資料結構，原因有很多：除了簡單性之外，列表在懶惰的純函式式環境中具有相當高的功率重量比。惰性使得列表能夠用作 *流*，我們按需順序處理生成的元素。該過程允許諸如 map、filter、foldr、takeWhile 和 zipWith 等函式作為許多常見迭代控制結構使用的有效替代品。

儘管列表可能很強大，但它們更適合流式傳輸和迭代控制等模式，而不是簡單的資料儲存和檢索。當然，切換到不同的資料結構會涉及權衡。任何資料結構都有優點和缺點，正確的選擇取決於手頭的任務。

查詢：Data.Map 及其相關

首先，我們將考慮一個常見的問題：對資料結構執行查詢。給定一個鍵和值之間關聯的集合，我們可能希望檢索與某個鍵對應的值（如果有的話）。我們可以簡單地將關聯儲存為一對列表，[(k, v)]。事實上，Prelude 包含 lookup :: Eq k => k -> [(k, v)] -> Maybe v，但是要從列表中找到一個值，我們必須遍歷列表中的所有對，測試鍵是否相等，直到我們找到我們要找的鍵（或者遍歷完列表）。在普通關聯列表中的查詢是 *O(n)* 操作，因為執行它所需的預期步驟數與列表長度成正比。不難看出，當關聯很多時，這將成為一個問題。

我們可以透過切換到更合適的資料結構來實現更好的查詢。由 containers 包中的 Data.Map 提供的 Map 型別是一個不錯的通用選擇。請注意，Data.Map 通常被匯入限定，以避免與 Prelude 函式發生名稱衝突。

GHCi> import qualified Data.Map as M
GHCi> :t M.empty
M.empty :: M.Map k a

在 Map 中，鍵和值被排列在一個（大小平衡的二叉）樹中。這種樹形結構使得查詢一個鍵只需簡單地沿著樹的特定分支向下遍歷即可。然而，樹的操作完全在幕後進行。Map 與庫中的許多其他資料結構一樣，透過一個不涉及樹實現的介面用作 *抽象* 型別。特別是，建構函式不被匯出：一個新的 Map 是透過以下方式構建的，例如，將關聯插入到一個 empty 對映中，或者透過使用實用函式 fromList

GHCi> let foo = M.fromList [(1, "Robert"), (5, "Ian"), (6, "Bruce")]
GHCi> :t foo
foo :: M.Map Integer [Char]

Data.Map 介面提供了 *O(log n)* 查詢...

GHCi> :t M.lookup
M.lookup :: Ord k => k -> M.Map k a -> Maybe a
GHCi> M.lookup 5 foo
Just "Ian"
GHCi> M.lookup 7 foo
Nothing

...以及許多其他有用的操作 - 並集、交集、刪除等等。一些重要型別類的例項（例如 Functor）也可用。

GHCi> M.size $ M.union foo $ M.fromList [(11, "Andrew"), (17, "Mike")]
5
GHCi> fmap reverse foo
fromList [(1,"treboR"),(5,"naI"),(6,"ecurB")]

變體

其他提供對映和類似對映的資料結構的模組值得了解，包括

• containers 中的 Data.IntMap 提供了一個更有效的對映實現，它僅限於 Int 鍵。
• containers 中的 Data.Set 提供了一個 *集合* 實現。集合適合於當有趣的操作只是查詢一個值是否在一個集合中，而不是檢索給定鍵的值。它們很像一個對映，其中只有鍵很重要，因此關於效能和實現的許多考慮因素都適用於集合和對映。
• unordered-containers 包提供了 *雜湊* 對映和集合。它們在不限制鍵型別為 Int 的情況下提供了效率提升（例如，幾乎恆定的查詢時間），代價是相對有限的介面和損失了 container 基於樹的對映的排序保證。

用 Data.Sequence 窺視兩端

列表的一個特點是它們是不對稱的。鑑於我們使用 `(:)` 透過頭部構建和解構列表，頭部操作比尾部操作效率更高。例如，雖然用 `(:)` 新增元素需要恆定的時間，但天真地用 \xs x -> xs ++ [x] 新增單個元素需要與 xs 長度成正比的時間。這意味著透過重複新增來構建列表將花費 *二次* 時間，這在元素數量上非常糟糕。

當必須對中間或尾部執行大量操作時，一個非常棒的列表類替代品是 *序列*，如 Data.Sequence 模組提供的，它也是 containers 的一部分。序列和列表在很多方面都不同，儘管許多熟悉的列表函式以某種形式出現在 Data.Sequence 中。雖然列表是懶惰的並且可以是無限的，但序列是有限的並且是嚴格的。使得序列有用的權衡是，以犧牲列表的一些開銷為代價，許多在列表中很麻煩的操作執行得更好。值得注意的是，我們可以得到在恆定時間內新增和新增、在恆定時間內獲得長度，以及在對數時間內進行連線和隨機訪問。所有這些都可透過一個令人愉快的純函式式介面獲得。

GHCi> import qualified Data.Sequence as S
GHCi> import Data.Sequence((<|), (|>), (><), ViewL(..), ViewR(..))
GHCi> let foo = S.fromList [1, 3, 5, 2, 9]
GHCi> :t foo
foo :: S.Seq Integer

(<|) 新增到頭部，(|>) 新增到尾部，(><) 連線。

GHCi> 0 <| foo
fromList [0,1,3,5,2,9]
GHCi> foo |> 18
fromList [1,3,5,2,9,18]
GHCi> foo >< foo
fromList [1,3,5,2,9,1,3,5,2,9]

你也可以在兩端進行模式匹配。為此，你可以使用 viewl 或 viewr 來獲取序列的所需檢視，然後分別使用 EmptyL 和 (:<) 以及 EmptyR 和 (:>) 進行匹配。

GHCi> S.viewl foo
1 :< fromList [3,5,2,9]
GHCi> S.viewr foo
fromList [1,3,5,2] :> 9
GHCi> let xs :> x = S.viewr foo
GHCi> xs
fromList [1,3,5,2]
GHCi> x
9

使用陣列進行原始效能

處理大量資料時的效能要求可能非常嚴格。對於需要快速處理大量資料的場景，惰性和流式傳輸不是相關問題，Haskell 提供了與 C 等語言中發現的類似的真陣列。陣列在記憶體方面是緊湊的，提供恆定的時間隨機訪問和許多極快的操作（主要例外是那些需要複製陣列的操作，例如不可變陣列連線），代價是由於陣列與我們通常處理的純函式式資料結構的行為之間的深刻差異而造成的一定程度的笨拙。有幾個陣列庫可用；它們通常提供多種型別的陣列 - 從那些使用起來與其他資料結構庫（如 containers）中的介面感覺不太不同的陣列到 C 風格的原始原始值的可變陣列。^[1] 在這裡，我們將提到三個最流行的陣列庫。

• vector 是一個不錯的預設選擇，如果你剛剛開始使用陣列，或者如果你沒有其他庫涵蓋的專門需求。它提供了一維陣列，其介面與其他資料結構庫（如 containers）中的介面相當類似。

• array 相反，它的介面更加令人望而生畏。至於功能，它支援多維陣列和自定義索引。重要的是，它也是語言標準的一部分，並且與 GHC 捆綁在一起，這對那些不想產生額外依賴關係的庫編寫者很有用。我們在 單獨的章節 中提供了標準陣列的概述，可以用作陣列相關術語的介紹。

• repa 是一個提供最先進的多維可並行陣列的複雜庫。它非常適合諸如影像處理之類的任務。

text、bytestring 和 String 的問題

快速瀏覽一下 base 庫，我們可能會留下這樣的印象：String 是將資料輸入和輸出 Haskell 程式的首選方式。但是，String 有幾個問題，使其不適合這樣的角色。

• 最明顯的問題是效能。String 只是一個 Char 列表。在需要處理中等甚至相當大文字或二進位制資料的應用程式中，通用連結串列的優勢被相對於專用實現可能實現的效率的巨大損失所掩蓋。

• 對於二進位制資料，更深層的問題是基於 Char 的表示沒有意義，因為我們實際上正在處理原始位元組。

• 最後，雖然 Haskell Char 是 Unicode 字元，但總體而言，base 庫對不同編碼和國際化的支援有些不足。

text 和 bytestring 庫解決了 String 的這些缺點。這兩個庫都是 *事實上的* 標準；幾乎所有現代庫，其功能涉及任何大量資料輸入或輸出，都使用它們。它們有明顯不同的用例。

• text 用於高效處理 Unicode 文字。它支援編碼之間的轉換，並且透過配套的 text-icu 庫，支援各種 Unicode 服務。

• bytestring 用於高效處理二進位制資料，無論其形式如何——案例包括網路資料包、原始影像資料、序列化（透過 binary 和 cereal 等庫）；任你選擇。

這兩個庫的核心型別 Text 和 ByteString 分別用作 Char 和 Word8（即原始位元組）的專門的單態容器。內部表示是基於陣列的，非常緊湊。在介面方面，這兩個庫都非常簡單明瞭。需要注意的主要細微之處是，在這兩種情況下，型別都有 *嚴格的* 和 *惰性的* 變體。嚴格版本非常適合處理大量小資料塊，而惰性版本則以塊的形式進行處理，因此允許流式處理和處理大型單片資料，而不會出現記憶體消耗問題。

在處理 String 替換時，值得注意的一個便利功能是 OverloadedStrings GHC 擴充套件允許將字串字面量自動、型別引導地轉換為 Text 或 ByteString。這非常有用，尤其是在使用 Text 時。