Haskell：多次重复一个函数而不会出现堆栈溢出

Question

作为 Haskell 的新手，我试图多次迭代一个函数（例如逻辑图）。在命令式语言中，这将是一个简单的循环，但是在 Haskell 中我最终会遇到堆栈溢出。以这段代码为例：

main  = print $ iter 1000000

f x = 4.0*x*(1.0-x)

iter :: Int -> Double
iter 0 = 0.3
iter n = f $ iter (n-1)

对于少量的迭代，代码可以工作，但是对于一百万次迭代，我会遇到堆栈空间溢出：

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

我无法理解为什么会发生这种情况。尾递归在这里应该没问题。 也许问题在于惰性评估。我尝试了多种方法来强制严格求值，例如在不同位置插入 $! 或 seq，但没有成功。

Haskell 多次迭代函数的方法是什么？

我已经尝试过相关帖子的建议：here 或 here，但我总是以 stackoverflow 进行大量迭代，例如， main = print $ 迭代 f 0.3 !! 1000000。

Answer 1

问题是你的定义

iter :: Int -> Double
iter 0 = 0.3
iter n = f $ iter (n-1)

试图以错误的方向进行评估。将其展开几个步骤，我们获得

iter n = f (iter (n-1))
       = f (f (iter (n-2)))
       = f (f (f (iter (n-3))))
       ...

从 iter 1000000 到 iter 0 的整个调用堆栈，然后才能进行任何评估。用严格的语言来说也是一样的。您必须对其进行组织，以便部分评估可以在重复之前进行。通常的方法是有一个累积参数，例如

iter n = go n 0.3
  where
    go 0 x = x
    go k x = go (k-1) (f x)

然后添加严格注释 - 如果编译器尚未添加它们 - 将使其顺利运行而不消耗堆栈。

iterate 变体与您的 iter 具有相同的问题，只是调用堆栈是由内向外构建的，而不是像您的那样由外向内构建。但由于 iterate 从内到外构建其调用堆栈，因此更严格的 iterate 版本（或之前强制执行早期迭代的消费模式）解决了问题，

iterate' :: (a -> a) -> a -> [a]
iterate' f x = x `seq` (x : iterate' f (f x))

计算 迭代'f 0.3 !! 1000000 没有问题。