6.30 Lists

8.12

6.30 Lists🔗ℹ

Lists can be constructed using the syntax [expr, ...], which creates list containing the values of the exprs as elements. More precisely, a use of square brackets without a preceding expression implicitly uses the #%brackets form, which is normally bound to construct a list.

A list is indexable using […] to access a list element by position—in O(log N) time—via #%index. A list also works with the ++ operator to append lists. A list can be used as sequence, in which case it supplies its elements in order.

The . operator can be used on a list expression as equivalent to calling List functions:

lst.length()
is
List.length(lst)
lst.get(n)
is
List.get(lst, n)
lst.set(n, v)
is
List.set(lst, n, v)
lst.first
is
List.first(lst)
lst.last
is
List.last(lst)
lst.rest
is
List.rest(lst)
lst.insert(n, v)
is
List.insert(lst, n, v)
lst.add(v)
is
List.add(lst, v)
lst.delete(n)
is
List.delete(lst, n)
lst.reverse()
is
List.reverse(lst)
lst.append(lst2, ...)
is
List.append(lst, lst2, ...)
lst.take(n)
is
List.take(lst, n)
lst.take_last(n)
is
List.take_last(lst, n)
lst.drop(n)
is
List.drop(lst, n)
lst.drop_last(n)
is
List.drop_last(lst, n)
lst.sublist(n, m)
is
List.sublist(lst, n, m)
lst.has_element(v, eqls, ...)
is
List.has_element(lst, v, eqls, ...)
lst.find(pred)
is
List.find(lst, pred)
lst.remove(v)
is
List.remove(lst, v)
lst.map(func)
is
List.map(lst, func)
lst.for_each(func)
is
List.for_each(lst, func)
lst.sort(arg, ...)
is
List.sort(lst, arg, ...)
lst.copy()
is
List.copy(lst)
lst.to_list()
is
List.to_list(lst)
lst.to_sequence()
is
List.to_sequence(lst)

annotation

List

annotation

List.of(annot)

Matches any list in the form without of. The of variant matches a list whose elements satisfy annot.

Static information associated by List or List.of makes an expression acceptable as a sequence to for in static mode.

function

fun List(v :: Any, ...) :: List

expression

#%brackets [expr_or_splice, ...]

repetition

#%brackets [repet_or_splice, ...]

expression

List[expr_or_splice, ...]

repetition

List[repet_or_splice, ...]

expr_or_splice	=	expr
	\|	repet , ellipses
	\|	& listable_expr

ellipses	=	ellipsis
	\|	ellipses , ellipsis

ellipsis

...

