package grenier

  1. Overview
  2. Docs
A collection of various algorithms in OCaml

Install 

dune-project
 Dependency

github.com Readme Changelog Edit opam file Versions (7)

Authors

  1. F
    Frederic Bour <frederic.bour@lakaban.net>

Maintainers

  1. F
    Frederic Bour <frederic.bour@lakaban.net>

Sources

grenier-0.17.tbz
sha256=adce547fae9b5648d902d91173bb787466a197f81610b76757424ab33980e625
sha512=dccce42254660831fbd45129718ce01d2a4fcf10d05fa40f10eb3be4e5c94300af7235cc88c76b2e5aff7a02b8a1e8e6150d2d3376d8b630911d1dc6247b7df6

doc/grenier.dbseq/Dbseq/index.html

Module DbseqSource

Dbseq immutable sequence

Dbseq is a small data structure that offers operations halfway between a list and an immutable array. Most operations have a logarithmic cost. In practice, it is a log with base 4 and small constant factors.

This data structure is particularly suitable to associate metadata to variables in De-Bruijn notation (hence the name).

Sourcetype +'a t

Sequences with element of type 'a *

Sourceval empty : 'a t

The empty sequence

Sourceval cons : 'a -> 'a t -> 'a t

cons x xs adds element x at the beginning of sequence xs. x now has index 0 and xs's elements are shifted by 1. Worst-case cost is O(log n), though the amortized cost is O(1).

Sourceval get : int -> 'a t -> 'a

get i xs access the i'th element of xs in cost O(log i). In particular, access to recent elements is quasi constant.

The operation is only defined if 0 <= i < length xs, and will raise Not_found if i is out of bounds.

O(log i).

Sourceval set : int -> 'a -> 'a t -> 'a t

set i x xs update the i'th element of xs to value x in cost O(log i).

The operation is only defined if 0 <= i < length xs, and will raise Not_found if i is out of bounds.

O(log i).

Sourceval update : 'a t -> int -> ('a -> 'a) -> 'a t

update xs i f behaves like set i (f (get i xs)) xs.

O(log i).

Sourceval length : 'a t -> int

n = length xs is the number of elements in xs.

O(log n).

Sourceval is_empty : 'a t -> bool

is_empty t iff t = empty (equivalently length t = 0).

O(1).

Sourceval uncons : 'a t -> ('a * 'a t) option

Revert the effect of the last cons (with the same complexity).

Sourceval drop : int -> 'a t -> 'a t

drop n x removes n elements from x. Faster than uncons'ing n times. (TODO: determine complexity)

Sourceval to_seq : 'a t -> 'a Seq.t

Returns the sequence of elements, in order (get 0, get 1, ...). O(1) per element on average, O(log n) per element worst case.

Sourceval to_rev_seq : 'a t -> 'a Seq.t

Returns the sequence of elements, in reverse order (get (length - 1), get (length - 2), ...). O(1) per element on average, O(log n) per element worst case.