-- Implements a Map ADT using a List data structure
-- by Scot Drysdale

module ListMap ( Map,
              (!), lookup, insert, member, insertWith, delete, size, empty, 
              keys, toList, fromList
            ) where
            
import Prelude hiding (lookup)  -- We re-define lookup here

type  Map a b = [(a,b)]

-- Create an empty  Map
empty ::  Map a b
empty = []

-- Insert key k and value v into this  Map.  
-- Replace value with f(new_val,old_val) if key already present.
insertWith ::  Eq a => (b -> b -> b) -> a -> b ->  Map a b ->  Map a b
insertWith _ k v [] = [(k,v)]
insertWith f k v (p@(k1, v1) : rest) 
           | k == k1   = (k, f v v1) : rest  -- Replace value using f
           | otherwise = p : insertWith f k v rest

-- Insert key k and value v into this  Map.  
-- Replace value with new value if key already present.
insert         :: Eq a => a -> b ->  Map a b ->  Map a b
insert k v list = insertWith (\x y->x) k v list

-- Find the key and return the value, or Nothing if not present 
lookup :: Eq a => a ->  Map a b -> Maybe b
lookup k []                           = Nothing
lookup k ((k1, v) : rest) | k == k1   = Just v
                          | otherwise = lookup k rest
                         
(!) :: Eq a =>  Map a b -> a -> b
t ! k = case lookup k t of
          Nothing -> error "Key not found in map"
          (Just v) -> v
          
-- Determines if key is in the  Map
member    :: Eq a => a ->  Map a b -> Bool
member k t = case lookup k t of
               Nothing -> False
               (Just _) -> True

-- Delete key from  Map.                          
delete :: Eq a => a ->  Map a b ->  Map a b
delete k [] = []
delete k (p@(k1, v) : rest) 
         | k == k1   = rest
         | otherwise = p : delete k rest


-- Converts a list into a list of (key, value) pairs
toList ::  Map a b -> [(a,b)]
toList list = list
          
-- Converts a list of (key, value) pairs to a  Map
fromList  :: [(a,b)] ->  Map a b
fromList list = list

-- Returns a list of the keys in the  Map
keys  ::  Map a b -> [a]
keys = map fst . toList

-- Returns the number of keys in the map
size ::  Map a b -> Int
size = length