You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
-- symmetric: a `eq` b == b `eq` a-- transitive: a `eq` b == b `eq` c == a `eq` cclassPartialEqawhereeq::a->a->BooleannotEq::foralla. PartialEqa=>a->a->Boolean
notEq = not <<< eq
-- reflexive a `eq` aclassPartialEqa<=Eqa-- pre orderclassPartialEq<=PartialOrdawherepcompare::a->a->MaybeOrderinglt::a->a->Booleanlte::a->a->Booleangt::a->a->Booleangte::a->a->Boolean-- total orderclass (Eqa, PartialOrda) <=Ordawherecompare::a->a->Ordering
It was discussed once long ago, when we considered adding lattices, but the consensus then was it's not common enough to warrant existing in Prelude. I'd still agree with that.
How does PartialEq differ from Eq - just the lack of reflexivity? Seems like it would only exist to satisfy Number, realistically?
I’m actually starting to come around to this. In that thread I mainly argued that if we are only going to provide one class for ordering in Prelude then it should be total rather than partial, but if we are considering providing both a partial and a total ordering class then I think that’s a slightly separate discussion. I also overlooked the fact that Number is not a well-behaved Ord there, which is quite an important detail. It feels wrong to me that inserting a NaN into a Map can totally break it, although to be fair I haven’t ever heard of this happening in practice.
It’s worth noting that it’s not just Number this would apply to, but also any type which contains a Number.
What’s nice about this approach is that while the ordering operators still work on Number, you can also capture trichotomy in the types where you need it by using compare - so all the relevant Map functions would have Ord constraints inferred, as we would want.
Your suggested definitions look good to me but I have a couple of notes about the descriptions. Firstly, we want the transitivity law for PartialEq to say “if A equals B and B equals C then A equals C,” which is not quite the same as what you have there. Secondly, I don’t think we would want to describe PartialOrd as a preorder anywhere because a preorder requires reflexivity - a <= a - which I think is too strong for Number because of NaN. I think our PartialOrd should only require transitivity - if a <= b and b <= c then a <= c.
Oh also, if we do this, I think we should consider having pcompare as the only member of PartialOrd so that we don’t have to expend a lot of effort explaining laws about how the other methods interact with each other or worry about people implementing them incorrectly.
On the other hand, if you have an Array Number that you know for sure doesn’t contain any NaNs, it’s going to be really annoying to be told that you can no longer sort it without using some kind of newtype wrapper which treats NaN as less than every other value something like that.
Floats implementing PartialOrd but not Ord is maddening. (Or rather, the *_by_key functions operating on Ord rather than PartialOrd is what’s frustrating.) Yes, this is technically correct, but it’s also hugely inconvenient to not be able to min_by_key on a collection of f32s that are definitely not NaN. I’ve seen a handful of workarounds for this, but none of them have been my favorite. f32s are incredibly, incredibly common in games, and it’s frustrating that tasks like “find the point in set S that’s closest to point P” are not as straightforward as they could be.
For what it's worth, in my own code I'm moving toward a type AffReal which is exactly that kind of newtype wrapper around Number that excludes the value NaN while retaining Inf and -Inf. It helps but floating point arithmetic still feels dangerous.
This seems like part of a broader, and difficult, problem with Purescript and floating point arithmetic. We get used to all the (substantial) advantages of law-abiding typeclass instances but floating point numbers are never fully law abiding. Not Ord, not Eq, not even Semiring.
It seems like there are three options:
Live the lie. Allow Number to be an instance of Eq, Ord, Semiring, etc with notes in the comments
Parallel typeclasses. New versions of Eq, Ord, Semiring, etc that define the similar operators but with (much) weaker laws
The nuclear option. Provide BigInt and BigInt-based Rationals in Prelude and banish fixed-size Ints and Floats into a use-at-your-own-risk library
I'm not sure I have a strong opinion on which path to take but I hope that we take one consistent path (one of the above or something I haven't thought of) rather than mix-and-match.
Activity
[-]Support `PartialEq` and PartialOrd`[/-][+]Support `PartialEq` and `PartialOrd`[/+]garyb commentedon Mar 3, 2022
It was discussed once long ago, when we considered adding lattices, but the consensus then was it's not common enough to warrant existing in Prelude. I'd still agree with that.
How does
PartialEqdiffer fromEq- just the lack of reflexivity? Seems like it would only exist to satisfyNumber, realistically?JordanMartinez commentedon Mar 3, 2022
Basically.
Where was that discussed?
garyb commentedon Mar 3, 2022
In the thread on lattices, search for
NCfor the relevant parts I think.hdgarrood commentedon Apr 4, 2022
I’m actually starting to come around to this. In that thread I mainly argued that if we are only going to provide one class for ordering in Prelude then it should be total rather than partial, but if we are considering providing both a partial and a total ordering class then I think that’s a slightly separate discussion. I also overlooked the fact that Number is not a well-behaved Ord there, which is quite an important detail. It feels wrong to me that inserting a NaN into a Map can totally break it, although to be fair I haven’t ever heard of this happening in practice.
It’s worth noting that it’s not just Number this would apply to, but also any type which contains a Number.
What’s nice about this approach is that while the ordering operators still work on Number, you can also capture trichotomy in the types where you need it by using
compare- so all the relevant Map functions would have Ord constraints inferred, as we would want.Your suggested definitions look good to me but I have a couple of notes about the descriptions. Firstly, we want the transitivity law for PartialEq to say “if A equals B and B equals C then A equals C,” which is not quite the same as what you have there. Secondly, I don’t think we would want to describe PartialOrd as a preorder anywhere because a preorder requires reflexivity -
a <= a- which I think is too strong for Number because of NaN. I think our PartialOrd should only require transitivity - ifa <= bandb <= cthena <= c.hdgarrood commentedon Apr 4, 2022
Oh also, if we do this, I think we should consider having
pcompareas the only member ofPartialOrdso that we don’t have to expend a lot of effort explaining laws about how the other methods interact with each other or worry about people implementing them incorrectly.hdgarrood commentedon Apr 4, 2022
Oh, I think we could describe PartialOrd as a strict preorder: https://en.m.wikipedia.org/wiki/Preorder#Strict_preorder
hdgarrood commentedon Apr 4, 2022
On the other hand, if you have an
Array Numberthat you know for sure doesn’t contain any NaNs, it’s going to be really annoying to be told that you can no longer sort it without using some kind of newtype wrapper which treats NaN as less than every other value something like that.A relevant quote from https://michaelfairley.com/blog/i-made-a-game-in-rust/ -
JordanMartinez commentedon Apr 4, 2022
Yeah... that would get really old really fast...
JamieBallingall commentedon Jun 29, 2022
For what it's worth, in my own code I'm moving toward a type
AffRealwhich is exactly that kind of newtype wrapper aroundNumberthat excludes the valueNaNwhile retainingInfand-Inf. It helps but floating point arithmetic still feels dangerous.This seems like part of a broader, and difficult, problem with Purescript and floating point arithmetic. We get used to all the (substantial) advantages of law-abiding typeclass instances but floating point numbers are never fully law abiding. Not
Ord, notEq, not evenSemiring.It seems like there are three options:
Eq,Ord,Semiring, etc with notes in the commentsEq,Ord,Semiring, etc that define the similar operators but with (much) weaker lawsI'm not sure I have a strong opinion on which path to take but I hope that we take one consistent path (one of the above or something I haven't thought of) rather than mix-and-match.