FSharp Functional Programming—Lazy Evaluation
|Visual C# Tutorials|
|.NET Framework Tutorials|
|© 2007 Robert Pickering|
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:
#light let lazyValue = lazy ( 2 + 2 ) let actualValue = Lazy.force lazyValue print_int actualValue print_newline()
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.
#light let lazySideEffect = lazy ( let temp = 2 + 2 print_int temp print_newline() 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.
seq values are created and manipulated using functions in the
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
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.
#light let lazyList = LazyList.unfold (fun x -> if x < 13 then Some(x, x + 1) else None) 10 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.
#light let fibs = Seq.unfold (fun (n0, n1) -> Some(n0, (n1, n0 + n1))) (1I,1I) 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.