CODEWITHSUNDEEP
listhaskelltuples
user6005857
user6005857

Reputation: 631

Sorting a list of tuples by second element without using sortBy

Suppose the input to the function is:

[(6,-275),(3,123),(7,1000),(9,-572),(3,333),(1,-23)]

The output should be:

[(9,-572),(6,-275),(1,-23),(3,123),(3,333),(7,1000)]

Here is the function I want to make:

sortBySnd :: Ord a => [(a,a)] -> [(a,a)]
sortBySnd [] = []
sortBySnd [(_,a),(_,b)]
    | a < b = [(_,a),(_,b)]
    | a > b = [(_,b),(_,a)]
    | a == b = [(_,a),(_,b)]

This of course is very wrong but I just wanted to show what I want to achieve.

For a sorting function, can just use mergesort or some builtin sorting function other than sortBy.

Upvotes: 3

Views: 1267

Answers (3)

erisco
erisco

Reputation: 14319

Just for fun, using Data.Map:

uncurry (fmap.flip(,))  -- distribute the keys over the values
<=< toList              -- convert back to a list, now sorted
. fromListWith (++)     -- convert to Map, collect values with same keys
. fmap (fmap(:[]).swap) -- swap the pairs and promote snd to a list

Upvotes: 2

leftaroundabout
leftaroundabout

Reputation: 120711

As already done by Carsten, you can achieve this by “masking” the first element and then just using a normal sort. Flipping the elements kind of achieves this, though it's rather a hack (the first element will still get sorted, just with lower priority)... a somewhat better method would be to use a type that really compares only the second element:

data SndOrd a b = SndOrd a b

instance Eq SndOrd where SndOrd _ x == SndOrd _ y = x==y
instance Ord SndOrd where compare (SndOrd _ x) (SndOrd _ y) = compare x y

Then you can do

sortT = map (\(SndOrd a b) -> (a,b)) . sort . map (\(a,b) -> SndOrd a b)

However, I wouldn't recommend this, because it's usually expected that == is a proper equality, but with this approach you have SndOrd 1 2 == SndOrd 3 2.

The right approach, of course, is to use sortBy! Or to implement it yourself. Writing a general sorting algorithm is a topic you can find tons of resources on on the internet, you should check out those first before asking on StackOverflow...

You own attempt is not completely meaningless. First we need to get it to actually cover lists of length other than 0 or 2, by recursion:

sortBySnd' ((_,a):(_,b):l)
    | a < b  = (_,a) : sortBySnd' ((_,b):l)
    | a > b  = (_,b) : sortBySnd' ((_,a):l)
    | a == b = (_,a) : sortBySnd' ((_,b):l)
sortBySnd' l = l  -- lists with length <2 are already sorted!

Note that you can unify the first and third guards:

sortBySnd' ((_,a):(_,b):l)
    | a > b     = (_,b) : sortBySnd' ((_,a):l)
    | otherwise = (_,a) : sortBySnd' ((_,b):l)
sortBySnd' l = l  -- lists with length <2 are already sorted!

Now, this doesn't work right yet, since every element can step at most one cell backwards in the list. You can salvage this by iterating the whole process as often as the list has elements:

sortBySnd'' l = iterate sortBySnd' l !! length l

This is bubble sort, a very inefficient algorithm but it works.

Upvotes: 1

Random Dev
Random Dev

Reputation: 52270

here is what I meant:

import Data.List (sort)
import Data.Tuple (swap)

sortT = map swap . sort . map swap

Upvotes: 6

Related Questions