View Source Arrays (Arrays v2.1.1)

Well-structured Arrays with fast random-element-access for Elixir, offering a common interface with multiple implementations with varying performance guarantees that can be switched in your configuration.

Using Arrays

Some simple examples:

Constructing Arrays

By calling Arrays.new or Arrays.empty:

iex> Arrays.new(["Dvorak", "Tchaikovsky", "Bruch"])
#Arrays.Implementations.MapArray<["Dvorak", "Tchaikovsky", "Bruch"]>

By using Collectable:

iex> [1, 2, 3] |> Enum.into(Arrays.new())
#Arrays.Implementations.MapArray<[1, 2, 3]>
iex> for x <- 1..2, y <- 4..5, into: Arrays.new(), do: {x, y}
#Arrays.Implementations.MapArray<[{1, 4}, {1, 5}, {2, 4}, {2, 5}]>

Some common array operations:

  • Indexing is fast.

  • The full Access calls are supported,

  • Variants of many common Enum-like functions that keep the result an array (rather than turning it into a list), are available.

    iex> words = Arrays.new(["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"])
    #Arrays.Implementations.MapArray<["the", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"]>
    iex> Arrays.size(words) # Runs in constant-time
    9
    iex> words[3] # Indexing is fast
    "fox"
    iex> words = put_in(words[2], "purple") # All of `Access` is supported
    #Arrays.Implementations.MapArray<["the", "quick", "purple", "fox", "jumps", "over", "the", "lazy", "dog"]>
    iex> Arrays.map(words, &String.upcase/1) # Map a function, keep result an array
    #Arrays.Implementations.MapArray<["THE", "QUICK", "PURPLE", "FOX", "JUMPS", "OVER", "THE", "LAZY", "DOG"]>
    iex> lengths = Arrays.map(words, &String.length/1)
    #Arrays.Implementations.MapArray<[3, 5, 6, 3, 5, 4, 3, 4, 3]>
    iex> Arrays.reduce(lengths, 0, &Kernel.+/2) # `reduce_right` is supported as well.
    36

Concatenating arrays:

iex> Arrays.new([1, 2, 3]) |> Arrays.concat(Arrays.new([4, 5, 6]))
#Arrays.Implementations.MapArray<[1, 2, 3, 4, 5, 6]>

Slicing arrays:

iex> ints = Arrays.new(1..100)
iex> Arrays.slice(ints, 9..19)
#Arrays.Implementations.MapArray<[10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]>

Rationale

Algorithms that use arrays can be used while abstracting away from the underlying representation. Which array implementation/representation is actually used, can then later be configured/compared, to make a trade-off between ease-of-use and time/memory efficiency.

Arrays itself comes with two built-in implementations:

By default, Elixir.Arrays.Implementations.MapArray is used when creating new array objects, but this can be configured by either changing the default in your whole application, or by passing an option to a specific invocation of new/0-2, or empty/0-1.

Implementations provided by other libraries:

  • ArraysAja adds support for Aja's A.Vector, which is an implementation of a 'Hickey Trie' vector. For most operations, it significantly outperforms ErlangArray and MapArray.

Protocols

Besides being able to use all functions in this module, one can use the following protocols and behaviours with them:

  • From Elixir's standard library:

    • Enumerable: Iterating over arrays
    • Collectable: Creating arrays from collections
    • the Access behaviour: access a particular element using square brackets, put_in etc.
  • From common container libraries:

Note: FunLand is an optional dependency of this library, so its functionality will only be available if :fun_land is also added to your mix.exs dependencies list.

Enumerable

iex> myarray = Arrays.new([2, 1, 4, 2, 0])
iex> Enum.sort(myarray)
[0, 1, 2, 2, 4]
iex> Enum.count(myarray)
5
iex> Enum.with_index(myarray)
[{2, 0}, {1, 1}, {4, 2}, {2, 3}, {0, 4}]
iex> Enum.slice(myarray, 1, 3)
[1, 4, 2]

iex> names = Arrays.new(["Ernie", "Bert", "Kermit"])
iex> names |> Stream.map(&String.upcase/1) |> Enum.into(Arrays.new())
#Arrays.Implementations.MapArray<["ERNIE", "BERT", "KERMIT"]>

