Custom Sort in Haskell

Question

Second Update:

I finally followed zurgl's suggestion and wrote something that traverses and groups recursively. Thanks to everyone who was trying to help!

First Update:

What I hoped could be a sorting function, but was unsure about, was meant to optimize a grouping that would follow (minimizing the number of groups). The grouping collects tuples that are adjacent horizontally or vertically:

f xs = 
  foldr (\a@(y,x) ((b@(y',x'):xs):bs) -> if (y == y' && abs (x-x') == 1) || 
                                            (x == x' && abs (y-y') == 1)
                                            then (a:b:xs):bs 
                                            else [a]:(b:xs):bs) 
                                            [[last xs]] (init xs)

Output of the second example, after the "sorting":

*Main> f [(0,1),(1,1),(2,1),(2,2),(2,3),(1,3),(0,3),(4,1),(4,2)]
[[(0,1),(1,1),(2,1),(2,2),(2,3),(1,3),(0,3)],[(4,1),(4,2)]]

--end of updates--

I'm having trouble conceiving of a sorting function and am hoping someone might have an idea about how to implement it or perhaps say if more might be needed than a custom sort. I've tried toying with sortBy but do not seem to be making much progress.

How do I get from this:

[(0,1),(0,3),(1,1),(1,3),(2,0),(2,1),(2,3),(4,1),(4,2)]

to this:

[(0,1),(1,1),(2,0),(2,1),(0,3),(1,3),(2,3),(4,1),(4,2)]

Differences of 0 or 1 between both y y' and x x' should be primary. Does that make sense?

Second example:

[(0,1),(0,3),(1,1),(1,3),(2,1),(2,2),(2,3),(4,1),(4,2)] 
=>
[(0,1),(1,1),(2,1),(2,2),(2,3),(1,3),(0,3),(4,1),(4,2)]

Answer 1

My Haskell is extremely rusty but this should do it

subsortGT a, b
  | a <= b = GT
  | a > b = LT

sortGT (a1, b1) (a2, b2)
  | a1 + b1 < a2 + b2 = GT
  | a1 + b1 > a2 + b2 = LT
  | a1 + b1 ==  a2 + b2= subsortGT a1 a2

sortBy sortGT [(0,1),(0,3),(1,1),(1,3),(2,0),(2,1),(2,3),(4,1),(4,2)]

Answer 2

Leveraging tuples for sorting

import Data.Ord (comparing)
import Data.List (sortBy)

customSort = sortBy (comparing (\(x,y) -> (x+y, abs (x-y))))

or with arrows point free (point less)

import Control.Arrow ((&&&))

customSort = sortBy (comparing $ uncurry ((uncurry (&&&) .) ((+) &&& ((abs .) . subtract))))

Answer 3

Try to define a custom data type and a specified order on it.
I propose you something like this,

data MPair a = MPair a a deriving (Show)

-- some helper to test
toTuple (MPair x y) = (x, y)
fromX x = MPair x x

instance (Eq a) => Eq (MPair a) where
    (MPair a b) == (MPair c d) = (a == c) && (b == d)

-- This is not exactly the ordering you are looking for
-- But at this stage it should no be a pain to define 
-- the required ordering, you just have to implement it below
instance (Ord a) => Ord (MPair a) where
    compare p@(MPair a b) q@(MPair c d)
            | p == q = EQ
            | otherwise = case (compare a c, compare b d) of  
                            (LT, _) -> LT
                            (_, LT) -> LT
                            _       -> GT

-- convert a list of tuple to a list or MPair.  
fromListToMPair :: [(a,a)] -> [MPair a]
fromListToMPair [] = []
fromListToMPair ((a, b):xs) = (MPair a b) : fromListToMPair xs

-- the inverse of the previous one   
fromMPairToList :: [MPair a] -> [(a,a)] 
fromMPairToList [] = []
fromMPairToList ((MPair a b):xs) = (a, b) : fromMPairToList xs

-- A test case
testList = [(0,1),(0,3),(1,1),(1,3),(2,0),(2,1),(2,3),(4,1),(4,2)]

Go to ghci and test it,

>>> fromMPairToList $ sort $ fromListToMPair testList
[(0,1),(0,3),(1,1),(1,3),(2,0),(2,1),(2,3),(4,1),(4,2)]
-- add a test to check the stability of your order.  
>>> fromMPairToList $ sort $ sort $ fromListToMPair testList 
[(0,1),(0,3),(1,1),(1,3),(2,0),(2,1),(2,3),(4,1),(4,2)]
-- ok this is stable

This doesn't satisfied your requirement but, it's another way that I'd like to illustrate.
In fact I've implemented the classical rule for sorting a list of tuple.
Now i'll try to define your "ordering" , then I will redefine the Ord instance for MPair. like so,

instance (Ord a, Num a) => Ord (MPair a) where  
    compare p@(MPair a b) q@(MPair c d) 
            | p == q        = EQ 
            | check a b c d = LT  
            | otherwise     = GT 
                where 
                  pred x y = (abs (x - y)) < 2
                  check a b c d = pred a c && pred b d

Then when I redo the test into ghci,

>>> fromMPairToList $ sort $ fromListToMPair testList
[(4,1),(4,2),(2,3),(2,0),(2,1),(1,3),(1,1),(0,3),(0,1)]
>>> fromMPairToList $ sort $ sort $ fromListToMPair testList
[(0,1),(0,3),(2,0),(1,1),(2,3),(1,3),(2,1),(4,1),(4,2)]
-- no this won't work, this is not an ordering, you cannot sort.  

I realize that the stability of your order is not satisfied, then sorting is not what you need.

Finally, I'd like to say it doesn't make sense as you criterion do no define an order upon your list of tuple. Your criterion is a discriminant, it will allow you to create two subgroup of data. ([criterion x is True], [criterion x is not True]). Sort your list of tuple as usual, and define a specify function (based on your criterion) which will create two distinct group.

PS : Maybe you can build an order on your data using a function based on your criterion, but I don't see how to achieve it.