List

type List<T> = Types.List<T>

List<T> provides a mutable list of elements of type T. Based on the paper "Resizable Arrays in Optimal Time and Space" by Brodnik, Carlsson, Demaine, Munro and Sedgewick (1999). Since this is internally a two-dimensional array the access times for put and get operations will naturally be 2x slower than Buffer and Array. However, Array is not resizable and Buffer has O(size) memory waste.

public func empty<T>() : List<T>

Creates a new empty List for elements of type T.

Example:

let list = List.new<Nat>(); // Creates a new List

public func singleton<T>(element : T) : List<T>

Returns a new list with capacity and size 1, containing element.

Example:

import Nat "mo:base/Nat";

let list = List.make<Nat>(1);
List.toText<Nat>(list, Nat.toText); // => "[1]"

Runtime: O(1)

Space: O(1)

public func repeat<T>(initValue : T, size : Nat) : List<T>

Create a List with size copies of the initial value.

let list = List.repeat<Nat>(2, 4); // [2, 2, 2, 2]

Runtime: O(size)

public func toPure<T>(list : List<T>) : PureList.List<T>

Converts a mutable List to a purely functional PureList.

Example:

let list = List.fromArray<Nat>([1, 2, 3]);
let pureList = List.toPure<Nat>(list); // converts to immutable PureList

Runtime: O(size)

Space: O(size)

public func fromPure<T>(pure : PureList.List<T>) : List<T>

Converts a purely functional List to a mutable List.

Example:

import PureList "mo:base/pure/List";

let pureList = PureList.fromArray<Nat>([1, 2, 3]);
let list = List.fromPure<Nat>(pureList); // converts to mutable List

Runtime: O(size)

Space: O(size)

public func addRepeat<T>(
  list : List<T>,
  initValue : T,
  count : Nat
)

Add to list count copies of the initial value.

let list = List.repeat<Nat>(2, 4); // [2, 2, 2, 2]
List.addRepeat(list, 2, 1); // [2, 2, 2, 2, 1, 1]

Runtime: O(count)

public func clear<T>(list : List<T>)

Resets the list to size 0, de-referencing all elements.

Example:

List.add(list, 10);
List.add(list, 11);
List.add(list, 12);
List.clear(list); // list is now empty
List.toArray(list) // => []

Runtime: O(1)

public func clone<T>(list : List<T>) : List<T>

Returns a copy of a List, with the same size.

Example:

list.add(1);

let clone = List.clone(list);
List.toArray(clone); // => [1]

Runtime: O(size)

public func map<T, R>(list : List<T>, f : T -> R) : List<R>

Creates and returns a new list, populated with the results of calling a provided function on every element in the provided list

Example:

list.add(1);

let t = List.map<Nat, Text>(list, Nat.toText);
List.toArray(t); // => ["1"]

Runtime: O(size)

public func filter<T>(list : List<T>, predicate : T -> Bool) : List<T>

Returns a new list containing only the elements from list for which the predicate returns true.

Example:

let list = List.fromArray<Nat>([1, 2, 3, 4]);
let evenNumbers = List.filter<Nat>(list, func x = x % 2 == 0);
List.toArray(evenNumbers); // => [2, 4]

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that predicate runs in O(1) time and space.

public func filterMap<T, R>(list : List<T>, f : T -> ?R) : List<R>

Returns a new list containing all elements from list for which the function returns ?element. Discards all elements for which the function returns null.

Example:

let list = List.fromArray<Nat>([1, 2, 3, 4]);
let doubled = List.filterMap<Nat, Nat>(list, func x = if (x % 2 == 0) ?x * 2 else null);
List.toArray(doubled); // => [4, 8]

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that f runs in O(1) time and space.

public func size<T>(list : List<T>) : Nat

Returns the current number of elements in the list.

Example:

List.size(list) // => 0

Runtime: O(1) (with some internal calculations)

public func add<T>(list : List<T>, element : T)

Adds a single element to the end of a List, allocating a new internal data block if needed, and resizing the internal index block if needed.

Example:

List.add(list, 0); // add 0 to list
List.add(list, 1);
List.add(list, 2);
List.add(list, 3);
List.toArray(list) // => [0, 1, 2, 3]

