hubFS: THE place for F#

I am new to the language and trying to solve Euler Problem 10 (http://projecteuler.net/):- "What is the sum of all primes below 2 million?"

I thought that this was a neat answer:-

let getPrimes1 (max) =

    let primes = new BitArray(max+1, true)

    [ for n in [2..max] do

            if primes.[int n] then

                for i in [int64 n * int64 n..int64 n..int64 max] do primes.[int i] <- false

                yield n ]

 

let solve1 () =

    getPrimes1 2000000 |> Seq.fold (fun acc itm -> int64 itm + acc) 0L

Well "awful" is always an objective assessment, but what I can say for sure is that it doesn't look "functional".  It looks like a solution you'd code in C# or C, translated into F#.  Which, while not ideal, is not always bad.  That's why F# gives you the ability to write imperative code, because sometimes it's just the best way to do things. 

That said, if you want to find a way to make it more functional, one thing you could do is find a way to introduce a recursion in order to replace the two loops.  A first attempt at this might look like this:

let getPrimes max =
    let primes = new BitArray(max+1, true)
    let max = max |> uint64
    let rec next_prime n results =
        if (n>max) then results
        else if (primes. [ n ]) then
            let start = n*n
            if start < max then
                let i = ref (int start)
                while !i < max do
                    primes.[!i] <- false
                    i := !i + n
            next_prime (n+1UL) (n::results)
        else next_prime (n+1UL) results
    next_prime 2UL []

(Warning, this code may not compile, I don't have a compiler I can test it on where I am).  But this is already better, because we removed some state (the results list), and instead changed it to an immutable list data type.  Instead of "results.Add n"  we only need to do "n::results", which sticks n onto the front of the list in an immutable fashion.  Since it is immutable, we obviously can't leave it declared at the top level scope because with no way to modify it, there would be no way to pass information about new primes to each successive recursive call.  So instead we add it as an argument to the recursive call, and each time through, if the number is prime we recurse with n::results, and if it's not prime, we just use the original results. 

Now to get rid of the ref variable in the inner while loop.  Really all you have here is a for loop that a) starts at "start", b) has a step value of "n", and c) stops when the index is greater than or equal to max.  F# provides a construct that does exactly this.

for i in [start .. n .. (max-1)] do
    primes. [ i ] <- false

Using a few more simplifications, we can now convert the code to:

let getPrimes max =
    let primes = new BitArray(max+1, true)
    let max = max |> uint64

    let rec next_prime n results =
        if (n>max) then results
        else if (primes. [ n ]) then
            for i in [(n*n) .. n .. (max-1)] do
                primes. [ i ] <- false
            next_prime (n+1UL) (n::results)
        else next_prime (n+1UL) results
    next_prime 2UL []

The bit array probably offers the best performance you're going to get, especially in terms of memory usage, but if you really want to take it an extra step, try to change this to an immutable data type as well.  Perhaps you could use another list here, and then use the List.filter() function.

Thanks for a comprehensive answer. I've tried your code, it works and is fast. It is much more 'functional programming friendly' than my second attempt (I accept that the sieve is best solved imperatively and that we should probably keep the mutable BitArray).

However, I don't quite see what has gone wrong with my first attempt. I have an almost identical solution written by a friend in c# and it has very good performance. So my follow on question is:- why does the c# below work well and the f# below not?

It looks like there are a few things you can do to speed up the more functional version.  First of all, in your inner for loop, you don't need to explicitly create a list; just use "for i in int64 n * int64 n..int64 n..int64 max" instead.  This will avoid lots of allocations, and on my machine speeds up the overall code by roughly 30%.

To eke more performance out of the code, you'll need to make changes which are more dramatic.  It looks like the main list comprehension slows things down a lot.  The following refactoring runs much faster on my computer (but still about 4 times slower than the imperitive version):

let getPrimes1 max =
  let primes = new BitArray(max+1, true)
  seq { 2 .. max } |>
  Seq.filter (fun n ->
    if primes.[int n] then
      for i in int64 n * int64 n..int64 n..int64 max do primes.[int i] <- false
    primes.[int n])

C# iterator blocks are compiled into state automatons, while F# sequences are composed using library components and lamda functions. The C# approach yields better performance, in particular for nested sequence expressions.

When iteration speed really matters, one better stays away from sequences (IEnumerables), since iterating over them costs about 1-2 allocations per iteration loop and 2 interface calls per element. See Joe Duffy's blog post for some numbers.

(Note that in the next release of F#, F# 'seq' blocks will get compiled into state machines, hurray.)

You guys are my heroes. [Edited: Removed question about generalization to computation expressions, which only makes limited sense.]

Thanks to all who responded to this thread. The speed and quality of support on HubFS has proved excellent. You all get a metion in Martin's writeup here http://blogs.msdn.com/mpeck/archive/2009/03/03/Solving-Problems-in-CSharp-and-FSharp-Part-1.aspx