(* Signatures and Structures *)

structure IntLT = struct
    type t = int
    val lt = (op <)
    val eq = (op =)
end

structure IntDiv = struct
    type t = int
    fun lt (m, n) = (n mod m = 0)
    fun eq (m, n) = (op =)
end

IntDiv.lt (1, 2) andalso IntDiv.eq (1, 2)

let
    open IntDiv
in
    lt (1, 2) andalso eq (1, 2)
end

let
    structure I = IntDiv
in
    I.lt (1, 2) andalso I.eq (1, 2)
end

structure PersQueue = struct
  type 'a queue = 'a list * 'a list
  val empty = (nil, nil)
  fun insert (x, (bs, fs)) = (x::bs, fs)
  exception Empty
  fun remove (nil, nil) = raise Empty
    | remove (bs, f::fs) = (f, (bs, fs))
    | remove (bs, nil) = remove (nil, rev bs)
end

val q = PersQueue.empty
val q' = PersQueue.insert (1, q)
val q'' = PersQueue.insert (2, q)
val (x'', _) = PersQueue.remove q''        (* 2 *)
val (x', _) = PersQueue.remove q'          (* 1 *)

let
  open PersQueue
in
  insert (1, empty)
end

let
  structure PQ = PersQueue
in
  PQ.insert (1, PQ.empty)
end

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


signature INT_ORDERED = sig
  type t = int
  val lt : t * t -> bool
  val eq : t * t -> bool
end

signature INT_ORDERED_VARIANT = sig
  type t = int
  val lt : int * int -> bool
  val eq : int * int -> bool
end

signature QUEUE = sig
  type 'a queue
  val empty : 'a queue
  val insert : 'a * 'a queue -> 'a queue
  exception Empty
  val remove : 'a queue -> 'a * 'a queue
end

signature LESS_THAN = sig
  type t = int
  val lt : t * t -> bool
end

signature MONOID = sig
  type t
  val unit : t
  val mult : t * t -> t
end

signature GROUP = sig
  type t
  val unit : t
  val mult : t * t -> t
  val inv : t -> t
end

signature INT_LESS_THAN = sig
  val lt : int * int -> bool
end

structure IntLT : ORDERED = struct
  type t = int
  val lt = (op <)
  val eq = (op =)
end

structure IntDiv : ORDERED = struct
  type t = int
  fun lt (m, n) = (n mod m = 0)
  val eq = (op =)
end

structure Queue :> QUEUE = struct
  type 'a queue = 'a list * 'a list
  val empty = (nil, nil)
  fun insert (x, (bs, fs)) = (x::bs, fs)
  exception Empty
  fun remove (nil, nil) = raise Empty
    | remove (bs, f::fs) = (f, (bs, fs))
    | remove (bs, nil) = remove (nil, rev bs)
end