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

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

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

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 и повторяющийся поиск и удаление на данной мультикарте).


list sorting haskell multimap
person bbtrb    schedule 28.12.2011    source источник

Ответы (4)


arrow_upward
6
arrow_downward

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

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)< /em>, что равно O(n log n), если m равно O(n).

person hammar    schedule 28.12.2011

arrow_upward
4
arrow_downward

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.

person Sjoerd Visscher    schedule 28.12.2011

arrow_upward
0
arrow_downward

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

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
person gspr    schedule 28.12.2011

arrow_upward
0
arrow_downward 

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
person FAQ-MAN    schedule 28.12.2011