In Haskell, how can I use the built in sortBy function to sort a list of pairs(tuple)?

Question

I am a beginner in Haskell so please bear with me. (Just started learning yesterday!) How can I sort a list of tuples primarily by their first components (highest to smallest) and secondarily by their second components (smallest to highest)? A sample input/output would be:

[(1, "b"), (1, "a"), (2, "b"), (2, "a")] (input)

[(1, "a"), (2, "a"), (1, "b"), (2, "b")] (middle step)

[(2, "a"), (2, "b"), (1, "a"), (1, "b")] (output)

I tried using the following but it gave wrong output:

sortGT a b = GT

sortBy sortGT lst

I am sure that I can do this by using sortBy only, but I can't figure it out myself. Any help would be highly appreciated!

Answer 1

You need to construct your function sortGT, so that it compares pairs the way you want it:

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

Using this you get the following results (I used ghci):

*Main Data.List> sortBy sortGT [(1, "b"), (1, "a"), (2, "b"), (2, "a")]
[(2,"a"),(2,"b"),(1,"a"),(1,"b")]

Answer 2

It's always tricky composing two-argument functions. Here's an implementation:

invert :: Ordering -> Ordering
invert GT = LT
invert LT = GT
invert EQ = EQ


sosort :: (Ord a, Ord b) => [(a, b)] -> [(a, b)]
sosort = sortBy (\p p' -> invert $ uncurry compare $ double fst p p') . 
         sortBy (\p p' ->          uncurry compare $ double snd p p')
  where double f a a' = (f a, f a')

Because sortBy expects a function of two arguments, function composition isn't so nice.

I have tested this code, and it works on your example.

As Fred points out, you can write compare EQ instead of invert. As Dario points out, I could be using on from Data.Function, but in fact on compare == comparing, which I can use instead. Now the code can be read only by a Haskell Master:

sosort :: (Ord a, Ord b) => [(a, b)] -> [(a, b)]
sosort = sortBy (compare EQ `post` comparing fst) . sortBy (comparing snd)
  where post f g x x' = f (g x x')

I have compiled and run this code and it works on the original example.

(I haven't got any votes for this answer, but thanks to good comments, I sure have learned a lot about the Haskell library. Who knows what function post is equivalent to? Not Hoogle...)

It would be more idiomatic to write a suitable comparison function for pairs, but your question asked for consecutive sorts.

Answer 3

May I suggest the following?

import Data.List (sortBy)
import Data.Monoid (mconcat)

myPredicate (a1, a2) (b1, b2) = mconcat [compare b1 a1, compare a2 b2]

You can then sort by writing sortBy myPredicate lst. The function mconcat simply scans through the list and obtains the first non-EQ occurence (or EQ if all elements are EQ and thus both pairs are considered equal).

On second thought, building the list isn't necessary.

import Data.List (sortBy)
import Data.Monoid (mappend)

myPredicate (a1, a2) (b1, b2) = compare b1 a1 `mappend` compare a2 b2

The definition of mappend for Ordering is essentially:

EQ `mappend` x = x
x  `mappend` _ = x

Which is exactly what we need.

Just for fun, generalizing gbacon's answer and making the use a little more flexible:

import Data.Ord
import Data.List
import Data.Monoid

ascending  = id
descending = flip

sortPairs f x g y = f (comparing x) `mappend` g (comparing y)

mySort = sortBy (sortPairs descending fst ascending snd)

Answer 4

Congratulations on taking your first steps to learn Haskell. It's a great journey!

Riffing on FredOverflow's answer:

import Data.Ord
import Data.List
import Data.Monoid

main :: IO ()
main = do
  print $ sortBy cmp [(1, "b"), (1, "a"), (2, "b"), (2, "a")]
  where
    cmp = flip (comparing fst) `mappend` comparing snd

Output:

[(2,"a"),(2,"b"),(1,"a"),(1,"b")]

Answer 5

First we should make the ordering function wich takes two touples and returns either EQ,LT or GT (ie. sortGT :: (a,b)->(a,b)->Ordering.) Since you want the first argument to have first priority and reversed order, we check that first and if they are equal (compare returns EQ) we check the second argument, otherwise we return LT if its GT and GT if its LT. This is what I think is easiest on the eyes :

sortGT (a1,b1) (a2,b2) = case compare a1 a2 of
                              EQ -> compare b1 b2
                              LT -> GT
                              GT -> LT

Now we use sortBy as you suggested :

*Main> sortBy sortGT [(1, "b"), (1, "a"), (2, "b"), (2, "a")]
[(2,"a"),(2,"b"),(1,"a"),(1,"b")]