类似 groupBy 的函数，使得二元谓词在每个组的连续元素之间而不是在任意两个元素之间

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] 这样的输入，谓词将 return [True, True, False, True, False, False] 并且生成的组索引将是 [0, 0, 0, 1, 1, 2, 3].

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

类似 groupBy 的函数，使得二元谓词在每个组的连续元素之间而不是在任意两个元素之间

groupBy-like function such that the binary predicate holds between consecutive elements of each group instead of any two

grouping

haskell

functional-programming