I have two defined datatypes
datatype adj = V of int * int list;
datatype graph = G of adj list;
adj is the information of a vertex, int is the id and int list is the list adjacent vertex id
I am writing a function, get_edges that returns a list of all edges incident to a given vertex vi in the graph. The edges are in the form of (vi, vj), for all vj ∈ L, from the adjacency list V (vi, L). The order of edges is the same as the order of vj in L.
val get_edges = fn : int * graph -> (int * int) list
e.g.
get_edges(0, G [V(0, [1]), V(1, [0])]);
val it = [(0,1)] : (int * int) list
However, I have no ideas of how to access the element inside the graph so that I can return the edge, any ideas?
Pattern matching is used to get at the parts of datatype.
You can write a pair of access functions:
fun node (V(i,_)) = i;
fun neighbors (V(_,nodes)) = nodes;
Then, for example:
- val a_list = V(0,[2,3,4,7]);
val a_list = V (0,[2,3,4,7]) : adj
-
- node a_list;
val it = 0 : int
-
- neighbors a_list;
val it = [2,3,4,7] : int list
In practice, there is seldom any need to write such access functions. Instead, you just directly use pattern matching in any function designed to work with your type.
To illustrate how this works in this case, we can define a helper function (which will be useful in your main function):
fun expand (V(i,[])) = []
| expand (V(i, node::nodes)) = (i,node) :: expand (V(i,nodes));
expand has type fn : adj -> (int * int) list
For example:
- expand(V(0,[2,3,4,7]));
val it = [(0,2),(0,3),(0,4),(0,7)] : (int * int) list
Given such a function and the idea of pattern-matching, you should be able to implement get_edges