Thursday, September 18, 2008

Programming with State in F# (Part 2)

In my last post, I talked about the contrast between F# where state is locked by default and your run-of-the-mill imperative language where it is very difficult to lock state. We also saw that F# allows us to explicitly use mutable state when we choose to do so but the point is that programmer must make an explicit choice. The theme of this series of posts is that F#'s answer to the "whether to use state or not to use state" question is the best: we try not to use state where we can get away with it but when we have to use state we make that decision explicitly and carefully.

I just want to talk about one example from the F# Core library. Here is an example from the Seq module:
let length (ie : seq<'a>)    = 
use e = ie.GetEnumerator()
let mutable state = 0
while e.MoveNext() do
state <- state + 1;
state
The length function takes any sequence and returns an int. The first line of the function retrieves the enumerator for the sequence. The second line declares a mutable identifier clearly labeled state. The rest of the function simply moves through the enumerator incrementing the count. Finally, the function returns the final count. Do the internals of the length function surprise you? This example is very similar to how a length might be determined in an imperative context and it highlights my favorite feature of F#: it's your choice. You certainly can implement length with a recursive function and an accumulating value but would it be as fast as the version shown above? Would it be as easy to understand? You decide.

Choices abound when using F# and one of the most important choices you can make will be whether or not to use state. The point of these last two posts are to highlight this quality of F#. State is generally discouraged but it is always available should you choose to use it.

3 comments:

Jay said...

Hey Ray:

"You certainly can implement length with a recursive function and an accumulating value but would it be as fast as the version shown above? Would it be as easy to understand? You decide."

So, one of the things I love about F# is that testing out these kinds of things with the F# Interactive session (FSI) is a breeze.

Using the "#time;;" directive in FSI, it turns out that the following functional definition of length is almost exactly as fast as the imperative, stateful version shown above.

let len2 (s : seq<'a>) =
    use e = s.GetEnumerator()
    let rec aux acc =
        if e.MoveNext() then
            aux (acc + 1)
        else
            acc
    aux 0


> #time;;

--> Timing now on

>
> seq {1..1000000000 } |> Seq.length;;
Real: 00:00:14.777, CPU: 00:00:14.531, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 1000000000
> seq {1..1000000000 } |> len2;;
Real: 00:00:14.802, CPU: 00:00:14.531, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 1000000000

Ray Vernagus said...

Great comment, Jay, thanks! I agree, FSI is an indispensable tool!

Art said...

I'm very interested in following your F# insights, they're helpful. I appreciate that you're coming at it from FP, OCaml, ML and not C variations.

Thanks
art