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).

Answer 3

First of all, the list is infinite, thus it's impossible to generate the whole list before the program runs. As MatrixFrog already pointed out, fibs is a thunk. You can roughly imagine a thunk as a function that takes no argument and returns a value. The only difference is, that the pointer to the function is replaced by a pointer to the result afterwards, causing the result to be cached. This happens only in case of funcions that are not depending on any typeclass, because a typeclass usually introduces a new argument containing a dictionary with the functions of that typeclass (This process is sometimes called reification).

A long time I posted an answer to this codegolf.SE question containing an own implementation of thunks in C. The code is not very good, the list stuff is not separated very well from the thunk itself, but it's worth having a look.

Answer 4

A function always involves the (->) type constructor, so it is not a function. It's a value. Functions are also values, but values are not functions, and that has nothing to do with laziness. The key property of a function is that you can apply it. Application has the type:

(a -> b) -> a -> b

Of course it is a lazy value and on the implementation level involves something called a thunk, but this is largely irrelevant to your question. Thunks are an implementation detail. Just because it is a lazily computed value doesn't turn it into a function. Don't confuse evaluation with execution! Functions in a language like C are not the same as function in Haskell. Haskell uses the real mathematical notion of a function, which is completely unrelated to with which strategy things are executed on the machine level.