Change Ord method defaults

[treeowl]

Currently, Ord is defined

class  (Eq a) => Ord a  where
    compare              :: a -> a -> Ordering
    (<), (<=), (>), (>=) :: a -> a -> Bool
    max, min             :: a -> a -> a

    compare x y = if x == y then EQ
                  -- NB: must be '<=' not '<' to validate the
                  -- above claim about the minimal things that
                  -- can be defined for an instance of Ord:
                  else if x <= y then LT
                  else GT

    x <  y = case compare x y of { LT -> True;  _ -> False }
    x <= y = case compare x y of { GT -> False; _ -> True }
    x >  y = case compare x y of { GT -> True;  _ -> False }
    x >= y = case compare x y of { LT -> False; _ -> True }

        -- These two default methods use '<=' rather than 'compare'
        -- because the latter is often more expensive
    max x y = if x <= y then y else x
    min x y = if x <= y then x else y
    {-# MINIMAL compare | (<=) #-}

The note about defining max and min using <= rather than compare actually applies to the other methods too. I propose we redefine them thus:

x >= y = y <= x
x > y = not (x <= y)
x < y = not (y <= x)

With these changes, no one should ever have to define a custom >=, >, or < to get optimal performance in optimized code.

What can go wrong? If someone defines <= in terms of either >=, >, or <, and lets the latter have its default implementation, then they'll end up in an infinite loop. This seems fairly unlikely to me, since there's absolutely no reason for anyone to do that.

Note that in some cases, certain methods may get lazier. Suppose we have

data Nat = Z | S Nat
  deriving Eq
instance Ord Nat where
  Z <= _ = True
  _ <= Z = False
  S m <= S n = m <= n

<= is lazy in its second argument: Z <= undefined = True. With the current defaults, all the other comparison methods are strict. However, with the proposed defaults, >= and < will be lazy in their second argument and > will be lazy in its first argument.

[googleson78]

If someone defines <= in terms of either >=, >, or <, and lets the latter have its default implementation, then they'll end up in an infinite loop. This seems fairly unlikely to me, since there's absolutely no reason for anyone to do that.

This also infinitely loops right now. Do you mean "if one defines compare and also defines (<=) in terms of..."?

[treeowl]

Yes, I'm referring to a proper implementation of compare along with a useless definition of <= in terms of methods I propose to change.

[Bodigrim]

@treeowl if you'd like to move this forward, please link an MR.

[Bodigrim]

@treeowl just a gentle reminder that this proposal needs an MR before holding a vote.

[Bodigrim]

@treeowl unless there is a progress with your proposal within two weeks, I'll close it as abandoned.

[treeowl]

I'll try to do something about it this weekend.

[Bodigrim]

@treeowl just a gentle reminder.

Or maybe someone else can help us to move this change to class Ord forward?

[treeowl]

@Bodigrim If someone has the time, I'd be very grateful.

[tbidne]

@treeowl @Bodigrim created an MR here.

[Bodigrim]

Thanks @tbidne!

Dear CLC members, let's vote on the proposal to express default implementations of >=, > and < in terms of <= instead of compare, https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8811.
@tomjaguarpaw @chessai @emilypi @cgibbard @mixphix

---

+1 from me.

[mixphix]

+1

[emilypi]

+1. ezpz.

[treeowl]

@treeowl @Bodigrim created an MR here.

Thanks, @tbidne! My low capacity has been exceeded by other priorities recently; I appreciate your help moving this along.

[cgibbard]

It logically makes good sense that it should be easier for the compiler to get better code out of this, but can we somehow quickly confirm that it really happens before pulling the trigger? If so, I'm +1. I really hope there are no libraries out there which would be negatively impacted by this (though if anyone has a good way to search Hackage, that'd be awesome) -- it's an easy fix in any case, but it'll be a nontermination bug that will only show up at runtime if someone really does have an offending definition.

[treeowl]

@cgibbard this is really about semantics, not performance.

[tomjaguarpaw]

-1

---

Proposer @treeowl mentions twice that it's about performance and doesn't mention semantics in the original proposal

The note about defining max and min using <= rather than compare actually applies to the other methods too

With these changes, no one should ever have to define a custom >=, >, or < to get optimal performance in optimized code.

yet then says it's about semantics, not performance. So I'm confused and unable to see what the purported benefit is.

[treeowl]

Proposer will think about that again and try to remember.

[Bodigrim]

Here is a current definition of instance Ord [a] from ghc-prim:

instance (Ord a) => Ord [a] where
    compare []     []     = EQ
    compare []     (_:_)  = LT
    compare (_:_)  []     = GT
    compare (x:xs) (y:ys) = case compare x y of
                                EQ    -> compare xs ys
                                other -> other

The definition of compare forces both arguments to WHNF, and so is the default definition of <= and other operations. This is arguably suboptimal: I would not expect [] <= xs to evaluate xs ever. Even if we add a hand-written definition of <= to instance Ord [a], it would not make <, >, >= lazier, because their default definitions are in terms of compare, not <=. The proposal aims to change the latter fact, allowing to define lazier instance Ord with less boilerplate.

With regards to performance, the very next instance in ghc-prim is revealing:

-- We don't use deriving for Ord Char, because for Ord the derived
-- instance defines only compare, which takes two primops.  Then
-- '>' uses compare, and therefore takes two primops instead of one.
instance Ord Char where
    (C# c1) >  (C# c2) = isTrue# (c1 `gtChar#` c2)
    (C# c1) >= (C# c2) = isTrue# (c1 `geChar#` c2)
    (C# c1) <= (C# c2) = isTrue# (c1 `leChar#` c2)
    (C# c1) <  (C# c2) = isTrue# (c1 `ltChar#` c2)

Under the proposal it would be enough to define (C# c1) <= (C# c2) = isTrue# (c1 `leChar#` c2), and everything else would just follow automatically without compromising performance.

@tomjaguarpaw @cgibbard does it help?

[Bodigrim]

@cgibbard does my explanation help to convert your conditional vote into an unconditional one?
@tomjaguarpaw shall I consider your vote as final?

[tomjaguarpaw]

+1

---

I change my vote. Thanks @Bodigrim, your explanation shows that the merit of this change with respect to performance.

(For posterity: This will help get better performance by default, which is great, but I still remain somewhat skeptical of the robustness of relying on default methods if you want good performance.)

[Bodigrim]

OK, this gives us at least 4 votes in favor. Approved, thanks all.

[chshersh]

I'm trying to summarise the state of this proposal as part of my volunteering effort to track the progress of all approved CLC proposals.

Field	Value
Author	@treeowl, @tbidne
Status	merged
base version	4.18.0.0
Merge Request (MR)	https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8811
Blocked by	nothing
CHANGELOG entry	present
Migration guide	not needed

Please, let me know if you find any mistakes 🙂