Amortized Runtime: O(1), Worst Case Runtime: O(sqrt(n))

public func removeLast<T>(list : List<T>) : ?T

Removes and returns the last item in the list or null if the list is empty.

Example:

List.add(list, 10);
List.add(list, 11);
List.removeLast(list); // => ?11

Amortized Runtime: O(1), Worst Case Runtime: O(sqrt(n))

Amortized Space: O(1), Worst Case Space: O(sqrt(n))

public func get<T>(list : List<T>, index : Nat) : T

Returns the element at index index. Indexing is zero-based. Traps if index >= size, error message may not be descriptive.

Example:

List.add(list, 10);
List.add(list, 11);
List.get(list, 0); // => 10

Runtime: O(1)

public func getOpt<T>(list : List<T>, index : Nat) : ?T

Returns the element at index index as an option. Returns null when index >= size. Indexing is zero-based.

Example:

List.add(list, 10);
List.add(list, 11);
let x = List.getOpt(list, 0); // => ?10
let y = List.getOpt(list, 2); // => null

Runtime: O(1)

public func put<T>(
  list : List<T>,
  index : Nat,
  value : T
)

Overwrites the current element at index with element. Traps if index >= size. Indexing is zero-based.

Example:

List.add(list, 10);
List.put(list, 0, 20); // overwrites 10 at index 0 with 20
List.toArray(list) // => [20]

Runtime: O(1)

public func sort<T>(list : List<T>, compare : (T, T) -> Order.Order)

Sorts the elements in the list according to compare. Sort is deterministic, stable, and in-place.

Example:

List.add(list, 3);
List.add(list, 1);
List.add(list, 2);
List.sort(list, Nat.compare);
List.toArray(list) // => [1, 2, 3]

Runtime: O(size * log(size))

Space: O(size) *Runtime and space assumes that compare runs in O(1) time and space.

public func indexOf<T>(
  list : List<T>,
  equal : (T, T) -> Bool,
  element : T
) : ?Nat

Finds the first index of element in list using equality of elements defined by equal. Returns null if element is not found.

Example:

let list = List.new<Nat>();
List.add(list, 1);
List.add(list, 2);
List.add(list, 3);
List.add(list, 4);

List.indexOf<Nat>(3, list, Nat.equal); // => ?2

Runtime: O(size)

*Runtime and space assumes that equal runs in O(1) time and space.

public func lastIndexOf<T>(
  list : List<T>,
  equal : (T, T) -> Bool,
  element : T
) : ?Nat

Finds the last index of element in list using equality of elements defined by equal. Returns null if element is not found.

Example:

let list = List.new<Nat>();
List.add(list, 1);
List.add(list, 2);
List.add(list, 3);
List.add(list, 4);
List.add(list, 2);
List.add(list, 2);

List.lastIndexOf<Nat>(2, list, Nat.equal); // => ?5

Runtime: O(size)

*Runtime and space assumes that equal runs in O(1) time and space.

public func firstIndexWhere<T>(list : List<T>, predicate : T -> Bool) : ?Nat

Finds the index of the first element in list for which predicate is true. Returns null if no such element is found.

Example:

let list = List.new<Nat>();
List.add(list, 1);
List.add(list, 2);
List.add(list, 3);
List.add(list, 4);

List.firstIndexWhere<Nat>(list, func(i) { i % 2 == 0 }); // => ?1

Runtime: O(size)

*Runtime and space assumes that predicate runs in O(1) time and space.

public func lastIndexWhere<T>(list : List<T>, predicate : T -> Bool) : ?Nat

Finds the index of the last element in list for which predicate is true. Returns null if no such element is found.

Example:

let list = List.new<Nat>();
List.add(list, 1);
List.add(list, 2);
List.add(list, 3);
List.add(list, 4);

List.lastIndexWhere<Nat>(list, func(i) { i % 2 == 0 }); // => ?3

Runtime: O(size)

*Runtime and space assumes that predicate runs in O(1) time and space.

public func all<T>(list : List<T>, predicate : T -> Bool) : Bool

