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

Question

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

Я ищу функцию со следующей подписью

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 имеет длину п и ys имеет длину м, время выполнения этого должно быть О (п войти п + (т + п) войти м), который является О (п § п), если м является 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 :: (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 

Answer 4

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