Re: [Haskell-cafe] Hashing over equivalence classes
* Ryan Ingram ryani.s...@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 r...@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@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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Hashing over equivalence classes
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hashing over equivalence classes
For the second case you might be able to come up with a commutative hash-combiner function for and ||. 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. 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? -- ryan On Sat, Mar 14, 2009 at 3:51 AM, Roman Cheplyaka r...@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
