时间戳

首页 > 解决方案 > Haskell：列表中满足谓词的最高序列

haskell - Haskell：列表中满足谓词的最高序列

问题描述

我想要一个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)))

标签： haskellfunctional-programmingsequence

解决方案

我认为您执行此操作的方式看起来不错，但是该groups功能很混乱-尤其是您从每一步不满足 p 的元素中精确删除 1 的方式，这可能导致您的结果有很多多余的空列表在里面。（这些当然不会影响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，并根据两个连续参数的函数是否为真。并且on（http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Function.html#v:on）是一个方便的小函数，Data.Function它可以将另一个函数的结果提供给 a 的输入二进制函数。结果是

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

将列表拆分p为 alwaysTrue或 always的部分False。然后我们将其过滤成正确的部分。

推荐阅读