Impure functions in F#

Despite F# being a functional-first language, it doesn't have out-of-the-box support to enforce the use of pure functions - or even detect them. Pure functions have some very useful properties for reasoning about code:

• For any given input, it will always return the same output. This is not only a useful property in terms of things like testability, but also has performance implications: pure functions can be easily cached.
• There are no side-effects. You can call a function and be confident that nothing defined outside of the function will be modified.

As Mark Seeman has written (and spoken) about, the only way that you can really guarantee this in F# is:

• Do not rely on external state to your function. Instead, only use arguments passed into your function.
• Do not pass functions into your function, which you cannot guarantee are pure. Instead, only pass values into your function.
• Do not call functions in your function that you cannot guarantee are pure.
• Do not permit mutable state, or at least do not permit mutable state to be accessible to your function. Instead, return values to the caller.

Examples of impure functions

I thought it would be useful to illustrate some different examples of impure functions and how you can prove this to be the case. All of the sample functions I'm going to define share the following common signature:

let f (x:int, y:int -> int) : int

In other words, given some function f that takes in two arguments:

• x: some integer
• y: some higher order function that takes in an integer and returns another integer

Then it should return an integer.

Here are five functions that obey the above type signature, yet only one of them is pure.

let mutable environment = 0
let mutable sideEffect = 0

let usesMutableVar (x, _) =
    x + environment
let usesRandom (x, _) =
    let z = System.Random().Next()
    x + z
let hasSideEffect (x, _) =
    sideEffect <- sideEffect + 1
    x
let usesDependency (x, y) =
    y x
let pureFn (x, _) =
    x + 10

1. The first function, usesMutableVar, is clearly at risk of being impure as it uses environment, a mutable value defined outside its scope, and this value could change at any time which would result in different outputs given the same input (one could suggest that simply using any external value not explicitly passed in is a sign of impurity...).
2. The second function, useRandom, is also impure - it calls another function, System.Random().Next(). This will give different outputs for the same input.
3. The third function, hasSideEffect, mutates the sideEffect variable in addition to performing the calculation. It is therefore impure.
4. usesDependency is a risky one - it could be pure, but only if the y supplied to it is also pure. In F#, we can't guarantee this. Therefore, the function can't be considered pure.
5. pureFn, as the name suggests, is pure. It only uses the x supplied to it, ignore the higher order function provided, and doesn't use or modify any external state.

Proving impurity

We can prove the above using something like the great FSCheck, which can provide random inputs to any function to prove certain properties, or behaviours that we expect. Properties in FSCheck are themselves just functions that prove, or disprove, some hypothesis. Look at this function:

let alwaysGivesTheSameOutput f x =
    let a = f (x, id)
    let b = f (x, id)
    a = b

This function says that given some function f (that adheres to our signature above), and some input value x, if the higher order function passed in is some constant function (in this case the identity function), then the output of f should always be the same. FSCheck can now prove this hypothesis against our five functions:

open FsCheck

Check.Quick (alwaysGivesTheSameOutput usesMutableVar) // passes
Check.Quick (alwaysGivesTheSameOutput usesRandom)     // fails
Check.Quick (alwaysGivesTheSameOutput usesDependency) // passes
Check.Quick (alwaysGivesTheSameOutput hasSideEffect)  // passes
Check.Quick (alwaysGivesTheSameOutput pureFn)         // passes

Notice that we only provided the value for the first argument (f) here, and not the value x - FSCheck will generate that for us. And FSCheck has indeed spotted that usesRandom does not work here:

Falsifiable, after 1 test (2 shrinks) (StdGen (1320957289,296747524)):
Original:
-1
Shrunk:
0

In other words, even given the input 0, this hypothesis fails.

Here are three other properties we can use to check if a function is pure or not:

let isNotAffectedByImpureInputs f x =
    let y x = (System.Random().Next() + x)
    let a = f (x, y)
    let b = f (x, y)
    a = b // should not be affected by impure dependency y

let isNotAffectedByEnvironmentChanges f x =
    let a = f (x, id)
    environment <- environment + 1
    let b = f (x, id)
    a = b // should still be equal

let isNotSideEffectful f x =
    let currentEnvironment = sideEffect
    f (x, id) |> ignore
    f (x, id) |> ignore
    currentEnvironment = sideEffect // should not have changed

Composing Properties with FsCheck

What's especially cool is that FsCheck lets you compose properties together, so we can create a single property that is the result of all four properties combined.

Note the .&. (compose two properties) and |@ (name a property) custom operators that FsCheck introduces for this specific scenario:

let isPure f x =
    (alwaysGivesTheSameOutput f x          |@ "Doesn't always give the same output") .&.
    (isNotAffectedByEnvironmentChanges f x |@ "Is affected by environment") .&.
    (isNotAffectedByImpureInputs f x       |@ "Is affected by impure inputs") .&.
    (isNotSideEffectful f x                |@ "Has a side effect")

We can now test our functions against all our properties simultaneously. Observe how the first four all fail with the exact property that we expect:

Check.Quick (isPure usesMutableVar) // Label of failing property: Is affected by environment
Check.Quick (isPure usesRandom)     // Label of failing property: Doesn't always give the same output
Check.Quick (isPure usesDependency) // Label of failing property: Is affected by impure inputs
Check.Quick (isPure hasSideEffect)  // Label of failing property: Has a side effect
Check.Quick (isPure pureFn)         // Ok, passed 100 tests.

Conclusion

We often talk about purity in the context of functional programming, but it's often not easy to observe some of the actual rules in tangible context. Hopefully this post has given you an understanding of what the rules of pure functions are, some of the tell-tale signs of an impure function (useful if your programming language doesn't support you here!) and lastly, a look at how the FsCheck library can help use prove or disprove rules about our code.

Have (fun _ -> ())

Isaac