(**** LECTURE 8: Dictionaries and Functional Arrays ****) (* $Id: dict.ML,v 1.1 1997/10/14 13:34:47 lcp Exp lcp $ *) (** Association lists **) exception Missing; fun update (pairs, b, y) = (b,y)::pairs; fun lookup ([], a) = raise Missing | lookup ((x,y)::pairs, a) = if a=x then y else lookup(pairs, a); exception Missing of string; fun lookup (Br ((a,x),t1,t2), b) = if b < a then lookup(t1, b) else if a < b then lookup(t2, b) else x | lookup (Lf, b) = raise Missing b; fun update (Lf, b: string, y) = Br((b,y), Lf, Lf) | update (Br((a,x),t1,t2), b, y) = if b