* Ryan Ingram <[email protected]> [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 <[email protected]> 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 > > [email protected] > > 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
