Module Cf_deque

Functional deque.

Overview

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). (Note: if the deque is not the product of concatenation, then it is a pure data structure. Concatenation entails a lazy evaluation of the recursive join.)

Type
type +'a t

The abstract type of a deque.

Interface
val nil : 'a t

The empty deque.

val one : 'a -> 'a t

Create a deque containing one element.

val empty : 'a t -> bool

Returns true if the deque is the empty deque.

module type Direction = sig ... end

Functions for operations on one of the two ends of a deque.

module A : Direction

Operations on the left end of a deque.

module B : Direction

Operations on the right end of a deque.

val catenate : 'a t -> 'a t -> 'a t

catenate q1 q2 returns a new deque composed by joining the right end of q1 to the left end of q2. The average cost is constant.