为什么会产生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| :}

否则后来的定义将影响早期的定义.请注意,您的提示可能不同.