adopted from Scott Smith with permission
This homework covers Caml modules and abstract data types.
Setin 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
Setis a fancier version. It is a structure which contains three things: a functor
Make, and two signatures,
Makeis used to make the set structure, but it needs an ordering relation on the elements;
OrderedTypestructure, which has nothing in it but an ordering relation
compare x ywhich 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
comparewhich works pretty well on ints and strings but may not do what you want on other types. Thats why Ocaml's
Setmodule is so fancy: you can define your own ordering relation, put it in a structure which the
Set.Makefunctor then imports.
Setmodule 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.
Graphstructure for an arbitrary directed graph with values of some type
'aat 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
10in 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 *) endIf you are adding a node/edge to a graph which already exists, please raise an exception
Already_exists; similarly, raise built-in Caml exception
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
Graphmodule. 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.
Setto 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
GraphFunctorfunctor 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 *)