Provides extended utility functions on Arrays.
Note the difference between mutable and non-mutable arrays below.
WARNING: If you are looking for a list that can grow and shrink in size, it is recommended you use either the Buffer class or the List class for those purposes. Arrays must be created with a fixed size.
Import from the base library to use this module.
import Array "mo:base/Array";func init<X>(size : Nat, initValue : X) : [var X]Create a mutable array with size copies of the initial value.
let array = Array.init<Nat>(4, 2);Runtime: O(size) Space: O(size)
func tabulate<X>(size : Nat, generator : Nat -> X) : [X]Create an immutable array of size size. Each element at index i
is created by applying generator to i.
let array : [Nat] = Array.tabulate<Nat>(4, func i = i * 2);Runtime: O(size) Space: O(size)
*Runtime and space assumes that generator runs in O(1) time and space.
func tabulateVar<X>(size : Nat, generator : Nat -> X) : [var X]Create a mutable array of size size. Each element at index i
is created by applying generator to i.
let array : [var Nat] = Array.tabulateVar<Nat>(4, func i = i * 2);
array[2] := 0;
arrayRuntime: O(size) Space: O(size)
*Runtime and space assumes that generator runs in O(1) time and space.
func freeze<X>(varArray : [var X]) : [X]Transforms a mutable array into an immutable array.
let varArray = [var 0, 1, 2];
varArray[2] := 3;
let array = Array.freeze<Nat>(varArray);Runtime: O(size)
Space: O(1)
func thaw<A>(array : [A]) : [var A]Transforms an immutable array into a mutable array.
let array = [0, 1, 2];
let varArray = Array.thaw<Nat>(array);
varArray[2] := 3;
varArrayRuntime: O(size)
Space: O(1)
func equal<X>(array1 : [X], array2 : [X], equal : (X, X) -> Bool) : BoolTests if two arrays contain equal values (i.e. they represent the same
list of elements). Uses equal to compare elements in the arrays.
// Use the equal function from the Nat module to compare Nats
import {equal} "mo:base/Nat";
let array1 = [0, 1, 2, 3];
let array2 = [0, 1, 2, 3];
Array.equal(array1, array2, equal)Runtime: O(size1 + size2)
Space: O(1)
*Runtime and space assumes that equal runs in O(1) time and space.
func find<X>(array : [X], predicate : X -> Bool) : ?XReturns the first value in array for which predicate returns true.
If no element satisfies the predicate, returns null.
let array = [1, 9, 4, 8];
Array.find<Nat>(array, func x = x > 8)Runtime: O(size)
Space: O(1)
*Runtime and space assumes that predicate runs in O(1) time and space.
func append<X>(array1 : [X], array2 : [X]) : [X]Create a new array by appending the values of array1 and array2.
Note that Array.append copies its arguments and has linear complexity;
when used in a loop, consider using a Buffer, and Buffer.append, instead.
let array1 = [1, 2, 3];
let array2 = [4, 5, 6];
Array.append<Nat>(array1, array2)Runtime: O(size1 + size2)
Space: O(size1 + size2)
func sort<X>(array : [X], compare : (X, X) -> Order.Order) : [X]Sorts the elements in the array according to compare.
Sort is deterministic and stable.
import Nat "mo:base/Nat";
let array = [4, 2, 6];
Array.sort(array, Nat.compare)Runtime: O(size * log(size))
Space: O(size)
*Runtime and space assumes that compare runs in O(1) time and space.
func sortInPlace<X>(array : [var X], compare : (X, X) -> Order.Order)Sorts the elements in the array, in place, according to compare.
Sort is deterministic, stable, and in-place.
import {compare} "mo:base/Nat";
let array = [var 4, 2, 6];
Array.sortInPlace(array, compare);
arrayRuntime: O(size * log(size))
Space: O(size)
*Runtime and space assumes that compare runs in O(1) time and space.
func reverse<X>(array : [X]) : [X]Creates a new array by reversing the order of elements in array.
let array = [10, 11, 12];
Array.reverse(array)Runtime: O(size)
Space: O(1)
func map<X, Y>(array : [X], f : X -> Y) : [Y]Creates a new array by applying f to each element in array. f "maps"
each element it is applied to of type X to an element of type Y.
Retains original ordering of elements.
let array = [0, 1, 2, 3];
Array.map<Nat, Nat>(array, func x = x * 3)Runtime: O(size)
Space: O(size)
*Runtime and space assumes that f runs in O(1) time and space.
func filter<X>(array : [X], predicate : X -> Bool) : [X]Creates a new array by applying predicate to every element
in array, retaining the elements for which predicate returns true.
let array = [4, 2, 6, 1, 5];
let evenElements = Array.filter<Nat>(array, func x = x % 2 == 0);Runtime: O(size)
Space: O(size)
*Runtime and space assumes that predicate runs in O(1) time and space.
func mapEntries<X, Y>(array : [X], f : (X, Nat) -> Y) : [Y]Creates a new array by applying f to each element in array and its index.
Retains original ordering of elements.
let array = [10, 10, 10, 10];
Array.mapEntries<Nat, Nat>(array, func (x, i) = i * x)Runtime: O(size)
Space: O(size)
*Runtime and space assumes that f runs in O(1) time and space.
func mapFilter<X, Y>(array : [X], f : X -> ?Y) : [Y]Creates a new array by applying f to each element in array,
and keeping all non-null elements. The ordering is retained.
import {toText} "mo:base/Nat";
let array = [4, 2, 0, 1];
let newArray =
Array.mapFilter<Nat, Text>( // mapping from Nat to Text values
array,
func x = if (x == 0) { null } else { ?toText(100 / x) } // can't divide by 0, so return null
);Runtime: O(size)
Space: O(size)
*Runtime and space assumes that f runs in O(1) time and space.
func mapResult<X, Y, E>(array : [X], f : X -> Result.Result<Y, E>) : Result.Result<[Y], E>Creates a new array by applying f to each element in array.
If any invocation of f produces an #err, returns an #err. Otherwise
returns an #ok containing the new array.
let array = [4, 3, 2, 1, 0];
// divide 100 by every element in the array
Array.mapResult<Nat, Nat, Text>(array, func x {
if (x > 0) {
#ok(100 / x)
} else {
#err "Cannot divide by zero"
}
})Runtime: O(size)
Space: O(size)
*Runtime and space assumes that f runs in O(1) time and space.
func chain<X, Y>(array : [X], k : X -> [Y]) : [Y]Creates a new array by applying k to each element in array,
and concatenating the resulting arrays in order. This operation
is similar to what in other functional languages is known as monadic bind.
import Nat "mo:base/Nat";
let array = [1, 2, 3, 4];
Array.chain<Nat, Int>(array, func x = [x, -x])
Runtime: O(size)
Space: O(size)
*Runtime and space assumes that k runs in O(1) time and space.
func foldLeft<X, A>(array : [X], base : A, combine : (A, X) -> A) : ACollapses the elements in array into a single value by starting with base
and progessively combining elements into base with combine. Iteration runs
left to right.
import {add} "mo:base/Nat";
let array = [4, 2, 0, 1];
let sum =
Array.foldLeft<Nat, Nat>(
array,
0, // start the sum at 0
func(sumSoFar, x) = sumSoFar + x // this entire function can be replaced with `add`!
);Runtime: O(size)
Space: O(1)
*Runtime and space assumes that combine runs in O(1) time and space.
func foldRight<X, A>(array : [X], base : A, combine : (X, A) -> A) : ACollapses the elements in array into a single value by starting with base
and progessively combining elements into base with combine. Iteration runs
right to left.
import {toText} "mo:base/Nat";
let array = [1, 9, 4, 8];
let bookTitle = Array.foldRight<Nat, Text>(array, "", func(x, acc) = toText(x) # acc);Runtime: O(size)
Space: O(1)
*Runtime and space assumes that combine runs in O(1) time and space.
func flatten<X>(arrays : [[X]]) : [X]Flattens the array of arrays into a single array. Retains the original ordering of the elements.
let arrays = [[0, 1, 2], [2, 3], [], [4]];
Array.flatten<Nat>(arrays)Runtime: O(number of elements in array)
Space: O(number of elements in array)
func make<X>(element : X) : [X]Create an array containing a single value.
Array.make(2)Runtime: O(1)
Space: O(1)
func vals<X>(array : [X]) : I.Iter<X>Returns an Iterator (Iter) over the elements of array.
Iterator provides a single method next(), which returns
elements in order, or null when out of elements to iterate over.
NOTE: You can also use array.vals() instead of this function. See example
below.
let array = [10, 11, 12];
var sum = 0;
for (element in array.vals()) {
sum += element;
};
sumRuntime: O(1)
Space: O(1)
func keys<X>(array : [X]) : I.Iter<Nat>Returns an Iterator (Iter) over the indices of array.
Iterator provides a single method next(), which returns
indices in order, or null when out of index to iterate over.
NOTE: You can also use array.keys() instead of this function. See example
below.
let array = [10, 11, 12];
var sum = 0;
for (element in array.keys()) {
sum += element;
};
sumRuntime: O(1)
Space: O(1)
func size<X>(array : [X]) : NatReturns the size of array.
NOTE: You can also use array.size() instead of this function. See example
below.
let array = [10, 11, 12];
let size = Array.size(array);Runtime: O(1)
Space: O(1)
func subArray<X>(array : [X], start : Nat, length : Nat) : [X]Returns a new subarray from the given array provided the start index and length of elements in the subarray
Limitations: Traps if the start index + length is greater than the size of the array
let array = [1,2,3,4,5];
let subArray = Array.subArray<Nat>(array, 2, 3);Runtime: O(length); Space: O(length);
func indexOf<X>(element : X, array : [X], equal : (X, X) -> Bool) : ?NatReturns the index of the first element in the array.
import Char "mo:base/Char";
let array = ['c', 'o', 'f', 'f', 'e', 'e'];
assert Array.indexOf<Char>('c', array, Char.equal) == ?0;
assert Array.indexOf<Char>('f', array, Char.equal) == ?2;
assert Array.indexOf<Char>('g', array, Char.equal) == null;Runtime: O(array.size()); Space: O(1);
func nextIndexOf<X>(element : X, array : [X], fromInclusive : Nat, equal : (X, X) -> Bool) : ?NatReturns the index of the next occurence of element in the array starting from the from index (inclusive).
import Char "mo:base/Char";
let array = ['c', 'o', 'f', 'f', 'e', 'e'];
assert Array.nextIndexOf<Char>('c', array, 0, Char.equal) == ?0;
assert Array.nextIndexOf<Char>('f', array, 0, Char.equal) == ?2;
assert Array.nextIndexOf<Char>('f', array, 2, Char.equal) == ?2;
assert Array.nextIndexOf<Char>('f', array, 3, Char.equal) == ?3;
assert Array.nextIndexOf<Char>('f', array, 4, Char.equal) == null;Runtime: O(array.size()); Space: O(1);
func lastIndexOf<X>(element : X, array : [X], equal : (X, X) -> Bool) : ?NatReturns the index of the last element in the array.
import Char "mo:base/Char";
let array = ['c', 'o', 'f', 'f', 'e', 'e'];
assert Array.lastIndexOf<Char>('c', array, Char.equal) == ?0;
assert Array.lastIndexOf<Char>('f', array, Char.equal) == ?3;
assert Array.lastIndexOf<Char>('e', array, Char.equal) == ?5;
assert Array.lastIndexOf<Char>('g', array, Char.equal) == null;Runtime: O(array.size()); Space: O(1);
func prevIndexOf<T>(element : T, array : [T], fromExclusive : Nat, equal : (T, T) -> Bool) : ?NatReturns the index of the previous occurance of element in the array starting from the from index (exclusive).
import Char "mo:base/Char";
let array = ['c', 'o', 'f', 'f', 'e', 'e'];
assert Array.prevIndexOf<Char>('c', array, array.size(), Char.equal) == ?0;
assert Array.prevIndexOf<Char>('e', array, array.size(), Char.equal) == ?5;
assert Array.prevIndexOf<Char>('e', array, 5, Char.equal) == ?4;
assert Array.prevIndexOf<Char>('e', array, 4, Char.equal) == null;Runtime: O(array.size()); Space: O(1);
func slice<X>(array : [X], fromInclusive : Nat, toExclusive : Nat) : I.Iter<X>Returns an iterator over a slice of the given array.
let array = [1, 2, 3, 4, 5];
let s = Array.slice<Nat>(array, 3, array.size());
assert s.next() == ?4;
assert s.next() == ?5;
assert s.next() == null;
let s = Array.slice<Nat>(array, 0, 0);
assert s.next() == null;Runtime: O(1) Space: O(1)
func take<T>(array : [T], length : Int) : [T]Returns a new subarray of given length from the beginning or end of the given array
Returns the entire array if the length is greater than the size of the array
let array = [1, 2, 3, 4, 5];
assert Array.take(array, 2) == [1, 2];
assert Array.take(array, -2) == [4, 5];
assert Array.take(array, 10) == [1, 2, 3, 4, 5];
assert Array.take(array, -99) == [1, 2, 3, 4, 5];Runtime: O(length); Space: O(length);