# MutList

`enum MutList[a: Type, r: Eff]`

Source`case MutList(Region[r], Ref[Array[a, r], r], Ref[Int32, r])`

Represents a mutable list.

Invariant - The length is always higher than the total capacity of the array. - The capacity of the array is always 8 or more.

## Definitions

Appends `m`

to `v`

i.e. inserts all elements from `m`

into the end of `v`

.

`def clear!(v: MutList[a, r]): Unit \ r`

SourceRemoves all elements from the given mutable list `v`

.

`def compress!(v: MutList[a, r]): Unit \ r`

SourceCompresses the given mutable list `v`

if needed.

The mutable list will be shrunk to 1/2 of its size if the load factor is less than 1/4.

`def copy(rc1: Region[r1], v: MutList[a, r]): MutList[a, r1] \ r + r1`

SourceReturns a shallow copy of the given mutable list `v`

.
The capacity of the copy is equal to the length of the list.

`def count(f: a -> Bool \ ef, v: MutList[a, r]): Int32 \ ef + r`

SourceReturns the number of elements in the given mutable list `v`

that satisfies the given predicate `f`

.

Returns `0`

if the given mutable list `v`

is empty.

`def empty(rc: Region[r]): MutList[a, r] \ r`

SourceReturns an empty empty mutable list with a default capacity.

`def exists(f: a -> Bool \ ef, v: MutList[a, r]): Bool \ ef + r`

SourceReturns `true`

if the given predicate `f`

holds for at least one element of the given mutable list `v`

.

Returns `false`

if the given mutable list `v`

is empty.

`def find(f: a -> Bool, v: MutList[a, r]): Option[a] \ r`

SourceAlias for `findLeft`

.

`def findLeft(f: a -> Bool, v: MutList[a, r]): Option[a] \ r`

SourceOptionally returns the left-most element in the given mutable list `v`

that satisfies the given predicate `f`

.

Returns `None`

if no element satisfies the given predicate `f`

.
Returns `None`

if the given mutable list `v`

is empty.

`def findRight(f: a -> Bool, v: MutList[a, r]): Option[a] \ r`

SourceOptionally returns the right-most element in the given mutable list `v`

that satisfies the given predicate `f`

.

Returns `None`

if no element satisfies the given predicate `f`

.
Returns `None`

if the given mutable list `v`

is empty.

`def flatMap(rc1: Region[r1], f: a -> MutList[b, r1] \ ef, v: MutList[a, r]): MutList[b, r1] \ ef + r + r1`

SourceApply `f`

to every element in `v`

and concatenate the results.

The result is a new mutable list.

`def flatten(rc1: Region[r1], v: MutList[MutList[a, r], r]): MutList[a, r1] \ r + r1`

SourceConcatenates all the contained MutLists.

`def foldLeft(f: b -> (a -> b \ ef), s: b, v: MutList[a, r]): b \ ef + r`

SourceApplies `f`

to a start value `s`

and all elements in `a`

going from left to right.

That is, the result is of the form: `f(...f(f(s, a[0]), a[1])..., xn)`

.

Returns the result of mapping each element and combining the results.

`def foldRight(f: a -> (b -> b \ ef), s: b, v: MutList[a, r]): b \ ef + r`

SourceApplies `f`

to a start value `s`

and all elements in `a`

going from left to right.

That is, the result is of the form: `f(...f(f(s, a[0]), a[1])..., xn)`

.

The implementation is tail recursive.

`def foldRightWithCont(f: a -> ((Unit -> b \ ef + r) -> b \ ef + r), z: b, v: MutList[a, r]): b \ ef + r`

SourceApplies `f`

to a start value `z`

and all elements in `a`

going from left to right.

That is, the result is of the form: `f(x1, ...f(xn-1, f(xn, z))...)`

.
A `foldRightWithCont`

allows early termination by not calling the continuation.

`def forAll(f: a -> Bool \ ef, v: MutList[a, r]): Bool \ ef + r`

SourceReturns `true`

if the given predicate `f`

holds for all elements of the given mutable list `v`

.

Returns `true`

if the given mutable list `v`

is empty.

`def forEach(f: a -> Unit \ ef, v: MutList[a, r]): Unit \ ef + r`

SourceApplies `f`

to all the elements in `v`

.

`def forEachWithIndex(f: Int32 -> (a -> Unit \ ef), v: MutList[a, r]): Unit \ ef + r`

SourceApplies `f`

to all the elements in `v`

along with that element's index.

`def head(v: MutList[a, r]): Option[a] \ r`

SourceOptionally returns the first element of the given mutable list `v`

.

Returns `None`

if the given mutable list `v`

is empty.

Optionally returns the position of the first occurrence of `x`

in `v`

searching from left to right.

Optionally returns the position of the first occurrence of `x`

in `v`

searching from right to left.

`def insert!(x: a, i: Int32, v: MutList[a, r]): Unit \ r`

