8
$\begingroup$

For example, recall the Ord class of Haskell:

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

    compare x y = if x <= y
        then if x == y
            then EQ
            else LT
        else GT
    x < y = not (y <= x)
    x <= y = not (compare x y == GT)
    x > y = not (x <= y)
    x >= y = y <= x

    max x y = if x <= y
        then y
        else x
    min x y = if x <= y
        then x
        else y

Long story short, instances of Ord require either compare or (<=) to be implemented explicitly, and then the other methods, including min and max, will have their implementation defaulted.

I see a big problem with this class. Namely, this class forces min and max to be implemented together with the comparison operators, when there are situations for which they must be implemented independently.

One example datatype that demonstrates such situation is (lazily evaluated) infinite lists, as implementable in Haskell as below:

infixr 5 :!
data InfList a = a :! InfList a

This datatype has semi-decidable inequality, but it doesn't have semi-decidable equality, resulting in lacking the Eq instance nor the Ord instance.

One workaround is to have a separate class dedicated for min and max, as below:

import Prelude hiding (Ord(..))

class MinMax a where
    min :: a -> a -> a
    max :: a -> a -> a

infix 4 <=, >=, <, >
class (Eq a, MinMax a) => Ord a where
    (<=) :: a -> a -> Bool
    (>=) :: a -> a -> Bool
    (<) :: a -> a -> Bool
    (>) :: a -> a -> Bool
    compare :: a -> a -> Ordering

    x <= y = min x y == x
    x >= y = min x y == y
    x < y = not (y <= x)
    x > y = not (x <= y)
    compare x y = if x <= y
        then if x == y
            then EQ
            else LT
        else GT

Here, note that the comparison operators are in a class of their own, enabling them to be overridden by a more efficient implementation.

Now InfList can have min and max for lexicographic order:

instance Ord a => MinMax (InfList a) where
    min x@(xh :! xt) y@(yh :! yt) = case compare xh yh of
        LT -> x
        EQ -> xh :! min xt yt
        GT -> y
    max x@(xh :! xt) y@(yh :! yt) = case compare xh yh of
        LT -> y
        EQ -> xh :! max xt yt
        GT -> x

So why doesn't Haskell, or any other major languages, do this?

$\endgroup$
6
  • 2
    $\begingroup$ Not enough material for a proper answer, but how often are you really trying to find the min/max of an infinite list? it's not something I would imagine comes up very often, and complicating the typeclass hierarchy even more for something that can be trivially user-defined if needed seems a bit odd $\endgroup$
    – blueberry
    Commented Jan 10 at 1:10
  • $\begingroup$ @blueberry I once tried to implement arbitrary-precision real numbers by representing them as infinite bitstrings, and I was so annoyed by the Ord class. $\endgroup$ Commented Jan 10 at 1:15
  • $\begingroup$ x < y = not (min x y == x) seems like a lot of effort for something that otherwise even has hardware support in many critical cases. $\endgroup$ Commented Jan 10 at 5:51
  • $\begingroup$ @MisterMiyagi Yes, that's why I let it to be override-able. $\endgroup$ Commented Jan 10 at 5:56
  • 4
    $\begingroup$ Do you have a reference (or a clearer criterion) for the "most languages" part of this? The example given seems very specific to the Haskell implementation, and many languages either a) don't feature operator overloading at all; or b) allow each operator to be overloaded individually. The example scenario of an infinite lazy list is also rather specific; in many languages the closest would be an iterator protocol, which would probably lead to a completely different approach. $\endgroup$
    – IMSoP
    Commented Jan 10 at 15:30

1 Answer 1

11
$\begingroup$

I doubt there is a direct answer to why the designers of most languages didn't do this. It's not something that most people would have the idea to do, and there aren't really any compelling reasons to do it, so it's unlikely there would be records of language designers deliberating on this. You mention lazy infinite lists, but "most languages" don't have these; or you might consider iterators to be analogous, but iterators generally aren't comparable.

That said, here are some reasons that comparison operators are better suited for user-defined behaviour than min and max:

min and max aren't operators

Generally speaking, operators like < or <= have native/intrinsic implementations, whereas functions like min or max can be implemented within the language as part of the standard library. Then it's natural that the comparison operators aren't implemented by calling out to the standard library. And it's also natural that a language allowing for operator overloading would allow users to implement < and <= themselves, but not replace the definition of min and max in the standard library.

