〈Haskell Tutorial（19）Data.Set 與 Data.Map 模組〉題目解答之二

Set.hs

module Set
(
    fromList,
    intersection,
    union
) where

import qualified Tree

data Set a = Set (Tree.Tree a)

fromList :: Ord a => [a] -> Set a
fromList = Set . Tree.fromList

intersection :: Ord a => Set a -> Set a -> Set a
intersection (Set t1) (Set t2) =
    let l2 = Tree.toList t2
    in Set (Tree.fromList (filter (`elem` l2) (Tree.toList t1)))

union :: Ord a => Set a -> Set a -> Set a
union (Set t1) (Set t2) =
    let l = filter (\ele -> not (Tree.node ele t2)) (Tree.toList t1)
    in Set (foldr (\ele t -> Tree.insert ele t) t2 l)

toList :: Set a -> [a]
toList (Set t) = Tree.toList t

instance Show a => Show (Set a) where
    show set = "fromList " ++ (show . toList) set