0

具体来说，我正在寻找一个函数'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等存在。

4

2 回答 2

4

让我把评论里的所有笔记都收集起来……

让我们看看sort。家庭有4个功能：

  • sortBy是实际的实现。
  • sort = sortBy compare使用Ord重载。
  • sortWith = sortBy . comparing是您想要的类似物maximumWith。但是，这个函数有一个问题。元素的排名是通过将给定的映射函数应用于它来给出的。但是，排名不会被记忆，所以如果一个元素需要多次比较，排名将被重新计算。如果排名功能非常便宜，您只能无罪地使用它。这样的函数包括选择器（例如fst）和newtype构造器。YMMV 关于简单算术和数据构造函数。在这种低效率、定义的简单性以及它在 中的位置之间GHC.Exts，很容易推断它不经常使用。
  • sortOn通过在一对排序函数下用其图像装饰每个元素，按等级排序，然后删除它们来解决效率低下的问题。

前两个在maximum:maximumBy和maximum. sortWith没有类比；你不妨maximumBy (comparing _)每次都写出来。也没有maximumOn，即使这样的事情会更有效率。定义 a 的最简单方法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

这些 pragma 可能有用：

{-# SPECIALIZE maximumOn :: Ord r => (a -> r) -> [a] -> a #-}
{-# SPECIALIZE maximumOn :: (a -> Int) -> [a] -> a #-}
于 2018-10-09T16:59:32.523 回答
2

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

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进入每个列表。这是最好的复杂性。maximumOn当然，只有当最长的列表比第二长的列表长得多时，它才比解决方案好得多。

于 2018-10-09T20:40:24.550 回答