(Ad, please don’t block.)

In this chapter, we look at the ReasonML data structure *lists*.

Lists are an immutable data structure for sequences of elements that all have the same type. It is especially well-suited for being processed via pattern matching.

In this chapter, you’ll see many type signatures such as this one:

`let map: ('a => 'b, list('a)) => list('b);`

Type signatures may still seem cryptic to you. But you’ll profit from learning how to read them. Let’s explore what the type signature tells us about `map`

– without us knowing what `map`

is or does (which will be explained later). Insights:

`let map: («parameters») => «result»;`

`map`

is a function.`'a => 'b`

`map`

’s first parameter is a function from type`'a`

to type`'b`

. The leading apostrophe indicates that`'a`

and`'b`

are*type variables*: They accept any types. But once a variable has accepted a particular type, it henceforth only accepts that type.`list('a)`

`map`

’s second parameter is a list whose elements are of type`'a`

.`list('b)`

`map`

’s result is a list whose elements are of type`'b`

.

The original standard library module for lists is `List`

. It has functions such as:

`let map: ('a => 'b, list('a)) => list('b);`

Module `List`

is also available in a labeled version, `ListLabels`

. It has functions such as:

`let map: (~f: 'a => 'b, list('a)) => list('b);`

You can use a trick and “replace” several normal modules with their labeled versions, by opening the module `StdLabels`

:

`open StdLabels;`

This module has the submodules `Array`

, `Bytes`

, `List`

and `String`

which are aliases for the global `ArrayLabels`

etc. Therefore, if you open it, you override the unlabeled implementations of `Array`

etc.

`list`

is a self-recursive parameterized variant. If you were to define it yourself, this is what it would look like:

```
type mylist('a) =
| Nil;
| Cons('a, mylist('a))
```

The names `Nil`

and `Cons`

(“construct”) are historical and originated with the Lisp programming language. You nest `Cons`

to create lists:

```
# let abc = Cons("a", Cons("b", Cons("c", Nil)));
let abc: mylist(string) = Cons("a", Cons("b", Cons("c", Nil)));
```

`mylist`

has the type parameter `'a`

. It is passed on to `Cons`

and its recursive use of `mylist`

. That means two things: First, the elements of `mylist`

can have any type. Second, they must all have the same type. In the previous interaction with ReasonML, you can see that it automatically inferred that for `abc`

, `'a`

is `string`

.

`abc`

is a singly-linked list. In memory, it may look like this:

The two parts of a cons pair are called:

*Head*(or*first*): It is the first value of the current list.*Tail*(or*rest*): It points to another list with the remaining elements.

ReasonML has special syntax for lists. The two constructors are:

- The empty list
`[]`

. - The cons pair
`[head, ...tail]`

.

Therefore, pattern matching works like this:

```
switch myList {
| [] => ···
| [head, ...tail] => ···
}
```

This is one way of recreating the list `abc`

from the previous section:

```
# let abc = ["a", ...["b", ...["c", ...[]]]];
let abc: list(string) = ["a", "b", "c"];
```

You can see that `rtop`

suggests the following, more compact, syntax, which is equivalent:

```
# let abc = ["a", "b", "c"];
let abc: list(string) = ["a", "b", "c"];
```

Let’s use pattern matching to compute the length of any list `myList`

:

```
let rec len = (myList: list('a)) =>
switch myList {
| [] => 0
| [_, ...tail] => 1 + len(tail)
};
```

We recurse over the two constructors:

- An empty list has length 0.
- A non-empty list has this length: 1 plus the length of the tail.

The type parameter `'a`

makes function `len`

generic. But we are never interested in the type of the elements, only in the structure of the list. The following interaction uses `len`

with various lists:

```
# len([]);
- : int = 0
# len(["a", "b"]);
- : int = 2
# len([1, 2, 3, 4]);
- : int = 4
```

ReasonML has no built-in support for printing complex data structures. But BuckleScript lets you use JavaScript’s `console.log()`

. It’s best to use this function like this:

`Js.log(Array.of_list(myList));`

Before we print the list `myList`

, we convert it to an array. But why? It leads to nicer output, because ReasonML lists are represented as nested 2-element arrays in JavaScript (an encoding of cons pairs).

The triple dot constructor is also called *spread operator*. This operator lets you prepend zero or more elements before an existing list:

