haskell - 为什么haskell中的递归列表这么慢？

Question

我对 Haskell 很陌生，我在 Haskell 中定义了一个函数：

febs :: (Integral a)=> a -> a
febs n 
    | n<=0 =0
    | n==1 =1
    | n==2 =1
    | otherwise =febs(n-1)+febs(n-2)

但是，它运行得很慢，当我执行“febs 30”时，大约需要 10 秒，而我在 C++ 中执行相同的函数，它运行得非常快。

int febs(int n)
{
    if(n == 1 || n ==2)
    {
        return 1;
    }
    return febs(n-1)+febs(n-2);
}

有什么方法可以提高我的 haskell func 速度吗？

score 21 · Accepted Answer

这是一个奇怪的比较，原因如下：

你没有说你是否正在编译 Haskell 代码，或者有什么选项。如果您只是在 ghci 中运行它，那么它当然会很慢 - 您正在将解释代码与编译代码进行比较。
您的 Haskell 代码是多态的，而您的 C++ 代码是单态的（也就是说，您使用了类型类Integral a => a -> a而不是具体类型Int -> Int）。因此，您的 Haskell 代码比您的 C++ 代码更通用，因为它可以处理任意大的整数，而不是被限制在Int. 编译器可能会对此进行优化，但我不确定。

如果我将以下代码放入文件 fib.hs

fibs :: Int -> Int
fibs n = if n < 3 then 1 else fibs (n-1) + fibs (n-2)

main = print (fibs 30)

并编译它，ghc -O2 fib.hs然后它运行得足够快，以至于它对我来说是瞬时的。您应该尝试一下，看看它与 C++ 代码的比较。

score 13 · Accepted Answer

尝试使用优化进行编译。使用带有 -O2 的 GHC 7.4.1，您的程序运行得非常快：

$ time ./test 
832040

real    0m0.057s
user    0m0.056s
sys     0m0.000s

这是与main = print (febs 30).

关于 Chris Taylor 的回答中的多态性考虑，这里是febs 40OP 的多态斐波那契函数：

$ time ./test 
102334155

real    0m5.670s
user    0m5.652s
sys     0m0.004s

这是一个非多态的，即用 OP 的签名替换为Int -> Int：

$ time ./test 
102334155

real    0m0.820s
user    0m0.816s
sys     0m0.000s

根据 Tikhon Jelvis 的评论，看看加速是由于替换Integer为Int还是由于摆脱了多态性会很有趣。这又是同一个程序，除了febs根据 Daniel Fischer 的评论移动到一个新文件，并且 with febs :: Integer -> Integer：

$ time ./test 
102334155

real    0m5.648s
user    0m5.624s
sys     0m0.008s

同样，febs在不同的文件中，并且具有与最初相同的多态签名：

$ time ./test 
102334155

real    0m16.610s
user    0m16.469s
sys     0m0.104s

score 3 · Accepted Answer

你也可以这样写函数：

fibs = 0:1:zipWith (+) fibs (tail fibs)

它非常快，即使对于大的“n”立即执行：

Prelude> take 1000 fibs

3 回答 3