haskell - 为什么这会产生 StackOverflow 错误？

Question

我最近开始使用 Haskell，并定义了这个看似简单的函数:

f 0 = 1
f x = x * f x - 1

但是，结果是这样的:

GHCi, version 8.2.1: http://www.haskell.org/ghc/  :? for help
Prelude> f 0 = 1
Prelude> f x = x * f x - 1
Prelude> f 10
*** Exception: stack overflow
Prelude>

Answer 1

你的阶乘看起来很无辜，但事实并非如此。解析如下:

f 0 = 1
f x = x * (f x) - 1

如果我们使用f 1会发生什么？

f 1 = 1 * (f 1) - 1 = 1 * (1 * (f 1) - 1) - 1
    = 1 * (1 * (1 * (f 1) - 1) - 1) - 1
    = 1 * (1 * (1 * (1 * (f 1) - 1) - 1) - 1) - 1
    = ...

我要停在这里了。这永远不会结束。它将构建一堆括号，有时整个塔会崩溃，最终导致堆栈溢出。

您必须使用括号:

f 0 = 1
f x = x * f (x - 1)

现在我们得到了正确的结果:

f 1 = 1 * f (1 - 1) = 1 * f 0 = 1 * 1 = 1

请记住，这仅适用于实现文件。在 GHCi 中，您必须使用多行模式或分号:

ghci> f 0 = 1; f x = x * f (x - 1)
ghci> -- or
ghci> :{
ghci| f 0 = 0
ghci| f x = x * f (x - 1)
ghci| :}

否则后面的定义将掩盖前面的定义。请注意，您的提示可能会有所不同。