In your own language you might choose to make min and max operators, but in most real languages they aren't. Alternatively you could go the Python route and have min and max be functions which call special __min__ and __max__ methods on the objects, if those methods exist. But most languages don't provide mechanisms like this for changing what standard library functions do.

Composite types can define comparisons without min and max, but not vice versa

Suppose you have objects with two fields foo and bar, and you want to order objects first by foo and then by bar. To implement < on these objects, you would do something like this:

x.foo < y.foo || (x.foo == y.foo && x.bar < y.bar)

On the other hand, to implement min for these objects, you would write:

x.foo < y.foo || (x.foo == y.foo && x.bar <= y.bar) ? x : y

There is no natural way to find min(x, y) for these objects using min(x.foo, y.foo) and min(x.bar, y.bar), without resorting to min(x.foo, y.foo) == x.foo comparisons. So the comparison operations are more fundamental.

min and max need an extra branch

It's more efficient for x <= y to be implemented directly, rather than implemented as min(x, y) == x. The latter will typically expand as (x <= y ? x : y) == x, because that's how min is ultimately implemented.

In some cases the branch might get optimised away if the compiler is smart enough, but this couldn't be relied on if min is implemented by arbitrary user code.

min and max can't return more than one bit of information

For correctness reasons, user implementations of min and max would be required (or, ought to be required) to return one of the two operands. However, to implement comparisons it's possible to provide just one function (or method) which can return three different values, representing 'less', 'equal' or 'greater'.

A three-way comparison could still be derived from min, like

min(x, y) == x ? (x == y ? EQUAL : LESS) : GREATER

But this requires yet another branch. Allowing the user to implement a three-way comparison directly could mean less branching in many cases.

If users can define comparisons, they don't need to also define min and max

There is no good reason to overload min and max if you have already overloaded the comparison operators for the same type. Defining min(x, y) to always mean x <= y ? x : y will give correct answers, whereas allowing it to give different answers would violate reasonable expectations and be a source of bugs.

min and max might take more than two arguments

Many languages allow min and max to be called with more than two arguments. In this case, either a user who overloads min and max would have the extra work of supporting extra arguments, or otherwise the signatures of min and max would be different when they are implemented vs. where they are used. That would be strange.

Likewise in Python, min and max can take a single argument, which is an iterable, and they return a minimum or maximum element from that iterable. The same applies: either the user has to handle this themselves, or what they're overloading isn't really the min and max functions.

min and max can only be used to implement comparisons if == is consistent with the ordering

In many languages it's possible to define comparisons in a way that x <= y and x >= y can both be true even when x == y is false. For example, objects which are compared by one field, but equality testing also checks another field. This is common when objects need to be stored in an ordered collection, for example.

If x <= y is defined as min(x, y) == x then you could get an incorrect result if x and y are 'equal' (in the ordering defined by min) but not equal (according to the == test). That is, suppose x and y are 'equal' in the ordering, and min(x, y) returns y, and x == y is false.

Things could also get strange when floating-point numbers and NaN values are involved, since x == x can be false. This wouldn't cause an issue with primitive floats or doubles, because min(x, y) == x would be false but also x <= y should be false. But it could cause problems if the user overloads min to have custom logic for object fields with NaN values.

$\endgroup$
3
  • 3
    $\begingroup$ "Generally speaking, operators like < or <= have native/intrinsic implementations" - I would have lead with this one. In practical terms, this sort of thing is very important to language designers - even when the language is intended to be very high-level. After all, if the people who had to make the hardware decided that one task is simpler than another, there's probably a good reason for that; and in general it only makes sense to implement the complex tasks in terms of the simpler ones rather than the other way around - that's one of the fundamental ideas in SICP. $\endgroup$ Commented Jan 12 at 4:46
  • $\begingroup$ @KarlKnechtel That's fair, I will edit to put it at the top. My intention was more along the lines of explaining why comparisons are conceptually more primitive than min/max, but the fact that they are more primitive in existing language designs is perhaps more significant for this question. $\endgroup$
    – kaya3
    Commented Jan 12 at 18:01
  • 1
    $\begingroup$ “Defining min(x, y) to always mean x <= y ? x : y will give correct answers.” Well, correct whenever <= represents a mathematical total order and doesn't return a non-Boolean value or have weird special values like IEEE NaN or SQL NULL. $\endgroup$
    – dan04
    Commented Jan 12 at 22:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .