blob: ebc3872abf7c43a83e9220840d2f7ed00363066f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
(************************************************************************)
(* v * The Coq Proof Assistant / The Coq Development Team *)
(* <O___,, * INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2012 *)
(* \VV/ **************************************************************)
(* // * This file is distributed under the terms of the *)
(* * GNU Lesser General Public License Version 2.1 *)
(************************************************************************)
(** * Purely functional, double-ended queues *)
(** This module implements the banker's deque, from Okasaki. Most operations are
amortized O(1). *)
type +'a t
exception Empty
(** {5 Constructor} *)
val empty : 'a t
(** The empty deque. *)
(** {5 Left-side operations} *)
val lcons : 'a -> 'a t -> 'a t
(** Pushes an element on the left side of the deque. *)
val lhd : 'a t -> 'a
(** Returns the leftmost element in the deque. Raises [Empty] when empty. *)
val ltl : 'a t -> 'a t
(** Returns the left-tail of the deque. Raises [Empty] when empty. *)
(** {5 Right-side operations} *)
val rcons : 'a -> 'a t -> 'a t
(** Same as [lcons] but on the right side. *)
val rhd : 'a t -> 'a
(** Same as [lhd] but on the right side. *)
val rtl : 'a t -> 'a t
(** Same as [ltl] but on the right side. *)
(** {5 Operations} *)
val rev : 'a t -> 'a t
(** Reverse deque. *)
val length : 'a t -> int
(** Length of a deque. *)
val is_empty : 'a t -> bool
(** Emptyness of a deque. *)
val filter : ('a -> bool) -> 'a t -> 'a t
(** Filters the deque *)
|
