(* Code of Figure 9.16, pages 396-397 from
   Kenneth C. Louden, Programming Languages
   Principles and Practice 2nd Edition
   Copyright (C) Brooks-Cole/ITP, 2003
   (Test code from page 397 added, too.)
*)

signature ORDER =
   sig
   type Elem
   val lt: Elem * Elem -> bool
   end;

signature ORDERED_LIST =
   sig
   type Elem
   type OList
   val create: OList
   val insert: OList * Elem -> OList
   val lookup: OList * Elem -> bool
   end;

functor OListFUN (structure Order: ORDER):
ORDERED_LIST =
   struct
   type Elem = Order.Elem;
   type OList = Order.Elem list;
   val create = [];
   fun insert ([], x) = [x]
     | insert (h::t, x) = if Order.lt(x,h) then x::h::t
                               else h:: insert (t, x);
   fun lookup ([], x) = false
     | lookup (h::t, x) =
         if Order.lt(x,h) then false 
         else if Order.lt(h,x) then lookup (t,x)
         else true;
   end;

structure IntOrder: ORDER =
   struct
   type Elem = int;
   val lt = (op <);
   end;

structure IntOList = 
   OListFUN(structure Order = IntOrder);

open IntOList;
val ol = insert(create,2);
val ol2 = insert(ol,3);
lookup (ol2,3);
lookup (ol,3);