signature DICTIONARY =
sig
   type Key
   type 'a Dict
   exception Lookup
   val empty  :  'a Dict
   val lookup :  'a Dict -> Key -> 'a
   val remove : Key *  'a Dict ->  'a Dict
   val enter  : (Key * 'a) *  'a Dict -> 'a Dict
end

functor DICTIONARY( eqtype Key ):DICTIONARY =
struct
    type Key  = Key
    exception Lookup
    datatype 'a Dict = D of (Key * 'a) list
        val empty = D []
        
        fun lookup (D((k,e)::t)) key = if(k = key)then e
                                        else lookup (D t) key
          | lookup _ _ = raise Lookup

        fun rem _ [] = []
          | rem key ((entry as (k,_))::t) = if(k = key) then rem key t (* this should be redundant *)
                                       else entry :: rem key t

        fun ent ((k,e),  []) = [(k, e)]
          | ent ((k,e), ((k',e') :: entries)) = 
		if k = k' then raise Lookup
		else
			(k',e') :: ent ((k,e), entries) 
        fun enter (ke, D entries) = D (ent(ke, entries) ) 
        fun remove (key, D entries) = D(rem key entries)

        fun alist (D l) = l

	fun size (D []) = 0 | size (D (_ :: t)) = 1 + size (D t);
end;