时间戳

首页 > 解决方案 > 具有无限列表的 Haskell 惰性求值和引入符号

list - 具有无限列表的 Haskell 惰性求值和引入符号

问题描述

让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？

标签： listhaskellinfinitelet

解决方案

foldl :: Foldable f => (b -> a -> b) -> b -> f a -> b将对于给定的 functionf和zlist的基值产生以下结果：[x1, x2, …, xn]

f (f (… (f (fzx 1 ) x 2 ) …) x n-1 ) x n

因此，如果我们想要确定弱头范式（WHNF），我们需要访问列表的最后一个元素。的 fold 函数f的foldl第一个参数可以是惰性的，但我们至少必须使用as 参数进行函数调用。这就是为什么文档说：xnfoldl

请注意，要生成运算符的最外层应用程序，必须遍历整个输入列表。像所有左关联折叠一样，foldl如果给定一个无限列表，它将发散。

我的猜测是 let in 表示法是惰性的，因此 span（在其 Prelude 定义中使用 let-in）仅在我们将 pack' 应用于无限列表时评估有限多个表达式。

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

它起作用的原因是因为它span :: (a -> Bool) -> [a] -> ([a], [a])是懒惰地实施的。实际上，实现span为[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尾部的外观如何以生成x满足谓词的 2 元组，将其放入第一项中，如果p x失败则放入第二项中。

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

推荐阅读