```
# [...["a", "b"]];
- : list(string) = ["a", "b"]
# ["a", ...["b", "c"]];
- : list(string) = ["a", "b", "c"]
# ["a", "b", ...["c", "d"]];
- : list(string) = ["a", "b", "c", "d"]
```

Alas, this operator only works at the end. In JavaScript, you can use it anywhere, but in ReasonML, you can’t:

```
# [...["a", "b"], ...["c", "d"]];
Error: Syntax error
```

ReasonML has its own operator for concatenating lists:

```
# ["a", "b"] @ ["c", "d"];
- : list(string) = ["a", "b", "c", "d"]
```

Note that concatenating lists is comparatively slow, because you must prepend each element of the first operand to the second operand:

```
let rec append = (l1: list('a), l2: list('a)) =>
switch l1 {
| [] => l2
| [head, ...tail] => [head, ...append(tail, l2)]
};
```

This is how you use `append`

:

```
# append([1,2,3], [4,5]);
- : list(int) = [1, 2, 3, 4, 5]
```

This is, once again, type inference at work:

First, ReasonML inferred the types of

`1`

etc. to be`int`

.Then it inferred the type of, e.g., the first input list to be

`list(int)`

:`# [1,2,3]; - : list(int) = [1, 2, 3]`

Then it checked that

`l1`

and`l2`

had the same value for the type parameter`'a`

.Lastly, it used the type data of

`l1`

and`l2`

to infer the type`list(int)`

of the result of`append`

.

`range()`

creates a list of ints:

```
/**
* Compute a list of integers starting with `start`,
* up to and excluding `end_`.
*/
let rec range = (start: int, end_: int) =>
if (start >= end_) {
[];
} else {
[start, ...range(start + 1, end_)];
};
```

`end`

is a keyword in ReasonML and therefore not a legal variable name. That’s why the parameter `end_`

has the underscore in its name. Let’s try out `range()`

:

```
# range(0, 0);
- : list(int) = []
# range(0, 1);
- : list(int) = [0]
# range(0, 5);
- : list(int) = [0, 1, 2, 3, 4]
```

`fill()`

creates a list filled with the value `~element`

:

```
/**
* Create a list of length `~length` where each
* element is `~element`.
*/
let rec fill = (~element: 'a, ~length: int) =>
if (length <= 0) {
[];
} else {
[element, ...fill(~element, ~length=length-1)];
};
```

ReasonML uses the type of `~element`

to infer the type of the result:

```
# fill("x", 4);
- : list(string) = ["x", "x", "x", "x"]
# fill(0, 3);
- : list(int) = [0, 0, 0]
```

`summarize()`

computes the total of all the ints in a list:

```
/**
* Compute the sum of all the ints in the list `l`.
*/
let rec summarize = (l: list(int)) =>
switch l {
| [] => 0
| [head, ...tail] => head + summarize(tail)
};
summarize([]); /* 0 */
summarize([3]); /* 3 */
summarize([1, 2, 3]); /* 6 */
```

`getElementAt()`

retrieves a list element by index:

```
/**
* Get the list element at index `~index`.
* The head of a list has the index 0,
* the head of its tail the index 1, etc.
*/
let rec getElementAt = (~index: int, l: list('a)) =>
switch l {
| [] => None
| [head, ...tail] =>
if (index <= 0) {
Some(head);
} else {
getElementAt(~index=index-1, tail);
}
};
```

We can eliminate the `if-then-else`

expression if we use a `when`

clause and an additional case for `switch`

. The resulting flat structure is slightly easier to read:

```
let rec getElementAt = (~index: int, l: list('a)) =>
switch l {
| [] => None
| [head, ..._] when index <= 0 => Some(head)
| [head, ...tail] => getElementAt(~index=index-1, tail)
};
```

A few things are noteworthy in this code:

- Failure is handled via the variant type
`option`

:`None`

means we have failed.`Some(x)`

means we have succeeded, with the result`x`

.

- Index 0 refers to the current head (2nd case).
- If we reach the end of the list
`[]`

, we have failed. This first case of`switch`

is triggered if either`l`

is empty or if we reach its end before`~index`

is 0.

The standard library has `ListLabels.nth()`

that works like `getElementAt()`

, but it throws an exception for illegal indices, it does not use `option`

.

