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

Question

考虑以下功能：

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

本质上，这需要两个as 的二维数组，并将它们从左到右连接起来，例如：

[[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，要么得到一个非终止计算，要么是堆栈溢出。

所以我的问题是：

1. 这里发生了什么？
2. 是否可以使用foldr1or或其他功能来完成我正在尝试完成的操作foldl1？（很高兴，如果我需要修改的实现<.>，只要它能计算出相同的功能）

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

Answer 1

我将继续在这里发表评论。我将借用GHC版本zipWith的GHC版本（的简化版本），以便进行本次讨论。

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]] ... ) ... )

好的，所以顶层是<.>。精细。让我们仔细看看。

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

仍然没有问题。现在我们来看一下的模式zipWith。第一个模式仅在左侧为空时匹配。威尔普，那绝对不是真的，所以让我们继续吧。仅当右侧为空时，第二个匹配。因此，让我们看看右侧是否为空。右侧看起来像

[[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 ...请输入惰性模式。让我们以这种方式重写我们的函数。

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

现在，如果给出有限列表，我们的功能肯定会中断。但这使我们可以“假装”列表上的模式匹配而无需实际进行任何工作。相当于更加冗长

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]], [] ]
[]

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

Silvio Mayolo的答案针对此问题通过了一些可能的解决方法。我的建议是使用列表的非空列表，而不是列表的普通列表：

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.zipWith 不必处理空列表大小写，因此它可能更懒。