Есть ли такая вещь, как MaximumWith? - PullRequest
Новая
       43

Есть ли такая вещь, как MaximumWith?

0 голосов
/ 09 октября 2018

В частности, я ищу функцию '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 и т. д.

Ответы [ 2 ]

0 голосов
/ 09 октября 2018

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, когда самый длинный список намного длиннее, чем второй, самый длинный.

0 голосов
/ 09 октября 2018

Позвольте мне собрать все заметки в комментариях вместе ...

Давайте посмотрим на 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> = 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 #-}
...