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:
Arrays.Implementations.ErlangArray
wraps the Erlang:array
module, allowing this time-tested implementation to be used with all common Elixir protocols and syntactic sugar.Arrays.Implementations.MapArray
is a simple implementation that uses a map with sequential integers as keys.
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 outperformsErlangArray
andMapArray
.
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 arraysCollectable
: Creating arrays from collections- the
Access
behaviour: access a particular element using square brackets,put_in
etc.
From common container libraries:
Insertable
: Append a single item from the end of an arrayExtractable
: Take a single item from the end of an arrayFunLand.Mappable
: Map a function over each element in the array, creating a new array with the resultsFunLand.Reducible
: Reduce an array to a single value.
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
, theinto:
option on afor
, orEnum.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
.
@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
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
.
@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
.
@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"]>
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
.
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"
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<[]>
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.
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"]>
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
.
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
.
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]>
@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
.
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.
@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.
Transforms the array into a list.
iex> Arrays.new(["Joe", "Mike", "Robert"]) |> Arrays.to_list
["Joe", "Mike", "Robert"]