Posted in:

After having seen a few presentations on F# over the last few months, I’ve been looking for some really simple problems to get me started, and this code golf question inspired me to see if I could factorize a number in F#. I started off by doing it in C#, taking the same approach as the answers on the code golf site (which are optimised for code brevity, not performance):

var n = 502978;
for (var i = 2; i <= n; i++)
{
    while (n%i < 1)
    {
        Console.WriteLine(i);
        n /= i;
    }
}

Obviously it would be possible to try to simply port this directly to F#, but it felt wrong to do so, because there are two mutable variables in this approach (i and n). I started wondering if there was a more functional way to do this working entirely with immutable types.

The algorithm we have starts by testing if 2 is a factor of n. If it is, it divides n by 2 and tries again. Once we’ve divided out all the factors of 2, we increment the test number and repeat the process. Eventually we get down to to the final factor when i equals n.

So the F# approach I came up with, uses a recursive function. We pass in the number to be factorised, the potential factor to test (so we start with 2), and an (immutable) list of factors found so far, which starts off as an empty list. Whenever we find a factor, we create a new immutable list with the old factors as a tail, and call ourselves again. This means n doesn’t have to be mutable – we simply pass in n divided by the factor we just found. Here’s the F# code:

let rec f n x a = 
    if x = n then
        x::a
    elif n % x = 0 then 
        f (n/x) x (x::a)
    else
        f n (x+1) a
let factorise n = f n 2 []
let factors = factorise 502978

The main challenge to get this working was figuring out where I needed to put brackets (and remembering not to use commas between arguments). You’ll also notice I created a factorise function, saving me passing in the initial values of 2 and an empty list. This is one of F#’s real strengths, making it easy to combine functions like this.

Obviously there are performance improvements that could be made to this, and I would also like at some point to work out how to make a non-recursive version of this that still uses immutable values. But at least I now have my first working F# “program”, so I’m a little better prepared for the forthcoming F# Tutorial night with Phil Trelford at devsouthcoast.

If you’re an F# guru, feel free to tell me in the comments how I ought to have solved this.

Comments

Comment by Sehnsucht

I'm not sure to understand the "make a non-recursive version that will still use immutable values". I don't see how one could do that without some kind of state to maintain (and thus mutate) ; mutation isn't that bad ; side-effect on the other hand ...
Your code as is is pretty decent IMO ; one thing to note though (not a big deal) ; as you construct the result list during recursion you end up with a reversed factors list that is [971;37;7;2] .
It could be solved prepending factor to recursion result ; but that way the function won't be tail-rec anymore (or simply reversing the results in factorise : f n 2 [] |> List.rev).
The other way to have both tail-rec and "good" order would be to use continuation but it's less readable.
I wrote a different version ; with the implementation "hidden" as a sub-function inside the "pretty, ready to use" one ; which use a recursive sequence expression with some reordering, a test to stop early (no need to go further if factor² > number) and "generalizing" it to allow all integral types (more for fun and demo purpose).
I also added a parameter to allow me to increase factor by 2 instead of 1 after factor 2 is done to avoid all other even number.
you can see it there : https://gist.github.com/Seh...

Sehnsucht
Comment by Mark Heath

Yes, not sure what I was thinking when I wrote about the "non-recursive immutable" version! I can't think of a way that can be done. And thanks again for sharing your solution. I always learn a lot from seeing how other people approach the same problem. I need to start making more using of the backwards pipe a bit more in my own code

Mark Heath
Comment by Sehnsucht

The backward pipe can be a bit tricky to use because of it's low precedence and left associatity ; meaning f <| g <| x is (f <| g) <| x and not the "expected" f <| (g <| x)
That leads to some weird syntax to make it right :


// associatity
let assoc_forward = { 1 .. 10 } |> Seq.map ((+) 3) |> Seq.toList
// let assoc_backward = Seq.toList <| Seq.map ((+) 3) <| { 1 .. 10 } // won't work
let assoc_backward = Seq.toList <| (Seq.map ((+) 3) <| { 1 .. 10 }) // need extra bracket

// precedence
//let pre_backward = { 1 .. 10 } |> Seq.map <| (+) 3 // won't work
let pre_backward = { 1 .. 10 } |> (Seq.map <| (+) 3) // need extra bracket

// incidentely this precedence allows this to work
let weirdo = (+) 3 |> Seq.map <| { 1 .. 10 }

That's why it's not so often used think. sometimes you see some people making their own high precedence right associatity backward pipe :


let inline (^<|) f x = f x

// associatity
let assoc_backward = Seq.toList ^<| Seq.map ((+) 3) ^<| { 1 .. 10 } // first could have been classic <| here

// precedence
let pre_backward = { 1 .. 10 } |> Seq.map ^<| (+) 3

Sehnsucht
Comment by Sehnsucht

I finally managed to understand what could be a non-recursion with immutable values :)
That's probably making a factorize function which is not recursive (a simple let instead of a let rec) ; but use high-order function to "hide" recursion and allowing us to keep immutability.
Once understood I manage to make one using Seq.unfold ; warning though it can be hard to understand because it's an Option hell (I only made it for int that time to keep things "simple")
https://gist.github.com/Seh...

Sehnsucht