A code-along is a story about coding in which you are encouraged to “code up” all the examples in the story. In a code-along you shouldnot cut-and-paste.
In this code-along, we will explore how to use the higher-function map to create edges and vertices in graphs. We will also explore how properties of curried functions can be used to help us create graphs in general ways.
Example 1
The Bricklayer program in this example creates a graph containing 7+1 = 8 vertices and 7 edges. In this graph, 1 central vertex c1 is connected to the 7 peripheral vertices, p0, …, p6. The vertices in the graph are manually defined (i.e., typed by the programmer). A more technical way of saying this is that the vertices are statically defined or hardcoded in the program. However, it is worth noting that the x-coordinate of the peripherial vertices consists of expressions that involve the variable delta. Similarly, the x and z coordinates of the central vertex are also defined in terms of expressions that involve delta. In the program, delta is statically defined to be the value 8.
One advantage of defining the vertices in our graph in terms of the variable delta is that all vertices can be repositioned in a systematic way by changing the value bound to delta. In other words, 8 vertices can be repositioned by making a single change to the program.
In the program shown here, a function is declared called multiConnect which takes 2 parameters in curried form. The first parameter v is a vertex, and the second parameter vs is a list of vertices. When called, the function multiConnect will draw a blue line from v to every vertex in vs. These lines are drawn using the higher-order function map together with a helper function called connect. The function connect takes two arguments in curried form. Both the first and second arguments are vertices. The body of connect then simply calls lineXZ to draw a blue line between these two vertices.
open Level_3;
val dimensions = 127;
val max = dimensions - 1;
fun graph () =
let
val delta = 8;
val peripheralVertices = [
(0*delta,0),
(1*delta,0),
(2*delta,0),
(3*delta,0),
(4*delta,0),
(5*delta,0),
(6*delta,0)
];
val centralVertex = (3*delta,3*delta);
fun multiconnect v vs =
let
fun connect v1 v2 = lineXZ v1 v2 BLUE;
in
map (connect v) vs
end;
in
multiconnect centralVertex peripheralVertices
end;
(* ======================================= *)
build2D(dimensions,dimensions);
graph ();
show2D "Graph";
Note that in this example, the function that is passed to map is (connect v). The parentheses are important here for if they were omitted, the expression involving the map function call would be grouped (as defined by the precidence rules of SML) as follows.
This grouping would be incorrect since v is not a list. Recall that the second argument passed to map must be a list.
Though we have not (until now) taken advantage of their true nature, curried functions, like connect, are higher-order functions. For example, a function call like connect v is perfectly legal. When evaluated, connect v returns a result that is a function! Let us call this function connect2. The function connect2 is equivalent to connect except for the fact that in connect2, the first argument ofconnect has been hardcoded.
The code below shows how the function multiconect could have been implemented using the function connect2.
fun multiconnect v vs =
let
fun connect2 v2 = lineXZ v v2 BLUE;
in
map connect2 vs
end;
In the implementation of multiconnect shown above, the need for the helper function connect2 is not as important as in the previous implementation. One could simplify the graph function as shown below. Notice that multiconnect is eliminated entirely and the map function, in the body of graph, is applied directly to connect2. The resulting code is shorted. However, the drawback of such an implementation is that it is not as flexible as the previous implementation.
fun graph () =
let
val delta = …
val peripheralVertices = …
val centralVertex = …
fun connect2 v2 = lineXZ centralVertex v2 BLUE;
in
map connect2 peripheralVertices
end;
Example 2
The Bricklayer program in this example creates a graph containing 17+2 = 19 vertices and 34 edges. In this graph, 2 central vertices c1 and c2 are connected via 34 edges to 17 peripheral vertices,p0, …, p16. Of these 34 edges, half are blue and half are red.
In this program, the peripheral vertices are created dynmically (i.e., during runtime) in the following manner. First, a list vs is statically defined consisting of consecutive integers in the range 0…16. Then a user-defined function, called makePeripheralVertex, is declared which translates integers into 2D coordinates. In makePeripheralVertex, the x value of the coordinate that is returned is an expression consisting of the variable half, which is defined in terms of the variable dimensions. Similarly, the z value of the coordinate returned is an expression involving delta. Lastly, the higher-order function map is applied to the arguments makePeripheralVertex and vs to create the list of peripheral vertices. The resulting list, which is bound to the variable peripheralVertices, consists of 17 evenly spaced vertices running the length of the virtual space along the z-axis positioned at the halfway point along the x-axis. The central vertices c1 and c2 are statically defined, but their position is dependent on the variables half and max.
In the graph shown, the lines between central and peripheral vertices are drawn using the function multiconnect, a curried function which is parameterized three arguments. The first argument is a brick, the second a vertex, and the third a vertex list. Except for the first parameter, multiconnect is identical to the version shown in the first example of this code-along. In the version in the second example, the (additional) brick parameter allows different calls to multiconnect to create lines consisting of different bricks. In particular, two calls to the higher-order function map are used to create the edges in the graph. These calls connect the central vertices c1 and c2 to the peripheral vertices using blue and red bricks respectively.
open Level_3;
val delta = 8;
val dimensions = 16*delta+1;
val max = dimensions - 1;
val half = dimensions div 2;
fun graph () =
let
val vs = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16];
fun makePeripheralVertex v = (half, v*delta);
val peripheralVertices = map makePeripheralVertex vs
val c1 = (0,half);
val c2 = (max,half);
fun multiconnect b v vs =
let
fun connect v1 v2 = lineXZ v1 v2 b;
in
map (connect v) vs
end;
in
multiconnect BLUE c1 points;
multiconnect RED c2 points
end;
(* ======================================= *)
build2D(dimensions,dimensions);
graph ();
show2D "Graph";
