CODEWITHSUNDEEP
functionsortinghaskell
user1351008
user1351008

Reputation: 63

Sort a list into tuples

I’m new to Haskell and am trying to sort a list of tuples using their first element, using the sort function. So if I had ["a", "b", "a", "c", "c"] I would get something like [(1,"b"), (2,"a"), (2,"c")] (in alphabetical order in the event of the same number).

How would I go about doing this? I am totally lost at the moment… I am still trying to get into the ‘Haskell way of thinking’.

Upvotes: 0

Views: 336

Answers (1)

dave4420
dave4420

Reputation: 47042

import Data.List (sort, group)
import Control.Arrow ((&&&))

answer :: Eq a => [a] -> [(Int, a)]
answer = sort . map (length &&& head) . group . sort

But as you're a beginner, it's perhaps a bit much to tell you about &&&, so I'll rewrite it like this:

import Data.List (sort, group)

answer :: Eq a => [a] -> [(Int, a)]
answer = sort . map f . group . sort
  where f xs @ (x:_) = (length xs, x)

You'll note I'm calling sort twice. This is intentional.

The final sort (the one on the left) sorts the output list of tuples, and it just so happens that it sorts in ascending order of the first element of the tuple, breaking ties by sorting on the second element of the tuple.

The initial sort (the one on the right) sorts the input list, because of what group does: it groups adjacent equal elements into a sublist. (Incidentally, these sublists are guaranteed never to be empty --- otherwise it wouldn't be safe to use head or ignore the empty list option in the pattern match.)

The map f then turns these lists (e.g. ["a", "a"]) into what we're interested in: the number of times these elements occur, and a single representative of these elements (e.g. (2, "a")).

The idiom here is that we're using a pipeline: our input goes into a function, the output of that function goes into another function, and so on until the function at the end of the pipeline produces output that we present as our own output. Note that this only works because each function takes only a single argument (map takes two arguments, f is the first of those arguments, so map f takes one argument).

As a consequence of this, answer is a function even though its argument doesn't explicitly appear. This is point-free style.

In non point-free style, it would look like

answer xs = sort . map f . group . sort $ xs
  where f xs @ (x:_) = (length xs, x)

or

answer xs = sort $ map f $ group $ sort xs
  where f xs @ (x:_) = (length xs, x)

or

answer xs = sort (map f (group (sort xs)))
  where f xs @ (x:_) = (length xs, x)

It is a good idea to use point-free style when it makes your code clearer.

If you like, you can use the <<< operator (from Control.Arrow again, sorry) to make the dataflow direction superficially more explicit:

import Data.List (sort, group)
import Control.Arrow ((<<<))

answer :: Eq a => [a] -> [(Int, a)]
answer = sort <<< map f <<< group <<< sort
  where f xs @ (x:_) = (length xs, x)

Some people think that this is the wrong way round and want the functions that "happen" first to be on the left. These people can use >>> (also from Control.Arrow), which is exactly the same as <<< except its arguments are flipped round:

import Data.List (sort, group)
import Control.Arrow ((>>>))

answer :: Eq a => [a] -> [(Int, a)]
answer = sort >>> group >>> map f >>> sort
  where f xs @ (x:_) = (length xs, x)

Upvotes: 9

Related Questions