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!

Solution 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")]

Solution 2

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)

Solution 3

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.) Then we can give this ordering function to sortBy and it will sort it's input according to this ordering.

Since you want the first components to have first priority, we check that first and if they are equal we check the second argument,if the first components is not equal we give it the opposite value of it's original ordering, so that it is ordered highest to lowest.

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")]

Solution 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")]

Solution 5

The following solution works best for me, a Haskell newbie. It looks a lot like 3lectrologos' answer: I actually only added the function definition and the List import, but it can cause some confusion if left out.

Create a function 'myCompare' and don't forget to import the List module. You'll need it to make the sortBy work. The function should look like this:

import Data.List

myCompare :: (Ord a, Ord b) => (a,b) -> (a,b) -> Ordering  
myCompare (a1,b1) (a2,b2)
     | a1 < a2     = GT  
     | a2 == a1    = EQ  
     | otherwise = LT

After loading the Haskell file, you can write the following in your terminal:

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

Which will return:

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

View more solutions

Comments

[Tyler]

@haskell noob Note that the comparison of the first arguments (the a's) actually comes first, because that comparison takes precedence over the b's. I would probably describe this as "sorting by the first argument first" but of course it's clear what you meant, since you gave an example.

[eclipseNoob]

Thanks 3lectrologos! Worked like a charm. @MatrixFrog - Sorry for the confusing english. Not my first language anyways!

[eclipseNoob]

Wow. This is too confusing. It works but it's hard and beyond my level of haskell knowledge. Thanks though!

[fredoverflow]

You can simplify the invert function to invert = compare EQ ;)

[Paul Johnson]

This is what "compare" does by default anyway. compare (1,"b") (2, "a") = LT. The original poster wanted to do it the other way around.

[Norman Ramsey]

@Fred: Sweet! But I do worry about making the code completely impenetrable. I've put your version up for comparison.

[Hans-Kristian Norum Eidesen]

Can't you even get rid of explicit lambda parameters p and p' and make your code pointlessly point-free ;) ? Would be nice too ...

[Hans-Kristian Norum Eidesen]

Isn't \p p' -> uncurry compare $ double fst p p' equal to compare 'on' fst?

[Norman Ramsey]

@Dario: Nice work. I always forget about on. But we can do better: on compare == comparing. Now if only there were a predefined version of post...

[3lectrologos]

@Paul Johnson: The above implementation gives sortGT (1,"b") (2,"a") = GT, because a1 = 1 < 2 = a2, so it's not what "compare" does by default.

[semicolon]

A quicker definition for sortGT is (flip compare `on` fst) <> compare. Due to the nice Monoid definition for functions. Or (flip compare `on` fst) <> (compare `on` snd) for slightly more speed as then the first element of each tuple is only ever compared once.