Eq and Ord classes don't seem very useful

[treeowl]

I could be wrong, but it seems to be that having == and (probably) compare consume their arguments is wrong for the vast majority of types that need to be handled linearly. I would expect something more like

class Eq a where
  (==) :: a %1-> a %1-> (Bool, a, a) -- return both values in case `==` is not structural equality
class Eq a => Ord a where
  compare :: a %1-> a %1-> (Ordering, a, a)
  (<=) :: a %1-> a %1-> (Bool, a, a)
  ...

[treeowl]

A couple examples:

1. Comparing two mutable arrays for (pointer) equality should not consume them.
2. Comparing the addresses of two pinned mutable byte arrays (with compare) should not consume them.

[aspiwack]

I'm being silent on this issue, because I need to think about it. Apologies.

[aspiwack]

Oooff… I kind of forgot about this issue for a while. Sorry.

My intention with these is type is that

• (==) :: a %1-> a %1-> (Bool, a, a) is a pretty awful type to work with
• types that can implement the equality test above will be Dupable.

You come with two counter-example. Mutable arrays are not dupable, neither would mutable byte arrays. Nevertheless it may make sense to compare them.

• You could have structural, $O(n)$, equality.
• Pointer equality doesn't make much sense for these: it's always false
• But you can have pointer comparisons for the sake of an ordered data structure. Probably not for mutable arrays, as this is not stable (it would have to be in IO); but for byte arrays that are pinned, it makes sense for comparison to be pure.

There is more than one way to think about this.

• We can keep the classes as they are and say: this is the most common case, Dupable structures, and they're better types when working on them. But I see an issue there that hadn't surfaced yet: pretty much every data structure requiring an Ord instance will have to use Dupable as well. Dubious.
• We can use your definitions, but then, when we always have to handle these pesky extra fields, even when we are in the Dupable case. Possible mitigation, add a copy of each method like so:

  class Eq a where
    (==:) :: a %1-> a %1-> (Bool, a, a)
    (==) :: Consumable a => a %1-> a %1-> Bool
    a == b = let !(r, a', b') = a ==: b in a' `lseq` b' `lseq` r

  But for Consumable data types, we can typically implement (==) directly, and bypass the extra call to consume/lseq.
• Or we could say that we need to invent something new.

---

Let me riff on this third possibility for a little while.

We could say that, instead of (==), compare and all that, the proper primitive is compare-and-swap:

cas :: a %1 -> a %1 -> (a, a)

Where the guarantee is that in the returned pair, the smaller a is first. As an aside cas has well-defined laws, and is equivalent to lattices (maybe distributive, I don't remember) (it works for partial orderings, in which case the result is to be understood as $(a \wedge b, a \vee b)$).

It's quite clear that a linear cas is a perfectly reasonable construction.

However, it's far from perfect. For instance, you can't write quicksort or mergesort with cas (exercise: try). Sorting that can be done with cas are called network sorts, the most famous is the bitonic sort.

One key issue with cas is that it doesn't let us decide equality.

Ok, maybe let's add a boolean:

cas :: a %1 -> a %1 -> (Bool,a, a)

It's not much worse, and it's easy to produce a version that doesn't return the boolean. It does encode the additional ordering structure in the ordering of the pair. Pretty neat.

But I don't think it suffices for mergesort: at some point in merge sort you have (a : as) (b : bs), and you need to pick the smaller of a and b, and leave the other one in its place. So we really need to know which one was the smaller. The above type doesn't give it to us. So we'd need to know whether a reordering has happened. Basically

cas :: a %1 -> a %1 -> (Ordering, a, a)

This is your compare but the two returned a may have been permuted. Not a very useful “improvement”. It's interesting that with a boolean we could still encode some data in the choice of which a to return in which place, but this isn't the case as soon as we add just a third alternative.

Well… I wrote a lot of words, not many are useful, are they?