Fantasy-land: Defining Ord in terms of lt vs lte

[gabejohnson]

Almost immediately after 3.2 was cut I thought about how libraries (Sanctuary in particular) would implement it. I realized that either there were going to be extra equality checks (not performant) or an indirect definition in terms of gt (unnecessarily convoluted).

// with Ord defined by lte
// note double equality checks
// only define 'fantasy-land/lte' and 'fantasy-land/equals'
const lte = a => b => a.lte(b);
const lt = a => b => a.lte(b) && !a.equals(b);
const gt = a => b => !a.lte(b);
const gte = a => b => !a.lte(b) || a.equals(b)

// with Ord defined by lte and lte defined in terms of gt
// solves extra equality checks
// requires implementing gt, 'fantasy-land/equals', and 'fantasy-land/lte' in terms of gt
const gt = a => b => a.gt(b);
const lte = a => b => !a.gt(b);
const lt = a => b => !a.gt(b) && !a.equals(b);
const gte = a => b => a.gt(b) || a.equals(b);

An alternative would be to define Ord in terms of lt and equals.

// no extra equality checks
// only define 'fantasy-land/lt` and 'fantasy-land/equals'
const lt = a => b => a.lt(b);
const lte = a => b => a.lt(b) || a.equals(b);
const gt = a => b => !a.lt(b) && !a.equals(b);
const gte = a => b => !a.lt(b);

laws:

1. If a.lt(b) then b.lt(a) === false (irreflexivity)
2. a.lt(b) or b.lt(a) or a.equals(b) (trichotomy)
3. If a.lt(b) and b.lt(c), then a.lt(c) (transitivity)

An added bonus is that we could refer to lt as precedes which has no connotation of quantity.

[safareli]

You still need to check for equals in two of this functions lte lt gt gte so i don't understand what the benefit is

[safareli]

In haskell Ord could be defined in terms of compare or <= so maybe we should add compare to Ord (as for example we have foldl/foldr when they can be expressed in terms of each other)

[gabejohnson]

@safareli

// two equals checks unless lte is defined in terms of gt
const lt = a => b => a.lte(b) && !a.equals(b);

[safareli]

I think i didn't understand something. you have provided 3 alternative implementation of lte lt gt and gte. in all this 3 cases equals is used in 2 of functions. so what's the difference

[gabejohnson]

Unless fantasy-land/lte is defined in terms of some gt, it is _likely_ to have a call to fantasy-land/equals in its implementation. If that is the case, the implementation of lt in any wrapper library (which can only rely on fantasy-land/lte) will indirectly make two calls to fantasy-land/equals.

[safareli]

so one should implement fantasy-land/lte in terms of gt then :d

[gabejohnson]

That was my second point in the OP. It's unnecessary indirection.

[gabejohnson]

@joneshf @davidchambers @scott-christopher any opinions?

[davidchambers]

I don't follow your argument about efficiency, @gabejohnson. I may be missing something, but what @safareli wrote earlier seems right to me: by specifying fantasy-land/lte we can implement lte with one check but lt takes two, whereas if we had specified fantasy-land/lt we could implement lt with one check but lte would take two.

I do, though, think that the implementations of {l,g}t{,e} are clearer when expressed in terms of fantasy-land/lt.

This reads very nicely (x < y OR x = y):

//    lte :: Ord a => a -> a -> Boolean
const lte = x => y => x.lt(y) || x.equals(y);

This is circuitous ((x < y OR x = y) AND NOT x = y):

//    lt :: Ord a => a -> a -> Boolean
const lt = x => y => x.lte(y) && !x.equals(y);

Perhaps due to symmetry, this upsets me less than the above:

//    lt :: Ord a => a -> a -> Boolean
const lt = x => y => x.lte(y) && !y.lte(x);

I'm not too worried about whether these implementations exactly match my mental model of what it means for one value to be _less than_ or _greater than_ another. We will define these functions once (in sanctuary-type-classes) and from that point forward only be concerned with the underpinnings (fantasy-land/lte) when defining new algebraic data types.

I suggest that the next step is for one of us to open a pull request to add Z.{l,g}t{,e} to sanctuary-type-classes, using [email protected]. We may agree at that point that the fantasy-land/lte-based implementations are quite acceptable. :)

@gabejohnson, does the circuitous lt definition capture your concerns about indirection?

[gabejohnson]

@davidchambers, the circuitous lt captures my concerns about making two calls to equals. But you're right. We should implement Z.lt and friends first to see if there are any problems in practice.

It might turn out that we won't end up defining fantasy-land/lte in terms of fantasy-land/equals in any of the cases 🙏

[joneshf]

I agree that it is presumptuous to assume someone will implement lte using equals.

[safareli]

https://hackage.haskell.org/package/base-4.9.1.0/docs/Data-Ord.html

Minimal complete definition: either compare or <=. Using compare can be more efficient for complex types.

So we can add compare for efficiency reasons.

