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.

- The functor
**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 signaturemodule 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 *)

`settest.ml`

and `graph.ml`

.