list - Haskell 惰性求值和带有无限列表的 let-in 表示法

Question

让pack是函数[a] -> [[a]]它接受一个列表并将连续的重复元素分组到子列表中。

这里有 pack 的两个实现在 haskell 。

pack :: (Eq a) => [a] -> [[a]]
pack x = reverse $ foldl f [] x where
  f cks@(ck1:_):rest) x
    | x == ck1 = (x:ck):rest
    | otherwise [x]:cks
  f _ x = [[x]]

pack' (x:xs) = let (first,rest) = span (==x) xs
  in (x:first) : pack' rest
pack' [] = []

这些实现有一个关键的语义差异:如果我们将第一个实现应用于无限列表，则第一个实现无法终止，例如[1..] 。 但是第二种实现确实适用于无限列表。例如，head $ pack' [1..]评估。

我的猜测是let in符号是惰性的，因此 span (在 Prelude 定义中使用 let - in)当我们应用 pack' 时，仅计算有限多个表达式。在无限列表中。

但是，这对我来说是一个不能令人满意的解释，因为我可以替换 reverse具有以下定义。

reverse' = foldl (\y x0 -> x0:y) []

如果我们这样做， pack 中的每个表达式从左到右折叠 - 所以我希望这适用于无限列表 - 但它仍然挂起。

问题:为什么 pack'适用于无限列表而不是 pack ？

Answer 1

foldl :: Foldable f => (b -> a -> b) -> b -> f a -> b will 对于给定的函数 f ，以及基值 z获取列表 [x<sub>1</sub>, x<sub>2</sub>, …, x<sub>n</sub>]产生结果:

f (f (… (f (f z x1) x2) …) xn-1) xn

如果我们想要确定弱头范式(WHNF)，我们需要访问列表的最后一个元素。折叠功能f foldl的它的第一个参数可以是惰性的，但我们至少必须使用 x<sub>n</sub> 进行函数调用。作为参数。这就是为什么 documentation on foldl says :

Note that to produce the outermost application of the operator the entire input list must be traversed. Like all left-associative folds, foldl will diverge if given an infinite list.

---

My guess is the let in notation is lazy, hence span (which uses let-in in its Prelude definition) only evaluates finitely many expressions when we apply pack' on an infinite list.

你是对的，let中的定义, where子句和所有其他子表达式都是惰性的。但最终，如果您对结果感兴趣，则需要确定 WHNF，有时甚至需要确定更多的 WHNF。

它起作用的原因是 span :: (a -> Bool) -> [a] -> ([a], [a]) 是惰性实现的。确实，span是 implemented as [src] :

span                    :: (a -> Bool) -> [a] -> ([a],[a])
span _ xs@[]            =  (xs, xs)
span p xs@(x:xs')
         | p x          =  let (ys,zs) = span p xs' in (x:ys,zs)
         | otherwise    =  ([],xs)

因此它不需要需要知道span如何尾部的外观是为了生成一个 2 元组，其中 x满足谓词的被放入第一项，或者如果p x则被放入第二项。失败。

这意味着 span将生成一个 2 元组，其中第一项将包含满足谓词的所有元素，而第二项是对要处理的列表其余部分的惰性引用。