Set.sml

set.sml

signature SetSig = 
sig
  val empty     : ''a list
  val is_in     : ''a -> ''a list -> bool
  val is_not_in : ''a -> ''a list -> bool
  val rm_elem   : ''a -> ''a list -> ''a list
  val isect     : ''a list -> ''a list -> ''a list
  val union     : ''a list -> ''a list -> ''a list
  val diff      : ''a list -> ''a list -> ''a list
end

structure Set :> SetSig = 
struct
  val empty = nil
  
  fun is_in _ nil     = false
    | is_in p (x::xs) = if p = x then true else (is_in p xs)

  fun is_not_in p xs = not (is_in p xs)

  fun rm_elem p nil = nil
    | rm_elem p (x::xs) = let
      val tmp_list = rm_elem p xs
    in
      if p = x then tmp_list else x::tmp_list
    end

  (* isect X Y = X and Y *)
  fun isect nil _ = nil
    | isect _ nil = nil
    | isect (x::xs) ys = let
      val tmp_list = isect xs ys
    in
      if (is_in x ys) then x::tmp_list else tmp_list
    end

  (* union X Y = X or Y *)
  fun union xs nil = xs
    | union nil ys = ys
    | union (x::xs) ys = let
      val tmp_list = union xs ys
    in
      if (is_in x ys) then tmp_list else x::tmp_list
    end

  (* diff X Y = Y - X (Y \ X) *)
  fun diff _ nil = nil
    | diff nil ys = ys
    | diff xs (y::ys) = let
      val diff_set = diff xs ys
    in
      if (is_not_in y xs) then y::diff_set else (rm_elem y diff_set)
    end

  (* sdiff X Y =  X \triangle Y *)
  fun sdiff xs ys = (union (diff xs ys) (diff ys xs))
end