Rash thoughts about .NET, C#, F# and Dynamics NAV.

This is the third part in a “Questions and Answers”-series about the F# BootCamp in Leipzig. This time we will look at lazy evaluation.

Question 5 – What is the difference between “Lazy Evaluation” and “Eager evaluation”?

Lazy evaluation is a technique of delaying a computation until the result is required. If we use eager evaluation an expression is evaluated as soon as it gets bound to a variable.

One participant answered that lazy evaluation is used in most programming languages to calculate boolean expressions faster. For instance in the expression “x() or y()” the function y() is never called if x() returns true.

Of course this answer is correct, but this "short-circuit evaluation" is only a special case of lazy evaluation. The program would also work correctly without it. But if we want to define an infinite sequence then we can not use eager evaluation. Let’s look at an example:

// val fibs: seq<int>
let fibs = (1, 1) |> Seq.unfold(fun (n0, n1) -> Some(n0, (n1, n0 + n1)))

We do not need to understand the concrete syntax of this code here. We’ll discuss this later. Let’s just say fibs is bound to an infinite sequence (IEnumerable<int>) of Fibonacci numbers. You could also write this in C#:

/// <summary>
/// Infinite sequence of Fibonacci numbers.
/// </summary>
public static IEnumerable<int> Fibs()
{
    var n0 = 1;
    var n1 = 1;
    while(true)
    {
        yield return n0;
        var t = n1;
        n1 = n1 + n0;
        n0 = t;
    }
}

The trick is IEnumerable evaluates the elements lazy. Only at the time we take an element from the sequence the element will be computed:

fibs
  |> Seq.take 10
  |> Seq.to_list
  |> printfn "%A" // prints [1; 1; 2; 3; 5; 8; 13; 21; 34; 55]

If we would use eager evaluation then “Seq.take” would never been called. But we can go one step further. If we want to get the first 10 even-valued terms in the Fibonacci sequence, we can write this code:

fibs 
  |> Seq.filter (fun fib -> fib % 2 = 0) // lazy (via pipe)
  |> Seq.take 10                         // lazy (via pipe)
  |> Seq.to_list                         // eager
  |> printfn "%A" 
  
// prints [2; 8; 34; 144; 610; 2584; 10946; 46368; 196418; 832040]

This would be a little bit tricky if we use eager evaluation, but of course this nice laziness comes with some costs for storing intermediate results (and code). So eager evaluation is still often the better choice and sometimes (e.g. DateTime.Now()) it makes no sense to use lazy evaluation – at least not if we don’t reevaluate the function.