Understanding Lazy Evaluation in Haskell

Sorry this is way too long but...

I'm afraid the answer is going to depend a lot on the meaning of the words...

First, here's that code in Haskell (which uses static binding and lazy evaluation):

readInt :: String -> Int
readInt = read

main = do
    x <- fmap readInt getLine
    let y = x + 3
    print y
    x <- fmap readInt getLine
    print y

It prints 8 and 8.

Now here's that code in R which uses lazy evaluation and what some people call dynamic binding:

delayedAssign('x', as.numeric(readLines(n=1)))
delayedAssign('y', x + 3)
print(y)

delayedAssign('x', as.numeric(readLines(n=1)))
print(y)

It prints 8 and 8. Not so different!

Now in C++, which uses strict evaluation and static binding:

#include <iostream>

int main() {
    int x;
    std::cin >> x;
    int y = x + 3;
    std::cout << y << "\n";
    std::cin >> x;
    std::cout << y << "\n";
}

It prints 8 and 8.

Now let me tell you what I think the point of the question actually was ;)

"lazy evaluation" can mean many different things. In Haskell it has a very particular meaning, which is that in nested expressions:

f (g (h x))

evaluation works as if f gets evaluated before g (h x), ie evaluation goes "outside -> in". Practically this means that if f looks like

f x = 2

ie just throws away its argument, g (h x) never gets evaluated.

But I think that that is not where the question was going with "lazy evaluation". The reason I think this is that:

• + always evaluates its arguments! + is the same whether you're using lazy evaluation or not.

• The only computation that could actually be delayed is keyboard input -- and that's not really computation, because it causes an action to occur; that is, it reads from the user.

Haskell people would generally not call this "lazy evaluation" -- they would call it lazy (or deferred) execution.

So what would lazy execution mean for your question? It would mean that the action keyboard input gets delayed... until the value x is really really needed. It looks to me like that happens here:

echo y

because at that point you must show the user a value, and so you must know what x is! So what would happen with lazy execution and static binding?

x = keyboard input     # nothing happens
y = x + 3              # still nothing happens!
echo y (8)             # y becomes 8. 8 gets printed.
x = keyboard input (2) # nothing happens
echo y                 # y is still 8. 8 gets printed.

Now about this word "dynamic binding". It can mean different things:

1. Variable scope and lifetime is decided at run time. This is what languages like R do that don't declare variables.

2. The formula for a computation (like the formula for y is x + 3) isn't inspected until the variable is evaluated.

My guess is that that is what "dynamic binding" means in your question. Going over the code again with dynamic binding (sense 2) and lazy execution:

x = keyboard input     # nothing happens
y = x + 3              # still nothing happens!
echo y (8)             # y becomes 8. 8 gets printed.
x = keyboard input (2) # nothing happens
echo y                 # y is already evaluated, 
                       # so it uses the stored value and prints 8

I know of no language that would actually print 7 for the last line... but I really think that's what the question was hoping would happen!

The key thing about lazy evaluation in Haskell is that it doesn't affect the output of your program at all. You can read it just as if everything were evaluated as soon as it is defined, and you'll still get the same result.

Lazy evaluation is just a strategy for figuring out the value of an expression in the program. There are many possible and they all give the same result[1]; any evaluation strategy that changes the meaning of the program wouldn't be a valid strategy!

So from a certain perspective, you don't have to understand lazy evaluation (yet) if it's giving you trouble. When you're learning Haskell, especially if it's your first functional and pure language, thinking about expressing yourself in this way is much more important. I would also rate training yourself to become comfortable with reading Haskell's (often quite dense) syntax as more important than fully "grokking" lazy evaluation. So don't worry about it too much if the concept gives you difficulty.

That said, my go at explaining it is below. I haven't used your examples, as they're not really affected by lazy evaluation, and Owen has talked more clearly than I can about dynamic binding and delayed execution wrt your example.

The most important difference between (valid) evaluation strategies is that some strategies can fail to return a result at all where another strategy might succeed. Lazy evaluation has the particular property that if any (valid) evaluation strategy can find a result, lazy evaluation will find it. In particular, programs that generate infinite data structures and then only use a finite amount of the data can terminate with lazy evaluation. In the strict evaluation you're probably used to, the program has to finish generating the infinite data structure before it can go on to use part of it, and of course it will.

The way lazy evaluation achieves this is by only evaluating something when it's needed to figure out what to do next. When you call a function that returns a list, it "returns" straight away and gives you a placeholder for the list. That placeholder can be passed to other functions, stored in other data structures, anything. Only when the program needs to know something about the list will it be actually evaluated, and only as far as needed.

Say the program now is going to do something different if the list is empty than if it is not. The the function call that originally returned the placeholder is evaluated a little bit further, to see if it returns an empty list or a list with a head element. Then the evaluation stops again, as the program now knows which way to go. If the rest of the list is never needed, it will never be evaluated.

But it's also not evaluated more times than needed. If the placeholder was passed into multiple functions (so it's now involved in other not-yet-evaluated function calls), or stored into several different data structures, Haskell still "knows" that they're all the same thing, and arranges for them all to "see" the effects of any further evaluation of the placeholder triggered from any of them. Eventually, if all of the list is needed somewhere, they'll all be pointing to an ordinary fully-evaluated data structure, and laziness has no further impact.

But the key thing to remember is that everything needed to produce that list is already determined and fixed when the placeholder was generated. It can't be affected by anything else that's happened in the program since. If that were not so, then Haskell would not be pure. And vice versa; impure languages can't have Haskell-style full laziness behind the scenes, because the results you would get could change dramatically depending on when in the future the results are needed. Instead, impure languages that support lazy evaluation tend to have it only for certain things explicitly declared by the programmer, with warnings in the manual saying "don't use laziness on something dependent on side effects".

[1] I lie a little here. Keep reading below the line to see why.

Lazy Evaluation in Haskell: Leftmost-Outermost + Graph Reduction

Square x = x * x

Square (Square 42)

(Square 42) * (Square 42) -> Square 42 will be computed only one time thanks to Graph Reduction

(42 * 42) * (Square 42)

(1764) * (Square 42) -> next is Graph Reduction

1764 * 1764
=3111696

Leftmost-innermost (Java, C++)

Square (Square 42)

square ( 42 * 42)

square ( 1764 )

1764 * 1764 =3111696