Why the recursive list is so slow in haskell？

Question

I am fresh in haskell, and I defined a func in Haskell :

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

but, it runs so slow, and when I do "febs 30", it will take about 10s, and I do the same func in C++, it runs very fast.

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

Is there any way to promote my haskell func speed?

Answer 1

This is an odd comparison, for the following reasons:

1. You don't say whether you're compiling the Haskell code, or with what options. If you're just running it in ghci, then of course it will be slow - you're comparing interpreted code with compiled code.

2. Your Haskell code is polymorphic whereas your C++ code is monomorphic (that is, you've used a type class Integral a => a -> a instead of the concrete type Int -> Int). Your Haskell code is therefore more general than your C++ code, because it can handle arbitrarily large integers instead of being restricted to the range of an Int. It's possible that the compiler will optimize this away, but I'm not certain.

If I put the following code in a file fib.hs

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

main = print (fibs 30)

and compile it with ghc -O2 fib.hs then it runs fast enough that it appears instantaneous to me. You should try that, and see how it compares with the C++ code.