CODEWITHSUNDEEP
f#functional-programmingimmutability
Den Tada
Den Tada

Reputation: 23

Multiplying two numbers by successive sums in F#

Giving m and n as integers, I can multiply them by successive sums like this:

    m * n = m + m + m + ... + m (n times)

So, let's consider the pseudo code below:

    m = ... (first number)
    n = ... (second number)

    Result = 0;
    while (n > 0)
    {
        Result = Result + m;
        n = n - 1;
    }

How can I implement this algorithm in F# knowing that variables are immutable? Put the question in another way, how can I update the variables Result and n along the successive iterations?

Can someone write this algorithm in F#?

Thank you

Foot note: I'm start to study F# and I'm complete puzzled with functional programming.

Upvotes: 1

Views: 863

Answers (2)

rasmusm
rasmusm

Reputation: 599

You can use Seq (lazy list like in haskell / IEnumerable like in C#) and the pipe operator:

let mult n (m:int) =
    Seq.initInfinite (fun _ -> m)
    |> Seq.take n
    |> Seq.sum

Upvotes: 1

Nikon the Third
Nikon the Third

Reputation: 2831

First of all, you can use mutable variables in F#, so your algorithm could be written like this:

let multiply1 m n =
    let mutable result = 0
    for i = 1 to n do
        result <- result + m
    result

But if you want to do it a little more the functional way, you would use recursion. In this case, an inner function that accumulates the result:

let multiply2 m n =
    let rec loop x acc =
        if x = 0 then acc
        else loop (x - 1) (acc + m)
    loop n 0

The multiply2 function uses an inner recursive function called loop that accumulates the result of the multiplication in the acc argument. So loop calls itself n times and adds m each time to the accumulator. Once x reaches zero, this result is returned.

Technically, you could also write the code without the accumulator argument:

let multiply3 m n =
    let rec loop x =
        if x = 0 then 0
        else m + loop (x - 1)
    loop n

Maybe this code is easier to understand for a beginner, but it should be avoided, since it does not use tail recursion and this leads to problems. For example, this will result in a StackOverflowException:

multiply3 5 1000000 // This will cause a StackOverflowException.
|> printfn "Result: %d"

Upvotes: 2

Related Questions