Adventures in F# - F# 101 Part 6 (Lazy Evaluation)

Time for another adventure in F#, covering some of the basics of functional programming and F# in particular.  This is intended at looking not only at the language, but the implementation as it regards to C#.

Where We Are

Before we begin today, let's catch up to where we are today:
So, today we'll be covering the topic of lazy evaluation, so, without further ado, let's get started.

Lazy Evaluation

Another fascinating topic in the land of functional programming is lazy evaluation.  This technique is basically delaying the execution of a given code block until it is needed.  Imagine for a minute that you have a function that is basically an if-else function.  This function would take a boolean condition, and if false, it will execute the second block of code.  The last thing you'd want to do is evaluate the else statement if the if is true and the results could be disastrous.  Instead, we can delay that result until we ultimately need it.  But why is it useful?  Well, think of infinite calculations, or infinite loops, the last thing you want to do is evaluate all of them, and instead do it lazily on command.

It's one of the more important features in languages such as Haskell where Simon Peyton Jones, the principal designer of the Glasgow Haskell Compiler (GHC), really likes this features and talks about it extensively on DotNetRocks Episode 310.  By default, all function parameters computation are delayed by default.  If you'd like to see more about Haskell's lazy evaluation of a Fibonacci sequence, check it out on the HaskellWiki.

Back to F# now.  When we talk about a pure functional language, the compiler should be free to choose which order to evaluate the argument expressions.  Instead, F# does allow for side effects in this way, such as printing to the console, writing to a file, etc, so being able to hold off on those kinds of items just aren't possible.  F# by default does not perform lazy evaluation, instead has what is called eager evaluation.  To take advantage of lazy loading, use the lazy keyword in the creation of your function and wrap the area to be lazy evaluated inside that block.  You then use the Lazy.force function to evaluate the expression.  Once that is called for the first time, the results is then cached for any subsequent call.  Let's walk through a quick sample of how that works:

#light

 

let lazyMultiply =

  lazy 

  (

    let multiply = 4 * 4

    print_string "This is a side effect"

    multiply

  )


let forcedMultiply1 = Lazy.force lazyMultiply
let forcedMultiply2 = Lazy.force lazyMultiply

What you'll notice from the above sample is that I intentionally put a side effect inside my lazy evaluated code.  But, since the evaluation only happens once, then I should only see it in my console once, and sure enough, when you run it, it does.  This is called memoization, which is a form of caching.  This uses the Microsoft.FSharp.Control.Lazy class.  But, I wonder how it's actually done through the magic of IL.  Since I think C# is a little bit more readable, let's crack open .NET Reflector and take a look.



What we notice is that it creates a new class for us called lazyMultiply.  There is a lot of syntactic sugar behind the scenes, but as you can see, it's calling the same get_lazyMultiply function off my main class.  It's nothing more than a simple property that does this:



If you'd like to dig more into the guts of how that works exactly, check out Jomo Fisher's blog post about the Lazy Keyword here.  I'm definitely glad to see F# team members blogging about these sorts of things.

Lazy Collections?

F# also has the notion of lazy collections.  What this means is that you can calculate the items in your collection upon demand.  Some of the collections inside the F# library may also cache those results as well.  We have two types that we're interested in, the LazyList class (full name: Microsoft.FSharp.Compatibility.FSharp.LazyList in FSharp.Compatibility.dll) and the Seq class (full name: Microsoft.FSharp.Collections.Seq in FSharp.Core.dll).

The LazyList is a list which caches the results of the computed results on the items inside the collection.  In order to create a truly lazy list, you must use the unfold function.  What this does is returns a list of values in a sequence starting with the given seed.  The computation itself isn't computed until the first one is accessed.  The rest of the elements are calculated by the residual and I'll show you that below:

#light

 

let sequence = LazyList.unfold (fun x -> Some(x , x + 1)) 1
let first20 = LazyList.take 20 sequence

print_any first20

What the above sample allows us to do is create a list of infinite numbers, starting at the seed of 1.  But, the values aren't computed until the first is accessed, and then the results are cached.  But, in order to access any value out of them, you need to take x number of values from them.  The LazyList provides that capability to do that with the take function.  What you'll also notice is that we can use the None or Some functions. The Some function, as shown above has its first value as the starting value, and the second value is what it will be like the next time it will be called.  The None function, not shown above, represents the end of the list.

You may also use the Seq class to represent these lazy values.  Think of the Seq as the magic collection class inside F# as it compatible with most, if not all arrays, and most collections as well. 

