7

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.

  • 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
3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.