Keith Wansbrough wrote:
> > OTOH, if we were to redefine all the xxxBy functions that involve
> > comparison, I'd vote for ((<=) :: a->a->Bool) over (compare ::
> > a->a->Ordering) as the comparison function since (<=) is often easier to
> > create a quick definition for. I wouldn't consider such a change until
> > Haskell 2, though.
>
> I disagree... I don't think we should be making `quick-and-dirty'
> definitions easy, I think we should be doing it the Right Way. It
> takes two `<=' comparisons to get the information obtainable from one
> `compare', but one `compare' is also enough to give a result for `<='.
> It usually requires no more computation to give the more specific
> result.
I don't disagree strongly with this, but... sortBy, insertBy, etc. can
almost always be implemented just as easily with (<=) as with compare.
That is, they don't need more calls to (<=) than they would calls to
compare. That means that if compare is more complex than (<=), as it
possibly can be, you end up with a less efficient algorithm.
Admittedly, there may be some algorithms that would make fewer
comparisons if defined in terms of compare rather than (<=).
> If you really want quick-and-dirty, you could add:
When I said "quick" I should probably have said "simple"; I didn't mean
"quick-and-dirty".
> le2ord :: (a -> a -> Bool) -> (a -> a -> Ordering)
> le2ord le a b = case (a `le` b, b `le` a) of
> (True, False) -> LT
> (True, True ) -> EQ
> (False,True ) -> GT
>
> to the prelude (or to an Ordering library). While you're constructing
> an Ordering library, you could add to it:
>
> isLE :: Ordering -> Bool
> isLE LT = True
> isLE EQ = True
> isLE GT = False
Yes, I'm well aware that compare can be defined in terms of (<=) and
vice-versa.
> thenCmp :: Ordering -> Ordering -> Ordering
> EQ `thenCmp` o2 = o2
> o1 `thenCmp` _ = o1
OK, so:
instance (Ord a) => Ord [a] where
compare (x:xs) (y:ys) = (compare x y) `thenCmp` (compare xs ys)
compare [] [] = EQ
compare [] _ = LT
compare _ [] = GT
instance (Ord a) => Ord [a] where
(x:xs) <= (y:ys) = not (y<=x) || ((x<=y) && (xs<=ys))
(_:_) <= [] = False
[] <= _ = True
I must admit I like the compare version better, and it involves N calls
to compare as opposed to 2N calls to (<=). It's one of those algorithms
I admitted might exist earlier! thenCmp looks very useful, and thenLE
can't be defined, of course. I think I'm starting to see the light. :)
> and a partial ordering class
>
> type POrdering = Maybe Ordering
>
> class POrd a where
> pcompare :: a -> a -> POrdering
>
> instance Ord a => POrd a where
> pcompare a b = Just (compare a b)
I know partial orderings are used in mathematics, but have you seen a
practical use in programming? I'm genuinely curious.
> Just my �0.02 (about US$0.04 I believe).
It seems I've been out-bid! ;-)
