List
isEmpty : List a -> Bool
Types A sequential list of values.
[1, 2, 3] # a list of numbers ["a", "b", "c"] # a list of strings [[1.1], [], [2.2, 3.3]] # a list of lists of numbers
The maximum size of a List
is limited by the amount of heap memory available
to the current process. If there is not enough memory available, attempting to
create the list could crash. (On Linux, where overcommit
is normally enabled, not having enough memory could result in the list appearing
to be created just fine, but then crashing later.)
The theoretical maximum length for a list created in Roc is half of
Num.maxNat
. Attempting to create a list bigger than that in Roc code will always fail, although in practice it is likely to fail at much smaller lengths due to insufficient memory being available.
Performance Details
Under the hood, a list is a record containing a len : Nat
field, a capacity : Nat
field, and a pointer to a reference count and a flat array of bytes.
Shared Lists
Shared lists are reference counted.
Each time a given list gets referenced, its reference count ("refcount" for short) gets incremented. Each time a list goes out of scope, its refcount count gets decremented. Once a refcount, has been decremented more times than it has been incremented, we know nothing is referencing it anymore, and the list's memory will be immediately freed.
Let's look at an example.
ratings = [5, 4, 3] { foo: ratings, bar: ratings }
The first line binds the name ratings
to the list [5, 4, 3]
. The list
begins with a refcount of 1, because so far only ratings
is referencing it.
The second line alters this refcount. { foo: ratings
references
the ratings
list, and so does bar: ratings }
. This will result in its
refcount getting incremented from 1 to 3.
Let's turn this example into a function.
getRatings = \first -> ratings = [first, 4, 3] { foo: ratings, bar: ratings } getRatings 5
At the end of the getRatings
function, when the record gets returned,
the original ratings =
binding has gone out of scope and is no longer
accessible. (Trying to reference ratings
outside the scope of the
getRatings
function would be an error!)
Since ratings
represented a way to reference the list, and that way is no
longer accessible, the list's refcount gets decremented when ratings
goes
out of scope. It will decrease from 3 back down to 2.
Putting these together, when we call getRatings 5
, what we get back is
a record with two fields, foo
, and bar
, each of which refers to the same
list, and that list has a refcount of 2.
Let's change the last line to be (getRatings 5).bar
instead of getRatings 5
:
getRatings = \first -> ratings = [first, 4, 3] { foo: ratings, bar: ratings } (getRatings 5).bar
Now, when this expression returns, only the bar
field of the record will
be returned. This will mean that the foo
field becomes inaccessible, causing
the list's refcount to get decremented from 2 to 1. At this point, the list is back
where it started: there is only 1 reference to it.
Finally let's suppose the final line were changed to this:
List.first (getRatings 5).bar
This call to List.first
means that even the list in the bar
field has become
inaccessible. As such, this line will cause the list's refcount to get
decremented all the way to 0. At that point, nothing is referencing the list
anymore, and its memory will get freed.
Things are different if this is a list of lists instead of a list of numbers.
Let's look at a simpler example using List.first
- first with a list of numbers,
and then with a list of lists, to see how they differ.
Here's the example using a list of numbers.
nums = [1, 2, 3, 4, 5, 6, 7] first = List.first nums last = List.last nums first
It makes a list, calls List.first
and List.last
on it, and then returns first
.
Here's the equivalent code with a list of lists:
lists = [[1], [2, 3], [], [4, 5, 6, 7]] first = List.first lists last = List.last lists first
TODO explain how in the former example, when we go to free nums
at the end,
we can free it immediately because there are no other refcounts. However,
in the case of lists
, we have to iterate through the list and decrement
the refcounts of each of its contained lists - because they, too, have
refcounts! Importantly, because the first element had its refcount incremented
because the function returned first
, that element will actually end up
not getting freed at the end - but all the others will be.
In the lists
example, lists = [...]
also creates a list with an initial
refcount of 1. Separately, it also creates several other lists - each with
their own refcounts - to go inside that list. (The empty list at the end
does not use heap memory, and thus has no refcount.)
At the end, we once again call List.first
on the list, but this time
- Copying small lists (64 elements or fewer) is typically slightly faster than copying small persistent data structures. This is because, at small sizes, persistent data structures tend to be thin wrappers around flat arrays anyway. They don't have any copying advantage until crossing a certain minimum size threshold.
- Even when copying is faster, other list operations may still be slightly slower with persistent data structures. For example, even if it were a persistent data structure,
List.map
,List.walk
, andList.keepIf
would all need to traverse every element in the list and build up the result from scratch. These operations are all - Roc's compiler optimizes many list operations into in-place mutations behind the scenes, depending on how the list is being used. For example,
List.map
,List.keepIf
, andList.set
can all be optimized to perform in-place mutations. - If possible, it is usually best for performance to use large lists in a way where the optimizer can turn them into in-place mutations. If this is not possible, a persistent data structure might be faster - but this is a rare enough scenario that it would not be good for the average Roc program's performance if this were the way
List
worked by default. Instead, you can look outside Roc's standard modules for an implementation of a persistent data structure - likely built usingList
under the hood! Check if the list is empty.
List.isEmpty [1, 2, 3] List.isEmpty []
get : List a, Nat -> Result a [OutOfBounds]
replace : List a, Nat, a -> { list : List a, value : a }
set : List a, Nat, a -> List a
Replaces the element at the given index with a replacement.
List.set ["a", "b", "c"] 1 "B"
If the given index is outside the bounds of the list, returns the original list unmodified.
To drop the element at a given index, instead of replacing it, see List.dropAt
.
append : List a, a -> List a
Add a single element to the end of a list.
List.append [1, 2, 3] 4 [0, 1, 2] |> List.append 3
prepend : List a, a -> List a
Add a single element to the beginning of a list.
List.prepend [1, 2, 3] 0 [2, 3, 4] |> List.prepend 1
len : List a -> Nat
Returns the length of the list - the number of elements it contains.
One List
can store up to 2,147,483,648 elements (just over 2 billion), which
is exactly equal to the highest valid #I32 value. This means the #U32 this function
returns can always be safely converted to an #I32 without losing any data.
withCapacity : Nat -> List a
Create a list with space for at least capacity elements
reserve : List a, Nat -> List a
Enlarge the list for at least capacity additional elements
releaseExcessCapacity : List a -> List a
Shrink the memory footprint of a list such that it's capacity and length are equal. Note: This will also convert seamless slices to regular lists.
concat : List a, List a -> List a
Put two lists together.
List.concat [1, 2, 3] [4, 5] [0, 1, 2] |> List.concat [3, 4]
last : List a -> Result a [ListWasEmpty]
Returns the last element in the list, or ListWasEmpty
if it was empty.
single : a -> List a
A list with a single element in it.
This is useful in pipelines, like so:
websites = Str.concat domain ".com" |> List.single
repeat : a, Nat -> List a
Returns a list with the given length, where every element is the given value.
reverse : List a -> List a
Returns the list with its elements reversed.
List.reverse [1, 2, 3]
join : List (List a) -> List a
Join the given lists together into one list.
List.join [[1, 2, 3], [4, 5], [], [6, 7]] List.join [[], []] List.join []
contains
walk : List elem, state, (state, elem -> state) -> state
Build a value using each element in the list.
Starting with a given state
value, this walks through each element in the
list from first to last, running a given step
function on that element
which updates the state
. It returns the final state
at the end.
You can use it in a pipeline:
[2, 4, 8] |> List.walk 0 Num.add
This returns 14 because:
state
starts at 0- Each
step
runsNum.add state elem
, and the return value becomes the newstate
.
Here is a table of how state
changes as List.walk
walks over the elements
[2, 4, 8]
using Num.add
as its step
function to determine the next state
.
state | elem | Num.add state elem |
---|---|---|
0 | ||
0 | 2 | 2 |
2 | 4 | 6 |
6 | 8 | 14 |
The following returns -6:
[1, 2, 3] |> List.walk 0 Num.sub
Note that in other languages, walk
is sometimes called reduce
,
fold
, foldLeft
, or foldl
.
walkBackwards : List elem, state, (state, elem -> state) -> state
Note that in other languages, walkBackwards
is sometimes called reduceRight
,
fold
, foldRight
, or foldr
.
walkUntil : List elem, state, (state, elem -> [ Continue state, Break state ]) -> state
Same as List.walk
, except you can stop walking early.
Performance Details
Compared to List.walk
, this can potentially visit fewer elements (which can
improve performance) at the cost of making each step take longer.
However, the added cost to each step is extremely small, and can easily
be outweighed if it results in skipping even a small number of elements.
As such, it is typically better for performance to use this over List.walk
if returning Break
earlier than the last element is expected to be common.
walkBackwardsUntil : List elem, state, (state, elem -> [ Continue state, Break state ]) -> state
Same as List.walkUntil
, but does it from the end of the list instead.
walkFrom : List elem, Nat, state, (state, elem -> state) -> state
Walks to the end of the list from a specified starting index
walkFromUntil : List elem, Nat, state, (state, elem -> [ Continue state, Break state ]) -> state
A combination of List.walkFrom
and List.walkUntil
sum : List (Num a) -> Num a
product : List (Num a) -> Num a
any : List a, (a -> Bool) -> Bool
Run the given predicate on each element of the list, returning Bool.true
if
any of the elements satisfy it.
all : List a, (a -> Bool) -> Bool
Run the given predicate on each element of the list, returning Bool.true
if
all of the elements satisfy it.
keepIf : List a, (a -> Bool) -> List a
Run the given function on each element of a list, and return all the
elements for which the function returned Bool.true
.
List.keepIf [1, 2, 3, 4] (\num -> num > 2)
Performance Details
List.keepIf
always returns a list that takes up exactly the same amount
of memory as the original, even if its length decreases. This is because it
can't know in advance exactly how much space it will need, and if it guesses a
length that's too low, it would have to re-allocate.
(If you want to do an operation like this which reduces the memory footprint
of the resulting list, you can do two passes over the lis with List.walk
- one
to calculate the precise new size, and another to populate the new list.)
If given a unique list, List.keepIf
will mutate it in place to assemble the appropriate list.
If that happens, this function will not allocate any new memory on the heap.
If all elements in the list end up being kept, Roc will return the original
list unaltered.
dropIf : List a, (a -> Bool) -> List a
Run the given function on each element of a list, and return all the
elements for which the function returned Bool.false
.
List.dropIf [1, 2, 3, 4] (\num -> num > 2)
Performance Details
List.dropIf
has the same performance characteristics as List.keepIf
.
See its documentation for details on those characteristics!
countIf : List a, (a -> Bool) -> Nat
Run the given function on each element of a list, and return the
number of elements for which the function returned Bool.true
.
keepOks : List before, (before -> Result after *) -> List after
This works like List.map
, except only the transformed values that are
wrapped in Ok
are kept. Any that are wrapped in Err
are dropped.
List.keepOks [["a", "b"], [], [], ["c", "d", "e"]] List.last fn = \str -> if Str.isEmpty str then Err StrWasEmpty else Ok (Str.len str) List.keepOks ["", "a", "bc", "", "d", "ef", ""]
keepErrs : List before, (before -> Result * after) -> List after
This works like List.map
, except only the transformed values that are
wrapped in Err
are kept. Any that are wrapped in Ok
are dropped.
List.keepErrs [["a", "b"], [], [], ["c", "d", "e"]] List.last fn = \str -> if Str.isEmpty str then Err StrWasEmpty else Ok (Str.len str) List.keepErrs ["", "a", "bc", "", "d", "ef", ""]
map : List a, (a -> b) -> List b
Convert each element in the list to something new, by calling a conversion function on each of them. Then return a new list of the converted values.
List.map [1, 2, 3] (\num -> num + 1) List.map ["", "a", "bc"] Str.isEmpty
map2 : List a, List b, (a, b -> c) -> List c
Run a transformation function on the first element of each list, and use that as the first element in the returned list. Repeat until a list runs out of elements.
Some languages have a function named zip
, which does something similar to
calling List.map2
passing two lists and Pair
:
zipped = List.map2 ["a", "b", "c"] [1, 2, 3] Pair
map3 : List a, List b, List c, (a, b, c -> d) -> List d
Run a transformation function on the first element of each list, and use that as the first element in the returned list. Repeat until a list runs out of elements.
map4 : List a, List b, List c, List d, (a, b, c, d -> e) -> List e
Run a transformation function on the first element of each list, and use that as the first element in the returned list. Repeat until a list runs out of elements.
mapWithIndex : List a, (a, Nat -> b) -> List b
This works like List.map
, except it also passes the index
of the element to the conversion function.
range
Returns a list of all the integers between start
and end
.
To include the start
and end
integers themselves, use At
like so:
List.range { start: At 2, end: At 5 } # returns [2, 3, 4, 5]
To exclude them, use After
and Before
, like so:
List.range { start: After 2, end: Before 5 } # returns [3, 4]
You can have the list end at a certain length rather than a certain integer:
List.range { start: At 6, end: Length 4 } # returns [6, 7, 8, 9]
If step
is specified, each integer increases by that much. (step: 1
is the default.)
List.range { start: After 0, end: Before 9, step: 3 } # returns [3, 6]
List.range will also generate a reversed list if step is negative or end comes before start:
List.range { start: At 5, end: At 2 } # returns [5, 4, 3, 2]
All of these options are compatible with the others. For example, you can use At
or After
with start
regardless of what end
and step
are set to.
sortWith : List a, (a, a -> [ LT, EQ, GT ]) -> List a
Sort with a custom comparison function
sortAsc : List (Num a) -> List (Num a)
Sorts a list in ascending order (lowest to highest), using a function which specifies a way to represent each element as a number.
To sort in descending order (highest to lowest), use List.sortDesc
instead.
sortDesc : List (Num a) -> List (Num a)
Sorts a list in descending order (highest to lowest), using a function which specifies a way to represent each element as a number.
To sort in ascending order (lowest to highest), use List.sortAsc
instead.
swap : List a, Nat, Nat -> List a
first : List a -> Result a [ListWasEmpty]
Returns the first element in the list, or ListWasEmpty
if it was empty.
dropFirst : List elem -> List elem
Remove the first element from the list.
Returns the new list (with the removed element missing).
dropLast : List elem -> List elem
Remove the last element from the list.
Returns the new list (with the removed element missing).
takeFirst : List elem, Nat -> List elem
Returns the given number of elements from the beginning of the list.
List.takeFirst [1, 2, 3, 4, 5, 6, 7, 8] 4
If there are fewer elements in the list than the requested number, returns the entire list.
List.takeFirst [1, 2] 5
To remove elements from the beginning of the list, use List.takeLast
.
To remove elements from both the beginning and end of the list,
use List.sublist
.
To split the list into two lists, use List.split
.
takeLast : List elem, Nat -> List elem
Returns the given number of elements from the end of the list.
List.takeLast [1, 2, 3, 4, 5, 6, 7, 8] 4
If there are fewer elements in the list than the requested number, returns the entire list.
List.takeLast [1, 2] 5
To remove elements from the end of the list, use List.takeFirst
.
To remove elements from both the beginning and end of the list,
use List.sublist
.
To split the list into two lists, use List.split
.
drop : List elem, Nat -> List elem
Drops n elements from the beginning of the list.
dropAt : List elem, Nat -> List elem
Drops the element at the given index from the list.
This has no effect if the given index is outside the bounds of the list.
To replace the element at a given index, instead of dropping it, see List.set
.
min : List (Num a) -> Result (Num a) [ListWasEmpty]
max : List (Num a) -> Result (Num a) [ListWasEmpty]
joinMap : List a, (a -> List b) -> List b
Like List.map
, except the transformation function wraps the return value
in a list. At the end, all the lists get joined together into one list.
You may know a similar function named concatMap
in other languages.
findFirst : List elem, (elem -> Bool) -> Result elem [NotFound]
Returns the first element of the list satisfying a predicate function.
If no satisfying element is found, an Err NotFound
is returned.
findLast : List elem, (elem -> Bool) -> Result elem [NotFound]
Returns the last element of the list satisfying a predicate function.
If no satisfying element is found, an Err NotFound
is returned.
findFirstIndex : List elem, (elem -> Bool) -> Result Nat [NotFound]
Returns the index at which the first element in the list
satisfying a predicate function can be found.
If no satisfying element is found, an Err NotFound
is returned.
findLastIndex : List elem, (elem -> Bool) -> Result Nat [NotFound]
Returns the last index at which the first element in the list
satisfying a predicate function can be found.
If no satisfying element is found, an Err NotFound
is returned.
sublist : List elem, { start : Nat, len : Nat } -> List elem
Returns a subsection of the given list, beginning at the start
index and
including a total of len
elements.
If start
is outside the bounds of the given list, returns the empty list.
List.sublist [1, 2, 3] { start: 4, len: 0 }
If more elements are requested than exist in the list, returns as many as it can.
List.sublist [1, 2, 3, 4, 5] { start: 2, len: 10 }
If you want a sublist which goes all the way to the end of the list, no matter how long the list is,
List.takeLast
can do that more efficiently.
Some languages have a function called slice
which works similarly to this.
intersperse : List elem, elem -> List elem
Intersperses sep
between the elements of list
List.intersperse 9 [1, 2, 3] # [1, 9, 2, 9, 3]
startsWith
Returns Bool.true
if the first list starts with the second list.
If the second list is empty, this always returns Bool.true
; every list
is considered to "start with" an empty list.
If the first list is empty, this only returns Bool.true
if the second list is empty.
endsWith
Returns Bool.true
if the first list ends with the second list.
If the second list is empty, this always returns Bool.true
; every list
is considered to "end with" an empty list.
If the first list is empty, this only returns Bool.true
if the second list is empty.
split : List elem, Nat -> { before : List elem, others : List elem }
Splits the list into two lists, around the given index.
The returned lists are labeled before
and others
. The before
list will
contain all the elements whose index in the original list was less than
than the given index, # and the others
list will be all the others. (This
means if you give an index of 0, the before
list will be empty and the
others
list will have the same elements as the original list.)
splitFirst
Returns the elements before the first occurrence of a delimiter, as well as the
remaining elements after that occurrence. If the delimiter is not found, returns Err
.
List.splitFirst [Foo, Z, Bar, Z, Baz] Z == Ok { before: [Foo], after: [Bar, Z, Baz] }
splitLast
Returns the elements before the last occurrence of a delimiter, as well as the
remaining elements after that occurrence. If the delimiter is not found, returns Err
.
List.splitLast [Foo, Z, Bar, Z, Baz] Z == Ok { before: [Foo, Z, Bar], after: [Baz] }
mapTry : List elem, (elem -> Result ok err) -> Result (List ok) err
Like List.map
, except the transformation function returns a Result
.
If that function ever returns Err
, mapTry
immediately returns that Err
.
If it returns Ok
for every element, mapTry
returns Ok
with the transformed list.
walkTry : List elem, state, (state, elem -> Result state err) -> Result state err
This is the same as iterate
but with Result
instead of [Continue, Break]
.
Using Result
saves a conditional in mapTry
.