Intro to Ocamlgraph

Ocamlgraph is a library for OCaml that gives the programmer several different types of graph data structure. Basically, you can mix and match the aspects of the graph that you want, finally resulting in an implementation you can use. Along with this, the library provides a number of common algorithms that work on any of the graphs you can create. How does all of this get done? Functors.

I will say, having started using the library before I knew what functors were, that making your library use functors is setting up a fairly steep barrier to entry. Not many people will want to spend time learning about how to use and write functors, just to use this library. And believe me if you want to do anything with a graph whose vertices and edges aren’t labeled with integers, you need to know functors.

One upside is that the library contains a graph implementation already constructed for you. Pack.Graph is an imperative undirected graph implementation, containing most of the useful algorithms implemented in the library. Algorithms for DFS, BFS, Dijkstra’s shortest path, Ford Fulkerson, Kruskal’s, and Topological sort. Also included are input and output functions; input builds a graph from a dot file and output can either create a dot file or run the graphviz program given the dot file.

Sounds wonderful except for the integer labeled vertices and edges. As soon as you want to label your vertices with strings and your edges with floats, you’re going to have to dive into functor land. Thankfully the existence of Pack.Graph makes figuring out how to make your own graph easier.

Say we’re creating a graph to model a map and we want to label each city (vertex) with its name (string) and each road (edge) with its distance (float). We’ll need to create a new graph structure since there is no ready-made version. Assuming the graph is undirected, and that we’ll be using an imperative graph (despite the name of the blog), let’s take a look at the Imperative.Graph module. You’ll see we’ve got 4 choices to make. Let’s choose ConcreteLabeled because our vertices aren’t abstract, and we do want the edges labeled. The signature of ConcreteLabeled:

module ConcreteLabeled: functor (V : Sig.COMPARABLE) ->
  functor (E : Sig.ORDERED_TYPE_DFT) -> Sig.I

So, we need to provide two structures, of the given types. Here they are:

module V = struct
  type t = string
  let compare = Pervasives.compare
  let hash = Hashtbl.hash
  let equal = (=)
end
module E = struct
  type t = float
  let compare = Pervasives.compare
  let default = 0.0
end

Now, because of the power of functors, creating the basic graph structure is one line of code:

module Graph = Imperative.Graph.ConcreteLabeled(V)(E)

Not only that, but the V and E structure will work for persistent and directed graphs that are concretelabeled, and you can switch by replacing Imperative with Persistent, and Graph with Digraph.

To get an implementation of Dijkstra’s algorithm for our newly created graph having looked at the signature of the functor (Path.Dijkstra). It requires the structure of the graph, and a weight structure that we use to tell the algorithm how to translate an edge’s label into a weight. Since we’ve labeled our edges with floats, the translation is trivial:

module W = struct
  type label = float
  type t = float
  let weight x = x
  let compare = Pervasives.compare
  let add = (+.)
  let zero = 0.0
end

And now, like our creation of the graph structure, creation of the algorithm’s structure is one line of code:

module Dijkstra = Path.Dijkstra(Graph)(W)

Finally, calling Dijkstra.shortest_path g v1 v2 will produce a list of edges signifying the path taken and a total weight.

The power of functors is that for an algorithm like Dijkstra’s that shouldn’t care about the structure of the graph or the labels on its edges, you can write the algorithm so that it doesn’t have to care about those things. The Path.Dijkstra functor works for both graphs and digraphs, and doesn’t have to care about edge labels because the programmer provides a way to translate between edge labels and weights.

Next time I’ll be talking about writing your own graph algorithm using functors, in the context of graph drawing.

More Functors

Aside from the features mentioned in my previous article, functors can also provide you with the ability to add more functions to the resulting structure of a functor you have no control over.

Take for instance the Set module in OCaml. Set.Make is a functor that creates the Set structure, given a structure of type Set.OrderedType. The OrderedType is simple. All you have to provide is a type and a compare function between two values of that type. (The reason is because the internal implementation of Set uses balanced binary trees and needs the compare function so the trees will work.) Here’s an example of a set containing integers:

