CODEWITHSUNDEEP
haskell
Florian
Florian

Reputation: 267

How to create a ranking based on a list of scores in Haskell?

So I got a score list and want to create a ranking list from it. If scores are the same they share a rank.

For example if I have a score list like

[100, 100, 50, 50, 20]

the generated list would be

[(100, 1), (100, 1), (50, 2), (50, 2), (20, 3)]

I guess this is a fairly simple task, but I haven't gotten to solve it yet. I tried to do it with pattern matching or folding but without any luck.

My last failed approach looks like this:

scores = [100, 100, 50, 50, 20, 10]

ranks = foldr (\x acc -> if x == (fst $ last acc)
  then last acc:acc
  else (x, (+1) $ snd $ last acc):acc) [(head scores, 1)] scores

Any help is appreciated.

Upvotes: 2

Views: 657

Answers (3)

dfeuer
dfeuer

Reputation: 48611

Here's a simple one-liner, putting some off-the-shelf pieces together with a list comprehension.

import Data.List
import Data.Ord (Down (..))

rank :: Ord a => [a] -> [(a, Int)]
rank xs = [(a, i) | (i, as) <- zip [1..] . group . sortBy (comparing Down) $ xs
          , a <- as]

If the list is already sorted in reverse order, you can leave out the sortBy (comparing Down).

Upvotes: 2

Silvio Mayolo
Silvio Mayolo

Reputation: 70297

This solution is fairly similar to Willem's, except that it doesn't explicitly use recursion. Many style guides, including the Haskell wiki, suggest to avoid explicit recursion if there's a simple implementation involving higher-order functions. In your case, your function is a pretty straightforward use of scanl, which folds a list with an accumulating value (in your case, the accumulator is the current rank and score) and stores the intermediate results.

ranks :: Eq a => [a] -> [(a, Int)]
-- Handle the empty case trivially.
ranks [] = []
-- Scan left-to-right. The first element of the result should always
-- have rank 1, hence the `(x, 1)' for the starting conditions.
ranks (x:xs) = scanl go (x, 1) xs
    -- The actual recursion is handled by `scanl'. `go' just
    -- handles each specific iteration.
    where go (curr, rank) y
              -- If the "current" score equals the next element,
              -- don't change the rank.
              | curr == y = (curr, rank)
              -- If they're not equal, increment the rank and
              -- move on.
              | otherwise = (y, rank + 1)

By avoiding explicit recursion, it's arguably easier to see at a glance what the function does. I can look at this, immediately see the scanl, and know that the function will be iterating over the list left-to-right with some state (the rank) and producing intermediate results.

Upvotes: 5

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477160

We can write a recursive algorithm that maintains a state: the current rank it is assigning. The algorithm each time looks two elements far. In case the next element is the same, the rank is not incremented, otherwise it is.

We thus can implement it like:

rank :: Eq a => [a] -> [(a, Int)]
rank = go 1
    where go i (x:xr@(x2:_)) = (x, i) : go'
              where go' | x == x2 = go i xr
                        | otherwise = go (i+1) xr
          go i [x] = [(x, i)]
          go _ [] = []

We thus specify that rank = go 1, we thus "initialize" a state with 1. Each time we check with go if the list contains at least two elements. If that is the case, we first emit the first element with the state (x, i), and then we perform recursion on the rest xr. Depending on whether the first element x is equal to the second element x2, we do or do not increment the state. In case the list only contains one element x, we thus return [(x, i)], and in case the list contains no elements at all, we return the empty list.

Note that this assumes that the scores are already in descending order (or in an order from "best" to "worst", since in some games the "score" is sometimes a negative thing). We can however use a sort step as pre-processing if that would not be the case.

Upvotes: 3

Related Questions