Is there a such thing as "unifiable data structures"? That is, data structures that have their normal operations with reasonable performance guarantees, but support efficient unification? What keywords should I be searching for?
-
-
Replying to @BrandonBloom
Maybe you're looking for "maximal sharing" and hash-consing because these can bring structural equality tests into O(1); used in term rewriting for theorem provers. Maximal sharing data structures are a branch of persistent data structures, due to the required immutability.
1 reply 0 retweets 2 likes -
Replying to @jurgenvinju
I'm familiar with maximal sharing and it's definitely a relevant technique, but I want something more. Consider a hash table with unknown values or a vector with holes in it. Can these permit unify operations? Still have efficient lookup? Concat? push/pop? etc.
1 reply 0 retweets 2 likes -
Replying to @BrandonBloom
Mmmm.. interesting. Every studied Steven Ekers' work on pattern matching modulo associativity and commutativity and idempotency? An ACI cons tree _is_ a set. Good reads! Maybe relevant; how to efficiently (and safely) backtrack, via Pierre Etienne Moreau's backtracking library.
2 replies 0 retweets 1 like
Interesting, I may take a peek at that.
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.