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

Question

考虑以下函数:

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

这实质上需要两个二维数组 a s 并将它们连接起来，从左到右，例如:

[[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]]产生所需的输出，但我正在寻找一种适用于任意无限列表的解决方案，而不仅仅是 repeat xs 形式的列表.

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

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

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

仍然没有问题。现在我们看看 zipWith 的模式。 .第一个模式仅在左侧为空时匹配。 Welp，这绝对不是真的，所以让我们继续吧。仅当右侧为空时，第二个才匹配。所以让我们看看右边是否为空。右手边看起来像

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

现在，如果给定一个有限列表，我们的函数肯定会中断。但这允许我们“假装”列表上的模式匹配，而无需实际做任何工作。它相当于更详细

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