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 速度吗？

Answer 1

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

你没有说你是否正在编译 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++ 代码的比较。