Constructs a list of the given vs values or results of the expr_or_splices. A & or ... form can appear within […] to splice a repetition or existing listable value into the constructed list, the same as in a function call (see #%call). List constructions can also serve as repetitions, where repet_or_splice is like expr_or_splice, but with repetitions in place of expressions.

The #%brackets form is implicitly used when […] is used in in an expression position. See also Implicit Forms.

> def lst = List(1, 2, 3)
> lst
[1, 2, 3]
> lst[0]
1
> lst ++ [4, 5]
[1, 2, 3, 4, 5]
> #%brackets [1, 2, 3]
[1, 2, 3]

binding operator

List(bind, ...)

binding operator

List(bind, ..., rest)

binding operator

#%brackets [bind, ...]

binding operator

#%brackets [bind, ..., rest]

binding operator

List[bind, ...]

binding operator

List[bind, ..., rest]

rest	=	repet_bind , ellipsis
	\|	& list_bind

ellipsis

...

Matches a list with as many elements as binds, or if rest is included, at least as many elements as binds, where the rest (if present) matches the rest of the list.

When & list_bind is used, the rest of the list must match the list_bind. Static information associated by List is propagated to list_bind.

When repet_bind is used and does not impose a predicate or conversion on a matching value (e.g., repet_bind is an identifier), then the corresponding elements of a matching value are not traversed, which means that matching can be constant-time. Using this repetition for the tail a new list similarly avoids traversing the elements.

The #%brackets form is implicitly used when […] is used in in a binding position. See also Implicit Forms.

> def List(1, x, y) = [1, 2, 3]
> y
3
> def [1, also_x, also_y] = [1, 2, 3]
> also_y
3
> def List(1, & xs) = [1, 2, 3]
> xs
[2, 3]
> def List(1, x, ...) = [1, 2, 3]
> [x, ...]
[2, 3]

annotation

NonemptyList

annotation

NonemptyList.of(annot)

Like List as an annotation, but matches only non-empty lists.

> [1] :: NonemptyList
[1]
> [] :: NonemptyList
::: value does not satisfy annotation
value: []
annotation: NonemptyList

reducer

List

A reducer used with for, accumulates each result of a for body into a result list.

function

fun List.insert(lst :: List, n :: NonnegInt, elem :: Any) :: List

Creates a list like lst, but with elem added before the nth element or at the end if n is the length of lst. The n index must be no more than the length of lst. Insertion takes O(log N) time.

> List.insert(["a", "b", "c"], 1, "x")
["a", "x", "b", "c"]

function

fun List.add(lst :: List, elem :: Any) :: List

Creates a list like lst, but with elem added to the end, equivalent to lst.insert(lst.length(), elem).

> List.add([2, 3], 1)
[2, 3, 1]
> [2, 3].add(1)
[2, 3, 1]
> block:
let l = [2, 3]
l.insert(l.length(), 1)
[2, 3, 1]

function

fun List.cons(elem :: Any, lst :: List) :: List

Creates a list like lst, but with elem added to the front, equivalent to lst.insert(0, elem).

> List.cons(1, [2, 3])
[1, 2, 3]
> [2, 3].insert(0, 1)
[1, 2, 3]

binding operator

List.cons(elem_bind, list_bind)

Matches a non-empty list where elem_bind matches the first element of the list and list_bind matches the rest of the list. Static information associated by List is propagated to list_bind.

> def List.cons(x, y) = [1, 2, 3]
> x
1
> y
[2, 3]

value

def List.empty :: List = []

binding operator

List.empty

A name and pattern for the empty list.

function

fun List.get(lst :: List, n :: NonnegInt) :: Any

Equivalent to lst[n] (with the default implicit #%index form). Returns the nth element of lst (starting from 0). Accessing a list element by position takes O(log N) time.

> ["a", "b", "c"].get(1)
"b"
> ["a", "b", "c"][1]
"b"

function

fun List.first(lst :: NonemptyList) :: Any

Returns the first element of lst. Accessing the first element takes O(log N) time.

> List.first(["a", "b", "c"])
"a"
> ["a", "b", "c"].first
"a"

function

fun List.last(lst :: NonemptyList) :: Any

Returns the last element of lst. Accessing the last element takes O(log N) time.

> List.last(["a", "b", "c"])
"c"
> ["a", "b", "c"].last
"c"

function

fun List.rest(lst :: NonemptyList) :: List

Returns a list like lst, but without its first element. Creating the list takes O(log N) time.

> List.rest(["a", "b", "c"])
["b", "c"]
> ["a", "b", "c"].rest
["b", "c"]

function

fun List.delete(lst :: List, n :: NonnegInt) :: List

Creates a list like lst, but without the nth element. The n index must be less than the length of lst. Deletion takes O(log N) time.

> List.delete(["a", "b", "c"], 1)
["a", "c"]

function

fun List.set(lst :: List, n :: NonnegInt, v :: Any) :: List

Returns a list like lst, but with the nth element replaced with v, equivalent to lst.delete(n).insert(n, v). Note that this function performs a functional update, as opposed to mutable, which means lists do not implement MutableIndexable.

> ["a", "b", "c"].set(1, "beta")
["a", "beta", "c"]
> ["a", "b", "c"].delete(1).insert(1, "beta")
["a", "beta", "c"]

repetition

List.repet(list_expr)

Creates a repetition from a list. This is a shorthand for using ... with a List binding.

> def lst = [1, 2, 3]
> block:
let [x, ...] = lst
[x+1, ...]
[2, 3, 4]
> [List.repet(lst) + 1, ...]
[2, 3, 4]

function

fun List.length(lst :: List) :: NonnegInt

Returns the number of items in lst. The length is produced in O(1) time.

> List.length([1, 4, 8])
3
> List.length([])
0
> [1, 4, 8].length()
3
> [].length()
0

function

fun List.reverse(lst :: List) :: List

Returns a list with the same items as lst, but in reversed order. Reversing a list takes O(N log N) time, equivalent asymptotically to adding each element of lst to another list one at a time.

> List.reverse([1, 4, 8])
[8, 4, 1]
> [1, 4, 8].reverse()
[8, 4, 1]

function

fun List.append(lst :: List, ...) :: List

Appends the lsts in order. See also ++. Appending takes O(log N) time, which is asymptotically faster than adding each element one at a time from one list to the other.

> List.append([1, 2, 3], [4, 5], [6])
[1, 2, 3, 4, 5, 6]
> [1, 2, 3].append([4, 5], [6])
[1, 2, 3, 4, 5, 6]

function

fun List.take(lst :: List, n :: NonnegInt) :: List

function

fun List.take_last(lst :: List, n :: NonnegInt) :: List

Returns a list like lst, but with only the first n elements in the case of List.take, or only the last n elements in the case of List.take_last. The given lst must have at least n elements, otherwise an Exn.Fail.Contract exception is thrown. Creating the new list takes O(log N) time, which is asymptotically faster than building a new list by adding or removing elements one at a time.

> [1, 2, 3, 4, 5].take(2)
[1, 2]
> [1, 2, 3, 4, 5].take_last(2)
[4, 5]
> [1].take(2)
List.take: index is out of range
  index: 2
  valid range: [0, 1]
  list: [1]

function

fun List.drop(lst :: List, n :: NonnegInt) :: List

function

fun List.drop_last(lst :: List, n :: NonnegInt) :: List

Returns a list like lst, but without the first n elements in the case of List.drop, or without the last n elements in the case of List.drop_last. The given lst must have at least n elements, otherwise an Exn.Fail.Contract exception is thrown. Creating the new list takes O(log N) time, which is asymptotically faster than building a new list by adding or removing elements one at a time.

> [1, 2, 3, 4, 5].drop(2)
[3, 4, 5]
> [1, 2, 3, 4, 5].drop_last(2)
[1, 2, 3]
> [1].drop(2)
List.drop: index is out of range
  index: 2
  valid range: [0, 1]
  list: [1]

function

fun List.sublist(lst :: List, n :: NonnegInt, m :: NonnegInt) :: List

Returns a sublist of lst containing elements from index n (inclusive) to m (exclusive), equivalent to lst.drop(n).take(m-n).

> [1, 2, 3, 4, 5].sublist(1, 3)
[2, 3]
> [1, 2, 3, 4, 5].drop(1).take(3-1)
[2, 3]

function

fun List.has_element(lst :: List, v :: Any,

eqls :: Function.of_arity(2) = fun (x, y): x == y)

:: Boolean

Returns #true if lst has an element equal to v, #false otherwise, where eqls determines equality. Searching the list takes O(N) time (multiplified by the cost of eqls) to find an element as position N.

> [1, 2, 3].has_element(2)
#true
> [1, 2, 3].has_element(200)
#false

function

fun List.find(lst :: List, pred :: Function.of_arity(1)) :: Any

Returns the first element of lst for which pred returns true, #false otherwise. Searching the list takes O(N) time (multiplied by the cost of pred) to find an element as position N.

> [1, 2, 3].find(fun (x): x mod 2 .= 0)
2
> [1, 2, 3].find(fun (x): x mod 10 .= 9)
#false

function

fun List.remove(lst :: List, v :: Any) :: List

Returns a list like lst, but with the first element equal to v (if any) removed. Searching the list takes O(N) time.

> [1, 2, 3, 2].remove(2)
[1, 3, 2]

function

fun List.map(lst :: List, f :: Function.of_arity(1))

:: List

function

fun List.for_each(lst :: List, f :: Function.of_arity(1))

:: Void

Like Function.map and Function.for_each, but with a single list of arguments first, with the function supplied second.

> List.map([1, 2, 3], fun (x): x + 1)
[2, 3, 4]
> [1, 2, 3].map(fun (x): x + 1)
[2, 3, 4]
> [1, 2, 3].for_each(println)
1
2
3

function

fun List.sort(lst :: List,

is_less :: Function.of_arity(2) = math.less)

:: List

Sorts lst using is_less to compare elements. Sorting takes O(N log N) time.

> List.sort([1, 3, 2])
[1, 2, 3]
> List.sort([1, 3, 2], math.greater)
[3, 2, 1]

function

fun List.iota(n :: NonnegInt) :: List.of(NonnegInt)

Returns a list containing the integers 0 to n (exclusive) in order.

> List.iota(3)
[0, 1, 2]
> List.iota(0)
[]

function

fun List.copy(lst :: List) :: MutableList

Equivalent to MutableList(& lst), creates a new mutable list with the same elements as lst.

> [1, 2, 3].copy()
MutableList[1, 2, 3]

function

fun List.to_list(lst :: List) :: List

Implements Listable by returning lst unchanged.

function

fun List.to_sequence(lst :: List) :: Sequence

Implements Sequenceable by returning a sequence of lst’s elements in order.

1	Rhombus Essentials
2	Collections and Iteration
3	Syntax Objects and Macros
4	Classes and Interfaces
5	Static Information and Binding
6	Core Reference
7	Meta and Macros Reference
8	Rhombus Static by Default
9	Libraries
10	Naming Conventions

6.1	General Forms
6.2	Definitions
6.3	Namespaces
6.4	Import
6.5	Export
6.6	Functions
6.7	Operators
6.8	Classes and Interfaces
6.9	Veneers
6.10	Mutable Variables and Assignment
6.11	Repetitions
6.12	Block
6.13	Conditionals
6.14	Matching
6.15	Iteration
6.16	Recursion
6.17	Context Parameters
6.18	Exceptions
6.19	Continuations
6.20	Implicit Forms
6.21	Static and Dynamic Lookup
6.22	Modules and Submodules
6.23	Booleans
6.24	Numbers
6.25	Characters
6.26	Strings
6.27	Keywords
6.28	Symbols
6.29	Byte Strings
6.30	Lists
6.31	Pairs and Pair Lists
6.32	Mutable Lists
6.33	Arrays
6.34	Maps
6.35	Sets
6.36	Boxes
6.37	Indexables
6.38	Listables
6.39	Sequences
6.40	Appendables
6.41	Comparables
6.42	Paths
6.43	Source Locations
6.44	Void
6.45	Equality
6.46	Dot
6.47	Multiple Values
6.48	Annotations
6.49	Enumerations
6.50	Input and Output
6.51	Eval
6.52	Syntax Objects
6.53	Syntax Classes
6.54	Simple Expression Macros
6.55	Unit Testing

lst.length()	is	List.length(lst)
lst.get(n)	is	List.get(lst, n)
lst.set(n, v)	is	List.set(lst, n, v)
lst.first	is	List.first(lst)
lst.last	is	List.last(lst)
lst.rest	is	List.rest(lst)
lst.insert(n, v)	is	List.insert(lst, n, v)
lst.add(v)	is	List.add(lst, v)
lst.delete(n)	is	List.delete(lst, n)
lst.reverse()	is	List.reverse(lst)
lst.append(lst2, ...)	is	List.append(lst, lst2, ...)
lst.take(n)	is	List.take(lst, n)
lst.take_last(n)	is	List.take_last(lst, n)
lst.drop(n)	is	List.drop(lst, n)
lst.drop_last(n)	is	List.drop_last(lst, n)
lst.sublist(n, m)	is	List.sublist(lst, n, m)
lst.has_element(v, eqls, ...)	is	List.has_element(lst, v, eqls, ...)
lst.find(pred)	is	List.find(lst, pred)
lst.remove(v)	is	List.remove(lst, v)
lst.map(func)	is	List.map(lst, func)
lst.for_each(func)	is	List.for_each(lst, func)
lst.sort(arg, ...)	is	List.sort(lst, arg, ...)
lst.copy()	is	List.copy(lst)
lst.to_list()	is	List.to_list(lst)
lst.to_sequence()	is	List.to_sequence(lst)