There is a bug in the code:<br><br>*Main&gt; 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) =&gt; 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 =&gt; YOrd [a] can be made to work, and that is absolutely awesome, esp. once you start thinking about things like Ord a =&gt; YOrd (InfiniteTree a). This really is very cool, Krzysztof.<br>
<br>Stephen<br><br><div class="gmail_quote">2008/3/20 Krzysztof SkrzÍtnicki &lt;<a href="mailto:gtener@gmail.com">gtener@gmail.com</a>&gt;:<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&#39;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&#39;t have to be just this way. Consider this class<br>
<br>
class YOrd a where<br>
 &nbsp; &nbsp;ycmp :: a -&gt; a -&gt; (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 &lt; 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>
 &nbsp; &nbsp;ycmp :: a -&gt; a -&gt; (a,a)<br>
<br>
<br>
instance (YOrd a) =&gt; YOrd [a] where<br>
 &nbsp; &nbsp;ycmp [] [] = ([],[])<br>
 &nbsp; &nbsp;ycmp xs [] = ([],xs)<br>
 &nbsp; &nbsp;ycmp [] xs = ([],xs)<br>
 &nbsp; &nbsp;ycmp xs&#39;@(x:xs) ys&#39;@(y:ys) = let (sm,gt) = x `ycmp` y in<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; let (smS,gtS) = xs `ycmp` ys in<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (sm:smS, gt:gtS)<br>
<br>
<br>
ycmpWrap x y = case x `compare` y of<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LT -&gt; (x,y)<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; GT -&gt; (y,x)<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; EQ -&gt; (x,y) -- biased - but we have to make our minds!<br>
<br>
-- ugly, see the problem below<br>
instance YOrd Int where<br>
 &nbsp; &nbsp;ycmp = ycmpWrap<br>
instance YOrd Char where<br>
 &nbsp; &nbsp;ycmp = ycmpWrap<br>
instance YOrd Integer where<br>
 &nbsp; &nbsp;ycmp = ycmpWrap<br>
<br>
<br>
-- ysort : sort of mergesort<br>
<br>
ysort :: (YOrd a) =&gt; [a] -&gt; [a]<br>
<br>
ysort = head . mergeAll . wrap<br>
<br>
wrap :: [a] -&gt; [[a]]<br>
wrap xs = map (:[]) xs<br>
<br>
<br>
mergeAll :: (YOrd a) =&gt; [[a]] -&gt; [[a]]<br>
mergeAll [] = []<br>
mergeAll [x] = [x]<br>
mergeAll (a:b:rest) = mergeAll ((merge a b) : (mergeAll rest))<br>
<br>
<br>
merge :: (YOrd a) =&gt; [a] -&gt; [a] -&gt; [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>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;sm : (merge [gt] $ merge xs ys)<br>
<br>
--- cut here ---<br>
<br>
I&#39;d like to write the following code:<br>
<br>
instance (Ord a) =&gt; YOrd a where<br>
 &nbsp; &nbsp;ycmp x y = case x `compare` y of<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; LT -&gt; (x,y)<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; GT -&gt; (y,x)<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; EQ -&gt; (x,y)<br>
<br>
<br>
But i get an error &quot;Undecidable instances&quot; 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>