Structures

SML provides an encapsulation mechanism known as a structure for bundling declarations. Conceptually, a struture can be thought of as a book containing the definitions of functions (and other elements such as datatypes). Structures can be used by programmers to simplify their programming tasks. For example, the definitions of Bricklayer functions (and pieces) associated with coding Level_3 reside in a structure called Level_3. Similar structures exist for all coding levels in Bricklayer.

The open directive can be used to make the entire contents of a structure (i.e., all declarations it contains) available within a program. For example, Bricklayer uses this mechanism to provide access to (i.e., to “open”) the functions (and pieces) corresponding to a given coding level. This is why Bricklayer Level_1 programs begin with the declaration open Level_1;, Bricklayer Level_2 programs begin with the declaration open Level_2;, and so on.

The elements of a structure can also be accessed individually using qualified identifiers. From a syntactic perspective, a qualified identifier consists of a sequence of (simple) identifiers separated by one or more “dots”. For example, the function build2D is part of Level_1. This function can be accessed directly (without using open) by the qualified identifier Level_1.build2D. Below is an example of a small Bricklayer program that accesses all it’s Bricklayer functions using qualified identifiers. Note that the program runs without using theopen directive.

Level_1.build2D(2,2);

Level_1.put2D_2x2_BLUE(0,0);

Level_1.show2D "thing";   

The List Structure

SML provides a number of functions relating to lists. The definitions of these functions reside in a structure (aka, a library) called List. Functions, such as map, which are declared in the List structure, are so frequently used in SML programs that SML makes them automatically available to all programs. This is done for the sake of convenience and is a bit of an anomaly. In contrast, less frequently used functions, such as tabulate are treated in a standard fashion and are not automatically available. They must be accessed either through the open directive, or through the qualified identifier List.tabulate.

SML’s tabulate Function

The function tabulate is a higher-order function that takes an intger and a function-on-integers as input. When given the proper input, tabulate will generate a list of integers (starting with 0) and then (like map) apply the function-on-integers to the elements in this list.

The semantics of the function tabulate can be understood as an extension of the semantics of map. Specifically, the relationship between tabulate and map is as follows.

Notice, that in the above expression involving map, the list [ 0, … , (n-1) ] must be created in some fashion. Previously, we have looked at Bricklayer programs where such lists are created manually (i.e., hardcoded in the program). The tabulate function eliminates the need for such hardcoding.

Examples

The program below contains a number of examples showing how tabulate can be used to construct lists. It is helpful to keep in mind that how tabulate is used is not that from how map is used –tabulate simply combines simple list generation with map.

fun identity v = v;
fun makeAscendingList n = List.tabulate (n, identity);
makeAscendingList 8;
(* [0,1,2,3,4,5,6,7] *)

fun descend max v = max - v;
fun makeDescendingList n = 
        List.tabulate (n, descend (n-1));
makeDescendingList 8;
(* [7,6,5,4,3,2,1,0] *)

fun even v = 2*v;
fun makeEvens n = List.tabulate (n, even);
makeEvens 8;
(* [0,2,4,6,8,10,12,14] *)

fun odd v = 2*v + 1;
fun makeOdds  n = List.tabulate (n, odd);
makeOdds 8;
(* [1,3,5,7,9,11,13,15] *)

fun diagonalUp v = (v,v);
fun makeDiagonalUp n = List.tabulate(n, diagonalUp);
makeDiagonalUp 4;
(* [ (0,0), (1,1), (2,2), (3,3) ] *)

fun diagonalDown max v = (max - v, v);
fun makeDiagonalDown n = List.tabulate(n, diagonalDown (n - 1));
makeDiagonalDown 4;
(* [ (3,0), (2,1), (1,2), (0,3) ] *)

fun nestedTabulate n = List.tabulate( n, makeAscendingList );
nestedTabulate 4;
(* [ [], [0], [0,1], [0,1,2] ] *)

In this special project, we are interested in using tabulate to automatically generate large lists of vertices and/or edges.