为什么在无限列表上使用 foldr 时 xs ++ acc 可以工作，但 acc ++ xs 不行？

Question

我知道问题标题可能会产生误导，因为我没有将无限列表与此处的任何内容连接起来。欢迎提出更合适的建议。

这是 Prelude 中 cycle 函数的有效实现，使用 foldr:

fold_cycle :: [a] -> [a]
fold_cycle xs = foldr step [] [1..]
    where step x acc = xs ++ acc

如果我们把++的操作数换成acc ++ xs，这个函数就失效了。它会产生堆栈溢出，据我了解，这是试图生成 never-ending 表达式以供以后评估的结果。

我很难理解这背后的原因。我的理由是，无论操作数的顺序如何，foldr 都应该计算一次 step，生成新的累加器并在必要时再次计算 step 函数。为什么会有差异？

Answer 1

如果不强制，

foldr 根本不会评估累加器。 fold_cycle 之所以有效，是因为它不一定评估 acc.

fold_cycle [1, 2]

减少到

[1, 2] ++ ([1, 2] ++ ([1, 2] ++ ([1, 2] ++ ...

这允许我们评估结果的前缀，因为 ++ 让我们遍历第一个参数而不评估第二个参数。

如果我们使用step _ acc = acc ++ xs，上面表达式中的括号关联到左边而不是右边。但是因为我们有无限数量的追加，表达式最终是这样的：

((((((((((((((... -- parentheses all the way down

直觉上，我们必须越过无数个括号才能检查结果列表的第一个元素。

Why xs ++ acc works when using foldr on an infinite list, but acc ++ xs doesn't?