Anand Patil wrote: Heinrich Apfelmus wrote:
Anand Patil wrote:
- Cheap equality by value:
user=> (= m {:a 1 :b 2 :c {:d 3 :f 4}}) false user=> (= m {:a 1 :b 2}) true
If I understand correctly, equality is computed based on some kind of hash rather than by comparing the two maps element by element, so it's efficient even for large and/or nested collections.
Why would you need this feature? I can only think of common subexpression elimination.
I have an expensive function that takes complicated data structures as an argument, and I know that it will often be evaluated twice running with the same argument, but it will be evaluated with lots of different arguments over the course of the program. A cheap equality test would make it easy to cache the last return value. Is there a better way to optimize this in Haskell?
Sounds indeed like a case for memoization to me. (While complicated data structures as keys sounds suspicious, in my opinion.) Cheap equality won't necessarily help, though, you want at least the hash value itself. But since calculating a hash will take O(length of complicated data structure) anyway, you can also use a memoization scheme based on "sums of products" which has the same complexity^1. In particular, have a look at http://hackage.haskell.org/package/data-memocombinators which is used like this: fib = Memo.integral fib' where fib' 0 = 0 fib' 1 = 1 fib' x = fib (x-1) + fib (x-2) You'll have to combine existing memo combinators to make one for your data structure; feel free to ask if you need more info on that. ^1: For common subexpression elimination, intermediate hashes count as well, so this comparison doesn't apply. Regards, apfelmus -- http://apfelmus.nfshost.com