(*
 * Interpreter for F - Environments
 *
 * 2000/02/02 Andreas Rossberg
 *)

import signature ENV from "ENV-sig"

structure Env :> ENV =
struct
    type        id  = string
    datatype 'a env = EMPTY | ELEM of id * 'a * 'a env * 'a env

    exception Unbound of id

    val empty = EMPTY

    fun insert (x, a, EMPTY) = ELEM (x, a, EMPTY, EMPTY)
      | insert (x, a, ELEM (x',a',e1,e2)) =
	case String.compare (x,x')
	  of EQUAL   => ELEM (x,a,e1,e2)
	   | LESS    => ELEM (x', a', insert (x,a,e1), e2)
	   | GREATER => ELEM (x', a', e1, insert (x,a,e2))

    fun lookup (x, EMPTY) = raise Unbound x
      | lookup (x, ELEM (x',a',e1,e2)) =
	case String.compare (x,x')
	  of EQUAL   => a'
	   | LESS    => lookup (x,e1)
	   | GREATER => lookup (x,e2)

    infix 6 ++

    fun e ++  EMPTY             = e
      | e ++ (ELEM (x,a,e1,e2)) = insert (x,a,e) ++ e1 ++ e2
end