Will a value that has a type with class constraints actually be a function at run time?

Question

Consider the famous

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

Suppose that, to avoid the monomorphism restriction, this is annotated with:

fibs :: Num a => [a]

This seems to imply that at runtime, a list value fibs does not really exist, but rather a function that computes the list anew each time an element of fibs is picked?

The question is how such cases are actually handled in different Haskell implementations you know of.

--- ADDED ---- I feel that I must elaborate a bit more. Consider:

fibsInteger :: [Integer]
fibsInteger = 0: 1: zipWith (+) fibsInteger (tail fibsInteger)

and suppose during program execution the value

(fibsInteger !! 42)

needs to be evaluated. In that case I would expect that subsequent evaluations like that would find that the first 43 elements of fibsInteger are already evaluated. This implies also that fibsInteger itself and the first 42 tails of it are already in WHNF.

Yet that would not be possible with a polymorphic fibs, as far as I can see. FUZxxl's remark

because a typeclass usually introduces a new argument containing a dictionary with the functions of that typeclass

seems to support my view that a value like fibs effectively appears as function at runtime?

If this were so, then an application like ((maximum . map (fibs!!)) [100000 .. 101000] :: Integer) shold take noticeably longer to evaluate than the non-polymorphic variant ((maximum . map (fibsInteger!!)) [100000 .. 101000] :: Integer) because the first 100000 numbers will have to be recomputed each time. (Unfortunately, I can't try this out at this time)

Answer 1

It depends on the implementation. In GHC, type classes are implemented using dictionaries. Let's say the Num class was defined like this (simplified for this example):

class Num a where
    fromInteger :: Integer -> a
    (+) :: a -> a -> a

Then it will be compiled as a "dictionary" data type:

data Num a = Num { fromInteger :: Integer -> a, plus :: a -> a -> a }

Anything with a Num constraint will get an extra argument for the dictionary, so for example foo x = x + 1 will become:

foo :: Num a -> a -> a
foo num x = plus num x (fromInteger num 1)

So let's see how GHC compiles fibs, shall we?

$ cat Fibs.hs
module Fibs where
fibs :: Num a => [a]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
$ ghc -c Fibs.hs -ddump-simpl

==================== Tidy Core ====================
Rec {
Fibs.fibs [Occ=LoopBreaker]
  :: forall a_abu. GHC.Num.Num a_abu => [a_abu]
[GblId, Arity=1]
Fibs.fibs =
  \ (@ a_akv) ($dNum_akw :: GHC.Num.Num a_akv) ->
    GHC.Types.:
      @ a_akv
      (GHC.Num.fromInteger
         @ a_akv $dNum_akw (GHC.Integer.smallInteger 0))
      (GHC.Types.:
         @ a_akv
         (GHC.Num.fromInteger
            @ a_akv $dNum_akw (GHC.Integer.smallInteger 1))
         (GHC.List.zipWith
            @ a_akv
            @ a_akv
            @ a_akv
            (GHC.Num.+ @ a_akv $dNum_akw)
            (Fibs.fibs @ a_akv $dNum_akw)
            (GHC.List.tail @ a_akv (Fibs.fibs @ a_akv $dNum_akw))))
end Rec }

If you squint a little, this is essentially

fibs :: Num a -> [a]
fibs num = fromInteger num 0
         : fromInteger num 1
         : zipWith (plus num) (fibs num) (tail (fibs num))

So for GHC, the answer is yes. As you suspected, this can have drastic implications on performance, as this destroys the sharing of fibs that this definition relies on, to the point where you get exponential runtime instead of linear¹.

Prelude Fibs> :set +s
Prelude Fibs> fibs !! 30
832040
(3.78 secs, 912789096 bytes)

We can fix this problem by introducing sharing ourselves:

module SharedFibs where
fibs :: Num a => [a]
fibs = let f = 0 : 1 : zipWith (+) f (tail f) in f

This is much better.

Prelude SharedFibs> :set +s
Prelude SharedFibs> fibs !! 30
832040
(0.06 secs, 18432472 bytes)
Prelude SharedFibs> fibs !! 100000
<huge number>
(2.19 secs, 688490584 bytes)

But it still has the same problem that fibs is not shared between separate calls. If you want this, you will have to specialize fibs to your desired number type in a let or where.

These sort of performance surprises is part of the reason why the dreaded monomorphism restriction exists.

_{¹ Ignoring the fact that Integer addition is not constant time.}

Answer 2

Polymorphism can bring an additional performance burden (which I think is the question you are asking). In Thomas' answer to this question, making the type non-polymorphic reduced runtime from 36 to 11 seconds.

Your statement:

This seems to imply that at runtime, a list value fibs does not really exist, but rather a function that computes the list anew each time an element of fibs is picked?

I'm not really sure what you mean here - you seem to be aware that it's lazy. You might be asking if Haskell considers this a "function declaration" or a "value declaration" - you can try using Template Haskell:

> runQ [d| fib = 0 : 1 : zipWith (+) fib (tail fib) |]
[ValD (VarP fib) ...

So it is a value declaration (ValD).