最小值在一个地图haskell

我有一个关于如何检索Map的最小值的问题。最小值在一个地图haskell

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

2012-11-30 user1544128

您将需要约束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

这是很难说什么样的行为，你真的想与问候到Nothing S，但另一种更合理的（*），替代将是最小的功能返回类型为Maybe k，如果找到的最小元素（如上所示）为(Nothing, _)，则返回Nothing。达到此目的的一种方法是首先用toList返回filter列表以消除所有值为(Nothing, _)的元素。

（*）让Just x小于Nothing有点不好。当你寻找最大的元素时，你会希望的行为与相反，所以它们都变得相当不稳定和丑陋。换句话说，当订购类型a时，类型Maybe a只有部分有序（以自然的方式 - 当然，您可以强制执行总订单，如上）。

来源

2012-11-30 12:46:26 gspr

您可能想要考虑的另一件事是，如果元组的第一个元素相等，该怎么做。在这种情况下，您可能需要使用第二个元素作为决胜盘。 – mhwombat

的确，但是这会引入'Ord b'约束，并且不清楚是否需要这种行为。但绝对是需要考虑的一点。 – gspr

@isturdy：我认为当mhwombat说“元组的第一个元素”时，他意味着* value *元组的第一个元素，而不是键值元组中的键。 – gspr

最小值在一个地图haskell

回答

相关问题