A Caml Implementation of Rational Numbers

Better Modules Because of Types

In my estimation most people today like OO programming for reasons that don't require objects or classes. When you think "objects" you may really have in mind a means of structuring your programs so as to keep namespaces separate and provide an abstraction for the actual implementation. Ruby solves the namespace issue by providing modules, but Caml additionally provides an interface for making functions and type definitions private.

The following implementation of rational numbers also introduces the beautiful concept of concise type definition.

type rational = R of int * int

In Lisp it's easy enough to pass pairs of ints around and call them rational numbers, but in ML there's no way to cheat because the functions won't take a pair of integers, they'll take and/or return the type rational. It's easy enough to make them:

let make n d =
  R (n, d)

Except that's not quite right because a rational is:

So we have to throw out any call that tries to set the denominator to zero.

exception BadDenomonator of int

let make n d =
  match d with
    0 -> raise (BadDenomonator d)
  | _ -> R (n, d)

Pattern-Matching on Parameters

One style guide suggests that instead of using match ... with inside a function definition to simply pattern match on the arguments.

let print (R (n, d)) =
  Printf.printf "%i/%i\n" n d

This makes the definition of basic helper functions very concise.

let numer (R (n, d)) = n

let denom (R (n, d)) = d

What's Wrong with Prefix?

Infix operators are very popular, but I have no problem with prefix operators, and isn't that what we do anyway when we define a function that performs some calculation?

Okay, I'm distracting myself. The textbook method of adding fractions is

Code:

let add (R (n1, d1)) (R (n2, d2)) =
  R ((n1 * d2 + n2 * d1), (d1 * d2))

And for multiply:

let multiply (R (n1, d1)) (R (n2, d2)) =
  R ((n1 * d1), (n2 * d2))

And subtract:

let subtract (R (n1, d1)) (R (n2, d2)) =
  R (((0 - n1) * d2 + n2 * d1), (d1 * d2))

And divide:

let divide (R (n1, d1)) (R (n2, d2)) =
  R ((n1 * d2), (d1 * n2))

Now back to my rant:

((n1 * d1), (n2 * d2)) looks a lot like ((* n1 d1), (* n2 d2)). Infix doesn't save many parentheses because besides they're frequently required to clear up precedent and they must be used to differentiate function application from arguments. The only problem here is that (* anywhere is the start of a comment. Hmmm.

# let r1 = make 5 7;;
val r1 : rational = R (5, 7)
# let r2 = make 2 3;;
val r2 : rational = R (2, 3)
# print (plus r1 r2);;
29/21
- : unit = ()

Conversion and Reduction

ML/Caml really does typing right. There is no coercion, only conversion. So I have to use a function to calculate the equivalent to anything, and my rational number module is no exception.

let float_of (R (n, d)) =
  (float_of_int n) /. (float_of_int d)

The last function I could really use is a means of applying the greatest common denominator before presenting fractions that I've done addition or multiplication on. I chose to implement this by sequentially dividing both terms by a series of prime numbers and checking for a remainder. If there is no remainder on the pair (0, 0) then divide by that number and start over.

let reduce (R (n, d)) =
  let finite_primes = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29] in
  let divisible x y z =
    match (x mod z), (y mod z) with
      0, 0 -> true
    | _    -> false in
  let rec reduce n d primes =
      match primes with
          []    -> make n d
        | h::t -> if (divisible n d h) then
            reduce (n / h) (d / h) finite_primes else reduce n d t in
  reduce n d finite_primes

I did several things which you may or may not consider naughty. First, I'm reusing the definition of reduce and the parameters n and d. I don't have a clear opinion on this yet, all I can say is that it doesn't confuse me. Unlike almost every other language known to man Caml function names are not in scope for the function body by default, and that's what rec does for us. Otherwise the recursive call to reduce would refer to outer function that takes only a rational. Because of the strong type-checker, this isn't a problem--my program would never compile if the wrong function was in scope.

Module Implementation

So where's the module? It's the name of the file: rational.ml. If I want to restrict access to some functions it's easy enough to define a corresponding .mli with only the interfaces that I want to make public. Start by loading the .ml file into the top level interpreter:

# #cd "/home/eradman/src/rational"
# #use "rational.ml";;
type rational = R of int * int
exception BadDenomonator of int
val make : int -> int -> rational = <fun>
val print : rational -> unit = <fun>
val numer : rational -> int = <fun>
val denom : rational -> int = <fun>
val plus : rational -> rational -> rational = <fun>
val times : rational -> rational -> rational = <fun>
val float_of : rational -> float = <fun>
val reduce : rational -> rational = <fun>

Cool, strip out = R of int * int and the references to = <fun> and it's ready for comments. It's considered good style to annotate the include file distributed with .cmo or .cmx code according to ocamldoc, and I agree. Compile and then use #load to test.

$ ocamlc -c rational.mli
$ ocamlc -c rational.ml

# #cd "/home/eradman/src/rational";;
# #load "rational.cmo";;
# let x = Rational.make 4 5;;
val x : Rational.rational = <abstr>