Zach
Zach

Reputation: 585

Purely Functional Programming

So, I'm an experienced OOP programmer (primarily C++), just now starting to dip my toes in with functional programming. From my understanding, in a purely functional paradigm, functions shouldn't have conditionals and should be broken down as much as possible using currying. Could someone provide me the "pure" functional version of the following example? Preferably using every strict technique that would be part of the functional paradigm:

let rec greatestCommonFactor a b =
    if a = 0 then b
    elif a < b then greatestCommonFactor a (b - a)
    else greatestCommonFactor (a - b) b

Upvotes: 14

Views: 320

Answers (1)

TheInnerLight
TheInnerLight

Reputation: 12184

The example function that you have supplied is already purely functional. When we talk about a function purity, what we are actually talking about is the property of functions being referentially transparent.

An expression is referentially transparent if it can be replaced with its value without altering the effect of the program. To give a simple example, imagine the function:

let add2 x = x + 2

Now, anywhere that the value add2 2 appears in our program, we can substitute the value 4 without altering the behaviour of the program.

Imagine now that we add some additional behaviour into the function that prints to the console:

let add2Print x =
    printfn "%d" x
    x + 2

Although the result of the function is the same as before, we can no longer perform value substitution with the value 4 without changing the behaviour of our program because our function has the additional side-effect of printing to the console.

This function is no longer referentially transparent and therefore not a pure function.


let rec greatestCommonFactor a b =
    if a = 0 then b
    elif a < b then greatestCommonFactor a (b - a)
    else greatestCommonFactor (a - b) b

Looking at this function that you have supplied, no side-effects are involved in its execution. We will always get the same output value for given inputs a and b, therefore this is already a pure function.

To be clear, there is absolutely no issue with functions containing conditionals in functional programming. Often, however, we make use of pattern matching rather than if/elif/else expressions but in the example you have described, this is purely stylistic. An alternative expression of your function using pattern matching would be:

let rec greatestCommonFactor a b =
    match a with
    |0 -> b
    |a' when a' < b -> greatestCommonFactor a' (b - a')
    |a' -> greatestCommonFactor (a' - b) b

Upvotes: 16

Related Questions