Returns true iff every element in list satisfies predicate. In particular, if list is empty the function returns true.

Example:

List.add(list, 2);
List.add(list, 3);
List.add(list, 4);

List.all<Nat>(list, func x { x > 1 }); // => true

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that predicate runs in O(1) time and space.

public func any<T>(list : List<T>, predicate : T -> Bool) : Bool

Returns true iff some element in list satisfies predicate. In particular, if list is empty the function returns false.

Example:

List.add(list, 2);
List.add(list, 3);
List.add(list, 4);

List.any<Nat>(list, func x { x > 3 }); // => true

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that predicate runs in O(1) time and space.

public func values<T>(list : List<T>) : Iter.Iter<T>

Returns an Iterator (Iter) over the elements of a List. Iterator provides a single method next(), which returns elements in order, or null when out of elements to iterate over.

List.add(list, 10);
List.add(list, 11);
List.add(list, 12);

var sum = 0;
for (element in List.values(list)) {
  sum += element;
};
sum // => 33

Note: This does not create a snapshot. If the returned iterator is not consumed at once, and instead the consumption of the iterator is interleaved with other operations on the List, then this may lead to unexpected results.

Runtime: O(1)

public func entries<T>(list : List<T>) : Iter.Iter<(T, Nat)>

Returns an Iterator (Iter) over the items, i.e. pairs of value and index of a List. Iterator provides a single method next(), which returns elements in order, or null when out of elements to iterate over.

List.add(list, 10);
List.add(list, 11);
List.add(list, 12);
Iter.toArray(List.entries(list)); // [(10, 0), (11, 1), (12, 2)]

Note: This does not create a snapshot. If the returned iterator is not consumed at once, and instead the consumption of the iterator is interleaved with other operations on the List, then this may lead to unexpected results.

Runtime: O(1)

Warning: Allocates memory on the heap to store ?(T, Nat).

public func valuesRev<T>(list : List<T>) : Iter.Iter<T>

Returns an Iterator (Iter) over the elements of a List in reverse order. Iterator provides a single method next(), which returns elements in reverse order, or null when out of elements to iterate over.

List.add(list, 10);
List.add(list, 11);
List.add(list, 12);

var sum = 0;
for (element in List.valuesRev(list)) {
  sum += element;
};
sum // => 33

Note: This does not create a snapshot. If the returned iterator is not consumed at once, and instead the consumption of the iterator is interleaved with other operations on the List, then this may lead to unexpected results.

Runtime: O(1)

public func entriesRev<T>(list : List<T>) : Iter.Iter<(T, Nat)>

Returns an Iterator (Iter) over the items in reverse order, i.e. pairs of value and index of a List. Iterator provides a single method next(), which returns elements in reverse order, or null when out of elements to iterate over.

List.add(list, 10);
List.add(list, 11);
List.add(list, 12);
Iter.toArray(List.entries(list)); // [(12, 0), (11, 1), (10, 2)]

Note: This does not create a snapshot. If the returned iterator is not consumed at once, and instead the consumption of the iterator is interleaved with other operations on the List, then this may lead to unexpected results.

Runtime: O(1)

Warning: Allocates memory on the heap to store ?(T, Nat).

public func keys<T>(list : List<T>) : Iter.Iter<Nat>

Returns an Iterator (Iter) over the keys (indices) of a List. Iterator provides a single method next(), which returns elements in order, or null when out of elements to iterate over.

List.add(list, 10);
List.add(list, 11);
List.add(list, 12);
Iter.toArray(List.values(list)); // [0, 1, 2]

Note: This does not create a snapshot. If the returned iterator is not consumed at once, and instead the consumption of the iterator is interleaved with other operations on the List, then this may lead to unexpected results.

Runtime: O(1)

public func fromIter<T>(iter : Iter.Iter<T>) : List<T>

Creates a List containing elements from iter.

Example:

import Nat "mo:base/Nat";

let array = [1, 1, 1];
let iter = array.vals();

let list = List.fromIter<Nat>(iter); // => [1, 1, 1]

Runtime: O(size)

public func addAll<T>(list : List<T>, iter : Iter.Iter<T>)

Adds elements to a List from iter.

