[Haskell-cafe] Hashing over equivalence classes

[Roman Cheplyaka]

* 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