How does one reason about algorithmic complexity in Haskell?

Question

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
    add = tracePlus

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.

Answer 1

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.