RATIONAL NUMBERS SML

rational1_sig.sml

signature Rational =
  sig

    type rational
    exception rat_error
    val make_rat: int * int -> rational
    val rat: int -> rational
    val reci: int -> rational
    val  == : rational * rational -> bool
    val  << : rational * rational -> bool
    val  ++ : rational * rational -> rational
    val  ~~ : rational -> rational
    val inverse : rational -> rational
    val  **  : rational * rational -> rational
    val  // : rational * rational -> rational
    val  -- : rational * rational -> rational
    val show: rational -> unit

  end;

rational1_str.sml

structure rational1 : Rational =

  struct

    type rational = {num:int, denom:int};

    exception rat_error;

    local
      fun gcd (0, b):int = b
        | gcd (a, b) = gcd (b mod a, a);
    in
      fun norm (p:rational) =
            let val a = #num p and b = #denom p;
                val g = gcd (abs(a), abs(b))
            in
              if b = 0 then raise rat_error
              else  let val c = a*b
                    in if c = 0 then {num = 0, denom = 1}
                       else if c > 0
                            then {num = abs(a) div g, denom = abs(b) div g}
                            else {num = ~(abs(a) div g), denom = abs(b) div g}
                    end
            end
    end;

    fun make_rat (a:int, b:int) =
       if b = 0 then raise rat_error
       else (norm {num = a, denom = b});

    fun rat (a:int) = make_rat(a, 1);

    fun reci (a:int) = if a = 0 then raise rat_error
                        else make_rat(1, a)

    infix <<;
    fun p << q =
	  let val np = norm p and  nq = norm q;
		val      nnp = #num np and dnp = #denom np
		    and  nnq = #num nq and dnq = #denom nq;
		val left = nnp * dnq and right = dnp * nnq
         in left < right
	   end;

    infix ==;
    fun p == q = (norm p = norm q);

    infix ++;
    fun (p:rational) ++ (q:rational) =
          let val a = #num p
              and b = #denom p
              and c = #num q
              and d = #denom q;
              val r = {num = a*d + b*c, denom = b*d}
          in
            norm r
          end;

    fun ~~(p:rational) = {num = 0-(#num p), denom = #denom p};

    infix --;
    fun p -- q = p ++ (~~ q);

    infix **;
    fun  (p:rational) ** (q:rational) =
          let val a = #num p
              and b = #denom p
              and c = #num q
              and d = #denom q;
              val r = {num = a*c, denom = b*d}
          in
            norm r
          end;

    fun inverse (p:rational) = norm (make_rat(#denom p, #num p));

    infix //;
    fun (p:rational) // (q:rational) = p ** (inverse q);

    fun show (p:rational) =
                    let val q = norm p;
                        val a = #num q
                        and b = #denom q;
                        val c = makestring a;
                        val d = makestring b
                    in
                        if (a = 0) orelse (b = 1)
                        then print (c^"  \n")
                        else print (c^"/"^d^"   \n")
                    end;

  end; 

rational2_str.sml

structure rational2 : Rational =

  struct

    abstype rational = RAT of int * int
    with
	    exception rat_error;

	    fun numer (RAT(x, _)) = x;

	    fun denom (RAT(_, y)) = y;

	    local
	      fun gcd (0, b):int = b
	        | gcd (a, b) = gcd (b mod a, a);
	    in
	      fun norm (p:rational) =
	            let val a = numer (p) and b = denom (p);
	                val g = gcd (abs(a), abs(b))
	            in
	              if b = 0 then raise rat_error
	              else  let val c = a*b
	                    in if c = 0 then RAT(0,1)
	                       else if c > 0
	                            then RAT(abs(a) div g, abs(b) div g)
	                            else RAT(~(abs(a) div g), abs(b) div g)
	                    end
	            end
	    end;

	    fun make_rat (a:int, b:int) =
	       if b = 0 then raise rat_error
	       else norm (RAT(a,b));

	    fun rat (a:int) = make_rat(a, 1);

	    fun reci (a:int) = if a = 0 then raise rat_error
	                        else make_rat(1, a)
	    fun show (p:rational) =
	                    let val q = norm p;
	                        val a = numer (q) and b = denom (q);
	                        val c = makestring a;
	                        val d = makestring b
	                    in
	                        if (a = 0) orelse (b = 1)
	                        then print (c^"  \n")
	                        else print (c^"/"^d^"  \n")
	                    end;
    end; (* abstype *)

    infix ==;

(* With the abstype declaration we cannot directly check for equality. Hence

    fun p == q = (norm p = norm q);

   the above definition will not work
*)

    fun p == q =
	  let val pp = norm p and  qq = norm q;
		val npp = numer pp and  dpp = denom pp
		and nqq = numer qq and dqq = denom qq
	   in (npp = nqq) andalso (dpp = dqq)
	  end;

    infix <<;
    fun p << q =
	  let val pp = norm p and  qq = norm q;
		val npp = numer pp and  dpp = denom pp
		and nqq = numer qq and dqq = denom qq
	   in (npp * dqq) < (dpp * nqq)
	  end;


    infix ++;
    fun (p:rational) ++ (q:rational) =
          let val a = numer p
              and b = denom p
              and c = numer q
              and d = denom q;
              val r = make_rat (a*d + b*c,  b*d)
          in
            norm r
          end;

    fun ~~(p:rational) = make_rat(~(numer p), denom p);

    infix --;
    fun p -- q = p ++ (~~ q);

    infix **;
    fun  (p:rational) ** (q:rational) =
          let val a = numer p
              and b = denom p
              and c = numer q
              and d = denom q;
              val r = make_rat(a*c, b*d)
          in
            r
          end;

    fun inverse (p:rational) = norm (make_rat(denom p, numer p));

    infix //;
    fun (p:rational) // (q:rational) = p ** (inverse q);

  end;

rational3_str.sml

structure rational3: Rational =
  struct
    type rational = int;

    exception rat_error;

    fun gcd(a,b) =
        if (b = 0) then a
        else gcd(b,a mod b);


    fun power(x,n) =
    let fun piter(p,xseq,n) =
        let fun odd(n) = (n mod 2 = 1);
        in
          if n=0 then p
          else if odd(n) then piter(p*xseq,xseq*xseq,n div 2)
          else piter(p,xseq*xseq,n div 2)
        end
    in piter(1,x,n)
    end;


    fun make_rat(n:int,d:int): rational = (* Always in normal form *)
      if d = 0 then raise rat_error
      else if n = 0 then 3  (* 0 = 0/1 = (2^0)*(3^1) = 3 *)
      else let val sign = (n div abs(n))*(d div abs(d)) and g = gcd (n, d);
		   val nn = n div g and dd = d div g;
	     in  sign * power (2, nn) * power (3, dd)
	     end;

(*
    fun absNumer_Iter (p, n)  = (* Assume p is a positive integer *)
        if (p mod 2 = 0) then absNumer_Iter ((p div 2), n+1)
        else n;

    fun absDenom_Iter (p, d) =  (* Assume p is a positive integer *)
        if (p mod 3 = 0) then absDenom_Iter (p div 3, d+1)
        else d;
*)
    fun unmake_rat (p: rational) =
	  let fun split_it (p, two, three) = (* Assume p is non-negative *)
		       if p = 0 then raise rat_error
			 else if (p mod 2 = 0) then split_it (p div 2, two+1, three)
			 else if (p mod 3 = 0) then split_it (p div 3, two, three+1)
			 else (p, two, three);
            val (q, n, d) = split_it (abs(p), 0, 0);
	  in  if q <> 1 then raise rat_error
            else if p < 0 then (~n, d)
		     else if n = 0 then (0, 1)
		          else (n, d)
	  end;

    fun numer (p:rational) =
	  let val (n, _) = unmake_rat (p)
	  in n
	  end

    fun denom (p:rational) =
	  let val (_, d) = unmake_rat (p)
	  in d
	  end

    fun norm (p: rational) = make_rat (unmake_rat (p))


    fun show (p:rational) =
	  let val (n, d) = unmake_rat p;
		val sho_n = makestring n and sho_d = makestring d
	  in  if (n = 0) orelse (d = 1)
            then print (sho_n^"  \n")
            else print (sho_n^"/"^sho_d^"  \n")
	  end;

    fun rat a = make_rat (a, 1);

    fun reci a = make_rat (1, a);

    infix ==;
    fun p == q =
	  let val pnorm = make_rat (unmake_rat p)
		and qnorm = make_rat (unmake_rat q)
	  in  pnorm = qnorm
	  end;

    infix <<;
    fun p << q =
	  let val (np, dp) = unmake_rat p
		and (nq, dq) = unmake_rat q
	  in  np*dq < nq*dp
	  end;

    infix ++;
    fun p ++ q =
	  let val (np, dp) = unmake_rat p and (nq, dq) = unmake_rat q;
		val gp = gcd (abs(np), dq) and gq = gcd (abs(nq), dq);
		val gnp = np div gp and gdp = dp div gp
		and gnq = nq div gq and gdq = dq div gq
	  in  make_rat(gnp*gdq + gnq*gdp, gnq*gdq)
	  end;

    infix --;
    fun p -- q =
	  let val (np, dp) = unmake_rat p and (nq, dq) = unmake_rat q;
		val gp = gcd (abs(np), dq) and gq = gcd (abs(nq), dq);
		val gnp = np div gp and gdp = dp div gp
		and gnq = nq div gq and gdq = dq div gq
	  in  make_rat(gnp*gdq - gnq*gdp, gnq*gdq)
	  end;

    infix **;
    fun p ** q =
	  let val (np, dp) = unmake_rat p and (nq, dq) = unmake_rat q;
		val gp = gcd (abs(np), dq) and gq = gcd (abs(nq), dq);
		val gnp = np div gp and gdp = dp div gp
		and gnq = nq div gq and gdq = dq div gq
	  in  make_rat(gnp*gnq, gdp*gdq)
	  end;
    fun inverse p =
	  let val (np, dp) = unmake_rat p
	  in  make_rat (dp, np)
	  end;

    infix //;
    fun p // q = p ** (inverse q);

    fun ~~ p = ~p;

  end (* struct *)