3

我的 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

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

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

谢谢。

4

3 回答 3

5

这并不比您原始帖子中的内容简单，但它具有线性时间、一次性解决方案的优势（您的版本是 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
于 2013-11-01T09:32:13.257 回答
2

你需要做 2 个任务 - 找到最大值，过滤

get_max_from_lst xs = map fst $ filter ((== m) . snd) xs
    where m = maximum $ map snd xs

这是为了列表。

如果我们有地图，那么：

import Data.Map.Lazy as M

get_max_from_map xs = M.keys $ M.filter (== m) xs
    where m = maximum $ M.elems xs
于 2013-11-01T09:12:48.127 回答
2

您可以使用monadData.Map中的函数来处理此问题。Maybe

编辑：这是一个使用镜头导入的工作版本。

import Control.Lens
import Data.Map (Map)
import qualified Data.Map as Map

getYourKeys :: Eq a => Map k a -> Maybe [k]
getYourKeys m = do
  maxValue <- maximumOf traverse m
  return . Map.keys . Map.filter (== maxValue) $ m
于 2013-11-01T09:10:47.647 回答