Array

Provides extended utility functions on Arrays.

If you are looking for a list that can grow and shrink in size, it is recommended you use either the Buffer or List data structure for those purposes.

[Assumptions]

Runtime and space complexity assumes that generator, equal, and other functions execute in O(1) time and space.

Import from the base library to use this module.

import Array "mo:base/Array";

Function init

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	Space
O(size)	O(size)

Function tabulate

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	Space
O(size)	O(size)

Function tabulateVar

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;
array

Runtime	Space
O(size)	O(size)

Function freeze

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	Space
O(size)	O(1)

Function thaw

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;
varArray

Runtime	Space
O(size)	O(1)

Function equal

func equal<X>(array1 : [X], array2 : [X], equal : (X, X) -> 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:base/Nat";

let array1 = [0, 1, 2, 3];
let array2 = [0, 1, 2, 3];
Array.equal(array1, array2, equal)

Runtime	Space
O(size1 + size2)	O(size1 + size2)

Function find

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

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];
Array.find<Nat>(array, func x = x > 8)

Runtime	Space
O(size)	O(1)

Function append

func append<X>(array1 : [X], array2 : [X]) : [X]

Create a new array by appending the values of array1 and array2.

[Efficient appending]

Array.append copies its arguments and runs in linear time. For better performance in loops, consider using Buffer and Buffer.append instead.

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

Runtime	Space
O(size1 + size2)	O(size1 + size2)

Function sort

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	Space
O(size * log(size))	O(size)

Function sortInPlace

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);
array

Runtime	Space
O(size * log(size))	O(size)

Function reverse

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	Space
O(size)	O(1)

Function map

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	Space
O(size)	O(size)

Function filter

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	Space
O(size)	O(size)

Function mapEntries

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	Space
O(size)	O(size)

Function mapFilter

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	Space
O(size)	O(size)

Function mapResult

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	Space
O(size)	O(size)

Function chain

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	Space
O(size)	O(size)

Function foldLeft

func foldLeft<X, A>(array : [X], base : A, combine : (A, X) -> 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: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	Space
O(size)	O(1)

Function foldRight

func foldRight<X, A>(array : [X], base : A, combine : (X, 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:base/Nat";

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

Runtime	Space
O(size)	O(1)

Function flatten

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	Space
O(n)	O(n)

Function make

func make<X>(element : X) : [X]

Create an array containing a single value.

Array.make(2)

Runtime	Space
O(1)	O(1)

Function vals

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.

[Alternative approach]

Alternatively, you can use array.size() to achieve the same result. See the example below.

let array = [10, 11, 12];
var sum = 0;
for (element in array.vals()) {
  sum += element;
};
sum

Runtime	Space
O(1)	O(1)

Function keys

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.

[Alternative approach]

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;
};
sum

Runtime	Space
O(1)	O(1)

Function size

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

Returns the size of array.

[Alternative approach]

Alternatively, you can use array.size() to achieve the same result. See the example below.

let array = [10, 11, 12];
let size = Array.size(array);

Runtime	Space
O(1)	O(1)

Function subArray

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	Space
O(length)	O(length)

Function indexOf

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

Returns 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	Space
O(array.size())	O(1)

Function nextIndexOf

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

Returns 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	Space
O(array.size())	O(1)

Function lastIndexOf

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

Returns 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	Space
O(array.size())	O(1)

Function prevIndexOf

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

Returns 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	Space
O(array.size())	O(1)

Function slice

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	Space
O(1)	O(1)

Function take

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	Space
O(length)	O(length)