Module Cf_deque

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.