Replacing an F# loop over a mutable variable by an immutable approach

Question

Consider:

        let mutable m' = m
        while m' % i = 0L do
            m' <- m' / i

I've refactored it into:

        let m' =
            let rec exhaust m =
                if m % i = 0L then exhaust (m/i)
                else m
            exhaust m

but it's pretty obvious to me that the original code was way more concise and clear than this last one. Is there anything simple and clear that I'm missing regarding this refactor?

The full algorithm:

(* Calculates all the prime factors of a given integer *)
let primeFactors x =
    let rec primeFactors' = function
        | (m, _, r) when m = 1L -> r
        | (m, i, r) ->
            let mutable m' = m
            while m' % i = 0L do
                m' <- m' / i
            primeFactors' (m', (i+1L), (if m <> m' then i::r else r))
    List.rev (primeFactors' (x, 2L, []))

Answer 1

I would write it this way

let rec exhaust m i =
    match m % i with
    | 0L -> exhaust (m / i) i
    | _ -> m

Not a huge improvement, but I think it's idiomatic. Now let's look at primeFactors:

let primeFactors x =
    let rec primeFactors' = function
        | (m, _, r) when m = 1L -> r
        | (m, i, r) ->
            let m' = exhaust m i
            primeFactors' (m', (i+1L), (if m <> m' then i::r else r))
    List.rev (primeFactors' (x, 2L, []))

Let's get rid of the when:

let primeFactors x =
    let rec primeFactors' = function
        | (1L, _, r) -> r
        | (m, i, r) ->
            let m' = exhaust m i
            primeFactors' (m', (i+1L), (if m <> m' then i::r else r))
    List.rev (primeFactors' (x, 2L, []))

And tidy up a little

let primeFactors x =
    let rec primeFactors' = function
        | 1L, _, r -> r
        | m, i, r ->
            let m' = exhaust m i
            primeFactors' (m', i + 1L, if m <> m' then i::r else r)
    primeFactors' (x, 2L, []) |> List.rev

I know the style in F# is for short variable names, and I'm all for that for the most part, but I think in this case we can/should make them a bit clearer.

let rec exhaust n factor =
    match n % factor with
    | 0L -> exhaust (n / factor) factor
    | _ -> n

let rec primeFactors' = function
    | 1L, _, factors -> factors
    | n, factor, factors ->
        let m = exhaust n factor
        primeFactors' (m, factor + 1L, if n <> m then factor::factors else factors)

let primeFactors n =
    primeFactors' (n, 2L, []) |> List.rev

Answer 2

It's been said that "recursion is the goto of functional programming". If you don't get the tail recursion right, your stack can explode, so I like to use alternatives like fold if I can.

In this case, how about using the under-appreciated unfold (PDF) instead?

let rec exhaust n factor =
    match n % factor with
    | 0L -> exhaust (n / factor) factor
    | _ -> n

let nextFactor (n,factor) =
    if n = 1L then 
        None  // None means terminate the unfold
    else         
        let m = exhaust n factor
        let maybePrimeFactor = if n <> m then Some factor else None
        let newState = m, (factor + 1L)
        Some (maybePrimeFactor,newState) // Some means keep the unfold going

let primeFactors n =    
    (n, 2L) 
    |> Seq.unfold nextFactor // this will contain Nones for non-prime factors 
    |> Seq.choose id         // so filter them out

No recursion in the prime factor generation now, but because it uses seq rather than list it is probably not as performant as the list version.

And because the "looping" is separated from the "processing", some people might consider this code somewhat cleaner as a result.