05 / Data structures

Lists, tuples and records

MnL has three containers, and they differ in exactly the way you would want them to: a list holds any number of items of one type, a tuple holds a fixed number of items of possibly different types, and a record is a tuple whose parts have names.

All three resize the same way

Lists, tuples and records take a variable number of inputs, so you add and remove members with the gear popup or the plus / minus buttons described under add / remove input.

The list

A list is a container holding a collection of items of the same type. It may be empty, or hold one or more items.

Empty list

To build an empty list, remove every member from the gear popup ⚙.

An empty list bound to a variable named list_constructor. — **Fig. 2** Bound to a name.

SML

[]

val list_constructor = []

Scala

List ()

val list_constructor = List ()

Non-empty list

A list constructor holding three string items: 'my name ', 'is ' and 'MNL'. — **Fig. 3** Three inhabitants.

The same three-item list bound to a variable named list_constructor. — **Fig. 4** Bound to a name.

SML

["my name ", "is ", "MNL"]

val list_constructor = ["my name ", "is ", "MNL"]

Scala

List ("my name ", "is ", "MNL")

val list_constructor = List ("my name ", "is ", "MNL")

List operators

Four operators live in the :: List category.

Is empty

Returns true when the list is empty and false otherwise.

The is-empty operator applied to a non-empty list, giving false. — **Fig. 6** On a non-empty list.

SML

null ([])

Scala

List ().isEmpty

Head

Retrieves the first inhabitant.

SML

hd (["My name ", "is ", "MNL"])

Scala

List ("My name ", "is ", "MNL").head

Tail

Everything from the second inhabitant to the last.

SML

tl (["My name ", "is ", "MNL"])

Scala

List ("My name ", "is ", "MNL").tail

Append

Inserts a new inhabitant at the front of the list.

A variable my_name_is_mnl holding a list, and a variable hello appending 'Hello, ' to it. — **Fig. 10** Appending to a bound list.

SML

("Hello, " :: ["My name ", "is ", "MNL"])

val my_name_is_mnl = ["My name", "is", "MNL"]
val hello = ("Hello, " :: my_name_is_mnl)

Scala

("Hello, " :: List ("My name ", "is ", "MNL"))

val my_name_is_mnl = List ("My name", "is", "MNL")
val hello = ("Hello, " :: my_name_is_mnl)

Example: sum a list

The three list operators together give you the standard recursive shape — test for empty, take the head, recurse on the tail.

A recursive sum_list function returning 0 for an empty list and otherwise the head plus the sum of the tail. — **Fig. 11** Summing a list of numbers.

SML

fun sum_list (list_a) =
  if null (list_a) then 0
  else (hd (list_a) + sum_list (tl (list_a)))

val sum_list_application = sum_list ([17, 2, 200, 4])

Scala

def sum_list (list_a : List[Float]) : Float =
  if (list_a.isEmpty) then 0
  else ((list_a.head) + sum_list ((list_a.tail)))

val sum_list_application = sum_list (List (17, 2, 200, 4))

Examples › Basic › Sum list loads this program directly, and Examples › Lists has filter, fmap and fold built the same way.

The tuple

A tuple holds a collection of inhabitants whose types may be the same or different. Its size is fixed, and it cannot be empty.

A tuple constructor holding true, the string 'is' and the number 1. — **Fig. 12** Tuple constructor.

The same tuple bound to a variable named tuple_constructor. — **Fig. 13** Bound to a name.

SML

(true, "is", 1)

val tuple_constructor = (true, "is", 1)

Scala

(true, "is", 1)

val tuple_constructor = (true, "is", 1)

Projection

Get item — the π operator — retrieves one element by position.

SML

val tuple_constructor = (true, "is", 1)
val projection = (#1 tuple_constructor)

Scala

val tuple_constructor = (true, "is", 1)
val projection = (tuple_constructor(1))

Counting from where?

SML numbers tuple positions from 1 and Scala from 0, which is why the two snippets above disagree. Read the position off the block label rather than assuming, and check the result with block info.

The record

A record has a fixed number of fields, each pairing an identifier with an expression. Where a tuple names its parts implicitly by order, a record lets you name them.

A record constructor with fields bool, str and num holding false, 'is' and 0. — **Fig. 15** Record constructor.

The same record bound to a variable named record_constructor. — **Fig. 16** Bound to a name.

SML

{bool = false, str = "is", num = 0}

val record_constructor = {bool = false, str = "is", num = 0}

Scala

/* Scala has no primitive Record type */

Projection

Get field retrieves a field by name.

A projection retrieving the str field from a bound record variable. — **Fig. 18** Projection over a bound record.

SML

(#str {bool = false, str = "is", num = 0})

val record_constructor = {bool = false, str = "is", num = 0}
val projection = (#str record_constructor)

Scala

/* Scala has no primitive Record type */

Records and tuples are also how you pass more than one value into a function — see two or more parameters.

MnL is developed at L-Workshop. This help was written against MnL 5.2.0 (build 240826).