(* Signature for dictionaries (aka environments, finite maps).  This
 * should be implemented in two structures:
 *
 *    AListDict : DICT
 *    FunDict   : DICT
 *
 * Each defines a representation, but the implementation is up to you.
 * Clients of DICT should behave the same regardless of which
 * representation they use.
 *)

signature DICT =
sig
  (* The type of a dictionary mapping string to 'a. *)
  type 'a dict

  (* The empty dictionary. *)
  val empty  : 'a dict

  (* Extend a dictionary with the given binding. *)
  val bind   : 'a dict * string * 'a -> 'a dict

  (* Lookup a value in a dictionary, returning NONE if not found. *)
  val lookup : 'a dict * string -> 'a option
end