Fledgling Forays in F#

So, to start learning F#, I searched for existing F# code. One of the first snippets I found was the sieve of Eratosthenes in many languages, including F#. Except the listed F# ‘sieve’ wasn’t; it did an exhaustive search from 2 to Math.Sqrt(int_of_float n) for every element n.

I thought, “Even as a beginner, I can do better than that.” Here’s my first attempt:

let rec primes_match n =
    match n with
        | nn when nn <= 1 -> []
        | nn when nn > 1 ->
            let so_far = primes_match (n - 1)
            if (so_far |> List.filter (fun d -> nn % d = 0) |> List.isEmpty)
            then nn :: so_far
            else so_far

let primes n = n |> primes_match |> List.rev

Then I realized ‘match’ was a bit heavy for what I’m doing, and shifted to if/then/else:

let rec primes_match n =
    if n <= 1 then []
    else
        let so_far = primes_match (n - 1)
        if (so_far |> List.filter (fun d -> n % d = 0) |> List.isEmpty)
        then n :: so_far
        else so_far

let primes n = n |> primes_match |> List.rev

And finally, I learned about List.exists.

let rec primes_match n =
    if n <= 1 then []
    else
        let so_far = primes_match (n - 1)
        if (so_far |> List.exists (fun d -> n % d = 0))
        then n :: so_far
        else so_far

let primes n = n |> primes_match |> List.rev

I was proud, but not satisfied. There are still two major problems with this code. First, it’s still not the sieve of Eratosthenes. It’s just a more-time-efficient version (I think, maybe) of the original algorithm. Second, it’s not tail-recursive, and stack depth grows with the input parameter, so it can only generate primes up to 32,750 or so.

So, I started from scratch. I managed to create a new sieve function that is, in fact, the sieve of Eratosthenes, and tail-recursive. As it turns out, Chris Smith has a sieve implementation as well, but I didn’t look at it before writing my own. Mine came out shorter, but probably less efficient.

let rec sieve_drain (sifted : int list) (unsifted : int list) =
    if List.isEmpty unsifted then sifted
    elif (sifted |> List.exists (fun d -> (List.head unsifted) % d = 0))
    then sieve_drain sifted (List.tail unsifted)
    else sieve_drain ((List.head unsifted) :: sifted) (List.tail unsifted)

let sieve n =
    sieve_drain [] (2::[3..2..n]) |> List.rev

Any suggestions? Am I being too strict when it comes to functional style? Is there any way I can polish this?

Update:

I managed to find a cleaner way to do this:

let rec sieve_drain (sifted : int list) (unsifted : int list) =
    match unsifted with
    | [] -> sifted
    | x :: xs ->
        if not (sifted |> List.exists (fun d -> x % d = 0))
        then sieve_drain (x::sifted) xs
        else sieve_drain sifted xs

let sieve n =
    if n < 2 then [] else sieve_drain [] (2::[3..2..n]) |> List.rev

But it’s not very efficient. Chris Smith’s implementation (due to the use of shared state) takes about 2.5 seconds to run from 1 to 500,000. Mine takes about 55.