module Cf_deque: sig .. end
A functional persistent double-ended catenable deque, with Oavg(1) cost
for every operation. Internally, this is a recursive data structure with
height O(log N).
type +'a t
The abstract type of a deque.
val nil : 'a t
The empty deque.
val empty : 'a t -> bool
Returns true if the deque is the empty deque.
module type Direction_T = sig .. end
Functions for operations on one of the two ends of a deque.
module A: Direction_T
Operations on the left end of a deque.
module B: Direction_T
Operations on the right end of a deque.
val iterate : ('a -> unit) -> 'a t -> unit
iterate f d applies f to every element in d in left-to-right
order. Not tail recursive.
val predicate : ('a -> bool) -> 'a t -> bool
predicate f d returns true if the result of applying f to every
element in the deque d is true, or if d is the empty deque. The
order in which elements are applied is left to right. If f returns
false, then no more elements from d will be applied and the result
will be returned immediately. Not tail recursive.
val filter : ('a -> bool) -> 'a t -> 'a t
filter f d returns a new deque composed by applying f to every element
in d, including only those elements for which the result is true. The
function is applied to the elements in the deque in left-to-right order.
Not tail recursive.
val map : ('a -> 'b) -> 'a t -> 'b t
map f d returns a new deque composed by applying f to every element in
d in left-to-right order. Not tail recursive.
val optmap : ('a -> 'b option) -> 'a t -> 'b t
optmap f d returns a new deque composed by applying f to every element
in d in left-to-right order, including only those elements of d
for which f returns Some value. Not tail recursive.
val listmap : ('a -> 'b list) -> 'a t -> 'b t
listmap f d returns a new deque composed by applying f to every element
in d in left-to-right order, taking all the resulting lists of
elements in order. Not tail recursive.
val seqmap : ('a -> 'b Cf_seq.t) -> 'a t -> 'b t
seqmap f d returns a new deque composed by applying f to every element
in d in left-to-right order, taking all the resulting sequences of
elements in order. Not tail recursive.
val partition : ('a -> bool) -> 'a t -> 'a t * 'a t
partition f s returns two deques. The first is the deque of
elements in d for which applying f results in true, and the second
is the deque of elements for which applying f results in false. The
elements are applied in left-to-right order.
val length : 'a t -> int
length d computes the number elements contained in the deque d. Not
tail recursive.
val catenate : 'a t -> 'a t -> 'a t
catenate d1 d2 returns a new deque composed by joining the right end of
d1 to the left end of d2. The average cost is constant. Not
tail-recursive.