haskell - *** 异常 : stack overflow : Stack overflow

Question

我正在学习 Haskell，但遇到了我没想到的异常“堆栈溢出”。

代码相当简单:

type Reals = Double

prod :: Reals -> Reals -> Reals
prod a b = a*b

coprod :: Reals -> Reals -> Reals
coprod a b = a + b - (prod a b)

newsum :: Reals -> Reals -> Int -> Reals
newsum a b n =   
    approxA!!n 
    where
      approxA = a : zipWith coprod approxA approxB 
      approxB = b : zipWith prod approxA approxB 

函数 prod、coprod 旨在对 [0,1] 中的实数进行评估。功能

newsum a b n

对于 n 趋于无穷大，计算函数 (a,b) -> min(1, a+b)。

你可以试试

newsum 0.5 0.5 10

和

newsum 0.5 0.5 10000

看到这个。但是，通过调用

newsum 0.5 0.5 10000000

我得到堆栈溢出。 newsum 函数很简单，可以进行线性(n 次)Double 类型的操作。换句话说，构造 [Reals] 类型的(无限)列表的第 n 个元素

approxA

和

approxB

需要线性时间。

问题 1:为什么会出现堆栈溢出？ |
Haskell(或 GHCi)的限制是什么，我如何在像上面那样的简单程序中(提前)估计它们？

问题 2:如果需要，Haskell 中是否有标志/命令指示解释器自动分页内存？我想编写类似于 Math 的代码，并且不想花时间考虑内存限制、堆栈溢出等问题。

谢谢!

Answer 1

问题是(!!)是惰性的:它不会强制计算列表中较早的值，因此 ghci以第 n 个项目的巨大表达式结束，它溢出了它的堆栈。

您可以使用运行时选项增加堆栈大小，例如对于 16GB 堆栈:

$ ghci +RTS -K16G
> newsum 0.5 0.5 10000000
0.9999999000001789

但是如果你超出了系统可用的内存(可以包括虚拟内存/交换页)，你就会遇到问题(这里的 Linux OOM 杀手让我失望了):

> newsum 0.5 0.5 100000000
Killed
$

这可以在实践中通过编写一个函数来解决，该函数强制在访问列表尾部之前对其进行评估:

strict :: [a] -> [a]
strict [] = []
strict (x:xs) = seq x (x : strict xs)

seq x y部队 x当 Double 的值被评估(到 WHNF，对于 y 意味着完全评估)被要求。
使用 strict像这样:

newsum' :: Reals -> Reals -> Int -> Reals
newsum' a b n =
    strict approxA!!n
    where
      approxA = a : zipWith coprod approxA approxB
      approxB = b : zipWith prod approxA approxB

现在它在小的常量内存中运行。

另一种方法是使用更严格的数据结构( !a 是严格的 a ):

data List' a = !a :! List' a

但是你需要重新实现 (!!)和 zipWith对于这种类型。