groupBy-like 函数，使得二元谓词在每个组的连续元素之间成立，而不是任何两个

Question

在 Hackage 我看到它groupBy的实现是这样的：

groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []           =  []
groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

这意味着谓词eq在每组的任意两个元素之间成立。例子：

> difference_eq_1 = ((==1).) . flip (-)
> first_isnt_newline = ((/= '\n').) . const
>
> Data.List.groupBy difference_eq_1 ([1..10] ++ [11,13..21])
[[1,2],[3,4],[5,6],[7,8],[9,10],[11],[13],[15],[17],[19],[21]]
>
> Data.List.groupBy first_isnt_newline "uno\ndue\ntre"
["uno\ndue\ntre"]

相反，如果我想对元素进行分组，使得谓词在任何一对连续元素之间成立，从而使上述结果如下，该怎么办？

[[1,2,3,4,5,6,7,8,9,10,11],[13],[15],[17],[19],[21]]
["uno\n","due\n","tre"]

我自己写的，看起来有点丑

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' p = foldr step []
  where step elem [] = [[elem]]
        step elem gs'@((g'@(prev:g)):gs)
          | elem `p` prev = (elem:g'):gs
          | otherwise = [elem]:gs'

所以我在徘徊，如果这样的功能已经存在，我只是没有找到它。

至于第二种用法，Data.List.groupBy first_isnt_newline二元谓词基本上忽略第二个参数并将一元谓词应用于第一个参数，我刚刚发现它Data.List.HT.segmentAfter unary_predicate可以完成工作，其中转发输出unary_predicate的一元谓词的否定在哪里const. 换句话说Data.List.groupBy ((/= '\n').) . const === Data.List.HT.segmentAfter (=='\n')。

Answer 1

有一个groupBy包可以做到这一点。

\n

但这里\xe2\x80\x99是另一种实现方式：

\n

\n

• 用尾部压缩列表以测试相邻元素上的谓词

  \n
\n

• 通过扫描结果并在谓词为 false 时递增组来生成 \xe2\x80\x9cgroup 索引\xe2\x80\x9d

  \n
\n

• 按索引分组

  \n
\n

• 删除索引

  \n
\n

\n

groupByAdjacent :: (a -> a -> Bool) -> [a] -> [[a]]\ngroupByAdjacent p xs\n  = fmap (fmap fst)\n  $ groupBy ((==) `on` snd)\n  $ zip xs\n  $ scanl\' (\\ g (a, b) -> if p a b then g else succ g) 0\n  $ zip xs\n  $ drop 1 xs\n

\n

对于像 之类的输入[1, 2, 3, 10, 11, 20, 30]，谓词将返回[True, True, False, True, False, False]，结果组索引将为[0, 0, 0, 1, 1, 2, 3]。

\n

扫描也可以写为 pointfree scanr (bool succ id . uncurry p) 0，因为扫描方向并不重要（尽管组索引将被反转）。组索引可能很方便，或者只是更易读以保存为整数，但它Bool也可以是 a，因为组的最小大小为 1：扫描的函数参数为bool not id . uncurry p，可以简化为(==) . uncurry p。其中几个部分可以分解为可重用函数，例如zipNext = zip <*> drop 1，但为了简单起见，我\xe2\x80\x99已经内联了它们\xe2\x80\x99s。

\n