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

Question

考虑以下函数：

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

这个操作实际上是将两个二维的 a 数组左右拼接在一起，例如：

[[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.除了foldr1或foldl1之外，是否有可能使用其他函数来实现我试图完成的内容？（如果需要修改<>的实现方式，使其计算相同的函数，那么我很高兴）

此外，请注意：我知道对于这个例子，map repeat [[1,2],[3,4]]可以产生所需的输出，但我正在寻找适用于任意无限列表的解决方案，而不仅仅是形如repeat xs的列表。

- Nathan BeDell

---

我不太确定我理解了重点，你能否给一个非平凡的例子（即不能用 map repeat . <.> 实现）？ - Lorenzo

问题在于 zipWith 至少需要评估顶层的列表。由于右参数是另一个 zipWith（并且继续进行），因此您会不断地调用。 - Willem Van Onsem

简而言之，在这里你只能对无限列表进行fold操作，如果你可以推迟右侧元素的计算。但是zipWith需要计算两个列表的所有元素。 - Willem Van Onsem

你可能会喜欢 map concat . transpose $ repeat [[1,2],[3,4]]。它至少满足了你的两个方程式...尽管如果你试图写下显而易见的第三个方程式，你可能会遇到麻烦！ - Daniel Wagner

Answer 1

我将在这里扩展评论中的内容。我将借鉴（简化版本的）GHC版本的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的模式。第一个模式只有在左侧为空时才匹配。嗯，显然不是这样，所以让我们继续。第二个仅在右侧为空时匹配。所以让我们看看右侧是否为空。右侧看起来像是：

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

- Silvio Mayolo

---

在像这样的情况下，我使用一个有用的组合器 nonempty ~(x:xs) = x:xs。它“断言”一个列表是非空的，并且允许更懒惰地使用它。我相信这将解决问题：foldr1 (\x y -> nonempty (x <.> y)) ... - luqui

我其实很好奇你遇到过哪些类似的“情况”。 - Silvio Mayolo

@luqui 我已经尝试过了，它确实有效。（在这种情况下，另一种可能性是使用 NonEmpty 作为中间层。） - duplode

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 不需要处理空列表情况，因此它可以更懒惰。

- duplode