6.32 Mutable Lists

8.13

6.32 Mutable Lists🔗ℹ

A mutable list is a mutable object that contains a list. A mutable list is not by itself a list (i.e., it will not satisfy the List annotation), but it is listable.

A mutable list is indexable using […] to access a list element by position—in O(log N) time—via #%index, and it also support element assignment via […] and :=. A mutable list can be used as sequence, in which case it supplies its elements in order.

Operations on a mutable list tend to modify the mutable list and produce #void, instead of creating a new list or returning the modified mutable list.

The model of a mutable list as an object containing a list explains its behavior in the case of concurrent modification: concurrent element assignments for different positions will not interfere, but races with other operations will sometimes negate one of the modifications. Concurrent modification is thus somewhat unpredictable but still safe, and it is not managed by a lock.

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

mlst.length()
is
MutableList.length(mlst)
mlst.get(n)
is
MutableList.get(mlst, n)
mlst.set(n, v)
is
MutableList.set(mlst, n, v)
mlst.insert(n, v)
is
MutableList.insert(mlst, n, v)
mlst.add(v)
is
MutableList.add(mlst, v)
mlst.delete(n)
is
MutableList.delete(mlst, n)
mlst.reverse()
is
MutableList.reverse(mlst)
mlst.append(lst2)
is
MutableList.append(mlst, lst2)
mlst.take(n)
is
MutableList.take(mlst, n)
mlst.take_last(n)
is
MutableList.take_last(mlst, n)
mlst.drop(n)
is
MutableList.drop(mlst, n)
mlst.drop_last(n)
is
MutableList.drop_last(mlst, n)
mlst.sublist(n, m)
is
MutableList.sublist(mlst, n, m)
mlst.has_element(v, eqls, ...)
is
MutableList.has_element(mlst, v, eqls, ...)
mlst.find(pred)
is
MutableList.find(mlst, pred)
mlst.remove(v)
is
MutableList.remove(mlst, v)
mlst.map(func)
is
MutableList.map(mlst, func)
mlst.for_each(func)
is
MutableList.for_each(mlst, func)
mlst.sort(arg, ...)
is
MutableList.sort(mlst, arg, ...)
mlst.snapshot()
is
MutableList.snapshot(mlst)
mlst.to_list()
is
MutableList.to_list(mlst)
mlst.to_sequence()
is
MutableList.to_sequence(mlst)

annotation

MutableList

annotation

MutableList.now_of(annot)

annotation

MutableList.later_of(annot)

Matches any mutable list in the form without now_of or later_of.

The MutableList.now_of form constructs a predicate annotation that matches a mutable list whose elements all currently satisfy annot, but it does not ensure in any way that future values installed into the mutable list will satisfy annot. The given annot must not be a converting annotation. Static information from annot is not propagated to accesses of the mutable list, since there’s no guarantee that the value will still satisfy the annotation.

The MutableList.later_of form constructs a converter annotation that immediately matches a mutable list without checking that its elements currently satisfy annot. The conversion result of the annotation is a view of the original mutable list, but one where annot is checked against a value that would be returned by accessing an element of the mutable list or a value to be installed into the mutable list. (A different view of the mutable list might change an element to one that does not astisfy annot.) Static information from annot is propagated to accesses of the mutable list. Note that a converter annot is applied for each access or update.

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

> MutableList(1, 2, 3) :: MutableList
MutableList[1, 2, 3]
> MutableList(1, 2, 3) :: MutableList.now_of(Number)
MutableList[1, 2, 3]
> MutableList(1, "b", 3) :: MutableList.now_of(Number)
::: value does not satisfy annotation
value: MutableList[1, "b", 3]
annotation: MutableList.now_of(Number)

def a :: MutableList.later_of(Number) = MutableList(1, "b", 3)

> a[0]
1
> a[1]
MutableList: current element does not satisfy annotation
  current element: "b"
  position: 1
  annotation: Number
> a[2] := "c"
MutableList: new element does not satisfy annotation
  new element: "c"
  position: 2
  annotation: Number

function

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

expression

MutableList[expr_or_splice, ...]

repetition

MutableList[repet_or_splice, ...]

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

ellipses	=	ellipsis
	\|	ellipses , ellipsis

ellipsis

...

Constructs a mutable 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). Mutable-list constructions can also serve as repetitions, where repet_or_splice is like expr_or_splice, but with repetitions in place of expressions.

> def mlst = MutableList(1, 2, 3)
> mlst
MutableList[1, 2, 3]
> mlst[0]
1
> mlst[0] := 10
> mlst
MutableList[10, 2, 3]
> MutableList.snapshot(mlst)
[10, 2, 3]

