Есть ли такая вещь, как 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 это фактическая реализация.
• sort = sortBy compare использования Ord перегрузка.
• sortWith = sortBy . 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 входит в каждый список. Это наилучшая возможная сложность. Конечно, это только значительно лучше, чем maximumOn решение, когда самый длинный список намного длиннее, чем второй, самый длинный.