Sample OCaml Code

This is page is intended to demonstrate good coding style in OCaml. The code here is a simple implementation of finite sets using unbalanced, ordered, binary trees. The amount of commenting in the code below is more than might be suggested by the style guide, but is acceptable for a submission. As a general rule, you should put a healthy dose of comments in your assignments. The TAs will be more inclined to look at your code and give partial credit if they can tell what you were trying to do with your code. Documenting known deficiencies in your code is also good; the TAs will tend to be more forgiving of bugs that are documented than bugs that are left unmarked.

(*
 * An implementation of functional, finite sets.
 *
 * Author:  Brian Emre Aydemir
 * Email:   emre@cs.caltech.edu
 *
 * ------------------------------------------------------------------------
 *
 * NOTE: The implementation here uses unbalanced, ordered, binary trees.
 * More efficient structures could be used, such as Red-Black trees. The
 * emphasis here is on coding style, not data structures.
 *
 * BUG: The implementation here relies on the (<) operator.  A more
 * general implementation would use modules and functors to specify
 * the element type and its comparison operator.
 *)

(*
 * The type for finite sets.
 * For simplicity, we use an unbalanced binary tree.  The first
 * 'a set is the left branch, and the second is the right branch.
 *)
type 'a set =
   Leaf
 | Node of 'a * 'a set * 'a set

(*
 * Duplicate_element is raised when an attempt is made to insert
 * an element twice into a set.
 *)
exception Duplicate_element

(*
 * The empty set.
 *)
let empty : 'a set = Leaf

(*
 * Test to see if a set is empty.
 *)
let is_empty (fset : 'a set) : bool =
   match fset with
      Leaf ->     true
    | Node _ ->   false

(*
 * Insert an element into a set and return the new set.
 * Raises Duplicate_element if the element is already in the set.
 *)
let rec insert (elt : 'a) (fset : 'a set) : 'a set =
   match fset with
      Leaf ->
         Node (elt, Leaf, Leaf)
    | Node (value, left_branch, right_branch) ->
         if elt < value then
            Node (value, insert elt left_branch, right_branch)
         else if value < elt then
            Node (value, left_branch, insert elt right_branch)
         else
            raise Duplicate_element

(*
 * Insert a list of elements into a set.
 *)
let insert_list (lst : 'a list) (fset : 'a set) : 'a set =
   let f set elt = insert elt set in
      List.fold_left f fset lst

(*
 * Test to see if an element is a member of the given set.
 * BUG: Doesn't use the fact that the nodes are ordered.
 *)
let rec member (elt : 'a) (fset : 'a set) : bool =
   match fset with
      Leaf ->
         false
    | Node (value, left_branch, right_branch) ->
         (value = elt) || (member elt left_branch) || (member elt right_branch)

(*
 * Implement a simple toploop and run it.  The code below would
 * not normally be in the same file as the above code.
 *)
let loop () =
   let set = ref empty in
      try
         while true do
            output_string stdout "set> ";
            flush stdout;
            let line = input_line stdin in
            if member line !set then
               Printf.printf "%s is already in the set\n" line
            else
               begin
                  (* It's safe to add line since it isn't in the set. *)
                  set := insert line !set;
                  Printf.printf "%s added to the set\n" line
               end
         done
      with
         End_of_file -> ()

let _ = loop ()