Hallux.Seq (Hallux v1.2.0) View Source
A representation of a sequence of values of type a, allowing access to the ends in constant time, and append and split in time logarithmic in the size of the smaller piece. (taken from here)
Supports efficient random access like accessing the nth element.
A sequence can be constructed using Hallux.Seq.new/0:
iex> new()
#HalluxSeq<[]>Elements can be inserted at the left end using Hallux.Seq.cons/2:
iex> new(1..4) |> cons(0)
#HalluxSeq<[0, 1, 2, 3, 4]>Or they can be inserted at the right end using Hallux.Seq.snoc/2:
iex> new(1..4) |> snoc(0)
#HalluxSeq<[1, 2, 3, 4, 0]>Accessing a single element is cheap:
iex> new(0..10) |> Enum.at(5)
5Link to this section Summary
Functions
(O(log(min(n1,n2)))). Concatenates two sequences.
(O(1)). Add an element to the left end of a sequence.
(O(log(min(i,n-i)))). Elements of a sequence after the first i.
(O(1)). Returns a new Seq.
(O(n)). Creates a Seq from an enumerable.
(O(n)). Creates a Seq from an enumerable via the transformation function.
(O(n)). Left-associative fold of the sequence.
(O(n)). Right-associative fold of the sequence.
(O(1)). Returns the number of elements in seq.
(O(log(min(i,n-i)))). Takes a slice from index i until index j
of the sequence.
(O(1)). Add an element to the right end of a sequence.
(O(log(min(i,n-i)))). Split a squence at a given position.
(O(log(min(i,n-i)))). The first i elements of a sequence.
(O(1)). Analyse the left end of a sequence.
(O(1)). Analyse the right end of a sequence.
Link to this section Types
Specs
Specs
t(value) :: %Hallux.Seq{
t: Hallux.Internal.FingerTree.t(Hallux.Internal.Elem, value)
}
Specs
value() :: term()
Link to this section Functions
Specs
(O(log(min(n1,n2)))). Concatenates two sequences.
Examples
iex> concat(new(), new(1..4))
#HalluxSeq<[1, 2, 3, 4]>
iex> concat(new(1..4), new())
#HalluxSeq<[1, 2, 3, 4]>
iex> concat(new(1..4), new(5..8))
#HalluxSeq<[1, 2, 3, 4, 5, 6, 7, 8]>
iex> concat(new(5..8), new(1..4))
#HalluxSeq<[5, 6, 7, 8, 1, 2, 3, 4]>Specs
(O(1)). Add an element to the left end of a sequence.
Examples
iex> cons(new(1..3), 0)
#HalluxSeq<[0, 1, 2, 3]>Specs
drop(t(val), non_neg_integer()) :: t(val) when val: value()
(O(log(min(i,n-i)))). Elements of a sequence after the first i.
If i is negative, drop(s, i) yields the whole sequence.
If the sequence contains fewer than i elements, the empty sequence
is returned.
Examples
iex> drop(new(1..10), 4)
#HalluxSeq<[5, 6, 7, 8, 9, 10]>Specs
new() :: t()
(O(1)). Returns a new Seq.
Examples
iex> new()
#HalluxSeq<[]>Specs
(O(n)). Creates a Seq from an enumerable.
Examples
iex> new([1, 2, 3], & &1 * 2)
#HalluxSeq<[2, 4, 6]>Specs
(O(n)). Creates a Seq from an enumerable via the transformation function.
Examples
iex> new([:b, :a, 3])
#HalluxSeq<[:b, :a, 3]>Specs
(O(n)). Left-associative fold of the sequence.
Reduces seq from left to right using acc as initial value and
rfn as the binary operator.
Examples
iex> reducel(new(1..10), [], fn x, acc -> [x | acc] end)
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]Specs
(O(n)). Right-associative fold of the sequence.
Reduces seq from right to left using acc as initial value and
rfn as the binary operator.
Examples
iex> reducer(new(1..10), [], fn x, acc -> [x | acc] end)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]Specs
size(t()) :: non_neg_integer()
(O(1)). Returns the number of elements in seq.
Examples
iex> size(new(1..3))
3
iex> size(new())
0Specs
(O(log(min(i,n-i)))). Takes a slice from index i until index j
of the sequence.
Examples
iex> slice(new(), 1..4)
#HalluxSeq<[]>
iex> slice(new(0..4), 0..10)
#HalluxSeq<[0, 1, 2, 3, 4]>
iex> slice(new(1..10), -5..-2)
#HalluxSeq<[6, 7, 8, 9]>
iex> slice(new(0..10), 4..7)
#HalluxSeq<[4, 5, 6, 7]>Specs
(O(1)). Add an element to the right end of a sequence.
Examples
iex> snoc(new(1..3), 4)
#HalluxSeq<[1, 2, 3, 4]>Specs
(O(log(min(i,n-i)))). Split a squence at a given position.
Examples
iex> {left, right} = split_at(new(0..8), 6)
iex> left
#HalluxSeq<[0, 1, 2, 3, 4, 5]>
iex> right
#HalluxSeq<[6, 7, 8]>Specs
take(t(val), non_neg_integer()) :: t(val) when val: value()
(O(log(min(i,n-i)))). The first i elements of a sequence.
If i is negative, take(s, i) yields the empty sequence.
If the sequence contains fewer than i elements, the whole sequence
is returned.
Examples
iex> take(new(1..10), 4)
#HalluxSeq<[1, 2, 3, 4]>Specs
(O(1)). Analyse the left end of a sequence.
Returns nil if empty. Otherwise, returns a tuple with the leftmost element and a new sequence with that element removed.
Examples
iex> view_l(new())
nil
iex> {1, rest} = view_l(new(1..10))
iex> rest
#HalluxSeq<[2, 3, 4, 5, 6, 7, 8, 9, 10]>Specs
(O(1)). Analyse the right end of a sequence.
Returns nil if empty. Otherwise, returns a tuple with the rightmost element and a new sequence with that element removed.
Examples
iex> view_r(new())
nil
iex> {rest, 10} = view_r(new(1..10))
iex> rest
#HalluxSeq<[1, 2, 3, 4, 5, 6, 7, 8, 9]>