Haskell Tutorial（18）認識 Data.List 模組 << 前情

程式大多在處理一組資料，依需求的不同，你需要不同的容器來管理資料，List 是有序、具索引的容器，除此之外，常用的資料容器還有集合（Set）與字典（Dictionary）等，這邊就先來探討與這兩種容器相關的 Data.Set 與 Data.Map 模組。

Data.Set 模組

集合不允許元素重複，一個 List 中若沒有重複的元素，某些程度就可以當作集合來看待，為了方便，最好是寫個 fromList，自動從指定的 List 中去除重複的元素：

module Set
(
    fromList,
    intersection,
    union 
) where

fromList :: Eq a => [a] -> [a]
fromList [] = []
fromList (x:xs) = x : fromList (filter (/= x) xs)

intersection :: Eq a => [a] -> [a] -> [a]
intersection xs1 xs2 = filter (`elem` xs2) xs1

union :: Eq a => [a] -> [a] -> [a]
union xs1 xs2 = filter (`notElem` xs2) xs1 ++ xs2

這個簡單的自訂模組也示範了交集、聯集的運算：

實際上，由於集合要能判斷重複元素，每次走訪都從 List 頭到尾，效率並不好，因此，最好能實作為具有排序能力的樹狀結構，例如，上面的 fromList，可以直接使用 Data.List 的 nub，也能達到相同功能，不過面對較長的 List，就會有效率的問題。

Haskell 的 Data.Set 模組就提供了相關功能，因為要能排序，要使用 Data.Set 的 fromList 等函式，你的元素必須是可排序的，也就是必須具有 Ord 的行為：

Data.Set 接受的元素必須具有 Ord 的行為，在於內部實作使用了樹狀結構，元素被加入樹時都會排序，因此，下個元素再加入時就可以很快地判定集合中是不是有重複元素，而不用像 nub 必須逐一對集合中的元素做相等比較，因此，對於較長的 List，想要取得不重複元素的 List，使用 Data.Set 的 fromList 後再用 toList，就可以得到，而且效率較好。

如果你想快速地瞭解這個模組還有哪些常用函式可以使用，可以參考 Data.Set。

Data.Map 模組

在〈Haskell Tutorial（17）定義與使用模組〉中，稍微探討過 Map 的實作：

module Map
( 
    Map,
    empty,
    fromList,
    findValue
) where

data Map k v = Empty | Cm (k, v) (Map k v)

empty = Empty

fromList :: [(k, v)] -> Map k v
fromList [] = Empty
fromList (x:xs) = Cm x (fromList xs)

findValue :: (Eq k) => k -> Map k v -> Maybe v
findValue key Empty = Nothing
findValue key (Cm (k, v) xm) =
    if key == k then Just v else findValue key xm

這個實作的出發點在於，可以使用 List，而其中元素為 (k, v) 的 Tuple 來模擬 Map，之後再定義專屬型能，當然，這個實作是很簡單的，第一，它沒有檢查鍵（Key）可能重複的情況，第二，findValue 每次都逐一走訪每個元素，效率並不好。

Data.Map 模組提供了字典（Dictionary）操作的相關功能，內部實作是樹狀結構，你的鍵必須具有 Ord 的行為，下面的示範，因為 lookup 方法會有名稱衝突，因此使用了 import qualified Data.Map as Map：

如果你想快速地瞭解這個模組還有哪些常用函式可以使用，可以參考 Data.Map。

既然談到了樹狀結構，最後來出個題目，試著實作一個 Tree 型態，並提供 fromList 函式可從 List 建立樹、insert 函式可將指定數值插入樹、node 函式可測試某節點是否在樹中、toList 可將樹轉為 List，例如：

進一步地，你可以試著改用以上自訂的樹，改寫先前的 Set 模組實作嗎？

後續 >> Haskell Tutorial（20）初探 IO 型態