We will first need to set up to use OCaml version 4.02.3 or later. By default, the computers in the salles info are set up to use 3.10.2.
Window > Preferences
and type
in paths
in the search box. Select OcaIDE
> Paths
. In the OCaml Binaries
Directory
field type in:
/usr/local/ocaml-4.02.3/binthen click on
apply
next to browse
.camlp4
and delete
its contents.OCaml lib path
and
change it to: /usr/local/ocaml-4.02.3/lib
Ok
.Project >
Clean
.X
icon, and then open a new
one from Window > Show View > OCaml
Toplevel
. You should see it print OCaml
version 4.02.3
before the #
prompt.This TD is designed to introduce you to the OCaml module system. During this TD you will build a flexible graph library that achieves a high level of modularity and genericity by exploiting the module system, particularly the notion of a higher-order module, also known as a functor.
The core idea of a graph is a set of vertices and a set of edges linking pairs of vertices. However, there are many variations of this idea depending on different choices of attributes for representing graphs, some of which we list below in the table.
Edges: | Directed | Undirected |
Labeled | Unlabeled | |
Weighted | Unweighted | |
Vertices: | Labeled | Unlabeled |
Usage Mode: | Persistent | Imperative |
Density: | Sparse | Dense |
It is beneficial to represent each of these possibilities with a different data structure that exploits its specific features. Nevertheless, we would like to derive common algorithms such as traversal and finding spanning trees regardless of which graph is being used. In this TD we will explore a few of these variations with an eye towards writing modular code. Our aim is to be flexible and reuse as much code as possible without sacrificing efficiency.
Let us begin by exploring the isomorphism between polymorphic types and functors that you have already seen in Amphi 4. This warmup exercise will familiarize you with module types and functors, in particular how to instantiate abstract types. Consider the following type of a printer and a small collection of obvious printers.
type 'a printer = 'a -> string let p_int : int printer = string_of_int ;; let p_bool : bool printer = string_of_bool ;; let p_pair : 'a printer -> 'b printer -> ('a * 'b) printer = fun pa pb (x, y) -> String.concat "" ["(" ; pa x ; "," ; pb y ; ")"] ;;
We are going to recast this code in the form of a collection of modules and functors.
print.ml
and start by defining
the module type of printers.
module type Printer = sig type t val print : t -> string end
Note the specific use of themodule IntPrinter : Printer with type t = int = struct (* ... *) end module BoolPrinter : Printer with type t = bool = struct (* ... *) end
What is the type ofmodule PairPrinter (P1 : Printer) (P2 : Printer) : Printer with type t = P1.t * P2.t = struct (* ... *) end
module ListPrinter (P : Printer) : Printer with type t = P.t list = struct (* ... *) end
You are only allowed to modify thelet p_listpairintbool : (int * bool) list -> string = let module P = (* ... *) in P.print
The module type cs.ml
:
module type Ordered = sig type t (** compare x y : positive if x > y, 0 if x = y, negative if x < y *) val compare : t -> t -> int end module type Hashable = sig type t val hash : t -> int val equal : t -> t -> bool end (* combination of Ordered and Hashable *) module type Comparable = sig include Ordered include Hashable with type t := t end
Module types are always compared structurally: if two
module types have the same contents, then they are considered
the same even if their names differ. This has some useful
consequences: the
traverse.ml
containing:
open Cs module type Graph = sig (* the type of graphs *) type t module V : Cs.Hashable type vertex = V.t (* run a fold over the immediately reachable vertices from a given vertex *) val fold_succ : (vertex -> 'acc -> 'acc) -> t -> vertex -> 'acc -> 'acc end module type Traverse = functor (G : Graph) -> sig val traverse : G.t -> G.vertex -> G.vertex list end
traverse.ml
.
Itsmodule Dfs : Traverse = (* ... *)
traverse.ml
.
Its behavior is very similar tomodule Bfs : Traverse = (* ... *)
that performs a fold over the visited vertices instead of returning a list of them. Updateval fold : (G.vertex -> 'acc -> 'acc) -> G.t -> G.vertex -> 'acc -> 'acc
You may be wondering how you can test the functors you wrote
in traverse.ml
. Let us try it with a graph
containing numbered vertices.
traverse_test.ml
that starts as follows.
open Cs open Traverse module Graph = struct module V = struct type t = int (* ... *) end type vertex = V.t type t = (vertex * vertex list) list (* ... *) end module DfsTest = Dfs(Graph) module BfsTest = Bfs(Graph)
So far we have not needed to deal with edges directly. Suppose we have edges of different lengths and we want to find the shortest path between two vertices. What more information should we add into our graphs to support this? One way to do this is to have a means of converting edges to weights.
paths.ml
with the following initial contents.
open Cs module type Weight = sig type t val to_int : t -> int end module type Graph = sig type t module V : Cs.Hashable type vertex = V.t module E : sig type t val dest : t -> vertex end type edge = E.t (* run a fold over the edges that go out of a given vertex *) val fold_succ_e : (edge -> 'acc -> 'acc) -> t -> vertex -> 'acc -> 'acc end module type Paths = functor (G : Graph) (Wt : Weight with type t = G.E.t) -> sig (* find g v0 v1 : find a path between v0 and v1 in g *) (* raise Not_found if no path exists *) val find : G.t -> G.vertex -> G.vertex -> G.edge list end
Note that in order to get the length (“weight”) of an edge, it suffices to callmodule Shortest : Paths
paths_test.ml
that tries to
find the shortest paths between all pairs of vertices in the
following graph.
A spanning forest of a graph is a forest (i.e, a collection of trees) built from the edges of the graph that connects all the nodes. In order to compute the spanning forest of the graph, we will use Kruskal's algorithm, which proceeds as follows.
The file uf.ml
contains an
implementation of union-find for representing sets of things.
It has the following module type.
type set (** create a new set *) val create : unit -> set (** combine two sets *) val unite : set -> set -> unit (** find an identifier of a set. After a (unite s1 s2), it must be the case that (id s1) = (id s2). *) val id : set -> int
spanning_tree.ml
that contains:
Themodule type Graph = sig type t type vertex (* ... *) type edge (* ... *) (* ... *) end module type Tree = functor (G : Graph) -> sig val spanning : G.t -> G.edge list end
module Kruskal : Tree
spanning_tree_test.ml
on the following graph.
Then, modify your implementation oftype tree = { root : G.vertex ; kids : (G.edge * tree) list ; } val spanning_forest : G.t -> tree list
As you may have realized by now, we have been writing graph algorithms by assuming just what we need from our graph structures. If we can keep all these assumptions compatible across the various algorithms, then we can use the same graph module for each of them. In this section we will start to create such a canonical graph module.
Create graph.ml
to store the signature of
vertices, edges, and graphs:
open Cs module type Vertex = sig type t (* all vertices are comparable *) include Comparable with type t := t end module type Edge = sig type t (* all edges are ordered *) include Ordered with type t := t type vertex val source : t -> vertex val dest : t -> vertex type label val label : t -> label (** edge src lab dst : edge with source src, dest dst, label lab *) val edge : vertex -> label -> vertex -> t end module type Graph = sig type t module V : Vertex type vertex = V.t module E : Edge with type vertex = V.t type edge = E.t val is_empty : t -> bool val cardinality_v : t -> int (* how many vertices? *) val cardinality_e : t -> int (* how many edges? *) (* Both the following raise Invalid_argument if the vertex is not in the graph *) val in_degree : t -> vertex -> int val out_degree : t -> vertex -> int (** mem_v g v : is v in g? *) val mem_v : t -> vertex -> bool (** mem_e g e : is e in g? *) val mem_e : t -> edge -> bool (** is_adj g v1 v2 : is v2 reachable with one edge from v1? *) val is_adj : t -> vertex -> vertex -> bool (* folds *) (** fold_v f g acc = fold f over all vertices in g using acc *) val fold_v : (vertex -> 'acc -> 'acc) -> t -> 'acc -> 'acc (** fold_e f g acc = fold f over all edges in g using acc *) val fold_e : (edge -> 'acc -> 'acc) -> t -> 'acc -> 'acc (** fold_succ f g v acc = fold f over the successor vertices of v in g using acc *) val fold_succ : (vertex -> 'acc -> 'acc) -> t -> vertex -> 'acc -> 'acc (** fold_succ_e f g v acc = fold f over the out edges of v in g using acc *) val fold_succ_e : (edge -> 'acc -> 'acc) -> t -> vertex -> 'acc -> 'acc (** fold_pred f g v acc = fold f over the predecessor vertices of v in g using acc *) val fold_pred : (vertex -> 'acc -> 'acc) -> t -> vertex -> 'acc -> 'acc (** fold_pred_e f g v acc = fold f over the in edges of v in g using acc *) val fold_pred_e : (edge -> 'acc -> 'acc) -> t -> vertex -> 'acc -> 'acc (* iterators *) val iter_v : (vertex -> unit) -> t -> unit val iter_e : (edge -> unit) -> t -> unit val iter_succ : (vertex -> unit) -> t -> vertex -> unit val iter_succ_e : (edge -> unit) -> t -> vertex -> unit val iter_pred : (vertex -> unit) -> t -> vertex -> unit val iter_pred_e : (edge -> unit) -> t -> vertex -> unit end
graph_test.ml
and write a module that
implements the module type spanning_tree.ml
.
Now that you have a full builder.ml
with the following.
digraph.ml
file).
open Cs open Graph module type Digraph = struct include Graph val empty : t val add_vertex : t -> vertex -> t val add_edge : t -> edge -> t val remove_vertex : t -> vertex -> t val remove_edge : t -> edge -> t end
module Digraph (V : Vertex) (E : Edge with type vertex = V.t) : Digraph with module V = V with module E = E = struct (* ... *) end
module type Builders = functor (G : Digraph with type V.t = int with type E.label = int) -> sig val vertices : int -> G.t val full : int -> G.t val divisors : int -> G.t end module Builders : Builders = struct (* ... *) end
digraph_imp.ml
).
module type Digraph_imp = sig include Graph val empty : unit -> t val add_vertex : t -> vertex -> unit val add_edge : t -> edge -> unit val remove_vertex : t -> vertex -> unit val remove_edge : t -> edge -> unit (** copy g : create a copy of g such that modifications to g do not affect the copy. *) val copy : t -> t end
digraph_imp.ml
.
Imagine that we want to implement a collection of operations on graphs that is captured by the following module type.
module type Graph_ops = sig type graph (** union g1 g2 = graph with all vertices and edges in either g1 or g2 *) val union : graph -> graph -> graph (** intersection g1 g2 = graph with all vertices and edges in both g1 and g2 *) val intersection : graph -> graph -> graph (* mirror g = graph where all edges are turned around *) val mirror : graph -> graph (** complement g = graph with edges where g doesn't have an edge *) val complement : graph -> graph end