In most programming languages, functions are evaluated eagerly. That means that, in an expression such as
f(g(),h()), the language first computes
g(), then it computes
h(), and only then it executes the body of f. That's bad, because sometimes the result is not needed. For example,
if f(x,y) => x, then computing
h() is wasteful.
Haskell fixes that problem by being lazy, i.e., it starts by executing the body of
f, and only if
h() are actually needed is that they are computed. But that brings other problems. If
f(g,h) = [g, g, g], for example, then
g() will be evaluated 3 times! Fortunately, Haskell solves that too by memoizing
g(). That's very clever, works well in practice and is the reason Haskell is side-effect free; but, in some cases, memoizing isn't possible. For example, if
g() itself returns another function which is then applied to some arguments; e.g., if
f(g,h) = [g(4), g(7), g(3)]; then g must be duplicated, because its body must be evaluated with 3 different substitutions (4, 7 and 3). Confused? Let's visualize the evolution of
-- Input (\ f x -> let f1 = not in let f2 = f1 . f1 in let f4 = f2 . f2 in let f8 = f4 . f4 in f8 x) $ f8 True -- Step 1 (\ x -> let f1 = not in let f2 = f1 . f1 in let f4 = f2 . f2 in let f8 = f4 . f4 in f8 x) $ True -- Step 2 let f1 = not in let f2 = f1 . f1 in let f4 = f2 . f2 in let f8 = f4 . f4 in f8 True -- Step 3 let f1 = not in let f2 = f1 . f1 in let f4 = f2 . f2 in (f4 . f4) True -- Step 4 let f1 = not in let f2 = f1 . f1 in (f2 . f2 . f2 . f2) True -- Step 5 let f1 = not in (f1 . f1 . f1 . f1 . f1 . f1 . f1 . f1) True -- Step 6 (not . not . not . not . not . not . not . not) True -- Step 7 not (not (not (not (not (not (not (not True))))))) -- Step 8 not (not (not (not (not (not (not False)))))) -- Step 9 not (not (not (not (not (not True))))) -- Step 10 not (not (not (not (not False)))) -- Step 11 not (not (not (not True))) -- Step 12 not (not (not False)) -- Step 13 not (not True) -- Step 14 not False -- Output True
As expected, this reduction was performed lazily: not and True were not evaluated before substituting them in the function body. But, in that case, that doesn't do anything, because not and True were fully computed already. Moreover, as expected, Haskell memoizes the result of evaluating not and True. But that also doesn't do anything here, because both variables only occur once, and again, they were in normal form anyway.
Seems like Haskell used all its tricks and now it must proceed, but a tragedy happens in Step 2. Here,
f8 must be applied to True. But what is
f8? It is just a symbol, not a lambda that can be applied. In order to proceed, Haskell must unfold the expression by rewritting let
f8 = f4 . f4 in (f8 x) as
((f4 . f4) x); and then it unfold it further, until the whole expression becomes
not (not (not ... x)). Notice how this removed all the sharing, and now not must be applied
N times, as we dreaded. Oh, no! But what if we unrolled the sharing upside-down, like this:
-- Step 2 let f2 = not . not in let f4 = f2 . f2 in let f8 = f4 . f4 in f8 True -- Step 3 let f2 = id in let f4 = f2 . f2 in let f8 = f4 . f4 in f8 True -- Step 4 let f4 = id . id in let f8 = f4 . f4 in f8 True -- Step 4 let f4 = id in let f8 = f4 . f4 in f8 True -- Step 5 let f8 = id in f8 True -- Step 6 id True -- Step 7 True
That's much better! What do we need for that? Simple: execute arguments before function calls. For example, if, when executing comp recursively, we evaluated intermediate arguments, then
comp(4, not . not, x) would have been evaluated as
comp(4, id, x), which is equivalent to upside-down reduction above. But we know Haskell never evaluates arguments of a function call until they are necessary, and, when they are, they could've been duplicated several times. In other words, fusing intermediate values requires some eagerness, and Haskell's laziness prevents it from doing that.
f(x,y) = x case. Not only that, but there are also terms on which eager evaluation performs worse, even when there is no discarding involved. The λ-term
(λx.x (λa.a)) (λy.(λx.x x) (y z)) is an example (feel encouraged to try evaluating it!). This is the moment you realize that, no matter what evaluation strategy you use, you'll always waste work in some case.