core/Array

Provides extended utility functions on immutable Arrays (values of type [T]).

Note the difference between mutable ([var T]) and immutable ([T]) arrays. Mutable arrays allow their elements to be modified after creation, while immutable arrays are fixed once created.

WARNING: If you are looking for a list that can grow and shrink in size, it is recommended you use List for those purposes. Arrays must be created with a fixed size.

Import from the core library to use this module.

import Array "mo:core/Array";

Function empty

func empty<T>() : [T]

Creates an empty array (equivalent to []).

let array = Array.empty<Text>();
assert array == [];

Runtime: O(1)

Space: O(1)

Function repeat

func repeat<T>(item : T, size : Nat) : [T]

Creates an array containing item repeated size times.

let array = Array.repeat<Text>("Echo", 3);
assert array == ["Echo", "Echo", "Echo"];

Runtime: O(size)

Space: O(size)

Function tabulate

func tabulate<T>(size : Nat, generator : Nat -> T) : [T]

Creates 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);
assert array == [0, 2, 4, 6];

Runtime: O(size)

Space: O(size)

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

Function fromVarArray

func fromVarArray<T>(varArray : [var T]) : [T]

Transforms a mutable array into an immutable array.

let varArray = [var 0, 1, 2];
varArray[2] := 3;
let array = Array.fromVarArray<Nat>(varArray);
assert array == [0, 1, 3];

Runtime: O(size)

Space: O(1)

Function toVarArray

func toVarArray<T>(array : [T]) : [var T]

Transforms an immutable array into a mutable array.

import VarArray "mo:core/VarArray";
import Nat "mo:core/Nat";

let array = [0, 1, 2];
let varArray = Array.toVarArray<Nat>(array);
varArray[2] := 3;
assert VarArray.equal(varArray, [var 0, 1, 3], Nat.equal);

Runtime: O(size)

Space: O(1)

Function equal

func equal<T>(array1 : [T], array2 : [T], equal : (T, T) -> Bool) : Bool

Tests 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:core/Nat";

let array1 = [0, 1, 2, 3];
let array2 = [0, 1, 2, 3];
assert 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.

Function find

func find<T>(array : [T], predicate : T -> Bool) : ?T

Returns the first value in array for which predicate returns true. If no element satisfies the predicate, returns null.

let array = [1, 9, 4, 8];
let found = Array.find<Nat>(array, func x = x > 8);
assert found == ?9;

Runtime: O(size)

Space: O(1)

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

Function findIndex

func findIndex<T>(array : [T], predicate : T -> Bool) : ?Nat

Returns the first index in array for which predicate returns true. If no element satisfies the predicate, returns null.

let array = ['A', 'B', 'C', 'D'];
let found = Array.findIndex<Char>(array, func(x) { x == 'C' });
assert found == ?2;

Runtime: O(size)

Space: O(1)

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

Function concat

func concat<T>(array1 : [T], array2 : [T]) : [T]

Create a new array by concatenating the values of array1 and array2. Note that Array.concat copies its arguments and has linear complexity.

let array1 = [1, 2, 3];
let array2 = [4, 5, 6];
let result = Array.concat<Nat>(array1, array2);
assert result == [1, 2, 3, 4, 5, 6];

Runtime: O(size1 + size2)

Space: O(size1 + size2)

Function sort

func sort<T>(array : [T], compare : (T, T) -> Order.Order) : [T]

Sorts the elements in the array according to compare. Sort is deterministic and stable.

import Nat "mo:core/Nat";

let array = [4, 2, 6];
let sorted = Array.sort(array, Nat.compare);
assert sorted == [2, 4, 6];

Runtime: O(size * log(size))

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

Function reverse

func reverse<T>(array : [T]) : [T]

Creates a new array by reversing the order of elements in array.

let array = [10, 11, 12];
let reversed = Array.reverse(array);
assert reversed == [12, 11, 10];

Runtime: O(size)

Space: O(1)

Function forEach

func forEach<T>(array : [T], f : T -> ())

Calls f with each element in array. Retains original ordering of elements.

var sum = 0;
let array = [0, 1, 2, 3];
Array.forEach<Nat>(array, func(x) {
  sum += x;
});
assert sum == 6;

Runtime: O(size)

Space: O(size)

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

Function map

func map<T, R>(array : [T], f : T -> R) : [R]

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 array1 = [0, 1, 2, 3];
let array2 = Array.map<Nat, Nat>(array1, func x = x * 2);
assert array2 == [0, 2, 4, 6];

