Most elegant approach to writing list renumbering function

I'm writing a function with the following signature:

(Ord a) => [a] -> [Int]

It's semantics is to find an order-preserving mapping from list of objects to list of Ints.

The version of mine:

import Data.List
import Data.Map (Map, (!))
import qualified Data.Map as Map 

renumber :: (Ord a) => [a] -> [Int]
renumber list = let mapping = buildmapping list Map.empty in
                map (mapping!) list
        where
            -- buildmapping :: (Ord a) => [a] -> Map a Int -> Map a Int
            buildmapping list mapping = let
                mapped = Map.keys mapping
                (rest, nextindex) = if (null mapped) then
                      (list, 1) else
                      (filter (> maximum mapped) list,
                        (1+) $ maximum $ Map.elems mapping)
                in case rest of
                  [] -> mapping -- nothing left, return
                  _  -> buildmapping rest $ Map.insert (minimum rest) nextindex mapping

I think a sorting-based approach would be simpler than using a map. The basic idea is that we sort the list, assign each item a value based on its position in the list, then undo the sorting and take the value assigned to each item. In order to undo the sorting we have to remember the position each item was at before the sort. So we get the following steps (illustrated using the example input ["a", "c", "b", "c"]):

• Annotate each item with its index. So ["a","c","b","c"] becomes [(1, "a"), (2, "c"), (3, "b"), (4, "c")].

• Sort the annotated items by their value. So for the example we get [(1, "a"), (3, "b"), (2, "c"), (4, "c")]

• Group the sorted annotated items by their values, so that duplicate items get assigned the same number in the next step. In the example: [[(1, "a")], [(3, "b")], [(2, "c"), (4, "c")]]

• Now annotate each group with its index again. In the example: [(1, [(1, "a")]), (2, [(3, "b")]), (3, [(2, "c"), (4, "c")])].

• Flatten the groups, so that instead of a list of groups we have a list of items again where each item has an old index and new index. In the example: [(1, (1, "a")), (2, (3, "b")), (3, (2, "c")), (3, (4, "c"))].

• Now undo the sorting by sorting the items by their old index. In the example: [(1, (1, "a")), (3, (2, "c")), (2, (3, "b")), (3, (4, "c"))].

• Lastly map each item to their new index. So for the example we get the output [1,3,2,3].

This leads to the following code:

{-# LANGUAGE TupleSections #-}
import Data.List
import Data.Function (on)
import Data.Ord (comparing)

renumber :: (Ord a) => [a] -> [Int]
renumber = map fst . unsort . number . indexAndSort
    where
      indexAndSort = sortBy (comparing snd) . zip [1..]
      number = concatMap (\(i,xs) -> map (i,) xs) . zip [1..] . groupBy ((==) `on` snd)
      unsort = sortBy (comparing (fst . snd))

Note that I chose 1-based indices instead of 0-based indices because you start numbering at 1 as well and this way my code produces the same results as yours.

StackExchange Code Review Q#2019, answer score: 4