CODEWITHSUNDEEP
listsortinghaskell
user1256228
user1256228

Reputation: 63

Applying custom ordering to lists (to sort a list of lists)

There's an example of how to sort a list with a custom ordering at this page: http://zvon.org/other/haskell/Outputlist/sortBy_f.html

xxx a b  | odd a = LT
         | otherwise = GT

Input: sortBy xxx [1,2,3,4,5,6,7] 

Output: [1,3,5,7,6,4,2]

The standard less than order lets me compare lists, e.g.

[1,2,3] < [0,4,5]

Is False. But this doesn't work with the above example function:

Main> xxx [1,2,6] [1,7,3]
ERROR - Cannot infer instance
*** Instance   : Integral [a]
*** Expression : xxx [1,2,6] [1,7,3]

Is there an easy way to extend such an order to lists?

The reason I want this functionality is to use sortBy to sort lists of lists using my custom ordering.

I'd be grateful for example solution code, advice on what to read up on, or anything in between. I'm hoping there's some built-in way to do this with the language rather than write a function that compares the lists directly.

Upvotes: 4

Views: 2347

Answers (2)

David Miani
David Miani

Reputation: 14678

You can convert a comparison function to a comparison function for lists with the code:

import Data.Monoid (mconcat)
compareList :: (a -> b -> Ordering) -> [a] -> [b] -> Ordering
compareList _ [] [] = EQ
compareList _ (_:_) [] = GT
compareList _ [] (_:_) = LT
compareList comparer (x:xs) (y:ys) = 
    comparer x y `mappend` compareList comparer xs ys

Now you can use xxx on two lists:

> compareList xxx [1,2,6] [1,7,3]
LT
> compareList xxx [2,2,6] [1,7,3]
GT

You could then use that to sort nested lists using your comparer:

> sortBy (compareList xxx) [[2,2,6], [1,7,3], [1,1,1]]
[[1,7,3],[1,1,1],[2,2,6]]

Upvotes: 5

Tikhon Jelvis
Tikhon Jelvis

Reputation: 68172

To replicate the behavior of < you would have to make your xxx function part of a type class. This is probably not worth it.

Instead, consider writing a new version of xxx specifically for lists:

xxxl :: Integral i => [i] -> [i] -> Ordering
xxx1 [] [] = EQ
xxxl [] _ = LT
xxxl _ [] = GT
xxxl (l1:_) (l2:_) | odd l1    = LT
                   | otherwise = GT

You might want to handle empty lists in some other fashion. This also illustrates why you cannot automatically generalize your xxx function to lists: how would you handle empty lists? You have to answer this question somehow, and writing a new function for lists is the easiest way.

You can now use your xxxl function with sortBy to sorts lists of lists: sortBy xxx ....

Upvotes: 1

Related Questions