1.5 Lists🔗ℹ

Shplait lists are uniform, meaning that all of the elements of a list must have the same type. Square brackets […] create a list with comma-separated elements.

> [1, 2, 3 + 4]

- Listof(Int)

[1, 2, 7]

> [string_append("a", "b"), "c"]

- Listof(String)

["ab", "c"]

The newline and indentation rules inside […] are the same as inside parentheses, so when an element of the list starts on a new line, it must be vertically aligned with the first element of the list.

> [1,    2,    3 + 4]

- Listof(Int)

[1, 2, 7]

> [1, 2, 3, 4,    5, 6, 7, 8,    9, 10, 11]

- Listof(Int)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

> [     1,     2,     3   ]

- Listof(Int)

[1, 2, 3]

As you can see from the examples, the type of a list is written as Listof followed by parentheses containing the type of the list’s elements.

A list is immutable. That is, the value [1, 2, 3] is as unchanging as the numbers 1, 2, and 3 within the list. You can’t change a list to add new elements to it—but you can create a new list that is like the old one, except that it has another element. The cons function takes an element and a list and adds the element to the front of the list, creating a new list with all of the elements:

> cons(1, [2, 3])

- Listof(Int)

[1, 2, 3]

> cons("apple", ["banana"])

- Listof(String)

["apple", "banana"]

The cons operation takes O(log n) time, because a list is internally represented as a tree, and cons creates a new tree that shares parts of the existing one.

If you have two lists, instead of one element and a list, you can combine the lists with append:

> append([1, 2], [3, 4])

- Listof(Int)

[1, 2, 3, 4]

Don’t confuse cons and append. The cons function takes an element and a list, while append takes a list and a list. That difference is reflected in their types:

> cons

- (?a, Listof(?a)) -> Listof(?a)

#<function:cons>

> append

- (Listof(?a), Listof(?a)) -> Listof(?a)

#<function:append>

Mixing them up will trigger a type error:

> cons([1], [2, 3])

typecheck failed: Listof(Int) vs. Int

> append(1, [2, 3])

typecheck failed: Listof(?_a) vs. Int

A list doesn’t have to contain any values:

> []

- Listof(?_a)

[]

Although the multi-element […] form is convenient, the true list-construction primitives are just [] and cons, and you can build up any other list using those:

> []

- Listof(?_a)

[]

> cons("food", [])

- Listof(String)

["food"]

> cons("dog", cons("food", []))

- Listof(String)

["dog", "food"]

The is_empty function determines whether a list is empty, and is_cons determines whether a list has at least one item:

> is_empty([])

- Boolean

#true

> is_cons(cons(1, []))

- Boolean

#true

> is_cons([1])

- Boolean

#true

> is_cons([])

- Boolean

#false

> is_empty([1])

- Boolean

#false

The cons operation constructs a new value from two pieces. The first and rest operations are the opposite of cons. Given a value produced by cons, first returns the item that cons added to the start of the list, and rest returns the list that cons added to. More generally, first gets the first item from a list, and rest gets everything in the list with the first item removed.

> first(cons(1, [2, 3]))

- Int

1

> rest(cons(1, [2, 3]))

- Listof(Int)

[2, 3]

> first(["apple", "banana", "coconut"])

- String

"apple"

> rest(["apple", "banana", "coconut"])

- Listof(String)

["banana", "coconut"]

> first(rest(["apple", "banana", "coconut"]))

- String

"banana"

> rest(rest(["apple", "banana", "coconut"]))

- Listof(String)

["coconut"]

Shplait also provides list_get for getting an element by its index, which is sometimes useful to extract pieces of a list that has a known shape. More commonly, a function that takes a nonempty list will need to use first and recur with the rest. Here’s a function that checks whether "milk" is in a list of strings (but we explain more about definitions in the next section):