[Haskell-cafe] Type constraints for class instances

[Krzysztof Skrzętnicki]

Hello everyone,

I'm working on a small module for comparing things incomparable with Ord.
More precisely I want to be able to compare equal infinite lists like [1..].
Obviously

(1) compare [1..] [1..] = _|_

It is perfectly reasonable for Ord to behave this way.
Hovever, it doesn't have to be just this way. Consider this class

class YOrd a where
    ycmp :: a -> a -> (a,a)

In a way, it tells a limited version of ordering, since there is no
way to get `==` out of this.
Still it can be useful when Ord fails. Consider this code:

(2) sort [ [1..], [2..], [3..] ]

It is ok, because compare can decide between any elements in finite time.
However, this one

(3) sort [ [1..], [1..] ]

will fail because of (1). Compare is simply unable to tell that two
infinite list are equivalent.
I solved this by producing partial results while comparing lists. If
we compare lists
(1:xs)
(1:ys)
we may not be able to tell xs < ys, but we do can tell that 1 will be
the first element of both of smaller and greater one.
You can see this idea in the code below.


--- cut here ---

{-# OPTIONS_GHC -O2 #-}

module Data.YOrd where

-- Well defined where Eq means equality, not only equivalence

class YOrd a where
    ycmp :: a -> a -> (a,a)


instance (YOrd a) => YOrd [a] where
    ycmp [] [] = ([],[])
    ycmp xs [] = ([],xs)
    ycmp [] xs = ([],xs)
    ycmp xs'@(x:xs) ys'@(y:ys) = let (sm,gt) = x `ycmp` y in
                                 let (smS,gtS) = xs `ycmp` ys in
                                 (sm:smS, gt:gtS)


ycmpWrap x y = case x `compare` y of
                 LT -> (x,y)
                 GT -> (y,x)
                 EQ -> (x,y) -- biased - but we have to make our minds!

-- ugly, see the problem below
instance YOrd Int where
    ycmp = ycmpWrap
instance YOrd Char where
    ycmp = ycmpWrap
instance YOrd Integer where
    ycmp = ycmpWrap


-- ysort : sort of mergesort

ysort :: (YOrd a) => [a] -> [a]

ysort = head . mergeAll . wrap

wrap :: [a] -> [[a]]
wrap xs = map (:[]) xs


mergeAll :: (YOrd a) => [[a]] -> [[a]]
mergeAll [] = []
mergeAll [x] = [x]
mergeAll (a:b:rest) = mergeAll ((merge a b) : (mergeAll rest))


merge :: (YOrd a) => [a] -> [a] -> [a]
merge [] [] = []
merge xs [] = xs
merge [] xs = xs
merge (x:xs) (y:ys) = let (sm,gt) = x `ycmp` y in
                      sm : (merge [gt] $ merge xs ys)

--- cut here ---

I'd like to write the following code:

instance (Ord a) => YOrd a where
    ycmp x y = case x `compare` y of
                 LT -> (x,y)
                 GT -> (y,x)
                 EQ -> (x,y)


But i get an error "Undecidable instances" for any type [a].
Does anyone know the way to solve this?


Best regards

Christopher Skrzętnicki