Here's an old question from 7 months ago, when stack overflowers agreed that Haskell's inefficiency in computing the Ackermann function was due to a compiler error.
Ackermann very inefficient with Haskell/GHC
7 months later, this appears to be fixed. It seems like ack runs with linear memory, but it runs pretty freakin' slow.
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)
I am just asking for any insights into this. The more detailed ones will get upvoted. Keep in mind I am new to functional programming and even simple remarks about tail recursion vs regular recursion would be appreciated and upvoted.