Example:

import Nat "mo:base/Nat";

let array = [1, 1, 1];
let iter = array.vals();
let list = List.repeat<Nat>(2, 1);

let list = List.addAll<Nat>(list, iter); // => [2, 1, 1, 1]

Runtime: O(size), where n is the size of iter.

public func toArray<T>(list : List<T>) : [T]

Creates an immutable array containing elements from a List.

Example:

List.add(list, 1);
List.add(list, 2);
List.add(list, 3);

List.toArray<Nat>(list); // => [1, 2, 3]

Runtime: O(size)

public func fromArray<T>(array : [T]) : List<T>

Creates a List containing elements from an Array.

Example:

import Nat "mo:base/Nat";

let array = [2, 3];

let list = List.fromArray<Nat>(array); // => [2, 3]

Runtime: O(size)

public func toVarArray<T>(list : List<T>) : [var T]

Creates a mutable Array containing elements from a List.

Example:

List.add(list, 1);
List.add(list, 2);
List.add(list, 3);

List.toVarArray<Nat>(list); // => [1, 2, 3]

Runtime: O(size)

public func fromVarArray<T>(array : [var T]) : List<T>

Creates a List containing elements from a mutable Array.

Example:

import Nat "mo:base/Nat";

let array = [var 2, 3];

let list = List.fromVarArray<Nat>(array); // => [2, 3]

Runtime: O(size)

public func first<T>(list : List<T>) : ?T

Returns the first element of list is empty.

Example:

let list = List.repeat<Nat>(1, 10);

List.first(list); // => ?1

Runtime: O(1)

Space: O(1)

public func last<T>(list : List<T>) : ?T

Returns the last element of list. Traps if list is empty.

Example:

let list = List.fromArray<Nat>([1, 2, 3]);

List.last(list); // => 3

Runtime: O(1)

Space: O(1)

public func forEach<T>(list : List<T>, f : T -> ())

Applies f to each element in list.

Example:

import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

let list = List.fromArray<Nat>([1, 2, 3]);

List.forEach<Nat>(list, func(x) {
  Debug.print(Nat.toText(x)); // prints each element in list
});

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that f runs in O(1) time and space.

public func forEachEntry<T>(list : List<T>, f : (Nat, T) -> ())

Applies f to each item (i, x) in list where i is the key and x is the value.

Example:

import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

let list = List.fromArray<Nat>([1, 2, 3]);

