fix

Algorithmic building blocks for memoization, recursion, and more
README

fix is an OCaml library that helps with various algorithmic
constructions that involve memoization, recursion, and numbering.

Documentation

See the documentation of the latest released
version
.

Demos

A few demos are provided:

  • brz sets up a hash-consed representation of regular
    expressions and shows how to convert a regular expression to a deterministic
    finite-state automaton by Brzozowski's method. This demo exploits many
    of the submodules listed above, and is accompanied with
    a commentary.

  • cyk presents a CYK-style parsing algorithm as an instance of
    Fix.

  • cfg uses Fix to perform certain static analyses of a
    context-free grammar; this includes computing nullability information and
    FIRST sets.

  • fib defines Fibonacci's function in several different ways
    using the fixed-point combinators offered by Memoize and Fix.

  • hco sets up simple-minded hash-consed trees
    using HashCons.

Install
Sources
archive.tar.gz
md5=48d8a5bdff23cf7fbf9288877df2b6aa
sha512=a851d8783c0c519c6e55359a5c471af433058872409c29a1a7bdfd0076813341ad2c0ebd1ce9e28bff4d4c729dfbc808c41c084fe12a42b45a2b5e391e77ccd2
Dependencies
dune
>= "1.3"
ocaml
>= "4.03"
Reverse Dependencies