Learning F# with Prime Factorization

Question

In my quest to learn F#, I implemented Prime Factorization.

First, the code:

let primefactors x = 

    let check = seq { let limit = uint64((ceil(sqrt(float(x)))));
                      for x in Seq.concat [seq { yield 2UL }; { 3UL .. 2UL .. limit }] do
                        yield x }

    let getFirstOrDefault def ns =
        if ns |> Seq.isEmpty then
            def
        else
            ns |> Seq.head

    let nextfactor x = 
        match x with
        |1UL -> x
        |_ -> check
              |> Seq.skipWhile(fun idx -> x % idx <> 0UL)
              |> getFirstOrDefault x

    let rec getfactors x factors =
        match nextfactor x  with
        |1UL -> factors
        |factor -> (factors |> List.append [factor]) |> getfactors (x / factor)

    [] |> getfactors x

let smallFactors = primefactors 3672215407307975928UL
let bigPrimeFactor = primefactors 18446744073709551556UL
let biggestuint64Prime = primefactors 18446744073709551557UL

Im satisfied with the performance, but have some gripes with this code that I'd like feedback on:

I'm checking for 1UL in two places. In nextfactor it's there to skip the last run through the numbers; in getfactors it's the break condition. I don't feel like this is as elegant as it could be.

Another thing I don't like is the getFirstOrDefault function. At first I simply had a Seq.head after the Seq.skipWhile but that throws if the number itself is prime and so the sequence is empty. I'd like to do pattern matching with that as I would with lists but in that case I'd have to materialize the whole sequence which I'd like to avoid. Is there something like |[] -> ... for sequences?

I would also like to hear suggestions on how to construct the check sequence in a more elegant way.

I am aware that the algorithm itself is a pretty naive implementation of the problem, but I'm ok with that as it's (for me) sufficiently fast in the range of uint64. If you do have suggestions on how to improve performance while keeping with this simple algorithm, I'd love to hear them, though!

I'm also interested in hearing where I'm missing functional concepts that might be applicable here.

Answer 1

I think you show a good understanding of F# as a language and functional programming in general as far as I can see. A couple of things though:

You use x as variable name on multiple levels of function definitions. It makes it hard to read.

IMO match .. with is a very readable construct for more than two matches. But for only two I prefer if-statements.

The check function/sequence is a kind of double sequence. I would do it this way:

let primefactors target = 
    let check ta = Seq.concat [seq { yield 2UL }; { 3UL .. 2UL .. uint64(ceil(sqrt(float(ta))))}]

and then call it like this:

let nextfactor x = 
    match x with
    |1UL -> x
    |_ -> check x
          |> Seq.skipWhile(fun idx -> x % idx <> 0UL)
          |> getFirstOrDefault x

It will make the function much faster.

The getfactors - function is not tail-recursive, but can easily be changed to be:

let rec getfactors x factors =
    match nextfactor x  with
    |1UL -> factors
    // Here the factors list is handled before the recursive call.
    |factor -> getfactors (x / factor) (factor :: factors)