btw in purescript default implementations are exported from the module where typeclass is defined. we currently do not export default implementations they exist only in readme.md. if we export those depending on FL will be much useful for library authors as it will also export default implementations which could be reused. will open Issue on this https://github.com/fantasyland/fantasy-land/issues/240

[davidchambers]

So we can add compare for efficiency reasons.

We'd then need to specify Ordering with members {-1, 0, 1} or {'LT', 'EQ', 'GT'} or similar. It would be nice to avoid this unless absolutely necessary. :)

[safareli]

We still specify result of equals ({true, false}) so what's the problem to use {-1, 0, 1} or similar?

[gabejohnson]

@safareli from https://github.com/fantasyland/fantasy-land/pull/235#issuecomment-289255757

There are other formulations for orderings, posets and comparisons we can use that don't require this C-style obfuscation.

I think @joneshf has a point. If FL had an Enum spec, I don't think this would be an issue.

[gabejohnson]

If we _did_ add an Enum spec and Ordering as an Enum, then we could add compare as an alternate for a minimal complete definition of Ord.

[gabejohnson]

Haskell's Enum implementation for Ordering for reference.

[gabejohnson]

See #241

[i-am-tom]

@safareli: RE Haskell (presumably GHC) asserting that compare can be more optimal, do the performance benefits translate to JS (a language without low-level enum / sum type support)? Obviously, equals is cool because its two-value enum matches a primitive already in the language, but it seems like the only _performant_ enum for LT/EQ/GT would be some arrangement of { true, false, null }, and that is terrifying. 😨

[davidchambers]

Why {true, false, null} rather than something such as {'LT', 'EQ', 'GT'}, @i-am-tom?

[i-am-tom]

@davidchambers It was a half-joking answer (though half-serious in the fact that null/bool checks are probably more performant than string comparisons) to @safareli's:

We still specify result of equals ({true, false}) so what's the problem to use {-1, 0, 1} or similar?

(i.e., there's only one built-in "type" with strictly three values, and that's the nullable boolean)

If compare _were_ introduced, then I personally agree with you that { 'LT', 'EQ', 'GT' } is the best idea. However, it'd be good to see an example of a structure and benchmarks where compare and its subsequent use _were_ notably faster than lte, as I suspect compare's superior Haskell speed (to a degree that it's worth mentioning) in certain GHC situations is because of magical inlining/annihilation - not something JS could do.

My two cents: I _love_ the idea of FL exporting its derivations section (as well as a set of common related functions, e.g. the other comparators), and then the spec needn't grow to include anything more. exports.compare = (a, b) => a.lte(b) ? a.equals(b) ? 'EQ' : 'LT' : 'GT', for example.

[davidchambers]

I _love_ the idea of FL exporting its derivations section (as well as a set of common related functions, e.g. the other comparators)

Are you familiar with sanctuary-type-classes? I believe it serves exactly the role you have in mind, and @gabejohnson is working on a patch to add {l,g}t{,e} to the library.

[i-am-tom]

@davidchambers ... Today, you have legitimately and significantly improved my life.

[xgbuils]

I don't really understand the root of the performance problem. I can take any Ord operator(lt, lte, gt, gte) and define the rest using only negation.

// based on .lte
const lte = a => b => a.lte(b);
const lt = a => b => !b.lte(a);
const gt = a => b => !a.lte(b);
const gte = a => b => b.lte(a);

// based on .gt
const lte = a => b => !a.gt(b);
const lt = a => b => b.gt(a); // edit: before const lt = a => b => b.lte(a);
const gt = a => b => a.gt(b);
const gte = a => b => !b.gt(a); // edit: before const gte = a => b => !b.lte(a);

[safareli]

@xgbuils your definitions are incorrect:

• lt based on lte
• gte based on lte

[gabejohnson]

There's also an issue in that !a.lte(b) === a.gt(b) only holds _if_ a and b are of the same type.

1. b must be a value of the same Ord
   i. If b is not the same Ord, behaviour of lte is
   unspecified (returning false is recommended).

I copied clause 1i from the Setoid definition.

Of course a lib that dispatches to FL methods and derives Ord operators from lte should check the types.

Incidentally, shouldn't 1i actually be 1a or 1.1?

[xgbuils]

@safareli , a counterexample please?

[xgbuils]

Hi @gabejohnson,

You are right, but the behaviour of values that does not belong to the same Ord is not specified, just recommended.

[safareli]

@xgbuils actually you are right i misinterpreted you example.

[gabejohnson]

@xgbuils has a really good point.

Additionally, the implementations of lte for Array and Object in https://github.com/sanctuary-js/sanctuary-type-classes/pull/46 are showing that doing an lte _and_ an equals comparison would only happen in the !equals(a, b) case.

This should only be expensive in a situation where you have a deeply nested structure.

[davidchambers]

Would you like to discuss this further, Gabe, or are you now happy with the status quo?

[gabejohnson]

I think it can be closed.