地图中的最小值haskell

Question

我有一个关于如何检索a的最小值的问题Map.

我有一个Map k (Maybe a,Maybe b),我需要检索元组的第一个元素(最小的a)上具有最小值的键,但我找不到任何预定义的函数.是否有一些我可以使用的功能,或者我应该自己实现？谢谢

Answer 1

你需要约束Ord a.此外,您还需要决定如何比较Just x和Nothing(因为你必须比较(Just x, y)有(Nothing, z)).我假设你想要Just x比Nothing所有人都小x.如果您使用toList将地图转换为列表,则可以minimumBy在列表中使用自定义比较功能.而且,元组(Maybe b)的第二部分是无关紧要的,所以我们只需要调用Map k (Maybe a, b)并获得更通用的函数.

我建议像

import qualified Data.Map as M
import Data.List

minimum' :: (Ord a) => M.Map k (Maybe a, b) -> k
minimum' = fst . (minimumBy comp) . M.toList
    where
      comp (_, (Nothing, _)) (_, (Just _, _)) = GT
      comp (_, (Just _, _)) (_, (Nothing, _)) = LT
      comp (_, (Nothing, _)) (_, (Nothing, _)) = EQ
      comp (_, (Just x, _)) (_, (Just y, _)) = compare x y

很难说出你真正想要的关于Nothings 的行为,但是另一个更合理的(*)替代方法是使最小函数具有返回类型Maybe k,Nothing如果找到最小元素则返回(如上所述)是(Nothing, _).实现此目的的一种方法是首先filter返回返回的列表toList以消除其值为的所有元素(Nothing, _).

(*)Just x小于Nothing有点坏.在寻找最大的元素时,你会想要相反的行为,所以这一切都变得相当不一致和丑陋.换句话说,当类型a被排序时,类型Maybe a只是部分排序(以自然的方式 - 当然你可以强制总订单,如上所述).