SourceInserts the given element `x`

at the given position `i`

in the given mutable list `v`

.

Shifts elements as necessary. Possibly expensive operation.

If the given index `i`

exceeds the length of the mutable list, the element is inserted at the last position.

`def isEmpty(v: MutList[a, r]): Bool \ r`

SourceReturns `true`

if the given mutable list `v`

is empty.

`def iterator(rc: Region[r1], l: MutList[a, r2]): Iterator[a, r1 + r2, r1] \ r1 + r2`

SourceReturns an iterator over `l`

.

Modifying `l`

while using an iterator has undefined behavior and is dangerous.

Returns the concatenation of the string representation
of each element in `v`

with `sep`

inserted between each element.

`def joinWith(f: a -> String \ ef, sep: String, v: MutList[a, r]): String \ ef + r`

SourceReturns the concatenation of the string representation
of each element in `v`

according to `f`

with `sep`

inserted between each element.

`def last(v: MutList[a, r]): Option[a] \ r`

SourceOptionally returns the last element of the given mutable list `v`

.

Returns `None`

if the given mutable list `v`

is empty.

`def length(v: MutList[a, r]): Int32 \ r`

SourceReturns the number of elements in the given mutable list `v`

.

`def map(rc1: Region[r1], f: a -> b \ ef, v: MutList[a, r]): MutList[b, r1] \ ef + r + r1`

SourceApply `f`

to every element in `v`

.

The result is an empty mutable list.

`def mapWithIndex(rc1: Region[r1], f: Int32 -> (a -> b \ ef), v: MutList[a, r]): MutList[b, r1] \ ef + r + r1`

SourceReturns the result of applying `f`

to every element in `v`

along with that element's index.

Optionally finds the largest element of `v`

according to the `Order`

on `a`

.

Returns `None`

if `v`

is empty.

`def maximumBy(cmp: a -> (a -> Comparison), v: MutList[a, r]): Option[a] \ r`

SourceOptionally finds the largest element of `v`

according to the given comparator `cmp`

.

Returns `None`

if `v`

is empty.

Returns `true`

if the given element `x`

is a member of the given mutable list `v`

.

Optionally finds the smallest element of `v`

according to the `Order`

on `a`

.

Returns `None`

if `v`

is empty.

`def minimumBy(cmp: a -> (a -> Comparison), v: MutList[a, r]): Option[a] \ r`

SourceOptionally finds the smallest element of `v`

according to the given comparator `cmp`

.

Returns `None`

if `v`

is empty.

`def nonEmpty(v: MutList[a, r]): Bool \ r`

SourceReturns `true`

if the given mutable list `v`

is non-empty.

`def nth(i: Int32, v: MutList[a, r]): Option[a] \ r`

SourceOptionally returns the element at position `i`

in the mutable list `v`

.

`def pop!(v: MutList[a, r]): Option[a] \ r`

SourceOptionally removes and returns the last element in the given mutable list `v`

.

`def push!(x: a, v: MutList[a, r]): Unit \ r`

SourceInserts the given element `x`

at the end of the given mutable list `v`

.

Appends `m`

to `v`

i.e. inserts all elements from `m`

into the end of `v`

.

`def range(rc: Region[r], b: Int32, e: Int32): MutList[Int32, r] \ r`

SourceReturns a mutable list of all integers between `b`

(inclusive) and `e`

(exclusive).

Returns an empty mutable list if `b >= e`

.

`def reduceLeft(f: a -> (a -> a \ ef), v: MutList[a, r]): Option[a] \ ef + r`

SourceApplies `f`

to all elements in `v`

going from left to right until a single value `v`

is obtained. Returns `Some(v)`

.

Returns `None`

if `v`

is empty.

`def reduceRight(f: a -> (a -> a \ ef), v: MutList[a, r]): Option[a] \ ef + r`

SourceApplies `f`

to all elements in `v`

going from right to left until a single value `v`

is obtained. Returns `Some(v)`

.

Returns `None`

if `v`

is empty.

`def remove!(i: Int32, v: MutList[a, r]): Unit \ r`

SourceRemoves the element at the given position `i`

in the given mutable list `v`

.

Shifts elements as necessary. Possibly expensive operation.

If the given index `i`

exceeds the length of the mutable list, no element is removed.

Replaces all occurrences of the `src`

with `dst`

in the given mutable list `v`

.

`def reserve!(n: Int32, v: MutList[a, r]): Unit \ r`

SourceIncreases the capacity of the given mutable list `v`

by at least `n`

.

That is, after the call, the mutable list is guaranteed to have space for at least `n`

additional elements.

The content of the mutable list is unchanged.

`def retain!(f: a -> Bool, v: MutList[a, r]): Unit \ r`

SourceRemoves all elements from the given mutable list `v`

that do not satisfy the given predicate `f`

.

`def reverse!(v: MutList[a, r]): Unit \ r`

