There is a bug in the code:<br><br>*Main> ycmp [5,2] [2,5] :: ([Int], [Int])<br>([2,2],[5,5])<br><br>I think it is impossible to define a working (YOrd a) => YOrd [a] instance. Consider:<br><br>let (a, b) = ycmp [[1..], [2..]] [[1..],[1..]]<br>
<br>head (b !! 1) -- would be nice if it was 2, but it is in fact _|_<br><br>We take forever to decide if [1..] is greater or less than [1..], so can never decide if [1..] or [2..] comes next.<br><br>However Ord a => YOrd [a] can be made to work, and that is absolutely awesome, esp. once you start thinking about things like Ord a => YOrd (InfiniteTree a). This really is very cool, Krzysztof.<br>
<br>Stephen<br><br><div class="gmail_quote">2008/3/20 Krzysztof Skrzêtnicki <<a href="mailto:gtener@gmail.com">gtener@gmail.com</a>>:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hello everyone,<br>
<br>
I'm working on a small module for comparing things incomparable with Ord.<br>
More precisely I want to be able to compare equal infinite lists like [1..].<br>
Obviously<br>
<br>
(1) compare [1..] [1..] = _|_<br>
<br>
It is perfectly reasonable for Ord to behave this way.<br>
Hovever, it doesn't have to be just this way. Consider this class<br>
<br>
class YOrd a where<br>
ycmp :: a -> a -> (a,a)<br>
<br>
In a way, it tells a limited version of ordering, since there is no<br>
way to get `==` out of this.<br>
Still it can be useful when Ord fails. Consider this code:<br>
<br>
(2) sort [ [1..], [2..], [3..] ]<br>
<br>
It is ok, because compare can decide between any elements in finite time.<br>
However, this one<br>
<br>
(3) sort [ [1..], [1..] ]<br>
<br>
will fail because of (1). Compare is simply unable to tell that two<br>
infinite list are equivalent.<br>
I solved this by producing partial results while comparing lists. If<br>
we compare lists<br>
(1:xs)<br>
(1:ys)<br>
we may not be able to tell xs < ys, but we do can tell that 1 will be<br>
the first element of both of smaller and greater one.<br>
You can see this idea in the code below.<br>
<br>
<br>
--- cut here ---<br>
<br>
{-# OPTIONS_GHC -O2 #-}<br>
<br>
module Data.YOrd where<br>
<br>
-- Well defined where Eq means equality, not only equivalence<br>
<br>
class YOrd a where<br>
ycmp :: a -> a -> (a,a)<br>
<br>
<br>
instance (YOrd a) => YOrd [a] where<br>
ycmp [] [] = ([],[])<br>
ycmp xs [] = ([],xs)<br>
ycmp [] xs = ([],xs)<br>
ycmp xs'@(x:xs) ys'@(y:ys) = let (sm,gt) = x `ycmp` y in<br>
let (smS,gtS) = xs `ycmp` ys in<br>
(sm:smS, gt:gtS)<br>
<br>
<br>
ycmpWrap x y = case x `compare` y of<br>
LT -> (x,y)<br>
GT -> (y,x)<br>
EQ -> (x,y) -- biased - but we have to make our minds!<br>
<br>
-- ugly, see the problem below<br>
instance YOrd Int where<br>
ycmp = ycmpWrap<br>
instance YOrd Char where<br>
ycmp = ycmpWrap<br>
instance YOrd Integer where<br>
ycmp = ycmpWrap<br>
<br>
<br>
-- ysort : sort of mergesort<br>
<br>
ysort :: (YOrd a) => [a] -> [a]<br>
<br>
ysort = head . mergeAll . wrap<br>
<br>
wrap :: [a] -> [[a]]<br>
wrap xs = map (:[]) xs<br>
<br>
<br>
mergeAll :: (YOrd a) => [[a]] -> [[a]]<br>
mergeAll [] = []<br>
mergeAll [x] = [x]<br>
mergeAll (a:b:rest) = mergeAll ((merge a b) : (mergeAll rest))<br>
<br>
<br>
merge :: (YOrd a) => [a] -> [a] -> [a]<br>
merge [] [] = []<br>
merge xs [] = xs<br>
merge [] xs = xs<br>
merge (x:xs) (y:ys) = let (sm,gt) = x `ycmp` y in<br>
sm : (merge [gt] $ merge xs ys)<br>
<br>
--- cut here ---<br>
<br>
I'd like to write the following code:<br>
<br>
instance (Ord a) => YOrd a where<br>
ycmp x y = case x `compare` y of<br>
LT -> (x,y)<br>
GT -> (y,x)<br>
EQ -> (x,y)<br>
<br>
<br>
But i get an error "Undecidable instances" for any type [a].<br>
Does anyone know the way to solve this?<br>
<br>
<br>
Best regards<br>
<br>
Christopher Skrzêtnicki<br>
<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br>