折叠无限列表时堆栈溢出？

Question

考虑以下函数：

(<.>) :: [[a]] -> [[a]] -> [[a]]
xs <.> ys = zipWith (++) xs ys

这基本上需要两个 a 的二维数组并将它们从左到右连接起来，e.x.:

[[1,2],[3,4]] <.> [[1,2],[3,4]] == [[1,2,1,2],[3,4,3,4]]

我希望能够写出如下内容：

x = foldr1 (<.>) $ repeat [[1,2],[3,4]]

由于 Haskell 的懒惰评估，这应该是有意义的，即我们应该获得：

x !! 0 == [1,2,1,2,1,2,1,2...]
x !! 1 == [3,4,3,4,3,4,3,4...]

然而，当我尝试使用 GHCi 运行这个例子时，无论是使用 foldr1 还是 foldl1，我要么得到一个非终止计算，要么得到一个堆栈溢出。

所以我的问题是：

这是怎么回事？
是否可以使用 foldr1 或 foldl1 以外的其他功能来完成我在这里尝试完成的工作？（如果我需要修改 <.> 的实现，我很高兴，只要它计算相同的函数）

另请注意：我知道对于此示例，map repeat [[1,2],[3,4]] 会产生所需的输出，但我正在寻找一种适用于任意无限列表的解决方案，而不仅仅是 [=] 形式的列表21=].

Answer 1

我将对此处的评论中所说的内容进行扩展。我将借用 GHC version of zipWith 的（简化版本），这足以满足本次讨论的需要。

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f [] _ = []
zipWith f _ [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys

现在，这就是你的计算最终的样子，它是光荣的无限形式。

[[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] ... ) ... )

好的，所以 top-level 是 <.>。美好的。让我们仔细看看。

zipWith (++) [[1, 2], [3, 4]] ([[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] ... ) ... )

还没有问题。现在我们看看 zipWith 的模式。第一个模式仅在 left-hand-side 为空时匹配。嗯，这绝对不是真的，所以让我们继续。第二个仅在 right-hand-side 为空时匹配。那么让我们看看 right-hand-side 是否为空。 right-hand-side 看起来像

[[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] <.> ([[1, 2], [3, 4]] ... ) ... )

这就是我们的起点。所以要计算结果，我们需要访问结果。因此，堆栈溢出。

现在，我们确定问题出在 zipWith 上。让我们来玩玩吧。首先，我们知道我们将把它应用于我们人为设计的示例的无限列表，所以我们不需要那个讨厌的空列表案例。摆脱它。

-- (I'm also changing the name so we don't conflict with the Prelude version)
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

(<.>) :: [[a]] -> [[a]] -> [[a]]
xs <.> ys = zipWith' (++) xs ys

但这并没有解决任何问题。我们仍然需要评估弱头范式（阅读：列表中的数字是空的）以匹配该模式。

要是有一种不用 WHNF 就可以进行模式匹配的方法就好了……输入 lazy patterns。让我们这样重写我们的函数。

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f ~(x:xs) ~(y:ys) = f x y : zipWith' f xs ys

现在，如果给定一个有限列表，我们的函数 肯定会 中断。但这允许我们在列表上进行 "pretend" 模式匹配而无需实际做任何工作。相当于更冗长的

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f xs ys = f (head xs) (head ys) : zipWith' f (tail xs) (tail ys)

现在我们可以正常测试你的功能了。

*Main> let x = foldr1 (<.>) $ repeat [[1, 2], [3, 4]]
*Main> x !! 0
[1,2,1,2,1,2,1,2,1,...]
*Main> x !! 1
[3,4,3,4,3,4,3,4,3,...]

这样做的明显缺点是它在有限列表上肯定会失败，因此您必须为这些列表设置不同的函数。

*Main> [[1, 2], [3, 4]] <.> [[1, 2], [3, 4]]
[[1,2,1,2],[3,4,3,4],*** Exception: Prelude.head: empty list

Answer 2

zipWith 并不是——事实上，它不可能——像你希望的那样懒惰。考虑你的例子的这种变化：

GHCi> foldr1 (zipWith (++)) [ [[1,2],[3,4]], [] ]
[]

输入中的任何空列表列表都将导致列表结果为空列表。既然如此，在整个输入被消耗之前，没有办法知道结果的任何元素。因此，您的函数不会在无限列表上终止。

针对此问题提出了一些可能的解决方法。我的建议是使用 non-empty-lists 个列表，而不是简单的列表列表：

GHCi> import qualified Data.List.NonEmpty as N
GHCi> import Data.List.NonEmpty (NonEmpty(..))
GHCi> take 10 . N.head $ foldr1 (N.zipWith (++)) $ repeat ([1,2] :| [[3,4]])
[1,2,1,2,1,2,1,2,1,2]

N.zipWithdoesn't have to deal with an empty list case,这样可以更懒

折叠无限列表时堆栈溢出？

Stack overflow when folding infinite lists?

haskell

lazy-evaluation

fold