Functions as Values

A distinctive feature of functional programming languages, like SML, is that functions are treated as values and enjoy first-class citizenship status. What this means is that function values are treated just like any other values in the language. Specifically, function values do not have additional (arbitrary) restrictions or limitations placed on how they can be used.

Let v denote an arbitrary value. Below is an incomplete list of things that one can do with v in general.

• A list can be created containing v.
• The value v can occupy a position in a tuple.
• The value v can be passed as an argument to a function.
• The value v can be returned as the result of a function call.
• A variable (e.g., x) can be bound to the value v (e.g., val x = v).

In SML, function values can participate in all of the things mentioned above.

The higher-order function map

A first-order function is a function whose inputs and whose result are all non-function values (e.g., integers, integer lists, etc.). A higher-order function is a function that either accepts another function as an input and/or returns a function as its result.

SML provides a number of very useful higher-order functions for manipulating lists. One such function is called map. The function map accepts two arguments in curried form. The first argument is a function and the second argument is a list containing elements to which the function can be applied. Let f denote a function that can be applied to values of type t. Let [ e₁, e₂, … e_n ] denote a list whose elements are also of type t. In symbolic terms, the application of map to these two values can be shown as follows:

In other words, map produces as its output a list whose elements are the result of applying the function f to corresponding elements in the input list. That is, the first element of the output list is obtained by applying f to the first element of the input list, the second element ofs the output list is obtained by applying f to the second element in the input list, and so on.

Example 1

Technically speaking, Bricklayer is an SML library. A Bricklayer program is an SML program that can access portions of the Bricklayer library. This access is accomlished using open. For example, the declaration open Level_3 provides access to the contents of the the Level_3 portion of the Bricklayer library. From the perspective of an SML interpreter (or compiler), a Bricklayer program is just another SML program. What this means is that a “regular” SML program can be executed as a Bricklayer program provided it is saved in a file having a dot-bl extension.

The code below is an SML program demonstrating the behavior of the higher-order function map. To run this program in Bricklayer, simply copy it into a text editor such as notepad++ and save the contents of the editor to file having a dot-bl extension. Then double-click on the file in the usual manner.

(* A Bricklayer program *)  
fun f x = x + 1;
val xs = [1,2,3,4];

map f xs;
(* result = [2,3,4,5] *)

The screenshot below shows the result of executing the code above. Note that since a Bricklayer function, such as show2D, is not called, LDD is not launched. As a result, all we see is the execution pane – the place we normaly look when our Bricklayer programs won’t run.

Using PowerPoint, the result of the map function call in the execution pane has been highlighted in red.

Example 2

In the previous example, the map function was applied to an integer list and produced an integer list as its result. However, having the input list be the same type as the output list is not required. In this example, a function f is declared which produces a tuple as its output. For example, the call f 1 will produce (1,1) as its result.

(* A Bricklayer program *)  
fun f x = (x,x);
val xs = [1,2,3];

map f xs;
(* result = [(1,1),(2,2),(3,3)] *)

Using PowerPoint, the result of the map function call in the execution pane has been highlighted in red.

Example 3

The Bricklayer program in this example declares a list of 2D coordinates. Next, a function f is declared that takes a coordinate (x,z) as an input and uses the Bricklayer function put2D to place a 1-bit blue brick at the coordinate (x,z). The map function call is then used to place 1-bit bricks at every coordinate in the list xs.

open Level_3;
 
val xs = [ (1,1), (2,2), (3,3) ]; 

fun f (x,z) = put2D (1,1) BLUE (x,z);
    
build2D(32,32);
 
map f xs;

show2D "map result";

Example 4

The Bricklayer program in this example declares a list of tuples where the first element of each tuple is a LEGO brick and the second element the tuple is itself a tuple denoting a 2D coordinate. Next, a function f is declared that takes a tuple of the form (b,(x,z)) as input and creates an L-shaped LEGO artifact using the brick b whose lower-left corner is at location (x,z). The map function call is then used to create properly positioned L-shaped artifacts for every element in the list xs.

open Level_3;
val xs = [ (RED,(1,1)), (BLUE,(2,2)), (YELLOW,(3,3)) ]; 

fun f (b,(x,z)) = 
    (
        put2D (2,1) b (x,z);
        put2D (1,1) b (x,z+1)
    );
    
build2D(32,32);
 
map f xs;

show2D "map result";

Example 5

The Bricklayer program in this example uses the map function twice. First, the program declares an integer list numbers and a function f1 that takes and integer as input and transforms it into a 2D coordinate. The function call map f1 numbers is then invoked to create a list of 2D coordinates. Next, a val-declaration is used to bind the variablepoints to this coordinate list. Then a function, called f2, is declared that takes a 2D coordinate as its input and creates an L-shaped LEGO artifact. The second call to map involves applying f2 to every coordinate in the list points resulting in the creation of the LEGO artifact shown below.

open Level_3;
 
val numbers = [ 0,1,2,3,4,5,6,7 ];

fun f1 x = (4*x,0)

val points = map f1 numbers;

fun f2 (x,z) = 
    (
        put2D (2,8) GREEN (x,z);
        put2D (2,2) GREEN (x+2,z)
    );
  
build2D(32,32);
 
map f points;

show2D "map result";