# What are the laws for Eq1, Eq2, Ord1, and Ord2?

7 messages
Open this post in threaded view
|

## What are the laws for Eq1, Eq2, Ord1, and Ord2?

 I was looking at the Eq2 instances for Data.Map and Data.HashMap, and the Eq1 instances for Set and HashSet, and I realized that they're a bit ... weird. My instinct is to remove these instances immediately, but I figure I should first check with the community (and Oleg, who added them to begin with) to make sure they don't make some sort of sense I don't understand. In particular, these instances compare keys in the order in which they appear in the container. That order may be completely unrelated to the given key comparison function. Data.Map example: suppose I have a Map k () and a Map (Down k) (), where Down is from Data.Ord. If I call liftEq2 (\x (Down y) -> x == y) (==), I will get what looks to me like a totally meaningless result. Data.HashMap example: suppose I have a HashMap Int () and a Hashmap String (). If I call liftEq2 (\x y -> show x == y) (==), that won't return True even if the strings in the second map are actually the results of applying show to the numbers in the first map. Intuitively, I think Eq1 f only makes sense if the shape of f x does not depend on the values of type x, and Eq2 p only makes sense if the shape of p x y does not depend on the values of types x and y. Is there a way to formalize this intuition with class laws? I believe that in the case of a Functor, parametricity will guarantee that   liftEq eq (f <\$> xs) (g <\$> ys) == liftEq (\x y -> eq (f x) (g y)) xs ys Are there *any* legitimate instances of Eq1 or Ord1 that are not Functors? Are there *any* legitimate instances of Eq2 or Ord2 that are not Bifunctors? My intuition says no. We might wish we could write instances for unboxed arrays or vectors, but I believe that is totally impossible anyway. David _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Open this post in threaded view
|

## Re: What are the laws for Eq1, Eq2, Ord1, and Ord2?

Open this post in threaded view
|

## Re: What are the laws for Eq1, Eq2, Ord1, and Ord2?

Open this post in threaded view
|

## Re: What are the laws for Eq1, Eq2, Ord1, and Ord2?

Open this post in threaded view
|