Haskell 计算 Ackermann 4 1 速度慢？

Question

这是 7 个月前的一个老问题，当时堆栈溢出者一致认为 Haskell 计算 Ackermann 函数的效率低下是由于编译器错误造成的。

Ackermann very inefficient with Haskell/GHC

7 个月后，这个问题似乎得到了解决。看起来 ack 是用线性内存运行的，但它运行得非常慢。

main = print (ack 4 1)
-- Ackermann function
ack 0 n = n + 1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n - 1))

$ time ./ack
65533

>real   8m53.274s
>user   8m47.313s
>sys    0m4.868s


Processor  2.8 GHz Intel Core i7
Memory  8 GB 1333 MHz DDR3
Software  Mac OS X Lion 10.7.5 (11G63)

我只是想询问对此的任何见解。更详细的将获得投票。请记住，我是函数式编程的新手，即使是关于尾递归与常规递归的简单评论也会受到赞赏和支持。

Answer 1

我不知道你是如何运行它的，但我怀疑完整的列表是:

1. 您的程序没有进行任何更改，也没有进行任何优化的编译。初始时间:7分29.755秒

2. 看来您没有使用优化。编译时请务必使用-O2并尝试-fllvm。新时间:1m2.412s

3. 尽可能使用显式类型签名并使用 Int(相对于默认的 Integer)。新时间:0m15.486s

因此，通过使用优化，我们获得了近 8 倍的加速(为什么其他所有基准测试问题不使用优化标志？!？!？)，并且通过使用 Int 而不是 获得了约 4 倍的加速>整数。