News for hackers. Stuff that matters.
Re:Ask HN: What are some cool but obscure data structures yo... by romes on Friday July 22, 2022 @04:01AM (#32189678)
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 "x*1 == 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

Re:Ask HN: What are some cool but obscure data structures yo... by gopiandcode on Friday July 22, 2022 @06:56AM (#32190621)
Shameless plug, I also maintain an OCaml implementation of egraphs (named ego) at https://github.com/verse-lab/ego

While the most popular implementation at the moment seems to be egg in Rust, I find that OCaml serves as a much more ergonomic environment for quickly prototyping out uses of egraphs in practice. As a bonus, ego also shares the same logical interface as egg itself, so once you've finalised your designs, you shouldn't have much trouble porting them to egg if you need the performance gains.

Re:Ask HN: What are some cool but obscure data structures yo... by smasher164 on Friday July 22, 2022 @10:30AM (#32192224)
I wonder if you could apply e-graphs to situations where the union-find data structure would be used, i.e. if there are any additional benefits gotten from the congruence relation.
Re:Ask HN: What are some cool but obscure data structures yo... by HelloNurse on Friday July 22, 2022 @11:24AM (#32192972)
More pointers and more processing in exchange for representing equivalence classes of many, often infinitely many graphs compactly and enumerating them efficiently. Usually not relevant when equivalence of simple nodes is the object.
Re:Ask HN: What are some cool but obscure data structures yo... by FnuGk on Friday July 22, 2022 @04:11AM (#32189740)
Isnt that the building blocks of logic based programming languages like Prolog?
Re:Ask HN: What are some cool but obscure data structures yo... by superlopuh on Friday July 22, 2022 @05:29AM (#32190183)
Yes, at least these egg-based projects are usign this idea, but it looks like it's just one of the options:

https://souffle-lang.github.io/docs.html http://www.philipzucker.com/souffle-egg4/ https://arxiv.org/pdf/2004.03082.pdf

Re:Ask HN: What are some cool but obscure data structures yo... by Twisol on Friday July 22, 2022 @05:08AM (#32190067)
I had a similar thought when I learned about e-graphs. I'm not sure yet, but I think congruence closure is a slightly different problem from the one Prolog unification solves. In particular, if you tell an e-graph that `f(x) = g(y)`, it will take you at your word -- while Prolog would give a unification error. (An e-graph should also handle `X = f(X)`, while this would fail Prolog's admittedly often-ignored occurs check.)