2.1 Lists
A […] form as an expression creates a list:
> [1, 2, 3]
[1, 2, 3]
> [0, "apple", Posn(1, 2)]
[0, "apple", Posn(1, 2)]
Operations on lists include functions like List.length, and some of those operations can be applied using . directly on an expression that produces a list. The ++ operator appends lists.
> List.length(["a", "b", "c"])
3
> ["a", "b", "c"].length()
3
> ["a", "b"] ++ ["c", "d", "e"]
["a", "b", "c", "d", "e"]
You can also use the List constructor, which takes any number of arguments:
> List(1, 2, 3)
[1, 2, 3]
List works as an annotation with :~ and :::
> classify([1])
"list"
> classify(1)
"number"
> classify("1")
"other"
As pattern, […] matches a list, and list elements can be matched with specific subpatterns. The List binding operator works the same in bindings, too.
> are_three_sorted([1, 2, 3])
#true
> are_three_sorted([1, 3, 2])
#false
The last element in a […] binding pattern can be ..., which means zero or more repetitions of the preceding pattern.
> starts_milk([])
#false
> starts_milk(["milk", "apple", "banana"])
#true
> starts_milk(["apple", "coffee", "banana"])
#false
Each variable in a pattern preceding ... is bound as a repetition, which cannot be used like a plain variable. Instead, a repetition variable must be used in an expression form that supports using repetitions, typically with before .... For example, a […] or List expression (as opposed to binding) supports ... in place of an element, in which case the preceding element form is treated as a repetition that supplies elements for the new list.
> got_milk([])
#false
> got_milk(["apple", "milk", "banana"])
#true
> got_milk(["apple", "coffee", "banana"])
#false
While ... can only be used at the end of a list in a binding, ... can be used anywhere in an expression, and it can be used multiple times.
> [grocery, ..., "cupcake"]
["apple", "banana", "milk", "cupcake"]
["apple", "banana", "milk", "apple", "banana", "milk"]
Instead of using ... in […] or List to bind or use a repetition, use & to bind or reference a plain list value whose elements are the rest of the list.
> others
["banana", "milk"]
["broccoli", "banana", "milk", "cupcake", "apple"]
> [others, ...]
others: used with wrong repetition depth
expected: 0
actual: 1
["apple", "banana", "milk", "pencil", "eraser"]
When […] appears after an expression, then instead of forming a list, it accesses an element of an indexable value. Lists are indexable using natural numbers starting with 0:
> others[0]
"banana"
> others[1]
"milk"
Indexing with […] is sensitive to binding-based static information in the same way as .. For example, a function’s argument can use a binding pattern that indicates a list of Posns, and then . can be used after [...] to efficiently access a field of a Posn instance:
> nth_x([Posn(1, 2), Posn(3, 4), Posn(5, 6)], 1)
3
An equivalent way to write nth_x is with the List.of annotation constructor. It expects an annotation that every element of the list must satisfy:
ps[n].x
The nth_x function could have been written as follows, but unlike the previous versions (where the relevant list existed as an argument), this one creates a new intermediate list of x elements:
> nth_x([Posn(1, 2), Posn(3, 4), Posn(5, 6)], 1)
3
Many operations on a list with N elements take O(log N) time, including getting an element of a list with […], appending lists with ++, adding to the front or end of a list with List.cons or List.add, inserting into the middle of a list with List.insert, deleting a list element with List.delete, or dropping or taking a list prefix or suffix with functions like List.drop_left. Internally, lists are implemented as relaxed radix balanced (RRB) trees.
As an alternative to List, PairList constructs a pair list, which is implemented as a singly linked list. As the name suggests, a pair list uses a pair to add each element to the front of an existing list. The PairList.cons operation performs that addition, and it takes O(1) time, as do its PairList.first and PairList.rest operations to access the initial pair’s components. Operations like appending or accessing a random element take O(N) time. When PairList prefixes […] for constructing or matching a list, then […] constructs or matches a pair list, instead of a list.
> Pair.cons("cadillac", autos)
PairList["cadillac", "beetle", "jeep", "miata"]
#false
#true
The Listable annotation is satisfied by a list, pair list, or another data structure that implements a conversion to list form. Listable values are generally allowed for explicit splicing operations, such as using & to build a list. One consequence is that & within a constructor can be used to convert among listable representations, potentially while also adding additional elements.
> autos
PairList["beetle", "jeep", "miata"]
> [& autos]
["beetle", "jeep", "miata"]
PairList["cadillac", "beetle", "jeep", "miata", "corvette"]