A polymorphic data structure parametrized by 'a
to represent lists of elements of
'a
while supporting constant time append operations.
One example of use is to manipulate a decorated text represented as a sequence of words. Eventually we are interested in producing the concatenation of all the word in some form, but we do not want to pay the allocation costs of buildings intermediate string concatenations.
This module is a generalization of the Rope
module. Essentially:
type Rope.t = string Appendable_list.t
The following operations all run in constant time:
empty
, of_list
, singleton
, append
, concat
, add_front
, add_back
to_sequence
builds a sequence where access to the next element has an amortized
constant time.
All traversal operations such as iter
and fold
are tail recursive.
The monad exported by the module is semantically the same than the one in List. That
is: bind t f
applies f
to each element of t
and append the resulting list
respecting the order in which the elements appear in t
.
A monad is an abstraction of the concept of sequencing of computations. A value of type 'a monad represents a computation that returns a value of type 'a.
return v
returns the (trivial) computation that returns v.
Checks whether the provided element is there, using polymorphic compare if equal
is not provided
fold t ~init ~f
returns f (... f (f (f init e1) e2) e3 ...) en
, where e1..en
are the elements of t
Returns true
if and only if there exists an element for which the provided
function evaluates to true
. This is a short-circuiting operation.
Returns true
if and only if the provided function evaluates to true
for all
elements. This is a short-circuiting operation.
Returns the number of elements for which the provided function evaluates to true.
Returns as an option
the first element for which f
evaluates to true.
Returns the first evaluation of f
that returns Some
, and returns None
if there
is no such element.
Returns a minimum (resp maximum) element from the collection using the provided
cmp
function, or None
if the collection is empty. In case of a tie, the first
element encountered while traversing the collection is returned. The implementation
uses fold
so it has the same complexity as fold
.