Open andreasabel opened 2 years ago
compare
is a bad name as it clashes with Ord
definition. I agree, it would be good to add such method to PartialOrd
.
Can we have efficient implementations for Set
and Map
s?
compare
is a bad name as it clashes withOrd
definition. I agree, it would be good to add such method toPartialOrd
.
compareMaybe
would be a canonical name.
Can we have efficient implementations for
Set
andMap
s?
I suppose symmetric difference would be the canonical avenue for Set
. However, it hasn't materialized yet:
Maybe a stand-in via Set.toAscList
wouldn't be too awful.
Also one can lift compareMaybe
from v
to k -> v
for a finite k
using minimum on the four point lattice (Hasse diagram):
Just EQ
Just LT Just GT
Nothing
This gives a general recipe for products of all kinds.
The interface for
PartialOrd a
has two methods:https://hackage.haskell.org/package/lattices-2.0.3/docs/Algebra-PartialOrd.html#t:PartialOrd
I think an interface as chosen in package
partial-order
allows for more efficient implementations:https://hackage.haskell.org/package/partial-order-0.2.0.0/docs/Data-PartialOrd.html#v:compare
From the latter, we easily define:
However, defining
compare
involves two calls to the interface:This may be problematic if there is common work to be done for
leq a b
andleq b a
. The pure interface does not allow sharing of this joint work.For example, consider sets implemented by sorted lists. A call to
leq a b = isPrefixOf a b
would have worst-time complexity O(min(n,m)); butcompare
would just run in the same time. So, the interface with justleq
gives a slow-down of factor 2 in the worst case.