iex> foods = Arrays.new(["Cheese", "Strawberries", "Cookies"])
iex> foods |> Enum.take(2)
["Cheese", "Strawberries"]

iex> Arrays.new([1, 2, 3]) |> Stream.zip(Arrays.new([4, 5, 6])) |> Enum.take(2)
[{1, 4}, {2, 5}]

Collectable

iex> [10, 20, 30, 40] |> Enum.into(Arrays.new())
#Arrays.Implementations.MapArray<[10, 20, 30, 40]>

Access

Fast random-element access and updates are supported.

iex> arr = Arrays.new([1, 2, 3, 4])
iex> arr = put_in(arr[2], 33)
#Arrays.Implementations.MapArray<[1, 2, 33, 4]>
iex> arr = update_in(arr[1], (&(&1 * -2)))
#Arrays.Implementations.MapArray<[1, -4, 33, 4]>
iex> update_in(arr[-1], (&(&1 + 1)))
#Arrays.Implementations.MapArray<[1, -4, 33, 5]>

Popping from a random location however, is not. Only removals of the last element of the array are fast. For this, use Arrays.extract/1.

iex> arr = Arrays.new([1, -4, 33, 5])
iex> {33, _arr} = pop_in(arr[-2])
** (ArgumentError) There is no efficient implementation possible to remove an element from a random location in an array, so `Access.pop/2` (and returning `:pop` from `Access.get_and_update/3` ) are not supported by Arrays.Implementations.MapArray. If you want to remove the last element, use `Arrays.extract/1`.

iex> arr2 = Arrays.new([10, 20, 30])
iex> {20, _arr2} = get_and_update_in(arr2[1], fn _ -> :pop end)
** (ArgumentError) There is no efficient implementation possible to remove an element from a random location in an array, so `Access.pop/2` (and returning `:pop` from `Access.get_and_update/3` ) are not supported by Arrays.Implementations.MapArray. If you want to remove the last element, use `Arrays.extract/1`.

iex> arr2 = Arrays.new([10, 20, 30])
iex> {:ok, {value, arr2}} = Arrays.extract(arr2)
iex> value
30
iex> arr2
#Arrays.Implementations.MapArray<[10, 20]>

square-bracket access, get_in, put_in and update_in are very fast operations. Unless pop/pop_in is used for the last element in the array, is a very slow operation, as it requires moving of all elements after the given index in the array.

Both positive indexes (counting from zero) and negative indexes (-1 is the last element, -2 the second-to-last element, etc.) are supported.

However, if positive_index > Arrays.size(array) or negative_index < -Arrays.size(array), an ArgumentError is raised (when trying to put a new value), or :error is returned when fetching a value:

iex> arr = Arrays.new([1,2,3,4])
iex> put_in(arr[4], 1234)
** (ArgumentError) argument error

iex> arr = Arrays.new([1,2,3,4])
iex> put_in(arr[-5], 100)
** (ArgumentError) argument error

iex> arr = Arrays.new([1,2,3,4])
iex> Access.fetch(arr, 4)
:error
iex> Access.fetch(arr, -5)
:error
iex> arr[4]
nil
iex> arr[-5]
nil

iex> arr = Arrays.new([1,2,3,4])
iex> update_in(arr[8], fn x -> x * 2 end)
** (ArgumentError) argument error

iex> arr = Arrays.new([1,2,3,4])
iex> update_in(arr[-8], fn x -> x * 2 end)
** (ArgumentError) argument error

Insertable

iex> arr = Arrays.new()
iex> {:ok, arr} = Insertable.insert(arr, 42)
iex> {:ok, arr} = Insertable.insert(arr, 100)
iex> arr
#Arrays.Implementations.MapArray<[42, 100]>

Extractable

iex> Extractable.extract(Arrays.new())
{:error, :empty}
iex> {:ok, {3, arr}} = Extractable.extract(Arrays.new([1, 2, 3]))
iex> arr
#Arrays.Implementations.MapArray<[1, 2]>

FunLand.Reducible

Note: FunLand is an optional dependency of this library.

iex> Arrays.new([1,2,3,4]) |> FunLand.reduce(0, &(&1+&2))
10

FunLand.Mappable

