(* Code for 15-212B Recitation 8: Modules
   March 14, 2001
   Joshua Dunfield (www.cs.cmu.edu/~joshuad)
   Carnegie Mellon University *)

signature SET = sig
  type set
  type elem
  val empty : set
  val incl : elem -> set -> set
  val excl : elem -> set -> set
  val has : set -> elem -> bool
  val toString : set -> string
end

signature EQ = sig
  type t
  val eq : t * t -> bool
end

signature PRINTABLE = sig
  type u
  val toString : u -> string
end

functor ListFn (structure Eq : EQ
                structure Pr : PRINTABLE
                sharing type Eq.t = Pr.u
) :> SET
where type elem = Eq.t
=
struct
  type elem = Eq.t
  type set = elem list

  val empty = []

  fun has s x = List.exists (fn y => Eq.eq(x,y)) s

  fun incl x s = if has s x then s else x::s

  fun excl x [] = []
    | excl x (y::s) = if Eq.eq(x,y) then s else y::(excl x s)

  fun toString s =     (* Probably a more elegant way to write this... *)
      let fun build ([], acc) = "{" ^ acc
	    | build ([elem], acc) = "{" ^ Pr.toString elem ^ acc
	    | build (elem::elems, acc) =
	          build (elems, ", " ^ Pr.toString elem ^ acc)
      in
          build (s, "}")
      end
end

structure IntEq : EQ = struct
  type t = int
  fun eq (a,b) = (a = b)
end

structure IntPr : PRINTABLE = struct
  type u = int
  val toString = Int.toString
end

structure IntList = ListFn(structure Eq = IntEq
                         structure Pr = IntPr)


val s = IntList.empty;
val incl = IntList.incl;
val excl = IntList.excl;
val s = incl 1 s;
val s = incl 2 s;
val s = incl 3 s;
IntList.toString s;
val s = excl 2 s;
IntList.toString s;