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

Tree.hs

module Tree
(
    Tree,
    fromList,
    singleNode,
    insert,
    node,
    toList
) where

data Tree a = EmptyTree | Node a (Tree a) (Tree a)

singleNode :: a -> Tree a
singleNode x = Node x EmptyTree EmptyTree

insert :: (Ord a) => a -> Tree a -> Tree a
insert x EmptyTree = singleNode x
insert x (Node a l r)
      | x == a = Node x l r
      | x < a  = Node a (insert x l) r
      | x > a  = Node a l (insert x r)

fromList :: Ord a => [a] -> Tree a
fromList [] = EmptyTree
fromList (x:xs) = insert x $ fromList xs

node :: (Ord a) => a -> Tree a -> Bool
node x EmptyTree = False
node x (Node a l r)
    | x == a = True
    | x < a  = node x l
    | x > a  = node x r

toList :: Tree a -> [a]
toList EmptyTree = []
toList tree = con [] tree
    where
        con lt EmptyTree = lt
        con lt (Node a l r) = con (a : (con lt l)) r

instance Show a => Show (Tree a) where
    show tree = "fromList " ++ (show . toList) tree