Back to Questions
2.4k
views5
comments
laziness of sequences
f#

Hi all.
I have a question regarding F# sequences.
In MSDN a sequence is described as follows: Sequences are particularly useful when you have a large, ordered collection of data but do not necessarily expect to use all the elements. Individual sequence elements are computed only as required, so a sequence can provide better performance than a list in situations in which not all the elements are used.

Are they implicitly lazy or it is unfold function that makes them lazy?

For example, is this 

1

seq { 0 .. 10 .. 100 }

lazy yet?
if yes, how is it lazy, because there is nothing to evaluate in this expression?

Or may be 

1

seq { for i in 1 .. 10 do yield i * i }

is lazy because a new value is yielded with each iteration?

Thanks and best regards.

.

They are lazy because none of the sequence elements are constructed/computed at the time of defining the sequence itself. When you type one of the above in F# Interactive, the value printer "forces" evaluating the first N elements (looks like 4 by default) - but the rest is not computed:

1
2

> seq { for i in 1 .. 10 do yield i * i };;
val it : seq<int> = seq [1; 4; 9; 16; ...]

If there is nothing that needs the values inside the sequence, they remain not computed, hence we say that the sequence is lazy.

Here is a practically infinite sequence:

1
2
3
4

    let rec numbersAbove i =
        seq {
            yield i
            yield! numbersAbove (i+1) }

Evaluating it in F# Interactive will be instant - since none of the elements are computed:

1
2
3
4

val numbersAbove : int -> seq<int>

> numbersAbove 0;;
val it : seq<int> = seq [0; 1; 2; 3; ...]

However, the followings gets you in trouble, since the sequence has practically no end:

1

> Seq.length <| numbersAbove 0;;
By on 12/4/2011 12:09 PM ()

So for example 

1

 let sequence = seq { for i in 1 .. 10 do yield i * i }

is somehow equivalent to 

1

let result = lazy (x + 10)

but for each element of the sequence, right?

By on 12/6/2011 10:12 AM ()

Almost, yes. They both delay computation until need comes to evaluate the expressions, so in that respect they are similar.

BTW, lazy has the same effect as wrapping the expression that follows it in a function:

1

lazy (x+10)    <==>    fun () -> x+10

However, the Lazy type provides some further bookkeeping, for instance it knows whether the expression it guards has been evaluated or not. This also means that a Lazy value needs allocated memory, and thus it is slightly different than the laziness of a sequence - which simply delays creating new values until the sequence is enumerated.

By on 12/6/2011 11:08 AM ()

Thanks for the explanations.

By on 12/6/2011 11:12 AM ()

Both are lazy, not only because it doesn't compute but also because it doesn't allocate the memory (in the first example, it means that it only remembers that the sequence is a range from 0 to 100 with jumps of 10, without allocating the 44 bytes to store the values).

By on 12/4/2011 7:29 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