合併列表中的等價物品

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）。