function

fun MutableList.insert(mlst :: MutableList,

n :: NonnegInt, elem :: Any)

:: Void

Modifies mlst to add elem 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.

> def mlst = MutableList["a", "b", "c"]
> MutableList.insert(mlst, 1, "x")
> mlst
MutableList["a", "x", "b", "c"]

function

fun MutableList.add(mlst :: MutableList, elem :: Any) :: Void

Modifies mlst to add elem to the end, equivalent to mlst.insert(mlst.length(), elem).

> def mlst = MutableList[2, 3]
> MutableList.add(mlst, 1)
> mlst
MutableList[2, 3, 1]
> mlst.add(0)
> mlst
MutableList[2, 3, 1, 0]
> mlst.insert(mlst.length(), 10)
> mlst
MutableList[2, 3, 1, 0, 10]

function

fun MutableList.cons(elem :: Any, mlst :: MutableList) :: Void

Modifies mlst to add elem before all current elements, equivalent to mlst.insert(0, elem).

> def mlst = MutableList[2, 3]
> MutableList.cons(1, mlst)
> mlst
MutableList[1, 2, 3]

function

fun MutableList.get(mlst :: MutableList, n :: NonnegInt) :: Any

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

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

function

fun MutableList.set(mlst :: MutableList,

n :: NonnegInt, v :: Any)

:: Void

Equivalent to mlst[n] := v (with the default implicit #%index form). Modifies mlst to replace the nth element with v. The n index must be no more than the length of lst. Setting an element takes O(log N) time.

> def mlst = MutableList["a", "b", "c"]
> mlst.set(1, "beta")
> mlst
MutableList["a", "beta", "c"]
> mlst[2] := "gamma"
> mlst
MutableList["a", "beta", "gamma"]

function

fun MutableList.delete(mlst :: MutableList, n :: NonnegInt)

:: Void

Modifies mlst to delete the nth element. The n index must be less than the length of mlst. Deletion takes O(log N) time.

> def mlst = MutableList["a", "b", "c"]
> MutableList.delete(mlst, 1)
> mlst
MutableList["a", "c"]

function

fun MutableList.length(mlst :: MutableList) :: NonnegInt

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

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

function

fun MutableList.reverse(mlst :: MutableList) :: Void

Modifies mlst to have the same elements but in reversed order. Reversing a list takes O(N log N) time, equivalent asymptotically to adding each element of mlst to another list one at a time.

> def mlst = MutableList[1, 4, 8]
> MutableList.reverse(mlst)
> mlst
MutableList[8, 4, 1]

function

fun MutableList.append(mlst :: MutableList,

lst :: List || MutableList)

:: Void

Modifies (mslt) to addend the elements of lst in order. Appending N elements takes O(N) time.

> def mlst = MutableList[1, 2, 3]
> MutableList.append(mlst, [4, 5])
> MutableList.append(mlst, MutableList[6])
> mlst
MutableList[1, 2, 3, 4, 5, 6]

function

fun MutableList.take(mlst :: MutableList, n :: NonnegInt)

:: Void

function

fun MutableList.take_last(mlst :: MutableList, n :: NonnegInt)

:: Void

Modifies mlst to keep only the first n elements in the case of MutableList.take, or only the last n elements in the case of MutableList.take_last. The given mlst must have at least n elements, otherwise an Exn.Fail.Contract exception is thrown. Modifying the list takes O(log N) time, which is asymptotically faster than building a new list by adding or removing elements one at a time.

> def mlst = MutableList[1, 2, 3, 4, 5]
> mlst.take(3)
> mlst
MutableList[1, 2, 3]
> mlst.take_last(2)
> mlst
MutableList[2, 3]
> mlst.take(10)
MutableList.take: index is out of range
  index: 10
  valid range: [0, 2]
  list: [2, 3]

function

fun MutableList.drop(mlst :: MutableList, n :: NonnegInt)

:: Void

function

fun MutableList.drop_last(mlst :: MutableList, n :: NonnegInt)

:: Void

Modifies mlst to remove the first n elements in the case of MutableList.drop, or the last n elements in the case of MutableList.drop_last. The given mlst must have at least n elements, otherwise an Exn.Fail.Contract exception is thrown. Modifying the list takes O(log N) time, which is asymptotically faster than building a new list by adding or removing elements one at a time.

> def mlst = MutableList[1, 2, 3, 4, 5]
> mlst.drop(2)
> mlst
MutableList[3, 4, 5]
> mlst.drop_last(1)
> mlst
MutableList[3, 4]
> mlst.drop(10)
MutableList.drop: index is out of range
  index: 10
  valid range: [0, 2]
  list: [3, 4]

function

fun MutableList.sublist(mlst :: MutableList,

n :: NonnegInt, m :: NonnegInt)

:: Void

Modifies mlst to keep only elements from index n (inclusive) to m (exclusive), equivalent to mlst.drop(n) followed by mlst.take(m-n).

> def mlst = MutableList[1, 2, 3, 4, 5]
> mlst.sublist(1, 3)
> mlst
MutableList[2, 3]

function

fun MutableList.has_element(mlst :: MutableList, v :: Any,

eqls :: Function.of_arity(2) = (_ == _))

:: Boolean

Returns #true if mlst 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 MutableList.find(mlst :: MutableList,

pred :: Function.of_arity(1))