Given that lists are immutable – how do you change them? To find an answer, consider that, so far, we have seen two kinds of algorithms:

- Algorithms that read data from lists by recursing over their structures. For example:
`len()`

,`summarize()`

, etc. - Algorithms that created lists by recursively building new structures. For example:
`range()`

,`fill()`

, etc.

To change a list, we combine both approaches: We create a completely new list and include data from the existing list or derive data from it, as needed.

`removeAll()`

The following is a first example of a function that changes an existing list.

```
/**
* Remove all elements from the list `l` that are
* equal to `~value`.
*/
let rec removeAll = (~value: 'a, l: list('a)) =>
switch l {
| [] => []
| [head, ...tail] when head == value => removeAll(~value, tail)
| [head, ...tail] => [head, ...removeAll(~value, tail)]
};
```

The first case means that we are done. The third case makes an exact copy of the existing list. The second case removes elements that are equal to `~value`

.

This is `removeAll()`

in action:

```
# removeAll(~value=9, [1,9,2,9,3]);
- : list(int) = [1, 2, 3]
```

`replaceAll()`

`replaceAll()`

replaces values:

```
/**
* Inside the list `l`, remove all occurrences of the value `~value`
* with the value `~with_`.
*/
let rec replaceAll = (~value: 'a, ~with_: 'a, l: list('a)) =>
switch l {
| [] => []
| [head, ...tail] when head == value =>
[with_, ...replaceAll(~value, ~with_, tail)]
| [head, ...tail] =>
[head, ...replaceAll(~value, ~with_, tail)]
};
```

The first case means we are finished. The third case makes an exact copy. The second case makes a replacement.

We can make `replaceAll()`

more compact via an internal helper function `replaceOne()`

:

```
let rec replaceAll = (~value: 'a, ~with_: 'a, l: list('a)) => {
let replaceOne = (x) => if (x == value) with_ else x;
switch l {
| [] => []
| [head, ...tail] =>
[replaceOne(head), ...replaceAll(~value, ~with_, tail)]
};
};
```

This is `replaceAll()`

in action:

```
# replaceAll(~value=1, ~with_=11, [1, 2, 1, 3]);
- : list(int) = [11, 2, 11, 3]
```

`drop()`

`drop()`

removes list elements:

```
/**
* Remove the first `~count` elements of `theList`.
*/
let rec drop = (~count, theList: list('a)) =>
switch theList {
| [] => []
| l when count <= 0 => l
| [_, ...tail] => drop(~count=count-1, tail)
};
```

Let’s use `drop()`

:

```
# drop(~count=0, ["a", "b", "c", "d"]);
- : list(string) = ["a", "b", "c", "d"]
# drop(~count=2, ["a", "b", "c", "d"]);
- : list(string) = ["c", "d"]
# drop(~count=2, ["a", "b"]);
- : list(string) = []
# drop(~count=2, ["a"]);
- : list(string) = []
# drop(~count=2, []);
- : list('a) = []
```

For the last result of `drop()`

, ReasonML can’t infer the element type and leaves the type parameter `'a`

unbound.

ReasonML’s standard library is still in flux. Therefore, We are only looking at a few highlights here. You can read up on the rest (as it currently exists) via the documentation for `ListLabels`

.

`ListLabels.map()`

Signature:

`let map: (~f: 'a => 'b, list('a)) => list('b);`

`map()`

takes a list with elements of type `'a`

, applies the function `~f`

to each element and returns the results in another list.

```
# ListLabels.map(~f=x => int_of_string(x), ["7", "15", "6"]);
- : list(int) = [7, 15, 6]
```

This function is a classic tool for processing lists of data.

`mapi()`

is a version of `map()`

that passes both the current element and the element’s index to the callback `~f`

. We can use `mapi()`

to non-destructively update lists:

```
/**
* Create a copy of `theList` whose element at index `~index`
* is `~value`.
*/
let setElementAt = (~index: int, ~value: 'a, theList: list('a)) =>
ListLabels.mapi(
~f=(i,x) => if (i==index) value else x,
theList
);
```

The parameter `~f`

passes on all elements unchanged, except for the element at index `~index`

.

This is `setElementAt()`

in use:

```
# setElementAt(~index=1, ~value="|", ["a", "b", "c"]);
- : list(string) = ["a", "|", "c"]
```

`ListLabels.filter()`

This is the function’s signature:

