Сортировать мультикарту относительно другого списка?

Question

Учитывая определенный порядок ключей, как я могу отсортировать мультикарту (список кортежей с дублирующимися ключами) относительно этого списка, где порядок дублирующих элементов не имеет значения?

I'mищу функцию со следующей сигнатурой

sortByList :: [(a,b)] -> [a] -> [(a,b)]

, чтобы, например,

a = [(1,'a'), (2, 'b'), (102, 'c'), (2, 'z')]
b = [2,102,1]
sortByList a b   --    [(2,'b'), (2,'z'), (102, 'c'), (1, 'a')]
                 -- or [(2,'z'), (2,'b'), (102, 'c'), (1, 'a')] 
                 -- (order in duplicate keys irrelevant)

У меня есть несколько идей, как это реализовать, но все они кажутся уродливыми и громоздкими (используяlookup и повторное обнаружение и удаление на заданной мультикарте).

Answer 1

Я думаю, что это должно быть довольно оптимальным:

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

sortByList :: Ord a => [(a, b)] -> [a] -> [(a, b)]
sortByList xs ys = map snd $ sortBy (comparing fst) [(pos (fst x), x) | x <- xs]
  where order = M.fromList $ zip ys [1..]
        pos x = M.findWithDefault 0 x order

Если xs имеет длину n и ys имеет длину m , время выполнения этого должно составлять O (n log n + (m + n) ) log m) , что составляет O (n log n) , если m равно O (n) .

Answer 2

elemIndex - это необходимая вам функция:

import Data.List (sortBy, elemIndex)
import Data.Function (on)

sortByList :: Eq a => [(a,b)] -> [a] -> [(a,b)]
sortByList m as = sortBy (compare `on` (flip elemIndex as . fst)) m

Он помещает ключи, которых нет в списке, потому что Nothing < Just 0.

Answer 3

import Data.List 
sortByList::(Ord a,Ord b)=>[(a,b)]->[a]->[(a,b)]
sortByList m [] = m
sortByList m (x:xs) = sort(filter (\(a,b)->a==x) m)++ sortByList (filter (\(a,b)->a/=x) m) xs

Уродливый код, но он работает

import Data.List 
sortByList::(Ord a,Ord b)=>[(a,b)]->[a]->[(a,b)]
sortByList m [] = m
sortByList m (x:xs) = let t = filter (\(a,b)->a==x) m in sort t ++ sortByList (m\\t) xs

Answer 4

Вот далеко не оптимальное предложение:

import Data.List

sortByList :: (Eq a) => [(a,b)] -> [a] -> [(a,b)]
sortByList toSort order = reverse (go [] toSort order)
    where
      go result xs [] = xs ++ result
      go result xs (k:ks) = go (matches ++ result) unmatches ks
          where
            (matches, unmatches) = partition ((==k) . fst) xs