Haskell groupBy函数:它究竟是如何工作的？

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"]

令我感到惊讶的是,我认为,基于下面的示例,groupBy每当谓词评估True为提供给谓词的两个连续元素时,就会拆分列表.但是在上面的第二个例子中,它会在每个元素上拆分列表,但谓词应该评估为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

但是在上面的第二个例子中,它会在每个元素上拆分列表,但谓词应该评估为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.

如果我们分析函数源代码,我们也可以得到这个结果:

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是由2构造的2元组的第一个元素span.

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

对于列表的剩余部分ys,我们构造一个新组,直到输入完全耗尽.