But, what does that code look like as well?  Very interesting question.  Let's take a look at the main function first:



Ok, so that looks a bit interesting.  So, what does the sequence@3 really look like.  What we see is that we're giving it a seed of 1 and then getting the first 20 from the list.  Let's now take a look at the sequence@3.  What's we're interesting in is not the actual constructor, but the Invoke method as you remember, it's a lazy list.



So, as you can see, it sure enough looks like we had in our code from above with a heck of a lot more angle brackets.  I'm sure that's why some of the var stuff was introduced in C# 3.0 was to hide this ugliness.

Conclusion

Just to wrap things up here on a Friday, I hope you enjoyed looking at some of the possibilities of lazy loading.  This could also help with Abstract Syntax Trees, loading of data from files, XML documents, etc.  The real power is to take infinite data loops and take chunks of them at a time.  And we really don't have to worry about the stack as well when we do this.  I hope you've enjoyed the series so far and there are a few more things I'd want to cover before I consider this series done.  Until next time...

kick it on DotNetKicks.com
Published Friday, March 21, 2008 7:43 PM by podwysocki
Filed under:

Comments

# re: Adventures in F# - F# 101 Part 6 (Lazy Evaluation)

Sunday, November 15, 2009 2:08 AM by Mr.ICE

F# Version 1.9.7.4, compiling for .NET Framework Version v4.0.21006

error FS0039: The field, constructor or member 'force' is not defined

# re: Adventures in F# - F# 101 Part 6 (Lazy Evaluation)

Sunday, April 25, 2010 10:41 AM by Nils Stritze;

Due to changes in F# a working version of the code might rather look like this

let lazyMultiply =

 lazy

 (

   let multiply = 4 * 4

   printfn "This is a side effect"

   multiply

 )

let forcedMultiply1 = lazyMultiply.Value

let forcedMultiply2 = lazyMultiply.Value

# re: Adventures in F# - F# 101 Part 6 (Lazy Evaluation)

Tuesday, July 24, 2012 11:31 AM by Salcedo

Thanks so much for writing all of that the first-class information!

Looking forward to checking out more posts!

# re: Adventures in F# - F# 101 Part 6 (Lazy Evaluation)

Sunday, November 18, 2012 7:01 PM by Miller

Well written post. Thumbs up!

# re: Adventures in F# - F# 101 Part 6 (Lazy Evaluation)

Tuesday, November 20, 2012 12:06 AM by Dowling

I am glad to be a visitant of this gross web blog !

, regards for this rare information ! .

# re: Adventures in F# - F# 101 Part 6 (Lazy Evaluation)

Friday, November 30, 2012 10:58 AM by Wagner

I enjoyed reading your pleasant website. I see you give priceless

info. stumbled into this website by chance on that the other hand I’m sure glad I clicked on that

link. You definitely answered all the questions I’ve been dying

to response for some time now. Will definitely come back for more

of this.

# re: Adventures in F# - F# 101 Part 6 (Lazy Evaluation)

Saturday, December 22, 2012 2:25 PM by Burt

A whole lot of thanks for placing up this post, I feel every

individual will thanks for that.

# re: Adventures in F# - F# 101 Part 6 (Lazy Evaluation)

Thursday, December 27, 2012 5:37 AM by Mccants

I am crazy about this blog. I have visit so a whole lot of time

to this blog. I have found this blog from Google. I have received a bunch

of info. I actually appreciate to meet to it and i emphasize

to this blog. My curiosity to learn more plus much more on this blog.

# re: Adventures in F# - F# 101 Part 6 (Lazy Evaluation)

Friday, December 28, 2012 12:34 PM by Mayer

We’re glad to become visitor on this pure site, regards in this rare information!

# re: Adventures in F# - F# 101 Part 6 (Lazy Evaluation)

Tuesday, January 1, 2013 10:48 PM by Goff

thumbs up if your watching this out of that the future cause your a time traveler

# re: Adventures in F# - F# 101 Part 6 (Lazy Evaluation)

Saturday, January 19, 2013 12:50 PM by Watts

You have been therefore cool! My other half and

i do not assume I have discover anything something like this

prior to. So first-class to search for somebody with several original thoughts on this subject matter.

realy tons of thanks for beginning this up. this web site is something that’s

needed on the web, someone using a bit of inspiration.

beneficial project for delivering something a new comer to that the internet!