相对于另一个列表排序多图？

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长度为n且ys长度为m,则其运行时间应为O(n log n +(m + n)log m),如果m为O(n),则为O(n log n).