List

Purely-functional, singly-linked lists. A list of type List<T> is either null or an optional pair of a value of type T and a tail, itself of type List<T>.

To use this library, import it using:

import List "mo:base/List";

Type `List`

type List<T> = ?(T, List<T>)

Function `nil`

func nil<T>() : List<T>

Create an empty list.

Example:

List.nil<Nat>() // => null

Runtime: O(1)

Space: O(1)

Function `isNil`

func isNil<T>(l : List<T>) : Bool

Check whether a list is empty and return true if the list is empty.

Example:

List.isNil<Nat>(null) // => true

Runtime: O(1)

Space: O(1)

Function `push`

func push<T>(x : T, l : List<T>) : List<T>

Add x to the head of list, and return the new list.

Example:

List.push<Nat>(0, null) // => ?(0, null);

Runtime: O(1)

Space: O(1)

Function `last`

func last<T>(l : List<T>) : ?T

Return the last element of the list, if present. Example:

List.last<Nat>(?(0, ?(1, null))) // => ?1

Runtime: O(size)

Space: O(1)

Function `pop`

func pop<T>(l : List<T>) : (?T, List<T>)

Remove the head of the list, returning the optioned head and the tail of the list in a pair. Returns (null, null) if the list is empty.

Example:

List.pop<Nat>(?(0, ?(1, null))) // => (?0, ?(1, null))

Runtime: O(1)

Space: O(1)

Function `size`

func size<T>(l : List<T>) : Nat

Return the length of the list.

Example:

List.size<Nat>(?(0, ?(1, null))) // => 2

Runtime: O(size)

Space: O(1)

Function `get`

func get<T>(l : List<T>, n : Nat) : ?T

Access any item in a list, zero-based.

NOTE: Indexing into a list is a linear operation, and usually an indication that a list might not be the best data structure to use.

Example:

List.get<Nat>(?(0, ?(1, null)), 1) // => ?1

Runtime: O(size)

Space: O(1)

Function `reverse`

func reverse<T>(l : List<T>) : List<T>

Reverses the list.

Example:

List.reverse<Nat>(?(0, ?(1, ?(2, null)))) // => ?(2, ?(1, ?(0, null)))

Runtime: O(size)

Space: O(size)

Function `iterate`

func iterate<T>(l : List<T>, f : T -> ())

Call the given function for its side effect, with each list element in turn.

Example:

var sum = 0;
List.iterate<Nat>(?(0, ?(1, ?(2, null))), func n { sum += n });
sum // => 3

Runtime: O(size)

Space: O(1)

Function `map`

func map<T, U>(l : List<T>, f : T -> U) : List<U>

Call the given function f on each list element and collect the results in a new list.

Example:

import Nat = "mo:base/Nat"
List.map<Nat, Text>(?(0, ?(1, ?(2, null))), Nat.toText) // => ?("0", ?("1", ?("2", null))

Runtime: O(size)

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

Function `filter`

func filter<T>(l : List<T>, f : T -> Bool) : List<T>

Create a new list with only those elements of the original list for which the given function (often called the predicate) returns true.

Example:

List.filter<Nat>(?(0, ?(1, ?(2, null))), func n { n != 1 }) // => ?(0, ?(2, null))

Runtime: O(size)

Space: O(size)

Function `partition`

func partition<T>(l : List<T>, f : T -> Bool) : (List<T>, List<T>)

Create two new lists from the results of a given function (f). The first list only includes the elements for which the given function f returns true and the second list only includes the elements for which the function returns false.

Example:

List.partition<Nat>(?(0, ?(1, ?(2, null))), func n { n != 1 }) // => (?(0, ?(2, null)), ?(1, null))

Runtime: O(size)

Space: O(size)

Function `mapFilter`

func mapFilter<T, U>(l : List<T>, f : T -> ?U) : List<U>

Call the given function on each list element, and collect the non-null results in a new list.

Example:

List.mapFilter<Nat, Nat>(
  ?(1, ?(2, ?(3, null))),
  func n {
    if (n > 1) {
      ?(n * 2);
    } else {
      null
    }
  }
) // => ?(4, ?(6, null))

Runtime: O(size)

Space: O(size)

Function `mapResult`

func mapResult<T, R, E>(xs : List<T>, f : T -> Result.Result<R, E>) : Result.Result<List<R>, E>

Maps a Result-returning function f over a List and returns either the first error or a list of successful values.

Example:

List.mapResult<Nat, Nat, Text>(
  ?(1, ?(2, ?(3, null))),
  func n {
    if (n > 0) {
      #ok(n * 2);
    } else {
      #err("Some element is zero")
    }
  }
); // => #ok ?(2, ?(4, ?(6, null))

Runtime: O(size)

Space: O(size)

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

Function `append`

func append<T>(l : List<T>, m : List<T>) : List<T>

Append the elements from one list to another list.

Example:

List.append<Nat>(
  ?(0, ?(1, ?(2, null))),
  ?(3, ?(4, ?(5, null)))
) // => ?(0, ?(1, ?(2, ?(3, ?(4, ?(5, null))))))

