[Haskell-cafe] Re: (flawed?) benchmark : sort

On 2008-03-13, David Menendez wrote:

On Wed, Mar 12, 2008 at 4:29 PM, Aaron Denney wrote:

...

When defining max, yes, you must take care to make sure it useable for cases when Eq is an equivalence relation, rather than equality.

If you're writing library code, then it won't generally know whether Eq means true equality rather than equivalence. If this would let you optimize things, you need some other way to communicate this.

The common typeclasses are for generic, parameterizable polymorphism. Equivalence is a more generally useful notion than equality, so that's what I want captured by the Eq typeclass.

I agree that equivalence is more general than equality, but I think equality makes more sense for Eq. Unfortunately, my reasons are mostly circumstantial.

Despite the circumstantial nature, still strong though.

(1) You get at most one instance of Eq per type, and you get at most one equality relation per type. On the other hand, you have at least one equivalence (trivial equivalence) and will usually have several. Type classes don't work well when you have more than one of something per type (consider monoids).

Right. But wrapping in newtypes gets around that somewhat.

(2) Libraries like Data.Set and the Edison have to go through a lot of hoops because they can't assume that an Eq tests equality. (The Edison API, in particular, has to create a distinction between observable and non-observable collections, in order to support, e.g., a bag that doesn't store multiple copies of equivalent elements.)

Why is this a distinction in the API, rather than just the same API by coalescing and non-coalescing collections?

(3) Eq uses (==), which is commonly known as the "equality" sign, not the "equivalence" sign.

Meh. Having the names be right is important, but choosing the right semantics comes first. Eq should be renamed (to either Equal or Equivalent, depending).

(4) The Prelude already provides alternative functions that support any equivalence (sortBy, nubBy, etc.).

Consider the old "if we have trees with different comparison operators, how do we keep the user from merging them together." Well, phantom types, and different instances provides a way to ensure this statically.

If I were creating Haskell right now, I'd use Eq for equality and provide an additional class for equivalences along these lines:

Well, Haskell' isn't yet finished...

data P r class Equivalence r where type EqOver r :: * equiv :: P r -> EqOver r -> EqOver r -> Bool

data Equality a

instance (Eq a) => Equivalence (Equality a) where type EqOver (Equality a) = a equiv _ = (==)

data Trivial a

instance Equivalence (Trivial a) where type EqOver (Trivial a) = a equiv _ _ _ = True

Hmm. Pretty nice, but I might prefer an MPTC solution. -- Aaron Denney -><-