Published: 16 May 2023
Fix: memoization and fixed points made easy
fix is an OCaml library that helps with various algorithmic constructions that involve memoization, recursion, and numbering.
A few demos are provided:
brzsets 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.
cykpresents a CYK-style parsing algorithm as an instance of
Fixto perform certain static analyses of a context-free grammar; this includes computing nullability information and FIRST sets.
fibdefines Fibonacci's function in several different ways using the fixed-point combinators offered by
hcosets up simple-minded hash-consed trees using