--
-- Abstract Data Types
--

{-- A Dictionary ADT
data Dictionary k v

newDictionary :: Dictionary k v
put           :: (Ord k) => Dictionary k v -> k -> v -> Dictionary k v
condGet       :: (Ord k) => Dictionary k v -> k -> v -> v
domain        :: Dictionary k v -> [k]

---}

module DictionaryADT (Dictionary,newDictionary,put,condGet,domain) where

type Dictionary k v = [(k,v)]

newDictionary :: Dictionary k v
put           :: (Ord k) => Dictionary k v -> k -> v -> Dictionary k v
condGet       :: (Ord k) => Dictionary k v -> k -> v -> v
domain        :: Dictionary k v -> [k]

newDictionary   = []

put []         key val             = [(key,val)]
put ((k,v):dr) key val | k == key  = (key,val):dr
                       | k > key   = (key,val):(k,v):dr
                       | k < key   = (k,v):put dr key val

condGet []         _   defValue             = defValue
condGet ((k,v):dr) key defValue | k == key  = v
                                | k > key   = defValue
                                | k < key   = condGet dr key defValue

domain d = map (\(k,_)->k) d