合并列表中的等价物品

Question

比方说，我有以下类型

type Key = String 
type Score = Int 
data Thing = Thing Key Score 

如果我对他们有一个这样的数组：

[Thing "a" 7, Thing "b" 5, Thing "a" 10] 

有减少这种这么一个标准的方法我没有任何重复的密钥？如果两个键匹配，我想要取得更好的分数

[Thing "b" 5, Thing "a" 10] 

Answer 1

基本上首先我们必须决定什么是问题解决和什么是实施困难。那么，如果我们首先按Score排序，然后将排序列表中的第一个匹配项保留为Key？这应该工作，让我们来看看Haskell的实现：

import Data.List 
import Data.Function 

type Key = String 
type Score = Int 
data Thing = Thing { key :: Key, score :: Score } 
    deriving (Show) 

myNub = nubBy ((==) `on` key) 
mySort = sortBy (compare `on` (negate . score)) 

selectFinest = myNub . mySort 

现在我们尝试在ghci运行此：

Prelude> :load Test.hs 
[1 of 1] Compiling Main    (Test.hs, interpreted) 
Ok, modules loaded: Main. 
*Main> selectFinest [Thing "a" 7, Thing "b" 5, Thing "a" 10] 
[Thing {key = "a", score = 10},Thing {key = "b", score = 5}] 

结帐hoogle如果你不确定我解决方案中使用的功能。确实需要一些时间来学习如何使用on和这些功能。

Answer 2

这是我的微弱尝试。肯定有更好的方法，但我不是一个Haskell程序员的大部分。

import Data.List 

type Key = String 
type Score = Int 
data Thing = Thing Key Score 
      deriving (Show, Ord) 

instance Eq Thing where 
    (Thing k1 _) == (Thing k2 _) = k1 == k2 
    (Thing k1 _) /= (Thing k2 _) = k1 /= k2 

thingSort :: [Thing] -> [Thing] 
thingSort = Data.List.sortBy (flip compare) 

ex = [Thing "a" 7, Thing "b" 5, Thing "a" 10] 

filtered = nub (thingSort ex) 

Answer 3

我张贴一个为O（n log n）的解决方案，因为每个人似乎罚款是为O（n^2）

consolidate :: (Ord a, Ord b) => [Thing a b] -> [Thing a b] 
consolidate xs = 
    max_from_each_group (sortBy (compare `on` getKey) xs) 
    where 
     max_from_each_group [] = [] 
     max_from_each_group (x:xs) = 
      let (same_key, rest) = span (\t -> x == getKey t) xs in 
      let group_max = maximumBy (compare `on` getValue) (x:same_key) in 
      group_max : max_from_each_group rest 

Answer 4

一个非常简单的解决方案是使用Data.Map.fromListWith，它转换一个给映射的键值对的列表，给定一个函数来将多个值与同一个键相结合。

Prelude Data.Map> fromListWith max [("a", 7), ("b", 5), ("a", 10)] 
fromList [("a",10),("b",5)] 

请注意，这需要元组，所以根据需要进行转换。此外，它不保留输入元素的顺序。运行时间是O（n log n）。