Previously: A document found in Level 2 discusses two primitive values in the SML language: integers and strings. This Level 2 document also discusses the tuple, a language construct which can be used to aggregate (i.e., group) values. In Bricklayer programs, 2-dimensional (and 3-dimensional) coordinates are represented as tuples constructed from 2 (and 3) integer values. For example, the Bricklayer origin in a 2D space is denoted by the tuple (0,0).
This document introduces the list. Slides covering this material can be found here.
Like a tuple, a list is a language construct which can be used to aggregate values. Syntactically, a list looks similar to a tuple. The only difference is that in a list, the open/close symbols are square brackets (while in a tuple the open/close symbols are parentheses).
| Tuple | List |
| () | [] |
| (1) | [1] |
| (1,2) | [1,2] |
In general, a list is a sequence of comma-separated expressions enclosed in square brackets.
[expression1, expression2, … , expressionn]
Though they are syntactically similar, lists and tuples are very different semantically. A tuple can be used to group values of any type, whereas a list can only group values belonging to a single type. For example, in SML it is perfectly legal to write (1,”hello”). However, writing [1,”hello”] results in a compile-time type error since the first element of the list is of type int while the second element of the list is of type string. To highlight this distinction, we say that tuples are a heterogeneous aggregation mechanism while lists are a homogeneous aggregation mechanism.
For technical reasons, because of their homogeneous nature, lists can be manipulated in important ways that tuples cannot. For example, it is possible to concatenate two lists to form a larger list. Elements can also be removed from lists to produce smaller lists. The central idea here is that lists can get larger and smaller dynamically (i.e., during program execution). In contrast, the size of a tuple is static and remains fixed during program execution. This flexibility makes the list a workhorse of SML (as well as other functional programming languages). In order for lists to change their size and still remain well-typed, the number of elements in a list cannot be part of its type. For example, the lists [1,2,3] and [4,5] both have the type int list. In contrast, the tuple (1,2,3) is of type int*int*int while the tuple (4,5) is of type int*int.
This brings us to the special case of the empty list which is denoted []. What is its type? For example, does the list [] have type int list or string list or does it have some other type? The solution is to let [] be a type that is compatible with all lists. The technical term for such a type is a polymorphic type.
Examples of Lists
The table below gives various examples of lists. Note that the elements of a list can be other lists as well as tuples or any combination thereof so long as all elements are of the same type.
| A list of integer values. | [1,2,3,4] |
| A list of integer lists. | [ [1,2,3,4], [2,3,4], [3], [] ] |
| A list of string lists. | [ [“hello”], [], [“hello”,”world”] ] |
| A list of int x int tuples. | [ (0,0), (1,1), (2,2) ] |
| A list of Bricklayer LEGO bricks. | [ BLUE, RED, YELLOW ] |
| A list of tuples consisting of Bricklayer LEGO bricks and 2D coordinates. | [ (BLUE,(0,0)), (RED,(1,1)), (YELLOW,(2,2)) ] |
List operators
SML provides two primitive operators for manipulating lists. The first operator is the construction operator and is generally referred to as the cons operator. The second operator is the concatenation operator.
The Cons Operator ::
In SML, the symbol :: is used to denote the cons operator. The cons operator is a binary infix operator. The fact that it is a binary operator means it is applied to 2 values (in this context, values are also referred to as operands). Examples of well-known binary operators include the arithmetic operators + and -. The fact that the cons operator is an infix operator means that must be positioned between the operands to which it is applied. Examples of well-known infix operators include the arithmetic operators + and -.
Given an element x and a list of elements xs the expression x :: xs denotes a list expression. Let x = 1 and xs = [2,3,4]. The evaluation of the expression x::xs will produce the list value [1,2,3,4] as its result.
The Concatenation Operator @
In SML, the symbol @ is used to denote the concatenation operator. The concatenation operator is also a binary infix operator. The concatenation operator may only be applied to two lists of the same type. For example, an int list and a string list cannot be concatenated because they are different types of lists.
Let xs = [1,2,3] and let ys = [4,5,6]. The evaluation of the expression xs @ ys will produce the list value [1,2,3,4,5,6] as its result.
The List Functions hd and tl
SML provides two basic functions for decomposing a list. The first function is called head and is denoted hd. The second function is called tail and is denoted tl. Both functions are unary functions, meaning they are only applied to a single argument. When applied to a list, the function hd returns the first element of the list (e.g., hd [1,2,3] = 1). When applied to a list, the function tl returns a list constructed from all but the first element of the input list (e.g., tl [1,2,3] = [2,3]).
Examples of List Expressions
The table below gives various examples of list expressions and the results of their evaluation.
| List Expression | Evaluation Result | List Expression | Evaluation Result |
| 1 :: [] | [ 1 ] | [1] @ [] | [ 1 ] |
| 1 :: [2,3,4] | [ 1,2,3,4 ] | [] @ [1] | [ 1 ] |
| [1] :: [[2,3],[4]] | [ [1], [2,3], [4] ] | [1,2] @ [2,3] | [ 1,2,2,3 ] |
| hd [1,2,3] | 1 | tl [1,2,3] | [2,3] |
Order Of Evaluation
When evaluating arithmetic expressions multiplication and division are performed before addition and subtraction. For example, when evaluating the expression 5 + 6 * 7, the multiplication operation is performed first followed by the addition operation. The resulting evaluation sequence is the following: 5 + 6 * 7 → 5 + 42 → 47.
Parentheses can be used to alter the order of evaluation. For example, when evaluating the expression (5 + 6) * 7, the addition operation is performed first followed by the multiplication operation. The resulting evaluation sequence is the following: (5 + 6) * 7 → 11 * 7 → 77.
The rules governing the evaluation of list expressions are conceptually similar to those governing the evaluation of arithmetic expressions. Here we discuss the evaluation of a particular kind of list expression which we will call a pure list-expression. A pure list-expression is a well-formed (i.e., type correct) expression consisting only of (1) the list operators :: and @, (2) values, (3) variables, and (4) the functions hd and tl. Note that this definition implies that a pure list-expression contains no evaluation-altering parentheses.
The following algorithm can be used when evaluating pure list expressions. Let e0 denote the initial pure list-expression that we want to evaluate.
- Replace all variables in e0 with the values to which they are bound. Let e1 denote the resulting expression.
- Process e1 from left-to-right evaluating all calls to the functions hd and tl. Let e2 denote the resulting expression. The phrase function application is left associative is the formal way of saying that function applications are to be evaluated in a left-to-right fashion.
- Process e2 from right-to-left evaluating each operation :: and @ in the order encountered. The phrase the list operators :: and @ are right associative is the formal way of saying that these list operations are to be evaluated in a right-to-left fashion.
The table below gives some examples of pure list-expressions as well as their evaluation sequences.
| Pure List-Expression | Evaluation Sequence |
| tl [1,2,3] @ [3,4] | tl [1,2,3] @ [3,4] → [2,3] @ [3,4] → [2,3,3,4] |
| hd [1,2,3] :: [3,4] | hd [1,2,3] :: [3,4] → 1 :: [3,4] → [1,3,4] |
| [1,2,3] @ tl [3,4] | [1,2,3] @ tl [3,4] → [1,2,3] @ [4] → [1,2,3,4] |
| [1,2,3] @ 4 :: [5,6] | [1,2,3] @ 4 :: [5,6] → [1,2,3] @ [4,5,6] → [1,2,3,4,5,6] |
| [1,2,3] @ 4 :: [5,6] @ [7] | [1,2,3] @ 4 :: [5,6] @ [7] → [1,2,3] @ 4 :: [5,6,7] → [1,2,3] @ [4,5,6,7] → [1,2,3,4,5,6,7] |
Efficient Computations
The evaluation algorithm discussed in the previous section is a standard one and can be extended in a straightforward manner so that it is suitable for the evaluation of any kind of (well-formed) expression. Note that in this algorithm, each evaluation step consists of a single operation or function call. An important question is whether other algorithms exist which can also correctly evaluate expressions. In particular, does there exist an algorithm in which the evaluation of a list expression (or any expression for that matter) requires fewer evaluation steps than the standard algorithm given here? More specifically, is it possible to perform more than one operation or function call during an evaluation step?