使用foldr的功能太急切了

我有一个小的替代实现groupBy,这对我来说比版本更有用Data.List,因为它不要求测试是等价关系:

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' f = foldr step []
    where step x [] = [[x]]
          step x (xs:xss)
              | x `f` head xs = (x:xs):xss
              | otherwise     = [x]:xs:xss

然而,它太急切,不会开始计算输入,如groupBy' (<) [1,2,3,2,3,4,1,undefined].我已经阅读了HaskellWiki和Wikibooks的文章,这些文章解释了为什么某些事情,比如模式匹配,可以使函数不那么懒惰,我想我理解那里给出的大多数例子.不过,我不明白为什么这个功能无法开始产生输出,直到它击中undefined.模式是否匹配导致此行为？

由于我刚读过这些文章,可能缺乏经验使我无法将我在那里阅读的内容应用到我的示例代码中.那么,为了表现得更懒,这个特定的实现怎么能改变呢？

关键问题是你知道step x xss总是会产生表单的结果(x:_):_,但是你在模式匹配后面"隐藏"了这个,所以Haskell被迫首先评估它们以确定step在它甚至看到那些构造函数之前要选择哪个案例.

通常,为了foldr f x能够在到达列表末尾之前产生任何输出,f必须能够在检查其第二个参数之前产生一些输出.

我们可以通过step分成两个来解决这个问题,这样我们就可以(:)在对第二个参数进行模式匹配之前生成两个构造函数.

groupBy' f = foldr step []
  where step x xss = let (ys, yss) = step' x xss in (x:ys):yss
        step' x [] = ([], [])
        step' x (xs:xss) | f x (head xs) = (xs, xss)
                         | otherwise     = ([], xs:xss)

这就像你可以得到它一样懒惰.

*Main> groupBy' (<) [1, 2, 3, 2, 3, 4, 1, undefined]
[[1,2,3],[2,3,4],[1*** Exception: Prelude.undefined