CMSC 631
Fall 2002
Homework 1

adopted from Scott Smith with permission

This homework covers Caml modules and abstract data types.

A. e

There is a built-in module Set in OCaml; here is the reference page. An obvious way to make a set is as a structure which directly has in it functions such as add, delete, member, etc, but Caml's Set is a fancier version. It is a structure which contains three things: a functor Make, and two signatures, S and OrderedType.

• The functor Make is used to make the set structure, but it needs an ordering relation on the elements;
• for this it imports an OrderedType structure, which has nothing in it but an ordering relation compare.
• An ordering relation is defined as a function compare x y which returns 1 if the first item is bigger, -1 if the second is bigger, and 0 if they are the same. There is a built-in compare which works pretty well on ints and strings but may not do what you want on other types. Thats why Ocaml's Set module is so fancy: you can define your own ordering relation, put it in a structure which the Set.Make functor then imports.
• For this question, you need to do is use the built-in Set module to create an empty set, add "hi", "ho", and "he" to it, check for membership of "ho", and return the maximal element in the set.

B.

Write a Graph structure for an arbitrary directed graph with values of some type 'a at each node. You can implement your graph however you want, as long as it is a pure functional implementation. One method would be to implement a graph as a set (i.e., Caml Set) of vertices and a set of edges, where each edge is a pair of vertices. The vertexes can hold any type information, but vertex information must be unique: so, you cannot have two vertexes 10 in the same graph. Have your graph structure match the signature

module type GRAPH =
sig
  type 'a graph
      (* abstract type of graphs with nodes of type 'a *)
  exception Already_exists
  val empty_graph   : 'a graph
  val insert_node   : 'a -> 'a graph -> 'a graph
  val delete_node   : 'a -> 'a graph -> 'a graph
  val contains_node : 'a -> 'a graph -> bool
  val insert_edge   : 'a -> 'a -> 'a graph -> 'a graph
  val delete_edge   : 'a -> 'a -> 'a graph -> 'a graph
  val contains_edge : 'a -> 'a -> 'a graph -> bool
      (* has an edge from first to second node *)
  val exists_path  : 'a -> 'a -> 'a graph -> bool
      (* true iff there is a path from first node to second *)
end

If you are adding a node/edge to a graph which already exists, please raise an exception Already_exists; similarly, raise built-in Caml exception Not_found as appropriate.

Here is a test run.

open Graph;;
let g1 = insert_node 3.4 empty_graph;;
let g2 = insert_node 6.0 g1;;
let g3 = insert_node 8.5 g2;;
let g4 = insert_node 9.2 g3;;
let g5 = insert_node 2.1 g4;;
let g6 = insert_node 3.2 g5;;
let g7 = insert_edge 8.5 9.2 g6;;
let g8 = insert_edge 3.4 6.0 g7;;
let g9 = insert_edge 8.5 3.2 g8;;
let g10 = insert_edge 9.2 2.1 g9;;
let g11 = insert_edge 2.1 3.4 g10;;
let test1 = contains_node 2.2  g11    (* false *) ;;
let test2 = contains_edge 3.4 6.0 g11 (* true *) ;;
let test3 = exists_path 8.5 6.0 g11  (* true *);;
let g12 = delete_node 3.2 g11 (* don't forget to delete associated edges *);;
let test4 = contains_edge 8.5 3.2 g12 (* should raise exception, this node gone *);;

You will want to write some of your own private auxilliary functions in your Graph module. Make sure your module is self-standing, i.e. you don't need to define anything else in the top loop before defining the module.

Using Functors

If you use the systems Set to make your graph, you can't make a polymorphic graph type so the signature given won't work :-( However, you can get this effect by making a GraphFunctor functor to which you pass the type of graph you want. So, here would be the signature and how to use it:

module type TYPE = sig type t end

module type GRAPH =
functor (T:TYPE) ->
sig
  type graph
      (* abstract type of graphs with nodes of type T.t *)
  exception Already_exists
  val empty_graph   : graph
  val insert_node   : T.t -> graph -> graph
  val delete_node   : T.t -> graph -> graph
  val contains_node : T.t -> graph -> bool
  val insert_edge   : T.t -> T.t -> graph -> graph
  val delete_edge   : T.t -> T.t -> graph -> graph
  val contains_edge : T.t -> T.t -> graph -> bool
      (* has an edge from first to second node *)
  val exists_path  : T.t -> T.t -> graph -> bool
      (* true iff there is a path from first node to second *)
end

module GraphFunctor : GRAPH = functor ... end

module FloatGraph = GraphFunctor(struct type t = float end);;
open FloatGraph;;
(* tests as above *)