:: Any

Returns the first element of mlst 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((_ mod 2 .= 0))
2
> [1, 2, 3].find((_ mod 10 .= 9))
#false

function

fun MutableList.remove(mlst :: MutableList, v :: Any) :: Void

Modifies mlst to remove the first element equal to v (if any). Searching the list takes O(N) time.

> def mlst = MutableList[1, 2, 3, 2]
> mlst.remove(2)

function

fun MutableList.map(mlst :: MutableList,

f :: Function.of_arity(1))

:: Void

function

fun MutableList.for_each(mlst :: MutableList,

f :: Function.of_arity(1))

:: Void

Similar to List.map and List.for_each, but MutableList.map modifies the mutable list to contain resulting items instead of returning a new list.

> def mlst = MutableList[1, 2, 3]
> MutableList.map(mlst, (_ + 1))
> mlst
MutableList[2, 3, 4]
> mlst.for_each(println)
2
3
4

function

fun MutableList.sort(mlst :: MutableList,

is_less :: Function.of_arity(2) = (_ .< _))

:: Void

Modifies mlst to contain its elements sorted using is_less to compare elements, Sorting takes O(N log N) time.

> def mlst = MutableList[1, 3, 2]
> MutableList.sort(mlst)
> mlst
MutableList[1, 2, 3]
> MutableList.sort(mlst, (_ .> _))
> mlst
MutableList[3, 2, 1]

function

fun MutableList.to_list(mlst :: MutableList) :: List

function

fun MutableList.snapshot(mlst :: MutableList) :: List

Implements Listable by returning a list containing the elements of mlst.

function

fun MutableList.to_sequence(mlst :: MutableList) :: Sequence

Implements Sequenceable by returning a sequence of mlst’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	Ranges
6.38	Indexables
6.39	Listables
6.40	Sequences
6.41	Appendables
6.42	Comparables
6.43	Paths
6.44	Source Locations
6.45	Void
6.46	Equality
6.47	Dot
6.48	Multiple Values
6.49	Annotations
6.50	Enumerations
6.51	Input and Output
6.52	Eval
6.53	Syntax Objects
6.54	Syntax Classes
6.55	Simple Expression Macros
6.56	Unit Testing

mlst.length()	is	MutableList.length(mlst)
mlst.get(n)	is	MutableList.get(mlst, n)
mlst.set(n, v)	is	MutableList.set(mlst, n, v)
mlst.insert(n, v)	is	MutableList.insert(mlst, n, v)
mlst.add(v)	is	MutableList.add(mlst, v)
mlst.delete(n)	is	MutableList.delete(mlst, n)
mlst.reverse()	is	MutableList.reverse(mlst)
mlst.append(lst2)	is	MutableList.append(mlst, lst2)
mlst.take(n)	is	MutableList.take(mlst, n)
mlst.take_last(n)	is	MutableList.take_last(mlst, n)
mlst.drop(n)	is	MutableList.drop(mlst, n)
mlst.drop_last(n)	is	MutableList.drop_last(mlst, n)
mlst.sublist(n, m)	is	MutableList.sublist(mlst, n, m)
mlst.has_element(v, eqls, ...)	is	MutableList.has_element(mlst, v, eqls, ...)
mlst.find(pred)	is	MutableList.find(mlst, pred)
mlst.remove(v)	is	MutableList.remove(mlst, v)
mlst.map(func)	is	MutableList.map(mlst, func)
mlst.for_each(func)	is	MutableList.for_each(mlst, func)
mlst.sort(arg, ...)	is	MutableList.sort(mlst, arg, ...)
mlst.snapshot()	is	MutableList.snapshot(mlst)
mlst.to_list()	is	MutableList.to_list(mlst)
mlst.to_sequence()	is	MutableList.to_sequence(mlst)