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 将用于给定函数 f ，和一个基值 z获取列表 [x1, x2, …, xn]产生以下结果:
f (f (… (f (f z x1) x2) …) xn-1) xn
如果我们因此想要确定弱头部范式(WHNF)，我们需要访问列表的最后一个元素。折叠功能f的foldl它的第一个参数可以是惰性的，但我们至少必须使用 xn 进行函数调用。作为参数。这就是为什么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将生成一个二元组，其中第一项将包含满足谓词的所有元素，而第二项是对要处理的列表其余部分的惰性引用。