package fix

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

Install

Dune Dependency

Authors

Maintainers

Sources

archive.tar.gz
md5=2a4afa633128c5010677222f7b3c9451
sha512=30d446ba6c19aef78b52d9831eb26f8f6ac10e88bd1eff36d16fbbfb32278b2637e31e63a160aec4abbbfdb1e7612ed25d68c936f4cbf2073e51d713ff3a8adf

Description

Published: 16 May 2023

README

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.

Dependencies (2)

  1. dune >= "1.3"
  2. ocaml >= "4.03"

Dev Dependencies

None

Used by (10)

  1. feat < "20211224"
  2. feat-core
  3. karamel
  4. kremlin < "transition"
  5. mezzo
  6. ocamlformat >= "0.14.0" & < "0.25.1"
  7. ocamlformat-lib
  8. ocamlformat-rpc < "0.21.0"
  9. reason >= "3.6.0"
  10. refl

Conflicts

None