package orsetto

  1. Overview
  2. Docs
package orsetto
Legend:
Library
Module
Module type
Parameter
Class
Class type

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.

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct