In Haskell, lazy evaluation can often be used to perform efficient calculations of expressions that are written in a clear and concise manner. However, it seems that the language itself does not provide enough details to determine, in general, the time and space needs of a given piece of code. The situation seems to be mitigated, to some degree, by common use of ghc, which I gather gives some more specific guarantees related to weak-head-normal-form. But if I'm not mistaken, the actual performance of code can still be quite difficult to understand.

For example, we also use polymorphism to express functions in a generic fashion, again without sacrificing clarity. However, when combined with lazily-evaluated structures, the two language features seem to interact in ways that are (to me) surprising. Consider:

``````import Debug.Trace (trace)
tracePlus a b = trace (show a ++ "+" ++ show b) (a+b)
-- This lets us try small integers to see how things get evaluated.
-- Those tests can thereby reveal the asymptotic behavior of the code, without
-- needing to actually try bigger values.

class Sum a where
one :: a
add :: a -> a -> a

instance Sum Integer where
one = 1

fibSums_list :: (Sum a) => [a]
fibSums_list = one : one : zipWith add fibSums_list (tail fibSums_list)

fibS :: Int -> Integer
fibS = (fibSums_list !!)
``````

I should note that this works fine if I compile it with `ghc -O2`. However, when run under `ghci`, it takes exponential time complexity to evaluate `fibS`. Yet, using a list of Fibonacci numbers of type `[Integer]` works fine as well.

So, one specific question I have is: is there a way to rewrite `fibSums_list` and/or `fibS`, such that it retains the use of the `Sum` type class, and is still clearly a generalization of the Fibonacci sequence, but that also evaluates efficiently in ghci? Where do I even start?

And I wonder if similar pitfalls await even in code compiled via `ghc -O2`. And if so, how do authors of Haskell code deal with those?

Another related question is When is it a good time to reason about performance in Haskell?. I think my question is an even more fundamental one; I don't even understand how to go about the task of such reasoning. There is a reasonable answer there, but it doesn't have enough specific information for me to actually go about writing a `fibSums_list` that works in `ghci`, let alone one that has any sort of guaranteed time complexity.

• I can't speak for everyone, but my approach is to assume that everything is always evaluated lazily. Therefore, I would generally assume that code like this will always evaluate every term from the beginning of the sequence up to the one being evaluated. Automatic memoization of terms so that they are evaluated only once is an optimization, and not relying on it makes sense. You can always introduce a data structure to store temporary results if you rely on them only being calculated once. – Jules Jan 8 '18 at 6:15
• I'm no Haskell expert, but I would assume that lazy evaluation changes little. Automatic memoization just means you're only evaluating fibonacci for a given number exactly once, but you would (or rather should) do no different writing said algorithm in another language. – Neil Jan 8 '18 at 9:09

No answer can really comprehensively provide The True Way of reasoning about Haskell algorithmic complexity. Partly this is because a lot of Haskell code relies on what the compiler will actually do to it in practice (GHC can make a program either faster or slower than you'd expect). But I can explain the source of your surprise in the example you gave, and maybe it will guide you to some enlightenment about how Haskell evaluates things.

For example, we also use polymorphism to express functions in a generic fashion, again without sacrificing clarity. However, when combined with lazily-evaluated structures, the two language features seem to interact in ways that are (to me) surprising.

If you inspect the Core IR for the code you wrote for `fibSums_list`, a few things will be revealed:

``````fibSums_list :: forall a. Sum a => [a]
fibSums_list
= \ (@ a) (\$dSum :: Sum a) ->
: (one \$dSum)
(: (one \$dSum)
(zipWith
(add \$dSum) (fibSums_list \$dSum) (tail (fibSums_list \$dSum))))
``````
1. `fibSums_list` is lowered to a function, not a value!
2. A value describing `Sum a` is actually a parameter to the function.
3. When you write `fibSums_list` in the body, you're actually calling the function recursively with the implicit argument.

Tying this back to the language, any polymorphic "value" has to be well-typed on its own. Therefore, the meaning of `fibSums_list` is "give me a thunk through which I can compute this value in the given class environment". A little time working this out on paper should convince you that sharing the thunk isn't strictly necessary to get a correct output when walking out to an index.

So a better way to think about ad-hoc polymorphic functions might be to look at them as OOP-esque factories for constructing their actual values from a typeclass environment. With that in mind, you can get the infinite list you desire:

``````fibSums_list :: Sum a => [a]
fibSums_list = fibz
where fibz = one : one : zipWith add fibz (tail fibz)
``````

Now, when we look at the Core, we can clearly see that "factory" behavior.

``````fibSums_list :: forall a. Sum a => [a]
fibSums_list
= \ (@ a) (\$dSum :: Sum a) ->
letrec {
fibz :: [a]
fibz
= break<3>()
: (one \$dSum)
(break<2>()
: (one \$dSum)
(break<1>() zipWith (add \$dSum) fibz (break<0>() tail fibz))); } in
break<4>(fibz) fibz
``````

The value `fibz` exists inside `fibSums_list`, so the class environment is already established. That means `fibz` isn't a function, but a value with a consistent thunk that will be expanded lazily.

You can see this in action computing `fibS 100` in GHCI here.

I suspect the reason GHC's -O2 is producing fast code for you is because it's specializing `fibSums_list` and rewriting it so the class environment is fixed from the point of view of `fibS`. Then it becomes as though you'd written `fibSums_list :: [Integer]` and everything becomes much simpler.