Combining equivalent items in a list

Question

Say I have the following type

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

And if I have an array like this:

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

Is there a standard way to reduce this so that I don't have duplicate keys? If two keys match, I want to get the best result

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

Answer 1

Basically, we must first decide what problem solving is and what are the difficulties of implementation. So, what if we sort the Score first and then just store the first occurrences in the sorted list with respect to Key ? This should work, look at the haskell implementation:

 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 

Now we try to run this in 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}] 

Checkout hoogle if you are not sure about the features that I used in the solution. It really takes some time to learn how to use on and these functions.

Answer 2

A very simple solution is to use Data.Map.fromListWith , which converts a list of key-value pairs into a map with a given function to combine multiple values ​​with the same key.

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

Note that this expects tuples, so convert them if necessary. In addition, it does not preserve the order of input elements. Runtime - O (n log n).

Answer 3

I am posting an O (n log n) solution as everything seems perfect with O (n ^ 2)

 consolidate :: (Ord a, Ord b) => [Thing ab] -> [Thing ab] 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

Here is my weak attempt. It’s better there, of course, but I'm not a big part of the Haskell programmer.

 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)