Frédéric Bour
60dfaff175

10 months ago  

balmap  2 years ago  
baltree  4 years ago  
biarray  3 years ago  
binder_introducer  10 months ago  
binpacking  2 years ago  
countish  6 years ago  
dbseq  2 years ago  
doc  6 years ago  
doubledouble  1 year ago  
fastdom  1 year ago  
hll  4 years ago  
jmphash  4 years ago  
orderme  4 years ago  
physh  3 years ago  
state_elimination  2 years ago  
strong  2 years ago  
trope  4 years ago  
valmari  1 year ago  
.gitignore  5 years ago  
.travis.yml  3 years ago  
CHANGES.md  10 months ago  
LICENSE  6 years ago  
Makefile  4 years ago  
README.md  10 months ago  
TODO  3 years ago  
duneproject  3 years ago  
grenier.opam  2 years ago 
README.md
grenier — A collection of various algorithms in OCaml.
Licensed under ISC license.
baltree : Generic balancedtree
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 stdliblike Set/Map is trivial and suffers only a ~5 % overhead (and one gains a O(1) length/cardinal operation).
balmap : Alternative to Map & Set implemented on top of baltree
These two modules can be used as a dropin replacement for Map
and Set
.
The performance characteristics are slightly different: cardinal
is now O(1),
some operations use that as a shortcut (compare
, subset
, ...).
In addition, the representation is exposed (the internal structure of the tree
can be pattern matched). It is protected by a private modifier, such that
invariants cannot be broken. However, custom operations are much easier to
implement (e.g. rank
to access the n'th element, which enables uniform
sampling in O(log n)).
binder introducer: transform graphs into trees by introducing binding nodes
A generic algorithm that turns a directed graph intro a tree. It finds where binding nodes should be introduced to make the resulting tree readable. The idea is described in this blog post.
For instance, this is useful to print cyclic values (see Cmon).
dbseq: fast sequence datastructure for DeBruijnindexed environments
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.
The name comes from the fact that the data structure is particularly suitable to associate metadata to variables in DeBruijn notation when traversing terms.
trope : Track objects accross ropelike 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 : Ordermaintenance problem
See Ordermaintenance 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 FarachColton, 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 107bits precision
An implementation of doubledouble 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 proofofconcept, 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!)
state elimination : convert an enfa to a regex
This library converts eNFA (including NFA and DFA) to regular expressions.
Unfortunately the regular expression is often of exponential size, unless you extend the language to allow sharing subexpressions (for instance with let binders).
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:
 typelevel equality and ordering
 unhabitated type
 an encoding of typelevel 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!
fastdom
An implementation of A Simple, Fast Dominance Algorithm by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy.