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

Question

在 Hackage 我看到 groupBy 's implementation这是:

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 正是这样做的包。
但这里有另一种实现方式:

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

通过扫描结果并在谓词为假时增加组来生成“组索引”

按索引分组

删除索引

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

对于像 [1, 2, 3, 10, 11, 20, 30] 这样的输入，谓词将返回 [True, True, False, True, False, False]结果组索引将为 [0, 0, 0, 1, 1, 2, 3] .
扫描也可以写成 scanr (bool succ id . uncurry p) 0 ，因为扫描方向无关紧要(尽管组索引将被反转)。组索引可能很方便，或者保存为整数更易读，但它可以是 Bool相反，因为组的最小大小为 1:扫描的函数参数将是 bool not id . uncurry p , 可以简化为 (==) . uncurry p .这些部分中的一些可以被分解为可重用的功能，例如 zipNext = zip <*> drop 1 ，但为了简单起见，我已将它们内联。