SourceReverses the order of the elements in the given mutable list `v`

.

Returns `true`

if the mutable lists `v1`

and `v2`

have the same elements in the same order, i.e. are structurally equal.

`def scan(rc1: Region[r1], f: b -> (a -> b \ ef), s: b, v: MutList[a, r2]): MutList[b, r1] \ ef + r2 + r1`

SourceAlias for `scanLeft`

.

`def scanLeft(rc1: Region[r1], f: b -> (a -> b \ ef), s: b, v: MutList[a, r2]): MutList[b, r1] \ ef + r2 + r1`

SourceAccumulates the result of applying `f`

to `v`

going left to right.

`def scanRight(rc1: Region[r1], f: a -> (b -> b \ ef), s: b, v: MutList[a, r2]): MutList[b, r1] \ ef + r2 + r1`

SourceAccumulates the result of applying `f`

to `v`

going right to left.

`def shrink!(v: MutList[a, r]): Unit \ r`

SourceShrinks the given mutable list `v`

to its actual size.

`def shuffle(rc1: Region[r1], rnd: Random, v: MutList[a, r1]): MutList[a, r1] \ r1 + IO`

SourceShuffles `v`

using the Fisherâ€“Yates shuffle.

`def size(v: MutList[a, r]): Int32 \ r`

SourceReturns the number of elements in the given mutable list `v`

.

Returns a sorted copy of MutList `v`

, where the elements are ordered from low to high according to
their `Order`

instance.

The sort is not stable, i.e., equal elements may appear in a different order than in the input `v`

.

The sort implementation is a Quicksort.

Sort MutList `v`

so that elements are ordered from low to high according to their `Order`

instance.
The MutList is mutated in-place.

The sort is not stable, i.e., equal elements may appear in a different order than in the input `v`

.

The sort implementation is a Quicksort.

`def sortBy(rc1: Region[r1], f: a -> b, v: MutList[a, r]): MutList[a, r1] \ r + r1 with Order[b]`

SourceReturns a sorted copy of MutList `v`

, where the elements are ordered from low to high according to
the `Order`

instance for the values obtained by applying `f`

to each element.

The sort is not stable, i.e., equal elements may appear in a different order than in the input `v`

.

The sort implementation is a Quicksort.

Sort MutList `v`

so that elements are ordered from low to high according to the `Order`

instance for
the values obtained by applying `f`

to each element. The MutList is mutated in-place.

The sort is not stable, i.e., equal elements may appear in a different order than in the input `v`

.

The sort implementation is a Quicksort.

`def sortWith(rc1: Region[r1], cmp: a -> (a -> Comparison), v: MutList[a, r]): MutList[a, r1] \ r + r1`

SourceReturns a sorted copy of MutList `v`

, where the elements are ordered from low to high according to
the comparison function `cmp`

.

The sort is not stable, i.e., equal elements may appear in a different order than in the input `v`

.

The sort implementation is a Quicksort.

`def sortWith!(cmp: a -> (a -> Comparison), v: MutList[a, r]): Unit \ r`

SourceSort MutList `v`

so that elements are ordered from low to high according to the comparison function `cmp`

.
The MutList is mutated in-place.

The sort is not stable, i.e., equal elements may appear in a different order than in the input `v`

.

The sort implementation is a Quicksort.

`def sum(v: MutList[Int32, r]): Int32 \ r`

SourceReturns the sum of all elements in the MutList `v`

.

`def sumWith(f: a -> Int32 \ ef, v: MutList[a, r]): Int32 \ ef + r`

SourceReturns the sum of all elements in the MutList `v`

according to the function `f`

.

`def toArray(rc1: Region[r1], v: MutList[a, r2]): Array[a, r1] \ r2 + r1`

SourceReturns `v`

as an array.

`def toChain(xs: MutList[a, r]): Chain[a] \ r`

SourceReturns the mutable list `xs`

as a chain.

`def toList(v: MutList[a, r]): List[a] \ r`

SourceReturns `v`

as an immutable list.

`def toMutDeque(rc1: Region[r1], v: MutList[a, r2]): MutDeque[a, r1] \ r2 + r1`

SourceReturns `v`

as a MutDeque.

Returns a string representation of the given MutList `l`

.

`def toVector(xs: MutList[a, r]): Vector[a] \ r`

SourceReturns `xs`

as a vector.

`def transform!(f: a -> a, v: MutList[a, r]): Unit \ r`

SourceApply `f`

to every element in `v`

.

`def transformWithIndex!(f: Int32 -> (a -> a), v: MutList[a, r]): Unit \ r`

SourceApply `f`

to every element in `v`

along with that element's index.

`def truncate!(l: Int32, v: MutList[a, r]): Unit \ r`

SourceTruncates the given mutable list `v`

to the given length `l`

.

That is, after the operation, the mutable list has length at most `l`

.

If the given length `l`

is negative, all elements are removed.