Haskell maximumBy对于Ord实例

Question

我一直在寻找自己想要的功能，而我总是需要自己实现它，但是我觉得它必须是内置的。

基本上，我想要的介于maximum和之间maximumBy。

maximum取值列表Ord并返回最大值。这是O（n）。

maximum :: (Ord a) => [a] -> a

maximumBy获取非Ord值列表和为它们提供排序的排序函数，并使用该函数计算最大值。这是O（nlogn）（或某种排序的复杂性）。

maximumBy :: (a -> a -> Ordering) -> [a] -> a

我想要一个maximumBy接受类型值列表a和一个返回Ord值的a函数，并a使用这些Ord值计算最大值的函数。这将是O（n），因为它只需要跟踪最大值即可。该签名将是这样的：

maximumBy' :: (Ord b) => (a -> b) -> [a] -> a

这是我的粗略实现：

maximumBy' func list = foldl1' (\max i -> let (maxby, iby) = (func max, func i) in if iby > maxby then i else max) list

是否有内置的这种功能，或者使用现有的内置功能编写此功能的简便方法？

Answer 1

首先，您提出错误的主张：

maximumBy获取非Ord值的列表以及为它们提供排序的排序函数，并使用该函数计算最大值。这是O（nlogn）。

无需排序即可计算最大元素。排序关系必须是自反的，反对称的和可传递的，因此可以简单地始终保持到目前为止的最大值，并使用自定义比较来检查新项目是否更大。

此外，您可以构造以下maximumBy'功能：

maximumBy' f = maximumBy (compare `on` f)

正确; 但是，“在f上进行比较”确实会对性能造成重大影响，因为对于每个比较，“ f”都需要在_both_元素上进行计算，即，对f的调用次数是必需的两倍。 (2认同)

Answer 2

我认为您所寻找的内容很容易用以下方式表达Data.Ord.comparing：

而不是使用你的maximumBy'函数：

maximumBy' head ["abc", "def", "geh"]

您可以构建一个比较器并将comparing其提供给通常的maximumBy：

maximumBy (comparing head) ["abc", "def", "geh"]

正如 Willem Van Onsem 在另一个答案中所说，您担心的成本是不正确的maximumBy：它不会对列表进行排序。