hegg: Fast equality saturation in Haskell

Fast equality saturation and equality graphs based on "egg: Fast and Extensible Equality Saturation" and "Relational E-matching".

This package provides e-graphs (see Data.Equality.Graph), a data structure which efficiently represents a congruence relation over many expressions

Secondly, it provides functions for doing equality saturation (see Data.Equality.Saturation), an optimization/term-rewriting technique that applies rewrite rules non-destructively to an expression represented in an e-graph until saturation, and then extracts the best representation.

Equality matching (see Data.Equality.Matching) is done as described in "Relational E-Matching"

For a walkthrough of writing a simple symbolic simplification program see the hegg symbolic tutorial.

Additional information can be found in the README.

• Data
  • Equality
    • Data.Equality.Analysis
    • Data.Equality.Extraction
    • Data.Equality.Graph
      • Data.Equality.Graph.Classes
        • Data.Equality.Graph.Classes.Id
      • Data.Equality.Graph.Dot
      • Data.Equality.Graph.Lens
      • Data.Equality.Graph.Monad
      • Data.Equality.Graph.Nodes
      • Data.Equality.Graph.ReprUnionFind
    • Data.Equality.Language
    • Data.Equality.Matching
      • Data.Equality.Matching.Database
      • Data.Equality.Matching.Pattern
    • Data.Equality.Saturation
      • Data.Equality.Saturation.Rewrites
      • Data.Equality.Saturation.Scheduler
    • Data.Equality.Utils
      • Data.Equality.Utils.IntToIntMap