Sort one list by the order of another list

Question

I need to sort one list by the order of another, but I don't know how it can be done.

For example: I could have a list a similar to:

[C, B, G, E]

And a list b (that sets the order):

[A, B, C, D, E, F, G, ...]

(Just as example, these aren't the actual values though)

Then, list a should be sorted the same way as List b and thus become sorted to:

[B, C, E, G]

How to do this sorting by the order of another list?

Answer 1

If I understand, one of the lists give the relative order of all the elements of the other list. Ie:

 > sortWithOrder [5,1,2,3,4] [1,2,3,4,5,5,4,3,2,1]
 [5,5,1,1,2,2,3,3,4,4]

This piece of code should work :

module SortWithOrder where

import qualified Data.Map.Strict as M
import Data.List
import Data.Ord

sortWithOrder :: Ord a
              => [a] -- order list
              -> [a] -- source list
              -> [a]
sortWithOrder order = sortBy (comparing getOrder)
    where
        getOrder k = M.findWithDefault (-1) k ordermap
        ordermap = M.fromList (zip order [0..])

Edit: a more efficient solution is to use sortOn, like this:

sortWithOrder order = sortOn getOrder

Answer 2

You could also map the order to the list and sort it:

Prelude> let order = zip ["A", "B", "C", "D", "E", "F", "G"] [0..]

Prelude> let myList = ["C", "B", "G", "E"]

Prelude> import Data.List (sort)

Prelude> map snd . sort . map (\x -> (lookup x order, x)) $ myList

["B","C","E","G"]

Thus we can define this function as

sortAlong :: Eq b => [b] -> [b] -> [b]
sortAlong order = map snd . sortBy (comparing fst) . map (\x -> (lookup x z, x))
    where
    z = zip order [0..]

An Ord constraint allows the more efficient route through Map but this version needs just Eq:

> sortAlong "ABCDEFG" "CBGE"
"BCEG"