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

[Aaron Denney]

On 2008-03-13, David Menendez <dave at zednenem.com> wrote:
> 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.

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
-><-