CODEWITHSUNDEEP
algorithmf#
Nils
Nils

Reputation: 9941

Primefactors in F#

I am trying to learn F#.
I wrote a function that factors out primes. 

let PrimeFactors x =
  let rec PrimeFactorsRecursive x div list =
     if x % div = 0 then PrimeFactorsRecursive (x/div) div list @ [div]
     elif div > int(System.Math.Sqrt(float(x))) then 
       if x > 1 then list @ [x]
       else list
     else PrimeFactorsRecursive x (div + 1) list
  PrimeFactorsRecursive x 2 []

Now I am unsure if this is a good F# function or if it is more like "c#, written in f#".

Is there a "more" functional way to write this code?

Upvotes: 1

Views: 255

Answers (3)

Stephen Swensen
Stephen Swensen

Reputation: 22297

Another "improvement" not yet mentioned is to use piping so that instead of 

int(System.Math.Sqrt(float(x)))

you have

(x |> float |> sqrt |> int)

Upvotes: 1

Yin Zhu
Yin Zhu

Reputation: 17119

The primal problem in your code is that you use @ to concat two lists. Concating two lists costs linear time, not constant time.

The constant way is to add the new prime number to the head of a list using :: operator as shown below:

let primeFactors x = 
    let rec fact x div list = 
        if x % div = 0 then
            fact (x/div) div (div::list)
        elif div > int(sqrt (float x)) then
            if x > 1 then x::list
            else list
        else
            fact x (div+1) list
    fact x 2 []

Also let bind values are usually following camleStyle naming conversions.

Upvotes: 4

Gian
Gian

Reputation: 13955

You could probably use guarded patterns to reduce the if-expression nesting. Other than that it looks like perfectly reasonable idiomatic functional code to me.

Upvotes: 0

Related Questions