Why does adding a polymorphic type signature degrade performance?

Question

Here's a simple function to compute Fibonacci numbers:

fib :: [Int]
fib = 1 : 1 : zipWith (+) fib (tail fib)

In ghci I can compute the series quickly. In fact, a bit of experimentation reveals that the computation runs in approximately linear time.

ghci> last $ take 100000 fib
354224848179261915075         -- takes under a second

If I change the type signature to be polymorphic instead:

fib :: Num a => [a]
fib = 1 : 1 : zipWith (+) fib (tail fib)

Then the algorithm becomes slower. In fact, it seems that it now runs in exponential time!

Does switching to a polymorphic type signature mean that the list being completely recomputed at each stage? If so, why?

Jabot

possible duplicate of Will a value that has a type with class constraints actually be a function at run time? – Goodhumored

Answer 1

This is because of the dictionary translation.

fib :: [Int]

is a top level constant.

But this:

fib :: Num a => [a]
fib = 1 : 1 : zipWith (+) fib (tail fib)

is just a top level function, which will be applied to a Num dictionary at runtime. Like so:

fib d = 1 : 1 : zipWith (d.+) (fib d) (tail (fib d))

So if you compile this without any optimizations, such that no specialization can happen, you'll end up with exponential time fib, as the list is rebuilt from scratch, on each function call -- it isn't a lazy data structure anymore.

Airdrop

Answer 2

Yes, the polymorphic type signature means it's being recomputed at each stage. The core produced by ghc-7.4.2 with -O2:

lvl_rcZ :: GHC.Integer.Type.Integer
[GblId, Str=DmdType]
lvl_rcZ = __integer 1

Rec {
PolyFib.fib [Occ=LoopBreaker]
  :: forall a_a9W. GHC.Num.Num a_a9W => [a_a9W]
[GblId, Arity=1, Str=DmdType L]
PolyFib.fib =
  \ (@ a_aal) ($dNum_aam :: GHC.Num.Num a_aal) ->
    GHC.Types.:
      @ a_aal
      (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ)
      (GHC.Types.:
         @ a_aal
         (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ)
         (GHC.List.zipWith
            @ a_aal
            @ a_aal
            @ a_aal
            (GHC.Num.+ @ a_aal $dNum_aam)
            (PolyFib.fib @ a_aal $dNum_aam)
            (case PolyFib.fib @ a_aal $dNum_aam of _ {
               [] -> GHC.List.tail1 @ a_aal;
               : _ xs_abD -> xs_abD
             })))
end Rec }

The reason is that it's not feasible to cache a list of Fibonacci numbers for each type belonging to Num, and fib is explicitly a polymorphic value, hence it doesn't get cached at all.

If you want to cache it at least for the computation at each type, use a local list

pfibs :: Num a => [a]
pfibs = res
  where
    res = 1 : 1 : zipWith (+) res (tail res)

does the caching for each computation (so pfibs !! 500 e.g. is fast) since now the list is monomorphic in each computation. It will still be recomputed for each query (unless you bind it to a monomorphic name), but not for each single list element.

*PolyFib> pfibs !! 999999 :: Int
-4249520595888827205
(0.31 secs, 137462088 bytes)

Aprilaprile