Haskell: самая высокая последовательность в списке, которая удовлетворяет предикату - PullRequest
Новая
       18

Haskell: самая высокая последовательность в списке, которая удовлетворяет предикату

0 голосов
/ 08 февраля 2019

Я хочу функцию takeUntill с сигнатурой takeUntill :: (Int -> Bool) -> [Int] -> [Int]. Я действительно вышел с реализацией, но я ищу более чистое решение этой проблемы, чем мое существующее, если оно существует.Мое текущее решение: 

takeUntill :: (Int -> Bool) -> [Int] -> [Int]
takeUntill p a = snd $ maximum $ [(length x, x) | x <- groups p a]
groups :: (Int -> Bool) -> [Int] -> [[Int]]
groups _ [] = []
groups p a = ((takeWhile p a):(groups p (drop 1 $ dropWhile p a)))

1 Ответ

0 голосов
/ 08 февраля 2019

Я думаю, что то, как вы это делаете, выглядит нормально, но функция groups грязная - особенно то, как вы отбрасываете ровно 1 из элементов, которые не удовлетворяют p на каждом шаге, что может привести к тому, что ваш результат будет иметьвнутри много лишних пустых списков.(Это, конечно, не повлияет на takeUntil, если хотя бы 1 элемент a удовлетворяет p, но они все еще там.)

Я бы переписал groups следующим образом, используя некоторыеполезные функции библиотеки: 

groups p a = filter (p . head) $ groupBy ((==) `on` p) a

Я не знаю, является ли это более эффективным или нет, но я определенно считаю, что его легче читать.Чтобы пояснить, groupBy (http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html#v:groupBy) относится к Data.List и разбивает список на список подсписков в зависимости от того, является ли функция из 2 последовательных аргументов истинной или нет. И on (http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Function.html#v:on) - это небольшая удобная функция из Data.Function, которая подает результат другой функции на входы двоичной функции. В результате 

groupBy ((==) `on` p) a

разбивает список на секции, где p всегда True или всегда False. Затем мы фильтруем это только по частям, которые являются Истиной.

...