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

"Every solution will only lead to new problems."

Wednesday, 24. June 2009

F# BootCamp – Questions and Answers – part III – Lazy evaluation

Filed under: English posts,F#,Informatik — Steffen Forkmann at 11:27 Uhr

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;
        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:

  |> 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:

  |> 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.

Tags: , ,


  1. “but this “short-circuit evaluation” is only a special case of lazy evaluation. The program would also work correctly without it”

    I would argue that many programs actually *rely* on short curcuit evaluation and would break without it. the most common case in OO style languages would be

    if (foo != null && foo.Bar == Baz) { … }

    Infinity is a much nicer reason to have proper lazy evaluation though 🙂

    Comment by Matt — Friday, 26. June 2009 um 14:07 Uhr

  2. Hi Matt,

    thanks for your remark. You are right, the short-circuit evaluation is mostly used to handle nulls – but this assumes a specific order of evaluation. Of course most programming languages are using left to right so this is no problem, but theoretically real lazy evaluation could be non-deterministic at this point.

    So maybe short-circuit evaluation of boolean expressions is not a real subtype of lazy evaluation.

    The problem of this null-check is, that it requires a sequential order. Consider this code:

    if f1() or f2() then
      printfn "One is true"

    If f1 and f2 are long running tasks (without side-effects), then it would be nice to run them in parallel. If one of the both finishes the other function could be cancelled.

    This (parallel) short-circuit evaluation strategy would break your null-check.


    Comment by Steffen Forkmann — Monday, 29. June 2009 um 9:28 Uhr

RSS feed for comments on this post. | TrackBack URI

Leave a comment

XHTML ( You can use these tags): <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> .