`let filter: (~f: 'a => bool, list('a)) => list('a);`

`filter()`

applies the function `~f`

to each element of its positional parameter. If it returns `true`

, the element is included in the result. If it returns `false`

, it isn’t. It is used as follows.

```
# ListLabels.filter(~f=x=>x>5, [8, 4, 9, 7, 2]);
- : list(int) = [8, 9, 7]
```

`ListLabels.for_all()`

Signature:

`let for_all: (~f: 'a => bool, list('a)) => bool;`

`for_all()`

returns `true`

if `~f`

returns true for each element of the list. For example:

```
# ListLabels.for_all(~f=x=>x>3, [4,5,6]);
- : bool = true
# ListLabels.for_all(~f=x=>x>3, [3,4,5,6]);
- : bool = false
```

`for_all`

stops processing as soon as `~f`

returns `false`

. Then the result is guaranteed to be `false`

. `for_all`

is named after the mathematical operator ∀.

`ListLabels.exists()`

is related to `for_all()`

: It returns `true`

if its callbacks returns `true`

for at least one of the elements of its list. `exists`

is named after the mathematical operator ∃.

`ListLabels.flatten()`

Signature:

`let flatten: list(list('a)) => list('a);`

`flatten()`

converts a list of lists `l`

, to a list, by concatenating the elements of `l`

. That is, the following three expressions are equivalent:

```
flatten([l1, l2, l3])
ListLabels.append(l1, ListLabels.append(l2, l3))
l1 @ l2 @ l3
```

This is how `flatten()`

is used:

```
# ListLabels.flatten([[1,2], [], [3,4,5]]);
- : list(int) = [1, 2, 3, 4, 5]
```

If you are wondering about arbitrarily nested lists, recall that, in ReasonML, all elements must have the same type. Therefore, if one list element is itself a list then all elements must be lists:

```
# ListLabels.flatten([[1,[2]], [], [3]]);
Error: This expression has type list('a)
but an expression was expected of type int
# ListLabels.flatten([[[1],[2]], [], [[3]]]);
- : list(list(int)) = [[1], [2], [3]]
```

Let’s continue by looking at use cases for `flatten()`

.

`flatten()`

lets you filter and map at the same time. As an example, consider the trying to extract the first elements of several lists stored in a list. You could:

- First filter out empty lists (which don’t have first elements) via
`ListLabels.filter()`

. - Then map each non-empty list to its head via
`ListLabels.map()`

.

Or you could use `flatten`

and do both at the same time:

```
module L = ListLabels;
let listFromHead = (l: list('a)) =>
switch (l) {
| [] => []
| [head, ..._] => [head]
};
let heads = (l: list(list('a))) =>
L.flatten(L.map(~f=listFromHead, l));
```

First, we map each non-empty list to a list with its head and each empty list to an empty list. Then we flatten the result. This looks as follows:

```
# let l0 = [[1, 2], [], [3,4,5]];
let l0: list(list(int)) = [[1, 2], [], [3, 4, 5]];
# L.map(~f=listFromHead, l0);
- : list(list(int)) = [[1], [], [3]]
# let l1 = L.map(~f=listFromHead, l0);
let l1: list(list(int)) = [[1], [], [3]];
# L.flatten(l1);
- : list(int) = [1, 3]
```

These steps are equivalent to:

```
# heads([[1, 2], [], [3,4,5]]);
- : list(int) = [1, 3]
```

It is instructive to compare `listFromHead`

to a function `getHead`

that uses `option`

to express failure:

```
let getHead = (l: list('a)) =>
switch (l) {
| [] => None
| [head, ..._] => Some(head)
};
```

That is, `None`

expresses “`l`

does not have a head”:

```
# getHead(["a", "b"]);
- : option(string) = Some("a")
# getHead([1, 2, 3]);
- : option(int) = Some(1)
# getHead([]);
- : option('a) = None
```

With `listFromHead`

, we used the empty list instead of `None`

and a one-element list instead of `Some`

.

Let’s assume that we have created a list of people and their children:

```
type person = Person(string, list(string));
let persons = [
Person("Daisy", []),
Person("Della", ["Huey", "Dewey", "Louie"]),
Person("Marcus", ["Minnie"])
];
```

If we want to collect the children in a list, `ListLabels.map()`

almost gives us what we want, but not quite:

