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.