Runtime: O(size(l))

Space: O(size(l))

Function `flatten`

func flatten<T>(l : List<List<T>>) : List<T>

Flatten, or concatenate, a list of lists as a list.

Example:

List.flatten<Nat>(
  ?(?(0, ?(1, ?(2, null))),
    ?(?(3, ?(4, ?(5, null))),
      null))
); // => ?(0, ?(1, ?(2, ?(3, ?(4, ?(5, null))))))

Runtime: O(size*size)

Space: O(size*size)

Function `take`

func take<T>(l : List<T>, n : Nat) : List<T>

Returns the first n elements of the given list. If the given list has fewer than n elements, this function returns a copy of the full input list.

Example:

List.take<Nat>(
  ?(0, ?(1, ?(2, null))),
  2
); // => ?(0, ?(1, null))

Runtime: O(n)

Space: O(n)

Function `drop`

func drop<T>(l : List<T>, n : Nat) : List<T>

Drop the first n elements from the given list.

Example:

List.drop<Nat>(
  ?(0, ?(1, ?(2, null))),
  2
); // => ?(2, null)

Runtime: O(n)

Space: O(1)

Function `foldLeft`

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

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

List.foldLeft<Nat, Text>(
  ?(1, ?(2, ?(3, null))),
  "",
  func (acc, x) { acc # Nat.toText(x)}
) // => "123"

Runtime: O(size(list))

Space: O(1) heap, O(1) stack

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

Function `foldRight`

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

Collapses the elements in buffer 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";

List.foldRight<Nat, Text>(
  ?(1, ?(2, ?(3, null))),
  "",
  func (x, acc) { Nat.toText(x) # acc}
) // => "123"

Runtime: O(size(list))

Space: O(1) heap, O(size(list)) stack

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

Function `find`

func find<T>(l : List<T>, f : T -> Bool) : ?T

Return the first element for which the given predicate f is true, if such an element exists.

Example:

List.find<Nat>(
  ?(1, ?(2, ?(3, null))),
  func n { n > 1 }
); // => ?2

Runtime: O(size)

Space: O(1)

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

Function `some`

func some<T>(l : List<T>, f : T -> Bool) : Bool

Return true if there exists a list element for which the given predicate f is true.

Example:

List.some<Nat>(
  ?(1, ?(2, ?(3, null))),
  func n { n > 1 }
) // => true

Runtime: O(size(list))

Space: O(1)

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

Function `all`

func all<T>(l : List<T>, f : T -> Bool) : Bool

Return true if the given predicate f is true for all list elements.

Example:

List.all<Nat>(
  ?(1, ?(2, ?(3, null))),
  func n { n > 1 }
); // => false

Runtime: O(size)

Space: O(1)

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

Function `merge`

func merge<T>(l1 : List<T>, l2 : List<T>, lessThanOrEqual : (T, T) -> Bool) : List<T>

Merge two ordered lists into a single ordered list. This function requires both list to be ordered as specified by the given relation lessThanOrEqual.

Example:

List.merge<Nat>(
  ?(1, ?(2, ?(4, null))),
  ?(2, ?(4, ?(6, null))),
  func (n1, n2) { n1 <= n2 }
); // => ?(1, ?(2, ?(2, ?(4, ?(4, ?(6, null))))))),

Runtime: O(size(l1) + size(l2))

Space: O(size(l1) + size(l2))

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

Function `compare`

func compare<T>(l1 : List<T>, l2 : List<T>, compare : (T, T) -> Order.Order) : Order.Order

Compare two lists using lexicographic ordering specified by argument function compare.

Example:

import Nat "mo:base/Nat";

List.compare<Nat>(
  ?(1, ?(2, null)),
  ?(3, ?(4, null)),
  Nat.compare
) // => #less

Runtime: O(size(l1))

Space: O(1)

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

Function `equal`

func equal<T>(l1 : List<T>, l2 : List<T>, equal : (T, T) -> Bool) : Bool

Compare two lists for equality using the argument function equal to determine equality of their elements.

Example:

import Nat "mo:base/Nat";

List.equal<Nat>(
  ?(1, ?(2, null)),
  ?(3, ?(4, null)),
  Nat.equal
); // => false

Runtime: O(size(l1))

Space: O(1)

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

Function `tabulate`

func tabulate<T>(n : Nat, f : Nat -> T) : List<T>

Generate a list based on a length and a function that maps from a list index to a list element.

Example:

List.tabulate<Nat>(
  3,
  func n { n * 2 }
) // => ?(0, ?(2, (?4, null)))

Runtime: O(n)

Space: O(n)

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

Function `make`

func make<T>(x : T) : List<T>

Create a list with exactly one element.

Example:

List.make<Nat>(
  0
) // => ?(0, null)

Runtime: O(1)

Space: O(1)

Function `replicate`

func replicate<T>(n : Nat, x : T) : List<T>

Create a list of the given length with the same value in each position.

Example:

List.replicate<Nat>(
  3,
  0
) // => ?(0, ?(0, ?(0, null)))

Runtime: O(n)

Space: O(n)

Function `zip`

func zip<T, U>(xs : List<T>, ys : List<U>) : List<(T, U)>

Create a list of pairs from a pair of lists.

If the given lists have different lengths, then the created list will have a length equal to the length of the smaller list.

Example:

List.zip<Nat, Text>(
  ?(0, ?(1, ?(2, null))),
  ?("0", ?("1", null)),
) // => ?((0, "0"), ?((1, "1"), null))

Runtime: O(min(size(xs), size(ys)))

Space: O(min(size(xs), size(ys)))

Function `zipWith`

func zipWith<T, U, V>(xs : List<T>, ys : List<U>, f : (T, U) -> V) : List<V>

Create a list in which elements are created by applying function f to each pair (x, y) of elements occuring at the same position in list xs and list ys.

If the given lists have different lengths, then the created list will have a length equal to the length of the smaller list.

Example:

import Nat = "mo:base/Nat";
import Char = "mo:base/Char";

List.zipWith<Nat, Char, Text>(
  ?(0, ?(1, ?(2, null))),
  ?('a', ?('b', null)),
  func (n, c) { Nat.toText(n) # Char.toText(c) }
) // => ?("0a", ?("1b", null))

Runtime: O(min(size(xs), size(ys)))

Space: O(min(size(xs), size(ys)))

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

Function `split`

func split<T>(n : Nat, xs : List<T>) : (List<T>, List<T>)

Split the given list at the given zero-based index.

Example:

List.split<Nat>(
  2,
  ?(0, ?(1, ?(2, null)))
) // => (?(0, ?(1, null)), ?(2, null))

Runtime: O(n)

Space: O(n)

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

Function `chunks`

func chunks<T>(n : Nat, xs : List<T>) : List<List<T>>

Split the given list into chunks of length n. The last chunk will be shorter if the length of the given list does not divide by n evenly.

Example:

List.chunks<Nat>(
  2,
  ?(0, ?(1, ?(2, ?(3, ?(4, null)))))
)
/* => ?(?(0, ?(1, null)),
        ?(?(2, ?(3, null)),
          ?(?(4, null),
            null)))
*/

Runtime: O(size)

Space: O(size)

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

Function `fromArray`

func fromArray<T>(xs : [T]) : List<T>

Convert an array into a list.

Example:

List.fromArray<Nat>([ 0, 1, 2, 3, 4])
// =>  ?(0, ?(1, ?(2, ?(3, ?(4, null)))))

Runtime: O(size)

Space: O(size)

Function `fromVarArray`

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

Convert a mutable array into a list.

Example:

List.fromVarArray<Nat>([var 0, 1, 2, 3, 4])
// =>  ?(0, ?(1, ?(2, ?(3, ?(4, null)))))

Runtime: O(size)

Space: O(size)

Function `toArray`

func toArray<T>(xs : List<T>) : [T]

Create an array from a list. Example:

List.toArray<Nat>(?(0, ?(1, ?(2, ?(3, ?(4, null))))))
// => [0, 1, 2, 3, 4]

Runtime: O(size)

Space: O(size)

Function `toVarArray`

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

Create a mutable array from a list. Example:

List.toVarArray<Nat>(?(0, ?(1, ?(2, ?(3, ?(4, null))))))
// => [var 0, 1, 2, 3, 4]

Runtime: O(size)

Space: O(size)

Function `toIter`

func toIter<T>(xs : List<T>) : Iter.Iter<T>

Create an iterator from a list. Example:

var sum = 0;
for (n in List.toIter<Nat>(?(0, ?(1, ?(2, ?(3, ?(4, null))))))) {
  sum += n;
};
sum
// => 10

Runtime: O(1)

Space: O(1)

List

Type List​

Function nil​

Function isNil​

Function push​

Function last​

Function pop​

Function size​

Function get​

Function reverse​

Function iterate​

Function map​

Function filter​

Function partition​

Function mapFilter​

Function mapResult​

Function append​

Function flatten​

Function take​

Function drop​

Function foldLeft​

Function foldRight​

Function find​

Function some​

Function all​

Function merge​

Function compare​

Function equal​

Function tabulate​

Function make​

Function replicate​

Function zip​

Function zipWith​

Function split​

Function chunks​

Function fromArray​

Function fromVarArray​

Function toArray​

Function toVarArray​

Function toIter​

Type `List`

Function `nil`

Function `isNil`

Function `push`

Function `last`

Function `pop`

Function `size`

Function `get`

Function `reverse`

Function `iterate`

Function `map`

Function `filter`

Function `partition`

Function `mapFilter`

Function `mapResult`

Function `append`

Function `flatten`

Function `take`

Function `drop`

Function `foldLeft`

Function `foldRight`

Function `find`

Function `some`

Function `all`

Function `merge`

Function `compare`

Function `equal`

Function `tabulate`

Function `make`

Function `replicate`

Function `zip`

Function `zipWith`

Function `split`

Function `chunks`

Function `fromArray`

Function `fromVarArray`

Function `toArray`

Function `toVarArray`

Function `toIter`