Runtime: O(size)

Space: O(size)

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

Function filter

func filter<T>(array : [T], f : T -> Bool) : [T]

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);
assert evenElements == [4, 2, 6];

Runtime: O(size)

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

Function filterMap

func filterMap<T, R>(array : [T], f : T -> ?R) : [R]

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:core/Nat";

let array = [4, 2, 0, 1];
let newArray =
  Array.filterMap<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
  );
assert newArray == ["25", "50", "100"];

Runtime: O(size)

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

Function mapResult

func mapResult<T, R, E>(array : [T], f : T -> Result.Result<R, E>) : Result.Result<[R], 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
let result = Array.mapResult<Nat, Nat, Text>(array, func x {
  if (x > 0) {
    #ok(100 / x)
  } else {
    #err "Cannot divide by zero"
  }
});
assert result == #err "Cannot divide by zero";

Runtime: O(size)

Space: O(size)

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

Function mapEntries

func mapEntries<T, R>(array : [T], f : (T, Nat) -> R) : [R]

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];
let newArray = Array.mapEntries<Nat, Nat>(array, func (x, i) = i * x);
assert newArray == [0, 10, 20, 30];

Runtime: O(size)

Space: O(size)

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

Function flatMap

func flatMap<T, R>(array : [T], k : T -> Types.Iter<R>) : [R]

Creates a new array by applying k to each element in array, and concatenating the resulting arrays in order.

let array = [1, 2, 3, 4];
let newArray = Array.flatMap<Nat, Int>(array, func x = [x, -x].values());
assert newArray == [1, -1, 2, -2, 3, -3, 4, -4];

Runtime: O(size)

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

Function foldLeft

func foldLeft<T, A>(array : [T], base : A, combine : (A, T) -> A) : A