iex> Arrays.new([1, 2, 3, 4]) |> FunLand.Mappable.map(fn x -> x * 2 end)
#Arrays.Implementations.MapArray<[2, 4, 6, 8]>

Arrays vs Lists

Elixir widely uses List as default collection type. Compared to lists, Arrays have the folowing differences:

  • Arrays keep track of their size. The size of a list needs to be computed.
  • Arrays allow fast¹ element indexing. Indexing later elements in a list slows down linearly in the size of the list.
  • Arrays allow fast slicing. For lists, this slows down the further away from the head of the list we are.
  • Pushing a single element to the end of an array is fast¹. Pushing a single element to the end of a list is very slow (the whole list needs to be copied), taking linear time.
  • Pushing a single element to the start of an array is slow, taking linear time (the whole array needs to be moved around). Pushing a single element to the head of a list is fast, taking constant time.
  • Concatenating arrays takes time proportional to the size of the second array (individual elements are pushed to the end). Concatenating two lists takes time proportional to the length of the first list. This means that repeated appending
  • Arrays are always well-formed. In certain cases, Lists are allowed to be improper.
  • Many common operations in Elixir transform an enumerable into a list automatically. Arrays are made using Arrays.new/0, Arrays.new/1 Arrays.empty/0, the into: option on a for, or Enum.into.

¹: Depending on the implementation, 'fast' is either O(1) (constant time, regardless of array size) or O(log(n)) (logarithmic time, becoming a constant amount slower each time the array doubles in size.)

The linear time many operations on lists take, means that the operation becomes twice as slow when the list doubles in size.

Implementing a new Array type

To add array-functionality to a custom datastructure, you'll need to implement the Arrays.Protocol.

Besides these, you probably want to implement the above-mentioned protocols as well. You can look at the source code of Arrays.CommonProtocolImplementations for some hints as to how those protocols can be easily implemented, as many functions can be defined as simple wrappers on top of the functions that Arrays.Protocol itself already provides.

Summary

Types

Any datatype implementing the Arrays.Protocol.

An array of elements of type element.

An array index can be either a nonnegative index (up to the size of the array), or a negative index (then we count backwards from the size.)

Type of the kind of value stored in the array. In practice, arrays can store anything so this is an alias for any.

Functions

Appends ('pushes') a single element to the end of the array.

Turns an array of arrays (or other enumerable of enumerables) into a single array.

Returns an array where all elements of right are added to the end of left.

Creates a new, empty, array.

Extracts ('pops') a single element from the end of the array.

Retrieves the value stored in array of the element at index.

Maps a function over an array, returning a new array.

Creates a new, empty array with default options.

Creates a new array, receiving its elements from the given Enumerable, with default options.

Creates a new array, receiving its elements from the given Enumerable, with the given options.

Reduce an array to a single value, by calling the provided accumulation function for each element, left-to-right.

Reduce an array to a single value, by calling the provided accumulation function for each element, right-to-left.

Replaces the element in array at index with value.

Changes the size of the array.

The number of elements in the array.

Returns a sub-array of the given array by index_range.

Returns a sub-array of the given array, from start_index (zero-based) with amount number of elements if available.

Transforms the array into a list.

Types

@type array() :: Arrays.Protocol.t()

Any datatype implementing the Arrays.Protocol.

Link to this type

array(_element)

View Source (since 2.1.0)
@type array(_element) :: array()

An array of elements of type element.

This type is equivalent to array/0 but is especially useful for documentation.

For example, imagine you define a function that expects an array of integers and returns an array of strings:

@spec integers_to_strings(Arrays.array(integer())) :: Arrays.array(String.t())
def integers_to_strings(integers) do
  Arrays.map(integers, &Integer.to_string/1)
end
@type index() :: Arrays.Protocol.index()

An array index can be either a nonnegative index (up to the size of the array), or a negative index (then we count backwards from the size.)

@type value() :: Arrays.Protocol.value()

Type of the kind of value stored in the array. In practice, arrays can store anything so this is an alias for any.

Functions

@spec append(array(), item :: any()) :: array()

Appends ('pushes') a single element to the end of the array.

iex> Arrays.new([1, 2, 3]) |> Arrays.append(4)
#Arrays.Implementations.MapArray<[1, 2, 3, 4]>

See also extract/1.

Link to this function