List.forEachEntry<Nat>(list, func (i,x) {
  // prints each item (i,x) in list
  Debug.print(Nat.toText(i) # Nat.toText(x));
});

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that f runs in O(1) time and space.

public func forEachEntryRev<T>(list : List<T>, f : (Nat, T) -> ())

Like forEachEntryRev but iterates through the list in reverse order, from end to beginning.

Example:

import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

let list = List.fromArray<Nat>([1, 2, 3]);

List.forEachEntryRev<Nat>(list, func (i,x) {
  // prints each item (i,x) in list
  Debug.print(Nat.toText(i) # Nat.toText(x));
});

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that f runs in O(1) time and space.

public func forEachRev<T>(list : List<T>, f : T -> ())

Applies f to each element in list in reverse order.

Example:

import Nat "mo:base/Nat";
import Debug "mo:base/Debug";

let list = List.fromArray<Nat>([1, 2, 3]);

List.forEachRev<Nat>(list, func (x) {
  Debug.print(Nat.toText(x)); // prints each element in list in reverse order
});

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that f runs in O(1) time and space.

public func contains<T>(
  list : List<T>,
  equal : (T, T) -> Bool,
  element : T
) : Bool

Returns true if List contains element with respect to equality defined by equal.

Example:

import Nat "mo:base/Nat";

List.add(list, 2);
List.add(list, 0);
List.add(list, 3);

List.contains<Nat>(list, Nat.equal, 2); // => true

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that equal runs in O(1) time and space.

public func max<T>(list : List<T>, compare : (T, T) -> Order.Order) : ?T

Finds the greatest element in list defined by compare. Returns null if list is empty.

Example:

import Nat "mo:base/Nat";

List.add(list, 1);
List.add(list, 2);

List.max<Nat>(list, Nat.compare); // => ?2

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that compare runs in O(1) time and space.

public func min<T>(list : List<T>, compare : (T, T) -> Order.Order) : ?T

Finds the least element in list defined by compare. Returns null if list is empty.

Example:

import Nat "mo:base/Nat";

List.add(list, 1);
List.add(list, 2);

List.min<Nat>(list, Nat.compare); // => ?1

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that compare runs in O(1) time and space.

public func equal<T>(
  list1 : List<T>,
  list2 : List<T>,
  equal : (T, T) -> Bool
) : Bool

Defines equality for two lists, using equal to recursively compare elements in the lists. Returns true iff the two lists are of the same size, and equal evaluates to true for every pair of elements in the two lists of the same index.

Example:

import Nat "mo:base/Nat";

let list1 = List.fromArray<Nat>([1,2]);
let list2 = List.new<Nat>();
list2.add(1);
list2.add(2);

List.equal<Nat>(list1, list2, Nat.equal); // => true

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that equal runs in O(1) time and space.

public func compare<T>(
  list1 : List<T>,
  list2 : List<T>,
  compare : (T, T) -> Order.Order
) : Order.Order

Defines comparison for two lists, using compare to recursively compare elements in the lists. Comparison is defined lexicographically.

Example:

import Nat "mo:base/Nat";

let list1 = List.fromArray<Nat>([1,2]);
let list2 = List.new<Nat>();
list2.add(1);
list2.add(2);

List.compare<Nat>(list1, list2, Nat.compare); // => #less

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that compare runs in O(1) time and space.

public func toText<T>(list : List<T>, f : T -> Text) : Text

Creates a textual representation of list, using toText to recursively convert the elements into Text.

Example:

import Nat "mo:base/Nat";

let list = List.fromArray<Nat>([1,2,3,4]);

List.toText<Nat>(list, Nat.toText); // => "[1, 2, 3, 4]"

Runtime: O(size)

Space: O(size)

*Runtime and space assumes that toText runs in O(1) time and space.

public func foldLeft<A, T>(
  list : List<T>,
  base : A,
  combine : (A, T) -> A
) : A

Collapses the elements in list into a single value by starting with base and progessively combining elements into base with combine. Iteration runs left to right.

Example:

import Nat "mo:base/Nat";

let list = List.fromArray<Nat>([1,2,3]);

List.foldLeft<Text, Nat>(list, "", func (acc, x) { acc # Nat.toText(x)}); // => "123"

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that combine runs in O(1)` time and space.

public func foldRight<T, A>(
  list : List<T>,
  base : A,
  combine : (T, A) -> A
) : A

Collapses the elements in list into a single value by starting with base and progessively combining elements into base with combine. Iteration runs right to left.

Example:

import Nat "mo:base/Nat";

let list = List.fromArray<Nat>([1,2,3]);

List.foldRight<Nat, Text>(list, "", func (x, acc) { Nat.toText(x) # acc }); // => "123"

Runtime: O(size)

Space: O(1)

*Runtime and space assumes that combine runs in O(1)` time and space.

public func reverseInPlace<T>(list : List<T>)

Reverses the order of elements in list by overwriting in place.

Example:

import Nat "mo:base/Nat";

let list = List.fromArray<Nat>([1,2,3]);

List.reverseInPlace<Nat>(list);
List.toText<Nat>(list, Nat.toText); // => "[3, 2, 1]"

Runtime: O(size)

Space: O(1)

public func reverse<T>(list : List<T>) : List<T>

Returns a new List with the elements from list in reverse order.

Example:

import Nat "mo:base/Nat";

let list = List.fromArray<Nat>([1,2,3]);

let rlist = List.reverse<Nat>(list);
List.toText<Nat>(rlist, Nat.toText); // => "[3, 2, 1]"

Runtime: O(size)

Space: O(1)

public func isEmpty<T>(list : List<T>) : Bool

Returns true if and only if the list is empty.

Example:

let list = List.fromArray<Nat>([2,0,3]);
List.isEmpty<Nat>(list); // => false

Runtime: O(1)

Space: O(1)