haskell - 使用 foldr 的功能太急切了

Question

我有一些 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 之前不能开始产生输出。 .模式匹配是否会导致此行为？

由于我刚刚阅读了这些文章，可能是缺乏经验使我无法将在那里阅读的内容应用到我的示例代码中。那么，如何改变这个特定的实现以使其表现得更懒惰呢？

Answer 1

关键问题是你知道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