Array

What is an array?

An immutable or mutable array of type [T] or [var T] is a sequence of values of type T. Each element can be accessed by its index, which is a Nat value that represents the position of the element in the array. Indexing starts at 0. Some properties of arrays are:

• Memory layout
  Arrays are stored in contiguous memory, meaning that all elements are stored next to each other in memory. This makes arrays more memory-efficient than some other data structures, like lists, where elements can be scattered throughout memory.

• Fast indexing
  Arrays provide constant-time access to elements by index. This is because the memory address of any element can be calculated directly from its index and the starting memory address of the array.

• Fixed size
  Once an array is created, its size cannot be changed. If you need to add or remove elements, you will have to create a new array of the desired size and copy the elements. This is different from other sequence data structures like lists or buffers that can grow or shrink dynamically.

• Computational cost of copying
  Since arrays are stored in a contiguous block of memory, copying an array requires copying all its elements to a new memory location. This can be computationally expensive, especially for large arrays.

Import

The convention is to name the module alias after the file name it is defined in:

import Array "mo:base/Array";

Array.mo module public functions

Size

Function size

Initialization

Function init
Function make
Function tabulate
Function tabulateVar

Transformation

Function freeze
Function thaw
Function sort
Function sortInPlace
Function reverse
Function flatten

Comparison

Function equal

Mapping

Function map
Function filter
Function mapEntries
Function mapFilter
Function mapResult

Iteration

Function vals
Function keys
Function find
Function chain
Function foldLeft
Function foldRight

Array.size

The size of an array can be accessed my the .size() method:

let array : [Nat] = [0, 1, 2];
array.size()

The module also provides a dedicated function for the size of an array.

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

import Array "mo:base/Array";

let array : [Text] = ["ICP", "ETH", "USD", "Bitcoin"];

Array.size(array);

Array.init

Initialize a mutable array of type [var X] with a size and an initial value initValue of generic type X.

func init<X>(

     size : Nat,
initValue : X

) : [var X]

import Array "mo:base/Array";

let size : Nat = 3;
let initValue : Char = 'A';

let a : [var Char] = Array.init<Char>(size, initValue);

Array.make

Make an immutable array with exactly one element of generic type X.

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

import Array "mo:base/Array";

let a : [Text] = Array.make<Text>("ICP");

Array.tabulate

The tabulate function generates an immutable array of generic type X and predefined size by using a generator function that takes the index of every element as an argument and produces the elements of the array.

func tabulate<X>(

     size : Nat,
generator : Nat -> X

) : [X]

import Array "mo:base/Array";

let size : Nat = 3;

func generator(i : Nat) : Nat { i ** 2 };

let a : [Nat] = Array.tabulate<Nat>(size, generator);

Array.tabulateVar

The tabulateVar function generates a mutable array of generic type X and predefined size by using a generator function that takes the index of every element as an argument and produces the elements of the array.

func tabulateVar<X>(

     size : Nat,
generator : Nat -> X

) : [var X]

import Array "mo:base/Array";

let size : Nat = 3;

func generator(i : Nat) : Nat { i * 5 };

let a : [var Nat] = Array.tabulateVar<Nat>(size, generator);

Array.freeze

Freeze converts a mutable array of generic type X to a immutable array of the same type.

func freeze<X>(varArray : [var X]) : [X]

import Array "mo:base/Array";

let varArray : [var Text] = [var "apple", "banana", "cherry", "date", "elderberry"];

varArray[1] := "kiwi";

let a : [Text] = Array.freeze<Text>(varArray);

Array.thaw

Thaw converts an immutable array of generic type X to a mutable array of the same type.

func thaw<X>(array : [X]) : [var X]

import Array "mo:base/Array";

let array : [Char] = ['h', 'e', 'l', 'l', 'o'];

let varArray : [var Char] = Array.thaw<Char>(array);

Array.sort

Sort takes an immutable array of generic type X and produces a second array which is sorted according to a comparing function compare. This comparing function compares two elements of type X and returns an Order type that is used to sort the array.

We could use a comparing function from the Base Library, like in the example below, or write our own custom comparing function, as long as its type is (X, X) -> Order.Order

func sort<X>(

   array : [X],
 compare : (X, X) -> Order.Order

) : [X]

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

let ages : [Nat] = [50, 20, 10, 30, 40];

let sortedAges : [Nat] = Array.sort<Nat>(ages, Nat.compare);

Array.sortInPlace

We can also 'sort in place', which behaves the same as sort except we mutate a mutable array in stead of producing a new array. Note the function returns unit type ().

func sortInPlace<X>(

   array : [var X],
 compare : (X, X) -> Order.Order

) : ()

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

var ages : [var Nat] = [var 50, 20, 10, 30, 40];

Array.sortInPlace<Nat>(ages, Nat.compare);

Array.reverse

Takes an immutable array and produces a second array with elements in reversed order.

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

import Array "mo:base/Array";

let rank : [Text] = ["first", "second", "third"];

let reverse : [Text] = Array.reverse<Text>(rank);

Array.flatten

Takes an array of arrays and produces a single array, while retaining the original ordering of the elements.

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

import Array "mo:base/Array";

let arrays : [[Char]] = [['a', 'b'], ['c', 'd'], ['e']];

