Contents
- Compositions <A>
- Empty = new Compositions<A>(Seq<Node>())
- Tree
- WellFormed <MonoidEqA> ()
- Skip (int amount)
- Take <MonoidA> (int amount)
- TakeComposed <MonoidA> (int amount)
- SplitAt <MonoidA> (int i)
- Composed <MonoidA> ()
- Singleton (A value)
- Count ()
- FromList <MonoidA> (IEnumerable<A> ma)
- Equals (Compositions<A> b)
- Equals (object obj)
- == (Compositions<A> a, Compositions<A> b)
- != (Compositions<A> a, Compositions<A> b)
- GetHashCode ()
- ToSeq ()
- AsEnumerable ()
- GetEnumerator ()
- Node
- CompositionsExt
- Compositions
- wellFormed <MonoidEqA, A> (Compositions<A> ca)
- skip <A> (int amount, Compositions<A> compositions)
- take <MonoidA, A> (int amount, Compositions<A> compositions)
- takeComposed <MonoidA, A> (int amount, Compositions<A> compositions)
- splitAt <MonoidA, A> (int i, Compositions<A> c)
- composed <MonoidA, A> (Compositions<A> compositions)
- singleton <A> (A value)
- count <A> (Compositions<A> compositions)
- cons <MonoidA, A> (A x, Compositions<A> xs)
- fromList <MonoidA, A> (IEnumerable<A> ma)
struct Compositions <A> Source #
A compositions list or composition tree is a list data type where the elements are monoids, and the 'mconcat' of any contiguous sublist can be computed in logarithmic time.
A common use case of this type is in a wiki, version control system, or collaborative editor, where each change or delta would be stored in a list, and it is sometimes necessary to compute the composed delta between any two versions.
This version of a composition list is strictly biased to right-associativity, in that we only support efficient consing to the front of the list. This also means that the 'take' operation can be inefficient.
The append operation append(a, b) performs O(a log (a + b)) element compositions, so you want
the left-hand list a to be as small as possible.
Fields
field Compositions<A> Empty = new Compositions<A>(Seq<Node>()) Source #
Methods
method bool WellFormed <MonoidEqA> () Source #
Returns true if the given tree is appropriately right-biased.
method Compositions<A> Skip (int amount) Source #
Return the compositions list with the first k elements removed, in O(log k) time.
method Compositions<A> Take <MonoidA> (int amount) Source #
Return the compositions list containing only the first k elements
of the input. In the worst case, performs O(k log k) element compositions,
in order to maintain the right-associative bias. If you wish to run composed
on the result of take, use takeComposed for better performance.
method A TakeComposed <MonoidA> (int amount) Source #
Returns the composition of the first k elements of the compositions list, doing only O(log k) compositions.
Faster than simply using take and then composed separately.
method (Compositions<A> taken, Compositions<A> skipped) SplitAt <MonoidA> (int i) Source #
A convenience alias for 'take' and 'skip'
method A Composed <MonoidA> () Source #
Compose every element in the compositions list. Performs only O(log n) compositions.
method Compositions<A> Singleton (A value) Source #
Construct a compositions list containing just one element.
method Compositions<A> FromList <MonoidA> (IEnumerable<A> ma) Source #
Convert a compositions list into a list of elements. The other direction is provided in the 'Data.Foldable.Foldable' instance.This will perform O(n log n) element compositions.
method int GetHashCode () Source #
Get hash code
Parameters
| returns | ||
method IEnumerable<A> AsEnumerable () Source #
Convert to an enumerable
method IEnumerator<A> GetEnumerator () Source #
Get enumerator
class CompositionsExt Source #
class Compositions Source #
Methods
method bool wellFormed <MonoidEqA, A> (Compositions<A> ca) Source #
Returns true if the given tree is appropriately right-biased.
method Compositions<A> skip <A> (int amount, Compositions<A> compositions) Source #
Return the compositions list with the first k elements removed, in O(log k) time.
method Compositions<A> take <MonoidA, A> (int amount, Compositions<A> compositions) Source #
Return the compositions list containing only the first k elements
of the input. In the worst case, performs O(k log k) element compositions,
in order to maintain the right-associative bias. If you wish to run composed
on the result of take, use takeComposed for better performance.
method A takeComposed <MonoidA, A> (int amount, Compositions<A> compositions) Source #
Returns the composition of the first k elements of the compositions list, doing only O(log k) compositions.
Faster than simply using take and then composed separately.
method (Compositions<A> taken, Compositions<A> skipped) splitAt <MonoidA, A> (int i, Compositions<A> c) Source #
A convenience alias for 'take' and 'drop'
method A composed <MonoidA, A> (Compositions<A> compositions) Source #
Compose every element in the compositions list. Performs only O(log n) compositions.
method Compositions<A> singleton <A> (A value) Source #
Construct a compositions list containing just one element.
method int count <A> (Compositions<A> compositions) Source #
Get the number of elements in the compositions list, in O(log n) time.