concat(enumerable_of_enumerables)

View Source (since 1.1.0)
@spec concat(Enumerable.t()) :: array()

Turns an array of arrays (or other enumerable of enumerables) into a single array.

iex> arr = Arrays.new([1, 2, 3])
iex> Arrays.concat([arr, arr, arr])
#Arrays.Implementations.MapArray<[1, 2, 3, 1, 2, 3, 1, 2, 3]>

iex> Arrays.concat([])
#Arrays.Implementations.MapArray<[]>

See also concat/2.

Link to this function

concat(left, right)

View Source (since 1.1.0)
@spec concat(array(), array() | Enumerable.t()) :: array()

Returns an array where all elements of right are added to the end of left.

left should be an array. right can be either an array or any other enumerable.

Takes time proportional to the number of elements in right. Essentially, each element in right is appended to left in turn.

iex> Arrays.new([1, 2, 3]) |> Arrays.concat(Arrays.new([4, 5, 6]))
#Arrays.Implementations.MapArray<[1, 2, 3, 4, 5, 6]>

iex> Arrays.new([1, 2, 3]) |> Arrays.concat((1..10))
#Arrays.Implementations.MapArray<[1, 2, 3, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]>

Creates a new, empty, array.

iex> Arrays.empty()
#Arrays.Implementations.MapArray<[]>

Options

  • implementation: Module name of array-implementation to use.

  • When not specified, will use the implementation which is configured in :arrays, :default_array_implementation,

  • When no configuration is specified either, Elixir.Arrays.Implementations.MapArray will be used by default.

    iex> Arrays.empty([implementation: Arrays.Implementations.MapArray])
    #Arrays.Implementations.MapArray<[]>
    
    iex> Arrays.empty([implementation: Arrays.Implementations.ErlangArray])
    #Arrays.Implementations.ErlangArray<[]>

Any other option is passed on to the particular array implementation. Not all array implementations recognize all options. However, the following two options are very common (and supported by both built-in implementations, Arrays.Implementations.ErlangArray and Arrays.Implementations.MapArray):

  • default: Value that empty elements should start with. (Default: nil)
  • size: Size of the array at start. (Default: 0)

Using the MapArray

iex> Arrays.empty([default: 42, size: 5, implementation: Arrays.Implementations.MapArray])
#Arrays.Implementations.MapArray<[42, 42, 42, 42, 42]>

Using the ErlangArray

iex> Arrays.empty([default: "Empty" , size: 1, implementation: Arrays.Implementations.ErlangArray])
#Arrays.Implementations.ErlangArray<["Empty"]>
@spec extract(array()) :: {:ok, {item :: any(), array()}} | {:error, :empty}

Extracts ('pops') a single element from the end of the array.

Returns {:ok, item_that_was_removed, array_without_item} if the array was non-empty. When called on an empty array, {:error, :empty} is returned.

iex> {:ok, {elem, arr}} = Arrays.new([1,2,3,4]) |> Arrays.extract()
iex> elem
4
iex> arr
#Arrays.Implementations.MapArray<[1, 2, 3]>

iex> Arrays.new([]) |> Arrays.extract()
{:error, :empty}

See also append/2.

@spec get(array(), index()) :: any()

Retrieves the value stored in array of the element at index.

Array indexes start at zero.

iex> Arrays.new([3, 6, 9]) |> Arrays.get(0)
3

iex> Arrays.new([3, 6, 9]) |> Arrays.get(1)
6

As Array types also implement the Access behaviour, the [] (square-bracket) syntactic sugar can also be used:

iex> myarray = Arrays.new([2, 4, 8])
iex> myarray[0]
2
iex> myarray[1]
4

Negative indexes

It is also possible to use negative indexes, to read elements starting from the right side of the array. For example, index -1 works equivalently to size - 1, if your array has size elements.

iex> names = Arrays.new(["Alice", "Bob", "Charlie", "David"])
iex> Arrays.get(names, -2)
"Charlie"
iex> names[-1]
"David"
@spec map(array(), (current_value :: value() -> updated_value :: value())) :: array()

Maps a function over an array, returning a new array.

iex> Arrays.new([1,2,3]) |> Arrays.map(fn val -> val * 2 end)
#Arrays.Implementations.MapArray<[2, 4, 6]>
@spec new() :: array()

