Haskell groupBy 函数 : How exactly does it work?

Question

我遇到了以下行为:

ghci :m +Data.List

ghci> groupBy (\x y -> succ x == y) [1..6]
[[1,2], [3,4], [5,6]]
ghci> groupBy (\x y -> succ x /= y) [1..6]
[[1], [2], [3], [4], [5], [6]]

ghci :m +Data.Char   -- just a test to verify that nothing is broken with my ghc

ghci> groupBy (const isAlphaNum) "split this"
["split"," this"]

这让我感到惊讶，我认为，根据下面的示例，每当提供给谓词的两个连续元素的谓词计算结果为 True 时，groupBy 就会拆分列表。但在上面的第二个示例中，它将列表拆分为每个元素，但谓词的计算结果应为 False。我也构建了它在 Haskell 中如何工作的假设，这样每个人都明白我相信它是如何工作的:

groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy p l@(x:y:ys)
  | p x y     = (x:y:(head l)) ++ (tail l)       -- assuming l has a tail, unwilling to
  | otherwise = [x] ++ (y:(head l)) ++ (tail l)  -- to debug this right now, I guess you
groupBy _ [x] = [[x]]                            -- already got the hang of it ;)

这让我得出结论，它的工作原理有些不同。所以我的问题是，这个功能实际上是如何工作的？

Answer 1

But in my second example above it splits the list on every element, but the predicate should evaluate to False.

在第二个示例中，它还计算每两个连续元素。它所作用的函数是const isAlphaNum。所以这意味着类型是:

const isAlphaNum :: b -> Char -> Bool

因此，它使用组和元素的开头来调用函数，但它只考虑第二个元素。

因此，如果我们使用以下方式调用它:groupBy (const isAlphaNum) "split this"，它将评估:

succs   2nd    const isAlphaNum
-------------------------------
"sp"    'p'    True
"sl"    'l'    True
"si"    'i'    True
"st"    't'    True
"s "    ' '    False
" t"    't'    True
" h"    'h'    True
" i"    'i'    True
" s"    's'    True

每次 const isAlphaNum 为 True 时，它都会将该字符追加到当前序列中。因此，如果我们评估 "t "、const isAlphaNum，它将评估为 False，groupBy 将启动一个新组。

因此，这里我们构建了两个组，因为只有一个 False。

分析函数 source code 也可以得到这个结果:

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

因此，如果给定列表为空，这里 groupBy 将返回空列表。如果它不是空列表 (x:xs) 那么我们将构造一个新序列。该序列以x 开始，并且还包含ys 的所有元素。 ys 是 span 构造的二元组的第一个元素。

span::(a -> Bool) -> [a] -> ([a],[a]) 构造一个 2 元组，其中第一个元素是最长可能的前缀满足谓词的列表，这里的谓词是 eq x 所以我们不断向组中添加元素，只要 eq x y (与 y > 一个元素)成立。

使用列表的剩余部分ys，我们构造一个新组，直到输入完全耗尽。