```
# ListLabels.map(~f=(Person(_, ch)) => ch, persons);
- : list(list(string)) = [[], ["Huey", "Dewey", "Louie"], ["Minnie"]]
```

Alas, this is a list of lists of strings, not a list of strings. We can fix this by applying `ListLabels.flatten()`

to this nested list:

```
let collectChildren = (persons: list(person)) =>
ListLabels.flatten(
ListLabels.map(
~f=(Person(_, children)) => children,
persons));
collectChildren(persons);
/* ["Huey", "Dewey", "Louie", "Minnie"] */
```

Now we get the desired result:

```
# collectChildren(persons);
- : list(string) = ["Huey", "Dewey", "Louie", "Minnie"]
```

Sometimes, you create lists where some elements are added or omitted depending on a condition (`cond`

in the following example):

```
let func = (cond: bool) => ListLabels.flatten([
if (cond) ["a"] else [],
[
"b",
"c"
]
]);
```

This is how `func()`

is used:

```
# func(true);
- : list(string) = ["a", "b", "c"]
# func(false);
- : list(string) = ["b", "c"]
```

`ListLabels.fold_left()`

Signature:

`let fold_left: (~f: ('a, 'b) => 'a, ~init: 'a, list('b)) => 'a;`

`fold_left()`

works as follows:

- Input: a list of type
`list('b)`

(last parameter) - Result: a value of type
`'a`

To compute the result, `fold_left()`

depends on its parameter, the function `~f`

. It calls `~f`

for each element `elem`

of its input list:

`let nextIntermediateResult = f(intermediateResult, elem);`

`intermediateResult`

is what has already been computed. The first intermediate result is `~init`

. The last `nextIntermediateResult`

is the result of `fold_left()`

.

Let’s look at a concrete example.

`fold_left()`

by example: `summarize()`

We have already encountered the function `summarize()`

which computes the total of a list of ints. Let’s implement that function via `fold_left()`

:

```
let rec summarize = (l: list(int)) =>
ListLabels.fold_left(~f=(r, elem) => r + elem, ~init=0, l);
```

To understand how `summarize()`

works, consider the following expression:

`summarize([1,2,3]) /* 6 */`

To compute the result `6`

, the following steps are taken:

```
/* Parameter */
let f = (r, elem) => r + elem;
let init = 0;
/* Steps */
let result0 = f(init, 1); /* 1 */
let result1 = f(result0, 2); /* 3 */
let result2 = f(result1, 3); /* 6 */
```

`result2`

is the result of `fold_left()`

.

`fold_left()`

Another way of looking at `fold_left()`

is that takes a binary operator `~f`

and turns it into an n-ary operator for lists. An example in mathematics for going from binary to n-ary is the binary operator `+`

also existing as an n-ary version (the operator Σ). `summarize()`

went from `+`

to Σ. It could also be written like this:

```
# ListLabels.fold_left(~f=(+), ~init=0, [1, 2, 3]);
- : int = 6
```

I find `fold_left`

easiest to understand if it works in this mode – with an `~f`

that is *commutative* (order of parameters doesn’t matter). But there is much you can do with it – read on for an example.

The function `contains()`

uses it to find a value in a list:

```
let contains = (~value: 'a, theList: list('a)) => {
let f = (found, elem) => found || elem == value;
fold_left(~f, ~init=false, theList);
};
```

`iteri()`

Signature:

`let iteri: (~f: (int, 'a) => unit, list('a)) => unit;`

`iteri()`

call `~f`

for every element of its list. The arguments are the index of the element and the element. It returns `unit`

, which means that anything useful that `iteri`

does, it does via side effects.

The following function uses `iteri()`

to fill an array. It does so as a side effect, by writing to an array `arr`

:

```
let arrayFromList = (~init: 'a, l: list('a)) => {
let arr = ArrayLabels.make(ListLabels.length(l), init);
ListLabels.iteri(~f=(i, x) => arr[i]=x, l);
arr;
};
```

`~init`

is a required parameter, because `make()`

needs it (why is explained later).

`arrayFromList()`

in action:

```
# arrayFromList(~init=0, [1,2,3]);
- : array(int) = [|1, 2, 3|]
```

Now is a good time to read the chapter on recursion in this book. It will give you a deeper understanding of recursion and tell you how you can make the code in this chapter more efficient (via *tail calls*).