map.hs

{-# LANGUAGE ExistentialQuantification #-}
module Main where

-- data Map key value = Empty | (Eq key, Ord key) => Node key value (Map key value) (Map key value)
data Map key value = Empty | Node key value (Map key value) (Map key value) deriving (Show)

contains :: (Ord a, Eq a) => Map a t -> a -> Bool
contains Empty _ = False
contains (Node k' _ l r) k
  | k' > k = contains l k
  | k' < k = contains r k
  | otherwise = True

insert :: Ord a => Map a value -> a -> value -> Map a value
insert Empty k v = Node k v Empty Empty
insert (Node origKey v' l r) k v
  | k > origKey = Node origKey v' l (insert r k v)
  | k < origKey = Node origKey v' (insert l k v) r
  | otherwise = Node k v l r

find :: Ord a => Map a value -> a -> Maybe value
find Empty _ = Nothing
find (Node k v l r) target
  | k > target = find l target
  | k < target = find r target
  | otherwise = Just v

toList :: Map t a -> [(t, a)]
toList Empty = []
toList (Node k v l r) = [(k, v)] ++ toList l ++ toList r

fromList :: Ord a => [(a, value)] -> Map a value
fromList [] = Empty
fromList xs = foldl (\m p -> (uncurry (insert m) p)) Empty xs

sample :: Map String Integer
sample = Node "1" 1
          Empty (Node "2" 432 Empty (Node "5" 200 Empty Empty))

main :: IO ()
main = print (find (fromList [("12", 12), ("300", 7), ("4", 98214)] :: Map String Integer) "4")