module IntSet = Set.Make(struct type t = int
                            let compare = compare
                         end)

Notice the analog between functions and functors. Here I’ve created an anonymous structure containing the type and function I need, and passed it to Set.Make. In this way I don’t need to pollute the module namespace for something this small.

So, say you’ve got this project your working on where you need to compare two sets lexicographically. How do we write a lexicographic function that works for a set of any type? Taking a look at the definition, it looks like we need a way to compare the individual elements, and a way to get the minimum element of both sets. The problem here is that once a functor is “applied” to its arguments, its types become concrete in a static fashion. If we wrote a function to lexicographically compare two of our IntSets, we would get val lexico_compare : IntSet.t -> IntSet.t -> int which is not a function that can work on any set. The solution to this problem is, surprise!, to write another functor.

Here’s the functor needed:

module LexSet (Ord : Set.OrderedType) = struct
  include Set.Make(Ord)
  let rec lexico_compare s1 s2 =
    if is_empty s1 then (if is_empty s2 then 0 else -1)
    else if is_empty s2 then 1
    else
      let min1,min2 = (min_elt s1),(min_elt s2) in
      let diff = Ord.compare min1 min2 in
        if diff != 0 then diff
        else lexico_compare (remove min1 s1) (remove min2 s2)
end

This fixes all of our problems. We have access to the compare function we need because it’s passed as an argument to the functor. We also have access to all of the functions Set.Make exposes, because we’ve included it into the body of the functor. The resulting structure of this functor is the same as Set.Make except with an extra lexico_compare function.

This is the funny thing about functors though. Once you’ve started using them, they tend to force you to use more functors. When functors get involved they almost seem to force you to be as general as possible. For more of an idea of what I’m talking about, stay tuned for the next article where I talk about the weird, powerful, functorial Ocamlgraph library

Functors for the Beginner

Let’s talk about Functors in the OCaml programming language. I will assume that you know about modules in OCaml, if not you can refresh by reading the manual.

Functors are “functions” from structures to structures.

The above is probably the best definition I’ve seen of a functor. It touches on what I see as the main motivation behind using a functor. A Functor being a function from structure to structure means that if you keep the signature of the input structure and the signature of the output structure constant, you are free to change the implementation details without affecting any of the modules that use it. Functors allow the software designer an easy way of avoiding duplication, increasing orthogonality, all in a type safe package.

Let’s write an algorithm to determine if a string contains balanced parentheses. To start, we’ll define the type of stack we want to work with:

module type STACK = sig
  type 'a t
  exception Empty
  val create : unit -> 'a t
  val push : 'a -> 'a t -> unit
  val pop : 'a t -> 'a
  val is_empty : 'a t -> bool
end

Here we have the basic operations on a very minimalist stack. Now, we’ll create a functor that will take a stack structure of this type and return a module containing our parenthesis matching algorithm.

module Matcher (S : STACK) = struct
  let is_balanced str =
    let s = S.create () in try
      String.iter
        (fun c -> match c with
            '(' -> S.push c s
          | ')' -> ignore (S.pop s)
          | _ -> ()) str;
        S.is_empty s
    with S.Empty -> false
end

While we rely on the Stack with the STACK type to not change the semantics of its functions, we can guarantee that for any stack with this kind of structure and with the right semantics, our algorithm will work. Any use of this functor will create a module with one function: val is_balanced : string -> bool. This also means that if we maintain the signature of the functor we just wrote, we can change any of the implementation details and not affect the outside world.

To use a different stack, all we have to do is change one line of code from module M = Matcher(Stack) to module M = Matcher(CStack) to change our algorithm to use a stack that keeps a count of the number of things pushed onto it in its lifetime.

Conclusion: functors allow you to write code that will work irrespective of the implementation of the given structure (so long as it does what it should), and produces a structure containing functions that we are free to modify, but only have to change in one location, that of the functor.