haskell - 按值对 Data.Map 进行排序并获取所有最大值

Question

我的 Data.Map 看起来像这样:

fromList [("eso",1),("mes",1),("ome",2),("som",2)]

我需要从此映射中获取值最大的键列表:

["ome","som"]

这是我的解决方案:

get_max_from_map m = map fst (filter is_biggest sorted)
    where sorted = List.sortBy (\(k1, v1) (k2, v2) -> v2 `compare` v1) $ Map.toList m
          max_v = snd $ head sorted
          is_biggest (key, value) = value == max_v

我将 map 转换为列表，对它们进行排序，获取第一个值作为最大值并过滤列表。

我只是想知道这个任务是否有更优化、更漂亮的解决方案？

谢谢。

Answer 1

这并不比您原始帖子中的内容简单，但它的优点是成为线性时间、一次性解决方案(您的版本是 O(n log n)因为它对列表进行排序，并且到目前为止发布的其他答案都是两次通过的解决方案)。

getMaxFromMap m = go [] Nothing (Map.toList m)
  where
    go ks _        []           = ks 
    go ks Nothing  ((k,v):rest) = go (k:ks) (Just v) rest
    go ks (Just u) ((k,v):rest)
        | v < u     = go ks     (Just u) rest
        | v > u     = go [k]    (Just v) rest
        | otherwise = go (k:ks) (Just v) rest