egraphs-good / egglog

egraphs + datalog!
https://egraphs-good.github.io/egglog/
MIT License
458 stars 54 forks source link

Add multiset-sum primitive #471

Closed RiscInside closed 1 week ago

RiscInside commented 1 week ago

multiset-sum combines values from both multisets together, allowing for rules such as

(rewrite (Add (Sum  xs) (Sum ys)) (Sum (multiset-sum xs ys)))

In my understanding, this primitive is crucial for modelling associative + commutative operations with multisets, but I might be missing something.

codspeed-hq[bot] commented 1 week ago

CodSpeed Performance Report

Merging #471 will not alter performance

Comparing RiscInside:multiset-new-primitives (53c8f01) with main (2c8d947)

Summary

✅ 8 untouched benchmarks

RiscInside commented 1 week ago

I did also consider adding other operations (union, intersection, and difference), but I don't immediately see a use-case for any of them (intersection/union also have a problem of being fragile to new equalities, e.g. {e1, e1, e2} union {e1, e2, e2} before and after e1 and e2 merge).

saulshanabrook commented 1 week ago

Sounds good.

Multiset should work with rebuilding canonicalization, but it would be good to add test for this (not related to the work in this PR necessarily). Meaning that if you have {a: 1, b: 1} and then a and b are unioned, the resulting multiset should be {(a | b): 2}. That is handled in canonicalize.