有没有maximumWith之类的东西？

Question

具体来说，我正在搜索一个函数 'maximumWith'，

maximumWith :: (Foldable f, Ord b) => (a -> b) -> f a -> a

其行为如下：

maximumWith length [[1, 2], [0, 1, 3]] == [0, 1, 3]
maximumWith null [[(+), (*)], []] == []
maximumWith (const True) x == head x

我的用例是选择列表中最长的单词。
为此，我想要类似于 maximumWith length.

的东西

我以为存在这样的东西，因为 sortWith 等存在。

Answer 1

让我把评论里的笔记全部收集起来...

我们来看sort。家族中有4个函数：

sortBy是实际执行。
<a href="https://hackage.haskell.org/package/base-4.12.0.0/docs/src/Data.OldList.html#sortBy" rel="nofollow noreferrer">sort</a> = sortBy compare 使用 Ord 重载。
<a href="https://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Exts.html#sortWith" rel="nofollow noreferrer">sortWith</a> = 排序方式。 comparing 是你想要的 maximumWith 的类似物。但是，这个功能有一个问题。元素的排名是通过将给定的映射函数应用于它来给出的。但是，排名不会被记忆，所以如果一个元素需要多次比较，排名将重新计算。如果排名功能非常便宜，您只能无罪地使用它。这些函数包括选择器（例如 fst）和 newtype 构造函数。 YMMV 关于简单算术和数据构造函数。在这种低效率、定义的简单性及其在 GHC.Exts 中的位置之间，很容易推断出它并不经常使用。
sortOn 通过在排名函数下成对地用图像装饰每个元素，按排名排序，然后擦除它们来解决效率低下的问题。

前两个在 maximum 中有类似物：maximumBy 和 maximum。 sortWith没有类比；你不妨每次写出maximumBy (comparing _)。也没有maximumOn，尽管这样的事情会更有效率。定义 maximumOn 的最简单方法可能只是复制 sortOn:

maximumOn :: (Functor f, Foldable f, Ord r) => (a -> r) -> f a -> a
maximumOn rank = snd . maximumBy (comparing fst) . fmap annotate
  where annotate e = let r = rank e in r `seq` (r, e)

maximumBy 中有一些有趣的代码阻止了它在列表上的正确优化。它也适用于使用

maximumOn :: (Foldable f, Ord r) => (a -> r) -> f a -> a
maximumOn rank = snd . fromJust . foldl' max' Nothing
    where max' Nothing x = let r = rank x in r `seq` Just (r, x)
          max' old@(Just (ro, xo)) xn = let rn = rank xn
                                         in case ro `compare` rn of
                                                 LT -> Just (rn, xo)
                                                 _ -> old

这些编译指示可能有用：

{-# SPECIALIZE maximumOn :: Ord r => (a -> r) -> [a] -> a #-}
{-# SPECIALIZE maximumOn :: (a -> Int) -> [a] -> a #-}

Answer 2

HTNW 已经解释了如何按照您的要求进行操作，但我想我应该提到对于您提到的特定应用程序，在某些情况下有一种更有效的方法（假设这些词由 String 表示）秒）。假设你想要

longest :: [[a]] -> [a]

如果您要求 maximumOn length [replicate (10^9) (), []]，那么您最终会不必要地计算一个非常长的列表的长度。有几种方法可以解决这个问题，但我会这样做：

data MS a = MS
  { _longest :: [a]
  , _longest_suffix :: [a]
  , _longest_bound :: !Int }

我们将确保 longest 是迄今为止看到的最长字符串中的第一个，并且 longest_bound + length longest_suffix = length longest.

step :: MS a -> [a] -> MS a
step (MS longest longest_suffix longest_bound) xs =
    go longest_bound longest_suffix xs'
  where
    -- the new list is not longer
    go n suffo [] = MS longest suffo n
    -- the new list is longer
    go n [] suffn = MS xs suffn n
    -- don't know yet
    go !n (_ : suffo) (_ : suffn) =
      go (n + 1) suffo suffn

    xs' = drop longest_bound xs

longest :: [[a]] -> [a]
longest = _longest . foldl' step (MS [] [] 0)

现在，如果倒数第二长的列表有 q 个元素，我们将最多 q 个 cones 进入每个列表。这是最好的复杂性。当然，只有当最长的列表比倒数第二长的列表长得多时，它才明显优于 maximumOn 解决方案。

有没有maximumWith之类的东西？

Is there such a thing as maximumWith?

sorting

haskell

foldable