let newArray : [Char] = Array.flatten(arrays);

Array.equal

Compare each element of two arrays and check whether they are all equal according to an equal function of type (X, X) -> Bool.

func equal<X>(

  array1 : [X],
  array2 : [X],
   equal : (X, X) -> Bool

) : Bool

import Array "mo:base/Array";

let class1 = ["Alice", "Bob", "Charlie", "David"];

let class2 = ["Alice", "Bob", "Charlie", "Eve"];

func nameEqual(name1 : Text, name2 : Text) : Bool {
    name1 == name2;
};

let isNameEqual : Bool = Array.equal<Text>(class1, class2, nameEqual);

Array.map

The mapping function map iterates through each element of an immutable array, applies a given transformation function f to it, and creates a new array with the transformed elements. The input array is of generic type [X], the transformation function takes elements of type X and returns elements of type Y, and the resulting array is of type [Y].

func map<X>(

array : [X],
    f : X -> Y

) : [Y]

import Array "mo:base/Array";

let array1 : [Bool] = [true, false, true, false];

func convert(x : Bool) : Nat {
  if x return 1 else 0;
};

let array2 : [Nat] = Array.map<Bool, Nat>(array1, convert);

Array.filter

The filter function takes an immutable array of elements of generic type X and a predicate function predicate (that takes a X and returns a Bool) and returns a new array containing only the elements that satisfy the predicate condition.

func filter<X>(

    array : [X],
predicate : X -> Bool

) : [X]

import Array "mo:base/Array";

let ages : [Nat] = [1, 2, 5, 6, 9, 7];

func isEven(x : Nat) : Bool {
     x % 2 == 0;
};

let evenAges : [Nat] = Array.filter<Nat>(ages, isEven);

Array.mapEntries

The mapEntries function takes an immutable array of elements of generic type [X] and a function f that accepts an element and its index (a Nat value) as arguments, then returns a new array of type [Y] with elements transformed by applying the function f to each element and its index.

func mapEntries<X,Y>(

array : [X],
    f : (X, Nat) -> Y

) : [Y]

import Array "mo:base/Array";
import Nat "mo:base/Nat";
import Int "mo:base/Int";

let array1 : [Int] = [-1, -2, -3, -4];

func map(x : Int, y : Nat) : Text {
  Int.toText(x) # "; " # Nat.toText(y);
};

let array2 : [Text] = Array.mapEntries<Int, Text>(array1, map);

Array.mapFilter

func mapFilter<X,Y>(

   array : [X],
       f : X -> ?Y

) : [Y]

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

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

func filter(x : Nat) : ?Text {
  if (x > 3) null else ?Nat.toText(100 / x);
};

let array2 = Array.mapFilter<Nat, Text>(array1, filter);

Array.mapResult

func mapResult<X, Y, E>(

  array : [X],
      f : X -> Result.Result<Y, E>

) : Result.Result<[Y], E>

import Array "mo:base/Array";
import Result "mo:base/Result";

let array1 = [4, 5, 2, 1];

func check(x : Nat) : Result.Result<Nat, Text> {
  if (x == 0) #err "Cannot divide by zero" else #ok(100 / x);
};

let mapResult : Result.Result<[Nat], Text> = Array.mapResult<Nat, Nat, Text>(array1, check);

Array.vals

func vals<X>(array : [X]) : I.Iter<X>

import Array "mo:base/Array";

let array = ["ICP", "will", "grow", "?"];

var sentence = "";

for (value in array.vals()) {
    sentence #= value # " ";
};

sentence

Array.keys

func keys<X>(array : [X]) : I.Iter<Nat>

import Array "mo:base/Array";
import Iter "mo:base/Iter";

let array = [true, false, true, false];

let iter = array.keys();

Iter.toArray(iter)

Array.find

func find<X>(

    array : [X],
predicate : X -> Bool

) : ?X

import Array "mo:base/Array";

let ages = [18, 25, 31, 37, 42, 55, 62];

func isGreaterThan40(ages : Nat) : Bool {
     ages > 40;
};

let firstAgeGreaterThan40 : ?Nat = Array.find<Nat>(ages, isGreaterThan40);

Array.chain

func chain<X, Y>(

  array : [X],
      k : X -> [Y]

) : [Y]

import Array "mo:base/Array";

let array1 = [10, 20, 30];

func chain(x : Nat) : [Int] { [x, -x] };

let array2 : [Int] = Array.chain<Nat, Int>(array1, chain);

Array.foldLeft

func foldLeft<X, A>(

  array : [X],
   base : A,
combine : (A, X) -> A

) : A

import Array "mo:base/Array";

let array = [40, 20, 0, 10];

func add(a : Nat, b : Nat) : Nat {
    a + b;
};

let base : Nat = 30;

let sum : Nat = Array.foldLeft<Nat, Nat>(array, base, add);

Array.foldRight

func foldRight<X, A>(

  array : [X],
   base : A,
combine : (X, A) -> A

) : A

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

let array1 = [7, 8, 1];

func concat(a : Nat, b : Text) : Text {
    b # Nat.toText(a);
};

let base : Text = "Numbers: ";

Array.foldRight<Nat, Text>(array1, base, concat);