# 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.