FSharp Functional Programming—Lazy Evaluation

Jump to: navigation, search
Visual C# Tutorials
.NET Framework Tutorials

F# Functional Programming

© 2007 Robert Pickering

Lazy Evaluation

Lazy evaluation is something that goes hand in hand with functional programming. The theory is that if there are no side effects in the language, the compiler or runtime is free to choose the evaluation order of expressions. As you know, F# allows functions to have side effects, so it’s not possible for the compiler or runtime to have a free hand in function evaluation; therefore, F# is said to have a strict evaluation order or be a strict language. You can still take advantage of lazy evaluation but must be explicit about which computations can be delayed, that is, evaluated in a lazy manner. You use the keyword lazy to delay a computation, that is, invoke lazy evaluation. The computation within the lazy expression remains unevaluated until evaluation; it is explicitly forced with the force function from the Lazy module. When the force function is applied to a particular lazy expression, the value is computed; then the result is cached, and subsequent calls to the force function return the cached value, whatever it is, even if this means raising an exception. The following code shows a simple use of lazy evaluation:

let lazyValue = lazy ( 2 + 2 )
let actualValue = Lazy.force lazyValue
print_int actualValue

On the first line, you delay a simple expression for evaluation later. The next line forces evaluation. Then you print the value. The value has been cached, so any side effects that take place when the value is computed will occur only the first time the lazy value is forced. This is fairly easy to demonstrate. In the next example, you create a lazy value that has a side effect when it is calculated: it writes to the console. To show that this side effect takes place only once, you force the value twice, and it is plain to see from the result that writing to the console takes place only once.

let lazySideEffect =
        ( let temp = 2 + 2
            print_int temp
            temp )
print_endline "Force value the first time: "
let actualValue1 = Lazy.force lazySideEffect
print_endline "Force value the second time: "
let actualValue2 = Lazy.force lazySideEffect

The results of this example are as follows:

Force value the first time:
Force value the second time:

Laziness can also be useful when working with collections. The idea of a lazy collection is that elements in the collection are calculated on demand. Some collection types also cache the results of these calculations, so there is no need to recalculate elements. F# provides the LazyList collection type, which caches computed results and is useful for functional programming and search. The second lazy collection is the seq type, a shorthand for the BCL’s IEnumerable type. This plays a similar role to LazyList but does not cache computed results. LazyList and seq values are created and manipulated using functions in the LazyList and Seq modules, respectively. Many other values are also compatible with the type seq; for example, all F# lists and arrays are compatible with this type, as are most other collection types.

The next example shows how to use the LazyList module. Possibly its most important function, and probably the most difficult to understand, is unfold. This function allows you to create a lazy list. What makes it complicated is that you must provide a function that will be repeatedly evaluated to provide the elements of the list. The function passed to LazyList.unfold can take any type of parameter and must return an option type. An option type is a union type that can be either None or Some(x), where x is a value of any type. None is used to represent the end of a list. The Some constructor must contain a tuple. The first item in the tuple represents the value that will become the first value in the list. The second value in the tuple is the value that will be passed into the function the next time it is called. You can think of this value as an accumulator.

The next example shows how this works. The identifier lazyList will contain three values. If the value passed into the function is less than 13, you append the list using this value to form the list element and then add 1 to the value passed to the list. This will be value passed to the function the next time it is called. If the value is greater than or equal to 13, you terminate the list by returning None. To display the list, you use the function display, a simple recursive function that processes the head of the list and then recursively processes the tail.

let lazyList =
        (fun x ->
            if x < 13 then
                Some(x, x + 1)
let rec display l =
    match  l with
    | LazyList.Cons(h,t) ->
        print_int h
        print_newline ()
        display t
    | LazyList.Nil ->
display lazyList

The results of this example, when compiled and executed, are as follows:


Lazy lists are also useful to represent lists that don’t terminate. A nonterminating list can’t be represented by a classic list, which is constrained by the amount of memory available. The next example demonstrates this by creating fibs, an infinite list of all the Fibonacci numbers; it uses the Seq module, although it could just as well have used the LazyList module because the unfold function works in the same way in both. To display the results conveniently, you use the function Seq.take to turn the first 20 items into an F# list, but you carry on calculating many more Fibonacci numbers as you use F# bigint integers, so you are limited by the size of a 32-bit integer.

let fibs =
       (fun (n0, n1)  ->
           Some(n0, (n1, n0 + n1)))
let first20 = Seq.take 20 fibs
print_any first20

The results of this example are as follows:

[1I; 1I; 2I; 3I; 5I; 8I; 13I; 21I; 34I; 55I; 89I; 144I; 233I; 377I; 610I; 987I;
1597I; 2584I; 4181I; 6765I]

These examples are too simple to really demonstrate the power of lazy evaluation. You’ll look at lazy evaluation again in several places in this book, notably in Chapter 7, where you’ll see how to use lazy evaluation in user-interface programming to make user interfaces more responsive by ensuring computations do not happen until really needed.

prevpp.png  nextpp.png
C# Online.NET