Back to Questions
869
views4
comments
Understanding lazy evaluation
f#

Hello !
Below is the solution to generating the nth prime number.
let primes =
{ 2L..System.Int64.MaxValue } |> Seq.filter isPrime
primes |> Seq.nth 10000

I don't quite understand the concept of lazy evaluation. In the fragment primes takes an input sequence (step - 1) (so it is lazy evaluated) applies "isPrime" predicate to filter it (step - 2) and from resulting sequence takes the nth element (step - 3). The thing that I quite don't get it is how step 3 "communicates" on the sequence generation (step 1) and the intermediary step 2 so as to make all this work of generating ONLY the first n primes possible. I think that composition is great ! but me coming from imperative programming (although find this mathematic solution of the problem very elegant) I have difficulties understanding how that really works under cover... I hope it makes sense what I've asked ...

Thanks !
Ghita

.

To a certain extent I think you can "let go" and not worry too much about how it is implemented under the covers.

However I guess it good to know how it works, so I'll try and explain:

In OO terms you can think of "primes" as an object that implements the IEnumerator interface. To implement IEnumerator you to do implement a method "MoveNext" and "Current". Because of the design of the interface there's no need to calculate anything in advance, you only need to do calculations when you call "MoveNext". F# takes advantage of this, calculation of the next item in the sequence is only preformed when you enumerate the sequence i.e. when move next is called.

You should note that the result is not cached so each time you enumerate the sequence you will (re)perform all the calculations. This is good in some cases, if for example the collection is large or even infinite and caching it would waste memory. It bad in other cases, for example when collections are expensive to calculate.

Hope that helps,

Robert

By on 6/10/2009 5:21 AM ()

Thanks for insights Robert !
I still have some issues to clarify although. I think that for a beginner like me in functional programming is important to understand or at least have a grasp of these concepts; later then I will not have to worry too much about these once I've understood the basics.

On the same line then: the composition of the functions is the key here. How does "Seq.nth" function provide "feedback" to our primes object that is should keep generating primes -> and then validation of the generated numbers against Seq.filter ...

Only from seeing the code fragment one could tell that you have those 3 steps, and apply them sequentially 1 -> 2 -> 3 . Seeing how that could be implemented in terms of OO and provide full benefit of functional composition would be a great way to explain the novice that there is no "magic" there...

By on 6/10/2009 5:44 AM ()

... I think that for a beginner like me in functional programming is important to understand or at least have a grasp of these concepts; later then I will not have to worry too much about these once I've understood the basics.

I think that one of the problems with F# is that it's very concise syntax can conceal complex functionality. That's what's happening with your example. In two lines you've got: big ints, a sequence, a sequence expression, the |> operator, a comprehension function, a "let" binding and lazy evaluation. This is far from basic.

You've also got some "magic" (I think this is the hard part). With sequences, the lazy evaluation is hidden. There's nothing in the syntax which discloses that it is any different from a non-lazy construct. But it is different. Robert's explanation of the implementation is very good, but I'll also agree with him that you can work with them, without understanding this (I do). In F# you can use the key word "lazy" to have user defined lazy evaluation, but sequences are the only case of hidden, system implemented lazy evaluation.

I'd suggest you break your example into it's components, and play with them, and then put it all together, and don't worry too much about the lazy evaluation. You've got other things to master before you get there. First up, try rewriting "primes" without |>.

------------------------

Answer:

let primes = Seq.filter isPrime { 2L..System.Int64.MaxValue }

No magic! It is *exactly* the same value

By on 6/12/2009 4:22 AM ()

It actually simpler than you think. 2 sequence objects are generates, but as are lazy there is little head in this. The fist sequence is a list of integers 0 to Int.Max, the second sequence is generated from this by apply isPrime to each item in the first list until it finds one that returns true. The function Seq.nth simply keeps calling the MoveNext - keep count of how many times its called it - until its reached the item you want.

You only "see" the filter sequence since you've choose not to bind the original list to an identifier.

Hope that makes sense.

Rob

By on 6/10/2009 6:13 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper