Lazy initialization is a creational design pattern in which computing a value or instantiation of (an) object(s) is delayed until the first time it is needed. The purpose of this article is to demonstrate the implementation of a general Lazy Initialization pattern using the F# language. Although F# has built-in faculties for dealing with Lazy Initialization it will be instructive if you are coming from a C# background to see how this can be implemented in the F# language.

F# is not implicitly lazy, however it is worthwhile to note that the keyword “eager” is reserved for future use and I have no idea why. As it is, right now, F# is eagerly evaluated and we have to tell the compiler to “be lazy here”. With regard to explicit laziness we have a few approaches at our disposal. Let’s start out with the core concepts and then work toward a solid implementation of Lazy Initialization.

Goals:

1. Delay the binding of values
2. Cache the results such that the computation is performed only once

The correct implementation of Lazy Initialization consists of two primary goals; first, an expensive computation must be delayed until the value is actually needed to continue executing the program. Second, the memoization of the result is needed so that additional requests for the value do not perform the computation again.

  1: // Delay with unit.
  2: type ComplicatedObject = System.Object
  3: let o     = new ComplicatedObject() // val a  : ComplicatedObject
  4: let f  () = new ComplicatedObject() // val a' : unit -> ComplicatedObject

In this example we are type aliasing System.Object to a type named ComplexObject, which saves me the hassle of creating anything complex for purposes of demonstration. On line 3 a new instance of ComplicatedObject is created and immediately bound to the value o. In line 4 we have created a thunk, by defining a function, the type here happens to be:

\(unit \rightarrow ComplicatedObject\)

The thunk is bound to the value f. Line 4 is really all it takes to delay binding, which is the first requirement listed in the primary goals of Lazy Initialization. A function like f used to delay the creation of ComplicatedObjects. When we evaluate f with unit, we receive a new ComplicatedObject in return, which can then be bound to some other value.

Although we shouldn’t neglect the consequences of eager evaluation when considering what problems, other than the *cough* obvious performance cost of initializing ComplicatedObject entails. Consider then, the following situation involving Schrödinger’s Cat:

  5: type Cat =
  6:   | Alive
  7:   | Dead
  8: 
  9: let whatsInTheBox () =
 10:   let aliveOrDead =
 11:     match (new System.Random()).Next 2 with
 12:     | 0 -> Alive
 13:     | _ -> Dead
 14:   let alive = printfn "A happy kitty"
 15:   let dead  = printfn "A dead kitty."
 16:   match aliveOrDead with
 17:   | Alive -> alive
 18:   | Dead  -> dead
 19: 
 20: whatsInTheBox ()

Now, when we ask whatsInTheBox () we find that our side effects are in the not-so-super position of being eagerly bound to the values alive : unit and dead : unit.

A happy kitty.
A dead kitty.
val it : unit = ()

So we use the technique on line 4 to instead create thunks to printfn. Since we’re really going to be opening the box this time we’ll also return the Cat to the caller.

 21: let openTheBox () =
 22:   let aliveOrDead =
 23:     match (new System.Random()).Next 2 with
 24:     | 0 -> Alive
 25:     | _ -> Dead
 26:   let alive = fun () -> printfn "A happy kitty."
 27:   let dead  = fun () -> printfn "A dead kitty."
 28:   match aliveOrDead with
 29:   | Alive -> alive
 30:   | Dead  -> dead
 31: 
 32: openTheBox ()

This behaves as intended, delaying the call to printfn until it is absolutely necessary. I’ve used a different syntax for lines 26 and 27 from line 4. Declarations such as: let f () = () and let f = fun () -> () are structurally identical. Deciding which syntax to use and where is a li.

A happy kitty.
val it : SchrodingersCat = Alive

In practice, the technique we’re using here is a bit cumbersome. If you had many types for which you needed to delay construction, you would have to wrap each of their default constructors in functions with different names. Or even a type with many properties whos construction is delayed until they are first accessed could potentially cause us to write a lot of repetitive code. Since F# treats functions as values we can create some higher order generalizations of delay:

 33: // Generalizing delay.
 34: let delay    x ()       = x // val delay    : 'a -> unit -> 'a
 35: let delayf   f x ()     = f x
 36: let delayAny x (_ : 'b) = x // val delayAny : 'a ->  'b  -> 'a
 37: let delayNew<'a when 'a : (new : unit -> 'a)> () = new 'a()
 38: 
 39: delayNew<ComplicatedObject>     // val it : (unit -> ComplicatedObject)
 40: delayNew<ComplicatedObject> ()  // val it : ComplicatedObject

We’ve accomplished our first goal of understanding how to delay values in F#, but what about the second? In order to cache the result of computations we will need a type to represent the kinds of results a computation may result in. I’ll use the word Idle as a synonym for Lazy so as to not conflict with the built-in lazy syntax in F#. First of all the result of the computation can either be currently delayed, already cached, or some exceptional case. We can use a Discriminated Union to express that.

 41: // our own lazy type implementation
 42: type IdleState<'a> =
 43:   | Delayed   of (unit -> 'a)
 44:   | Cached    of 'a
 45:   | Exception of System.Exception

Now we will construct an Idle<'a> type to encapsulate and mutate IdleState<'a>. We will need a static member to create instances of Idle, a property that tells us if the delayed value has already been computed, and finally a way to force the computed value. We can use a mutable record type augmented with the appropriate members to pull this off. However, with mutability there creeps in the hidden danger of shared state. We’ll get around that easily in F# using the built-in lock function.

 47: type Idle<'a> = 
 48:   { mutable status : IdleState<'a> }
 49:   static member Create f = 
 50:     {status = (Delayed (f))}
 51:   member x.IsValueCreated 
 52:     with get() =
 53:       lock x.status (delay <|
 54:         match x.status with 
 55:         | Cached _  -> true 
 56:         | _         -> false)
 57:   member x.Force () = 
 58:     lock x.status (delay <|
 59:       match x.status with
 60:       | Cached    v -> v
 61:       | Delayed   f -> try 
 62:                          let v = f () in 
 63:                          x.status <- (Cached(v))
 64:                          v
 65:                        with e -> 
 66:                          x.status <- Exception(e)
 67:                          reraise()
 68:       | Exception e -> raise e)
 69:   member x.Value 
 70:     with get() = x.Force ()
 71: 
 72: module Idle =
 73:   let create  (f : unit -> 'a) = Idle.Create(f)
 74:   let force   (x : Idle<'a>)   = x.Value

Here is how we would go about using our Idle type. First I define the ackerman function, something that should eat up a few cycles so we can see the difference between creating the delayed computation and forcing it to be computed.

 75: // a vicious recursive function
 76: let rec ackerman = function
 77:   | (m,n) when m = 0I -> n + 1I
 78:   | (m,n) when n = 0I -> ackerman (m - 1I, 1I)
 79:   | (m,n)             -> ackerman (m - 1I, ackerman (m, n-1I))
 80: 
 81: // delayed by our Idle mechanism
 82: let ack3_9 = Idle.create(delayf ackerman (3I,9I))
 83: 
 84: ack3_9.Value

Fortunately, we don’t actually have to do all of this ourselves. F# provides some syntactical sugar for us in the form of a lazy keyword and a Lazy module that provides a functional wrapper over the type Lazy in the .NET BCL. Using these faculties is strait forward, and the lazy keyword allows us to create a Lazy with any valid F# expression. So here is a lazy explination of F# lazy…

 85: let y = Lazy.Create(fun () -> 5) // give it a thunk
 86: let x = lazy (printfn "automatically wraps your expression in a thunk",37)
 87: 
 88: y.IsValueCreated                    // No
 89: x.IsValueCreated                    // No
 90: y.Force()                           // This will force y'
 91: y.IsValueCreated                    // Yes
 92: x.IsValueCreated                    // No
 93: let result = y.Value + (snd x.Value)// Uses chached y', forces x'
 94: y.IsValueCreated                    // Yes
 95: x.IsValueCreated                    // Yes
 96: x.Value                             // It's cached
 97: result // is bound to the value of 42 due to the forcing of x' and y'
 98: 
 99: // this should verify that the Next System.Random has been computed only once
100: let multipleForcing = lazy ((new System.Random()).Next 100)
101: [for x in 1..10 do yield multipleForcing.Force()]
102: 
103: let add a b = a + b                  // Function not lazy
104: let theSum  = add 41 1               // Value not lazy
105: let sum a b = lazy ( a + b )         // Function is lazy
106: let theSum' = sum 41 1               // Value is lazy
107: theSum'.Force()                      // Force it when you want
108: 
109: module Lazy =                        
110:   let force (x : Lazy<'a>) =         // Make a helper function
111:     x.Force()
112: 
113: Lazy.force <| sum 5 37               // Use it like this

In closing, we’ve taken a look at how to build our own type implementing a Lazy Initialization pattern in the F# language that is made thread-safe by using the F# Operators.lock function wherever the state is accessed. We’ve also breifly looked into the F# Lazy module and lazy keyword concluding nothing beats the ability to use lazy as a keyword that implicitly thunks any expression!

F# Web Snippets