package fix

  1. Overview
  2. Docs
Algorithmic building blocks for memoization, recursion, and more

Install

Dune Dependency

Authors

Maintainers

Sources

archive.tar.gz
md5=0f633b0cdd5faba947d11da113c81fcc
sha512=6817ce5c79e0c957ef01def7b89059262414af8e8bc7ffafef96430cfb1d78e32350fe7a57e118e68727962338c4fc45023cddb1c4db8c344910d6c8c1873a18

README.md.html

Fix: memoization and fixed points made easy

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.

OCaml

Innovation. Community. Security.