2. How to use modules with ocaml

ocaml modules allow to package together data structures definitions and functions operating on them. This allow to reduce code size and name confusion, as any identifier can appear in different modules, with different meanings, without any interference. This packaging is called structure, and is defined with the struct..end construction, that surrounds a sequence of definitions.

As an example, a module describing a priority queue can be like the following:

# module PrioQueue =
    struct
      type priority = int
      type 'a queue = Empty | Node of priority * 'a * 'a queue * 'a queue
      let empty = Empty
      let rec insert queue prio elt =
        match queue with
          Empty -> Node(prio, elt, Empty, Empty)
        | Node(p, e, left, right) ->
            if prio <= p
            then Node(prio, elt, insert right p e, left)
            else Node(p, e, insert right prio elt, left)
      exception Queue_is_empty
      let rec remove_top = function
          Empty -> raise Queue_is_empty
        | Node(prio, elt, left, Empty) -> left
        | Node(prio, elt, Empty, right) -> right
        | Node(prio, elt, (Node(lprio, lelt, _, _) as left),
                          (Node(rprio, relt, _, _) as right)) ->
            if lprio <= rprio
            then Node(lprio, lelt, remove_top left, right)
            else Node(rprio, relt, left, remove_top right)
      let extract = function
          Empty -> raise Queue_is_empty
        | Node(prio, elt, _, _) as queue -> (prio, elt, remove_top queue)
    end;;

To access a definition in the module, the usual dot-notation is used. As an example:

# PrioQueue.insert PrioQueue.empty 1 "hello";;
- : string PrioQueue.queue =
PrioQueue.Node (1, "hello", PrioQueue.Empty, PrioQueue.Empty)

In ocaml, the idea of module signature can be found. The signature is built out of some definitions of the ones present in the module definition, those that will be seen outside the module itself, i.e. that will be exported.

As an example, PrioQueue (see above) could have a signature exporting empty, insert and extract, but not remove_top.

# module type PRIOQUEUE =
    sig
      type priority = int         (* still concrete *)
      type 'a queue               (* now abstract *)
      val empty : 'a queue
      val insert : 'a queue -> int -> 'a -> 'a queue
      val extract : 'a queue -> int * 'a * 'a queue
      exception Queue_is_empty
    end;;

Functors are functions from structures to structures. They are useful to have some parameters in the definition of a structure: a structure A with a parameter B behaves as a functor F with a formal parameter B, that returns the actual structure A.

As an example, a structure implementing an ordered set, having as a parameter a structure that exports the data type of set elements and a comparing function, could be:

# type comparison = Less | Equal | Greater;;

# module type ORDERED_TYPE =
    sig
      type t
      val cmp: t -> t -> comparison
    end;;

# module Set =
    functor (Elt: ORDERED_TYPE) ->
      struct
        type element = Elt.t
        type set = element list
        let empty = []
        let rec add x s =
          match s with
            [] -> [x]
          | hd::tl ->
             match Elt.cmp x hd with
               Equal   -> s         (* x is already in s *)
             | Less    -> x :: s    (* x is smaller than all elements of s *)
             | Greater -> hd :: add x tl
        let rec member x s =
          match s with
            [] -> false
          | hd::tl ->
              match Elt.cmp x hd with
                Equal   -> true     (* x belongs to s *)
              | Less    -> false    (* x is smaller than all elements of s *)
              | Greater -> member x tl
      end;;

To create the actual structure, ocaml uses a syntax like the following:

# module OrderedString = (* ordered set of strings *)
    struct
      type t = string
      let cmp x y = if x = y then Equal else if x < y then Less else Greater
    end;;

# module StringSet = Set(OrderedString);; (* creazione del modulo *)