hegg

Fast equality saturation in Haskell (by alt-romes)

Hegg Alternatives

Similar projects and alternatives to hegg

NOTE: The number of mentions on this list indicates mentions on common posts plus user suggested alternatives. Hence, a higher number means a better hegg alternative or higher similarity.

hegg reviews and mentions

Posts with mentions or reviews of hegg. We have used some of these posts to build our list of alternatives and similar projects. The last one was on 2022-08-26.
  • [ANN] E-graphs and equality saturation: hegg 0.1
    3 projects | /r/haskell | 26 Aug 2022
  • Ask HN: What are some 'cool' but obscure data structures you know about?
    54 projects | news.ycombinator.com | 21 Jul 2022
    Equality graphs (e-graphs) for theorem proving and equality saturation and other equality-related things.

    They're awesome data structures that efficiently maintain a congruence relation over many expressions

    > At a high level, e-graphs extend union-find to compactly represent equivalence classes of expressions while maintaining a key invariant: the equivalence relation is closed under congruence.

    e.g. If I were to represent "f(x)" and "f(y)" in the e-graph, and then said "x == y" (merged "x" and "y" in the e-graph), then the e-graph, by congruence, would be able to tell me that "f(x) == f(y)"

    e.g. If I were to represent "a(2/2)", in the e-graph, then say "2/2 == 1", and "x1 == x", by congruence the e-graph would know "a*(2/2) == a" !

    The most recent description of e-graphs with an added insight on implementation is https://arxiv.org/pdf/2004.03082.pdf to the best of my knowledge.

    P.S: I'm currently implementing them in Haskell https://github.com/alt-romes/hegg

Stats

Basic hegg repo stats
3
72
7.5
5 months ago

Sponsored
SaaSHub - Software Alternatives and Reviews
SaaSHub helps you find the best software and product alternatives
www.saashub.com