Collapses 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:core/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`!
  );
assert sum == 7;

Runtime: O(size)

Space: O(1)

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

Function foldRight

func foldRight<T, A>(array : [T], base : A, combine : (T, A) -> A) : A

Collapses 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:core/Nat";

let array = [1, 9, 4, 8];
let bookTitle = Array.foldRight<Nat, Text>(array, "", func(x, acc) = toText(x) # acc);
assert bookTitle == "1948";

Runtime: O(size)

Space: O(1)

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

Function join

func join<T>(arrays : Types.Iter<[T]>) : [T]

Combines an iterator of arrays into a single array. Retains the original ordering of the elements.

Consider using Array.flatten() for better performance.

let arrays = [[0, 1, 2], [2, 3], [], [4]];
let joinedArray = Array.join<Nat>(arrays.values());
assert joinedArray == [0, 1, 2, 2, 3, 4];

Runtime: O(number of elements in array)

Space: O(number of elements in array)

Function flatten

func flatten<T>(arrays : [[T]]) : [T]

Combines an array of arrays into a single array. Retains the original ordering of the elements.

This has better performance compared to Array.join().

let arrays = [[0, 1, 2], [2, 3], [], [4]];
let flatArray = Array.flatten<Nat>(arrays);
assert flatArray == [0, 1, 2, 2, 3, 4];

Runtime: O(number of elements in array)

Space: O(number of elements in array)

Function singleton

func singleton<T>(element : T) : [T]

Create an array containing a single value.

let array = Array.singleton(2);
assert array == [2];

Runtime: O(1)

Space: O(1)

Function size

func size<T>(array : [T]) : Nat

Returns the size of an array. Equivalent to array.size().

Function isEmpty

func isEmpty<T>(array : [T]) : Bool

Returns whether an array is empty, i.e. contains zero elements.

Function fromIter

func fromIter<T>(iter : Types.Iter<T>) : [T]

Converts an iterator to an array.

Function keys

func keys<T>(array : [T]) : Types.Iter<Nat>

Returns an iterator (Iter) over the indices of array. An 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;
};
assert sum == 3; // 0 + 1 + 2

Runtime: O(1)

Space: O(1)

Function values

func values<T>(array : [T]) : Types.Iter<T>

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.values() instead of this function. See example below.

let array = [10, 11, 12];

var sum = 0;
for (element in array.values()) {
  sum += element;
};
assert sum == 33;

Runtime: O(1)

Space: O(1)

Function enumerate

func enumerate<T>(array : [T]) : Types.Iter<(Nat, T)>

Iterator provides a single method next(), which returns pairs of (index, element) in order, or null when out of elements to iterate over.

let array = [10, 11, 12];

var sum = 0;
for ((index, element) in Array.enumerate(array)) {
  sum += element;
};
assert sum == 33;

Runtime: O(1)

Space: O(1)

Function all

func all<T>(array : [T], predicate : T -> Bool) : Bool

Returns true if all elements in array satisfy the predicate function.

let array = [1, 2, 3, 4];
assert Array.all<Nat>(array, func x = x > 0);

Runtime: O(size)

Space: O(1)

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

Function any

func any<T>(array : [T], predicate : T -> Bool) : Bool

Returns true if any element in array satisfies the predicate function.

let array = [1, 2, 3, 4];
assert Array.any<Nat>(array, func x = x > 3);

Runtime: O(size)

Space: O(1)

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

Function indexOf

func indexOf<T>(element : T, array : [T], equal : (T, T) -> Bool) : ?Nat

Returns the index of the first element in the array.

import Char "mo:core/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)

Function nextIndexOf

func nextIndexOf<T>(element : T, array : [T], fromInclusive : Nat, equal : (T, T) -> Bool) : ?Nat

Returns the index of the next occurence of element in the array starting from the from index (inclusive).

import Char "mo:core/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)

Function lastIndexOf

func lastIndexOf<T>(element : T, array : [T], equal : (T, T) -> Bool) : ?Nat

Returns the index of the last element in the array.

import Char "mo:core/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)

Function prevIndexOf

func prevIndexOf<T>(element : T, array : [T], fromExclusive : Nat, equal : (T, T) -> Bool) : ?Nat

Returns the index of the previous occurence of element in the array starting from the from index (exclusive).

Negative indices are relative to the end of the array. For example, -1 corresponds to the last element in the array.

If the indices are out of bounds, they are clamped to the array bounds. If the first index is greater than the second, the function returns an empty iterator.

import Char "mo:core/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);

Function range

func range<T>(array : [T], fromInclusive : Int, toExclusive : Int) : Types.Iter<T>

Returns an iterator over a slice of array starting at fromInclusive up to (but not including) toExclusive.

Negative indices are relative to the end of the array. For example, -1 corresponds to the last element in the array.

If the indices are out of bounds, they are clamped to the array bounds. If the first index is greater than the second, the function returns an empty iterator.

let array = [1, 2, 3, 4, 5];
let iter1 = Array.range<Nat>(array, 3, array.size());
assert iter1.next() == ?4;
assert iter1.next() == ?5;
assert iter1.next() == null;

let iter2 = Array.range<Nat>(array, 3, -1);
assert iter2.next() == ?4;
assert iter2.next() == null;

let iter3 = Array.range<Nat>(array, 0, 0);
assert iter3.next() == null;

Runtime: O(1)

Space: O(1)

Function sliceToArray

func sliceToArray<T>(array : [T], fromInclusive : Int, toExclusive : Int) : [T]

Returns a new array containing elements from array starting at index fromInclusive up to (but not including) index toExclusive. If the indices are out of bounds, they are clamped to the array bounds.

let array = [1, 2, 3, 4, 5];

let slice1 = Array.sliceToArray<Nat>(array, 1, 4);
assert slice1 == [2, 3, 4];

let slice2 = Array.sliceToArray<Nat>(array, 1, -1);
assert slice2 == [2, 3, 4];

Runtime: O(toExclusive - fromInclusive)

Space: O(toExclusive - fromInclusive)

Function toText

func toText<T>(array : [T], f : T -> Text) : Text

Converts the array to its textual representation using f to convert each element to Text.

import Nat "mo:core/Nat";

let array = [1, 2, 3];
let text = Array.toText<Nat>(array, Nat.toText);
assert text == "[1, 2, 3]";

Runtime: O(size)

Space: O(size)

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

Function compare

func compare<T>(array1 : [T], array2 : [T], compare : (T, T) -> Order.Order) : Order.Order

Compares two arrays using the provided comparison function for elements. Returns #less, #equal, or #greater if array1 is less than, equal to, or greater than array2 respectively.

If arrays have different sizes but all elements up to the shorter length are equal, the shorter array is considered #less than the longer array.

import Nat "mo:core/Nat";

let array1 = [1, 2, 3];
let array2 = [1, 2, 4];
assert Array.compare<Nat>(array1, array2, Nat.compare) == #less;

import Nat "mo:core/Nat";

let array3 = [1, 2];
let array4 = [1, 2, 3];
assert Array.compare<Nat>(array3, array4, Nat.compare) == #less;

Runtime: O(min(size1, size2))

Space: O(1)

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