Creates a new, empty array with default options.

iex> Arrays.new()
#Arrays.Implementations.MapArray<[]>
@spec new(Enum.t()) :: array()

Creates a new array, receiving its elements from the given Enumerable, with default options.

Link to this function

new(enumerable, options)

View Source
@spec new(
  Enum.t(),
  keyword()
) :: array()

Creates a new array, receiving its elements from the given Enumerable, with the given options.

Which options are supported depends on the type of array.

iex> Arrays.new([1, 2, 3])
#Arrays.Implementations.MapArray<[1, 2, 3]>

iex> Arrays.new(["Hello"])
#Arrays.Implementations.MapArray<["Hello"]>
@spec reduce(array(), acc :: any(), (item :: any(), acc :: any() -> any())) :: array()

Reduce an array to a single value, by calling the provided accumulation function for each element, left-to-right.

If the array is empty, the accumulator argument acc is returned as result immediately. Otherwise, the function is called on all elements in the array, in order, with acc as second argument. The result of each of these function calls creates the new accumulator passed to the next invocation.

iex> Arrays.new([1, 2, 3]) |> Arrays.reduce(0, fn val, sum -> sum + val end)
6

iex> Arrays.new(["the", "quick", "brown", "fox"]) |> Arrays.reduce("", fn val, result -> result <> " " <> val end)
" the quick brown fox"

iex> Arrays.new([]) |> Arrays.reduce(1234, fn val, mul -> mul * val end)
1234

See also reduce_right/3.

Link to this function

reduce_right(array, acc, fun)

View Source
@spec reduce_right(array(), acc :: any(), (acc :: any(), item :: any() -> any())) ::
  array()

Reduce an array to a single value, by calling the provided accumulation function for each element, right-to-left.

If the array is empty, the accumulator argument acc is returned as result immediately. Otherwise, the function is called on all elements in the array, in reverse (right-to-left) order, with acc as first argument. The result of each of these function calls creates the new accumulator passed to the next invocation.

iex> Arrays.new([1, 2, 3]) |> Arrays.reduce_right(0, fn sum, val -> sum + val end)
6

iex> Arrays.new(["the", "quick", "brown", "fox"]) |> Arrays.reduce_right("", fn result, val -> result <> " " <> val end)
" fox brown quick the"

iex> Arrays.new([]) |> Arrays.reduce_right(1234, fn mul, val -> mul * val end)
1234

See also reduce/3.

Link to this function

replace(array, index, value)

View Source
@spec replace(array(), index(), value :: any()) :: array()

Replaces the element in array at index with value.

iex> Arrays.new([4, 5, 6]) |> Arrays.replace(1, 69)
#Arrays.Implementations.MapArray<[4, 69, 6]>

Just like get/2, negative indices are supported.

iex> Arrays.new([7, 8, 9]) |> Arrays.replace(-1, 33)
#Arrays.Implementations.MapArray<[7, 8, 33]>
Link to this function

resize(array, size, default \\ nil)

View Source
@spec resize(array(), size :: non_neg_integer(), default :: any()) :: array()

Changes the size of the array.

When the array becomes larger, new elements at the end will al receive the default value. When the array becomes smaller, elements larger than the new size will be dropped.

iex> Arrays.new([1, 2, 3]) |> Arrays.resize(6)
#Arrays.Implementations.MapArray<[1, 2, 3, nil, nil, nil]>

iex> Arrays.new([1, 2, 3]) |> Arrays.resize(5, 42)
#Arrays.Implementations.MapArray<[1, 2, 3, 42, 42]>

iex> Arrays.new([1, 2, 3]) |> Arrays.resize(1)
#Arrays.Implementations.MapArray<[1]>

iex> Arrays.new([9, 8, 7]) |> Arrays.resize(0)
#Arrays.Implementations.MapArray<[]>

iex> Arrays.new([1, 2, 3]) |> Arrays.resize(3)
#Arrays.Implementations.MapArray<[1, 2, 3]>

See also size/1.

@spec size(array()) :: non_neg_integer()

The number of elements in the array.

Looking up the size of an array is fast: this function runs in constant time.

iex> Arrays.new([2, 4, 6]) |> Arrays.size()
3

