[Haskell-cafe] Hashing over equivalence classes
Roman Cheplyaka
roma at ro-che.info
Mon Mar 16 05:59:15 EDT 2009
* Ryan Ingram <ryani.spam at gmail.com> [2009-03-14 11:36:33-0700]
> For the second case you might be able to come up with a commutative
> hash-combiner function for && and ||.
What a beautiful idea! I wish I thought of it myself.
> For the lambda-term situation, I can think of a couple ways to hash
> that give what you want.
>
> (1) Ignore variable names altogether while hashing; this gives you
> what you want but has the disadvantage that (\a b. a) and (\a b. b)
> hash to the same value.
> (2) Hash the term with de Bruijn indices. But this is the same as
> "hash the canonical element".
Thanks for the reference.
> I don't see that you have much other choice, though. Fortunately, due
> to laziness, hash . canonicalize should not have much worse space
> behavior than just hash.
>
> Did you have something else in mind?
Not yet.
> -- ryan
>
> On Sat, Mar 14, 2009 at 3:51 AM, Roman Cheplyaka <roma at ro-che.info> wrote:
> > Are there some known ways to define hashing (or any other) functions over
> > equivalence classes? I.e.
> >
> > a ~ b => hash(a) == hash(b)
> >
> > where (~) is some equivalence relation. For example, you might want to
> > hash lambda terms modulo alpha-equivalence or hash logical terms with
> > respect to commutativity of (&&) and (||).
> >
> > Often we can choose 'canonical' element from each class and hash it.
> > But (at least, in theory) it's not necessary. So, are there (practical)
> > ways to define hash function without it?
> >
> > --
> > Roman I. Cheplyaka :: http://ro-che.info/
> > "Don't let school get in the way of your education." - Mark Twain
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
--
Roman I. Cheplyaka :: http://ro-che.info/
"Don't let school get in the way of your education." - Mark Twain
More information about the Haskell-Cafe
mailing list