Lists

The bread and butter of functional programming is list processing. A list is either the empty list, written as Nil, or a cons cell, written as x :: xs where x is the head element and xs is the tail of the list. The List type is polymorphic so you can have a list of integers, written as List[Int32], or a list of strings written as List[String]. The List type and list operations are part of the Flix standard library.

We write the empty list as follows:

Nil

We can construct a list of strings with the strings "Hello" and "World" as follows:

"Hello" :: "World" :: Nil

Given a list there are many useful operations we can perform on it.

For example, we can compute the length of a list as follows:

List.length(1 :: 2 :: 3 :: Nil)

We can also reverse the order of elements in a list:

List.reverse(1 :: 2 :: 3 :: Nil)

We can append two lists using the List.append function as follows:

let xs = (1 :: 2 :: 3 :: Nil);
let ys = (4 :: 5 :: 6 :: Nil);
List.append(xs, ys)

Or, alternatively, we can use the built-in append operator ::: as follows:

let xs = (1 :: 2 :: 3 :: Nil);
let ys = (4 :: 5 :: 6 :: Nil);
xs ::: ys

Flix has an extensive collection of functions to operate on lists.

Here are some of the most common:

List.count(x -> x == 1, 1 :: 2 :: 3 :: Nil);
List.filter(x -> x == 1, 1 :: 2 :: 3 :: Nil);
List.map(x -> x + 1, 1 :: 2 :: 3 :: Nil);
List.foldLeft((x, y) -> x + y, 0, 1 :: 2 :: 3 :: Nil)

And here are some more exotic functions:

List.intersperse("X", "a" :: "b" :: "c" :: Nil)

which inserts "X" between every element in the list.

let l1 = "X" :: "Y" :: Nil;
let l2 = ("a" :: "b" :: Nil) :: ("c" :: "d" :: Nil) :: Nil;
List.intercalate(l1, l2)

which inserts the list l1 between every element in the list l2.

We can write our own recursive functions to operate on lists.

For example, here is an implementation of the map function:

///
/// Returns the result of applying `f` to every element in `l`.
/// That is, the result is of the form: `f(x1) :: f(x2) :: ...`.
///
pub def map(f: a -> b \ ef, l: List[a]): List[b] \ ef = match l {
    case Nil     => Nil
    case x :: xs => f(x) :: map(f, xs)
}