A collection of algorithms implemented in OCaml.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Frédéric Bour af8eae4864 WIP: add Dset2, for incremental transformation of sequence of elements 5 months ago
baltree emergency fix in baltree 1 year ago
biarray implement Biarray 7 months ago
binpacking jbuild -> dune 1 year ago
countish add approximate frequency counts poc, inspired by https://github.com/shanemhansen/countish 3 years ago
dbseq Dbseq is covariant 5 months ago
doc documentation index 4 years ago
doubledouble Doubledouble: remove references to Pervasives 1 year ago
dset WIP: add Dset2, for incremental transformation of sequence of elements 5 months ago
hll jbuild -> dune 1 year ago
jmphash jbuild -> dune 1 year ago
orderme jbuild -> dune 1 year ago
pcg jbuild -> dune 1 year ago
physh Require OCaml >= 4.04 9 months ago
strong remove Biarray from Strong, this will be reintroduced as a separate library 7 months ago
trope jbuild -> dune 1 year ago
valmari port valmari to strong library 9 months ago
.gitignore Port everything to dune 2 years ago
.travis.yml Add missing (but supported) versions of OCaml to the CI 8 months ago
CHANGES.md Add Dbseq 6 months ago
LICENSE switch license to ISC 4 years ago
Makefile jbuild -> dune 1 year ago
README.md describe the strong library 7 months ago
TODO Update TODO 7 months ago
dune-project remove META, jbuilder -> dune 1 year ago
grenier.opam describe the strong library 7 months ago


grenier — A collection of various algorithms in OCaml.

Licensed under ISC license.

baltree : Generic balanced-tree

A binary tree with smart constructors that ensure the resulting tree is balanced.

This data structure can be used as a primitive on top of which one can easily build balanced data structures, including but not limited to binary search trees.

For instance, implementing stdlib-like Set/Map is trivial and suffers only a ~5 % overhead (and one gains a O(1) length/cardinal operation).

trope : Track objects accross rope-like operations

This data structure allows efficient implementation of text markers for text editors (see Emacs Markers).

More generally it allows to track the movement of objects on a line where chunks are added and removed, with queries O(log n) amortized time.

Finally, it is persistent so you easily compare markers movement between different revisions.

orderme : Order-maintenance problem

See Order-maintenance problem for a detailed description of what this intent to solve.

Main algorithm follows the amortized solution from “Two Simplified Algorithms for Maintaining Order in a List”, Michael A. Bender, Richard Cole, Erik D. Demaine, Martín Farach-Colton, and Jack Zito..

A managed implementation provide finer integration with OCaml GC to collect items that are no longer reachable via the public API.

binpacking : Maxrects rectangle packing implementation

An implementation of Maxrects packing algorithm in 2D. This algorithm try to pack a maximum number of 2d boxes inside a 2d rectangle.

See Even More Rectangle Bin Packing

Useful for generating spritesheets, texture atlases, etc.

doubledouble : Floating points with around 107-bits precision

An implementation of double-double arithmetic.

Code is translated from DD by Martin Davis. See tsusiatsoftware for more information.

hll : HyperLogLog

An implementation of the HyperLogLog probabilistic cardinality estimator. See HyperLogLog.

jmphash : Jump consistent hashing

An implementation of “A Fast, Minimal Memory, Consistent Hash Algorithm” from John Lamping and Eric Veach.

physh : Physical hashtable

Hashtables indexing OCaml values by their physical indentities. A proof-of-concept, playing with the GC in tricky ways.

Its main purpose is to efficiently observe sharing, detect cycles, etc, in arbitrary OCaml values without having to stop and stay out of the OCaml runtime.

Can be used to experiment and learn about the GC but do expect bugs and don’t expect any kind of compatibility with future OCaml versions. (Would be nice to have proper upstream support for such feature though!)

strong : Some strongly typed primitives (typed equality, ordering, finite sets)

This library defines a few strongly typed idioms that are sometimes useful in OCaml codebase:

  • type-level equality and ordering
  • unhabitated type
  • an encoding of type-level naturals
  • finite sets (the set of numbers less than a given constant)

valmari : Valmari’s DFA minimization algorithm

An implementation of the algorithm desribed in Fast brief practical DFA minimization by Valmari et al.

The tests and some fixes come from WalkerCodeRanger/dfaMinimizationComparison, thanks!

pcg : PCG random generator

Playing with PCG generators in OCaml. Not even alpha, consider this doesn’t exist.