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

[David Menendez]

On Wed, Mar 12, 2008 at 4:29 PM, Aaron Denney <wnoise at ofb.net> 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.

(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).

(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.)

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

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

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

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


Similar tricks can be used for orderings.

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>