(* Recall in our previous attempts to write a program to merge two sorted
   lists, we always had to specify the type of the list -- because inequality
   is not polymorphic.
   The solution to this problem, in ML, is to write a generic merge function
   packaged in a FUNCTOR that has, as an argument, an inequality structure.
   Then we can create at will a merge function that works on specific types of
   lists by calling the functor with an inequality structure specific to that
   type.
*)

fun partition _ [] = ([],[])
 |  partition  P (head::tail) = let val (Ppass,Pfail) = partition P tail
                            in  if (P head)
                                then (head::Ppass,Pfail)
                                else (Ppass,head::Pfail)
                            end
;

signature Inequality =    (* defines what an inequality-structure looks like *)
sig
   type Type
   val function: Type*Type -> bool
end;

functor make_merge (inequality: Inequality) =
struct
   type t = inequality.Type
   fun merge []  x = x |  merge x  [] = x          (* generic merge function *)
    |  merge (l1 as (h1::t1)) (l2 as (h2::t2)) =
         if inequality.function (h1,h2)
         then h1::(merge t1 l2)
         else if inequality.function (h2,h1)
              then h2::(merge l1 t2)
              else (* h1 = h2 *)  h1::(merge t1 t2)
end;

structure INT =      (* the inequality structure for integers *)
struct
  type Type = int
  val function = fn (a,b:Type) => a < b
end;

structure REAL =      (* the inequality structure for reals *)
struct
  type Type = real
  val function = fn (a,b:Type) => a < b
end;

structure MI = make_merge(INT);  (* unfortunately, there is no way to put *)
val mi = MI.merge;               (* these two statements together into one.  *)
structure MR = make_merge(REAL);
val mr = MR.merge;