iex> Arrays.new([]) |> Arrays.size()
0

See also resize/2.

Link to this function

slice(array, index_range)

View Source (since 1.1.0)
@spec slice(array(), Range.t()) :: array()

Returns a sub-array of the given array by index_range.

index_range must be a Range. Given an array, it drops elements before index_range.first (zero-based), then it takes elements until element index_range.last (inclusively).

Indexes are normalized, meaning that negative indexes will be counted from the end (for example, -1 means the last element of the array).

If index_range.last is out of bounds, then it is assigned as the index of the last element.

If the normalized index_range.first is out of bounds of the given array, or if it is is greater than the normalized index_range.last, then an empty array is returned.

iex> Arrays.slice(Arrays.new([1, 2, 3, 4, 5, 6]), 2..4)
#Arrays.Implementations.MapArray<[3, 4, 5]>

iex> Arrays.slice(Arrays.new(1..100), 5..10)
#Arrays.Implementations.MapArray<[6, 7, 8, 9, 10, 11]>

iex> Arrays.slice(Arrays.new(1..10), 5..20)
#Arrays.Implementations.MapArray<[6, 7, 8, 9, 10]>

# last five elements (negative indexes)
iex> Arrays.slice(Arrays.new(1..30), -5..-1)
#Arrays.Implementations.MapArray<[26, 27, 28, 29, 30]>

If values are out of bounds, it returns an empty array:

iex> Arrays.slice(Arrays.new(1..10), 11..20)
#Arrays.Implementations.MapArray<[]>

# first is greater than last
iex> Arrays.slice(Arrays.new(1..10), 6..5)
#Arrays.Implementations.MapArray<[]>

See also slice/3.

This function is similar to Enum.slice/2, but will always return an array (whereas Enum.slice will return a list).

Slicing on arrays is significantly faster than slicing on plain lists or maps, as there is no need to iterate over all elements we're going to skip since we can index them directly.

Link to this function

slice(array, start_index, amount)

View Source (since 1.1.0)
@spec slice(array(), index(), non_neg_integer()) :: array()

Returns a sub-array of the given array, from start_index (zero-based) with amount number of elements if available.

Given an array, it skips elements right before element start_index; then, it takes amount of elements, returning as many elements as possible if there are not enough elements.

A negative start_index can be passed, which means the array is enumerated once and the index is counted from the end (for example, -1 starts slicing from the last element).

It returns an empty array if amount is 0 or if start_index is out of bounds.

iex> Arrays.slice(Arrays.new([1, 2, 3, 4, 5, 6]), 2, 4)
#Arrays.Implementations.MapArray<[3, 4, 5, 6]>

iex> Arrays.slice(Arrays.new([1, 2, 3, 4, 5, 6]), 10, 20)
#Arrays.Implementations.MapArray<[]>

iex> Arrays.slice(Arrays.new(1..100), 5, 10)
#Arrays.Implementations.MapArray<[6, 7, 8, 9, 10, 11, 12, 13, 14, 15]>

# amount to take is greater than the number of elements
iex> Arrays.slice(Arrays.new(1..10), 5, 100)
#Arrays.Implementations.MapArray<[6, 7, 8, 9, 10]>

iex> Arrays.slice(Arrays.new(1..10), 5, 0)
#Arrays.Implementations.MapArray<[]>

# using a negative start index
iex> Arrays.slice(Arrays.new(1..10), -6, 3)
#Arrays.Implementations.MapArray<[5, 6, 7]>

# out of bound start index (positive)
iex> Arrays.slice(Arrays.new(1..10), 10, 5)
#Arrays.Implementations.MapArray<[]>

# out of bound start index (negative)
iex> Arrays.slice(Arrays.new(1..10), -11, 5)
#Arrays.Implementations.MapArray<[]>

See also slice/2.

This function is similar to Enum.slice/3, but will always return an array (whereas Enum.slice will return a list).

Slicing on arrays is significantly faster than slicing on plain lists or maps, as there is no need to iterate over all elements we're going to skip since we can index them directly.

@spec to_list(array()) :: list()

Transforms the array into a list.

iex> Arrays.new(["Joe", "Mike", "Robert"]) |> Arrays.to_list
["Joe", "Mike", "Robert"]