structure Set = 
struct
  type 'a set = 'a list
  val empty = []
  fun singleton a = [a]
  fun member (x,ys) = List.exists (fn y => x = y) ys
  fun insert (x,ys) = if member (x,ys) then ys else x::ys
end ;

Set.empty ;

val s1 = Set.insert (1,Set.singleton 2) ;

open Set ;

empty ;

signature AbsStack =
sig
  exception EmptyStack
  type 'item stack
  val empty : 'item stack
  val pop : 'item stack -> 'item stack
  val push : 'item * 'item stack -> 'item stack
  val top : 'item stack -> 'item
end ;

structure Stack : AbsStack =
struct
  exception EmptyStack
  datatype 'item stack = Empty
                       | Node of 'item * 'item stack
  val empty = Empty
  fun pop (Empty) = raise EmptyStack
    | pop (Node(x,S)) = S
  fun push (x,S) = Node(x,S)
  fun top (Empty) = raise EmptyStack
    | top (Node(x,S)) = x
end ;

val s = Stack.empty ;

Stack.push (32,s) ;

structure Stack1 :> AbsStack =
struct
  exception EmptyStack
  datatype 'item stack = Empty
                       | Node of 'item * 'item stack
  val empty = Empty
  fun pop (Empty) = raise EmptyStack
    | pop (Node(x,S)) = S
  fun push (x,S) = Node(x,S)
  fun top (Empty) = raise EmptyStack
    | top (Node(x,S)) = x
end ;

Stack1.push (32,Stack1.empty) ;

Stack1.top it ;

structure Stack2 : AbsStack =
struct
  exception EmptyStack
  type 'item stack = 'item list
  val empty = []
  fun pop [] = raise EmptyStack
    | pop (x::S) = S
  fun push (x,S) = x::S
  fun top [] = raise EmptyStack
    | top (x::S)  = x
end ;

Stack2.empty ;

Stack2.push (34,it) ;

Stack2.push (35,it) ;

Stack2.push (99,it) ;

Stack2.top it ;

structure Remove = 
struct
  fun smaller a [] = []
    | smaller a (x::xs) = 
      if x < a then (smaller a xs)
      else x::(smaller a xs)
end ;

signature Ordered =
sig
  type T
  val eq  : T * T -> bool
  val lt  : T * T -> bool
  val leq : T * T -> bool
end ;

structure Integer : Ordered =
struct
  type T = int
  fun eq  (x,y) = (x = y)
  fun lt  (x,y) = (x < y)
  fun leq (x,y) = (x <= y)
end ;

functor RemoveGen (s : Ordered) = 
struct
  fun smaller a [] = []
    | smaller a (x::xs) = 
      if (s.lt (x,a)) then (smaller a xs)
      else x::(smaller a xs)
end ;

structure IntRemove = RemoveGen (Integer) ;

IntRemove.smaller 12 [12,31,14] ;

IntRemove.smaller 15 [12,31,14] ;