Arrays

hex.pm version.github/workflows/ci.yml

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.

Installation

Arrays is available in Hex and can be installed by adding arrays to your list of dependencies in mix.exs:

def deps do
[
  {:arrays, "~> 1.0.0"}
]
end

Documentation can be found at https://hexdocs.pm/arrays.

Using Arrays

The general idea is that 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, #{@default_array_implementation} 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.

Protocols

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

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())
    ##{@current_default_array}<["ERNIE", "BERT", "KERMIT"]>

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

Collectable

    iex> [10, 20, 30, 40] |> Enum.into(Arrays.new())
    ##{@current_default_array}<[10, 20, 30, 40]>

Access

    iex> arr = Arrays.new([1, 2, 3, 4])
    iex> arr = put_in(arr[2], 33)
    ##{@current_default_array}<[1, 2, 33, 4]>
    iex> arr = update_in(arr[1], (&(&1 * -2)))
    ##{@current_default_array}<[1, -4, 33, 4]>
    iex> arr = update_in(arr[-1], (&(&1 + 1)))
    ##{@current_default_array}<[1, -4, 33, 5]>
    iex> {33, arr} = pop_in(arr[-2])
    iex> arr
    ##{@current_default_array}<[1, -4, 5]>
    iex> {1, arr} = pop_in(arr[0])
    iex> arr
    ##{@current_default_array}<[-4, 5]>
    iex> {5, arr} = pop_in(arr[-1])
    iex> arr
    ##{@current_default_array}<[-4]>

    iex> arr2 = Arrays.new([10, 20, 30])
    iex> {20, arr2} = get_and_update_in(arr2[1], fn _ -> :pop end)
    iex> arr2
    ##{@current_default_array}<[10, 30]>

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:

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

    iex> arr = Arrays.new([1,2,3,4])
    iex> pop_in(arr[-5])
    ** (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 = 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
    ##{@current_default_array}<[42, 100]>

Extractable

    iex> Extractable.extract(Arrays.new())
    {:error, :empty}
    iex> {:ok, {3, arr}} = Extractable.extract(Arrays.new([1, 2, 3]))
    iex> arr
    ##{@current_default_array}<[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)
    ##{@current_default_array}<[2, 4, 6, 8]>

Arrays vs Lists

Elixir widely uses List as default collection type. Arrays have the folowing differences:

¹: 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, two things are required:

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 on top of the calls that the Arrays.Protocol protocol itself already provides.

Changelog