Combine equivalent items in a list

Question

Let's say I have the following type

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

And if I have an array of them 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 any duplicate keys? If two keys match, I want to take the better score

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

Answer 1

A very simple solution is to use Data.Map.fromListWith, which converts a list of key-value pairs to a map, given a 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 as necessary. Also, it does not preserve the order of the input elements. Run time is O(n log n).

Answer 2

Basically first we must decide what is problem solving and what is implementation difficulties. So what If we first sort by Score, and then just keep the first occurrences in the sorted list with respect to Key? That should work, let's 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 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 uncertain about the functions I used in the solution. It indeed takes some time to learn how to use on and those functions.