Pure functions

Pure functions

Pure functions are functions which will give exact result when the same arguments are passed. For example the mathematical function sin (0) always results 0. This means that every time you call the function with the same arguments, you will always get the same result. A function can be a pure function provided it should not have any external variable which will alter the behaviour of that variable.

Let us see an example

let square x

return: x * x

The above function square is a pure function because it will not give different results for same input.

There are various theoretical advantages of having pure functions. One advantage is that if a function is pure, then if it is called several times with the same arguments, the compiler only needs to actually call the function once. Lt’s see an example

let i: = 0;

if i <strlen (s) then

--Do something which doesn't affect s

 ++i

If it is compiled, strlen (s) is called each time and strlen needs to iterate over the whole of ‘s’. If the compiler is smart enough to work out that strlen is a pure function and that ‘s’ is not updated in the loop, then it can remove the redundant extra calls to strlen and make the loop to execute only one time. From these what we can understand, strlen is a pure function because the function takes one variable as a parameter, and accesses it to find its length. This function reads external memory but does not change it, and the value returned derives from the external memory accessed.

1. Impure functions

The variables used inside the function may cause side effects though the functions which are not passed with any arguments. In such cases the function is called impure function. When a function depends on variables or functions outside of its definition block, you can never be sure that the function will behave the same every time it’s called. For example the mathematical function random() will give different outputs for the same function call.

let Random number

let a := random()

if a > 10 then

return: a

else

return: 10

Here the function Random is impure as it is not sure what will be the result when we call the function.

2. Side-effects (Impure functions)

As you are aware function has side effects when it has observable interaction with the outside world. There are situations our functions can become impure though our goal is to make our functions pure. Just to clarify remember that side effect is not a necessary bad thing.Sometimes they are useful (especially outside functional programming paradigm).

Modify variable outside a function

One of the most popular groups of side effects is modifying the variable outside of function.

For example

let y: = 0

(int) inc (int) x

y= y + x;

return (y)

In the above example the value of y get changed inside the function definition due to which the result will change each time. The side effect of the inc () function is it is changing the data of the external visible variable ‘y’. As you can see some side effects are quite easy to spot and some of them may tricky. A good sign that our function impure (has side effect) is that it doesn’t take any arguments and it doesn’t return any value.

From all these examples and definitions what we can understand about the main differences between pure and impure functions are

Now let’s see the example of a pure function to determine the greatest common divisor (gcd) of two positive integer numbers.

let rec gcd a b :=

if b <> 0 then gcd b (a mod b) else return a;;

output

gcd 13 27;;

- : int = 1

gcd 20536 7826;;

- : int = 2

In the above example program ‘gcd’ is the name of the function which recursively called till the variable ‘b’ becomes ‘0’. Remember b and (a mod b) are two arguments passed to ‘a’ and ‘b’ of the gcd function.

Chameleons of Chromeland problem using function

Recall the In the Chameleons of Chromeland problem what you have studied in class XI. suppose two types of chameleons are equal in number. Construct an algorithm that arranges meetings between these two types so that they change their color to the third type. In the end, all should display the same color.

Let us represent the number of chameleons of each type by variables a, b and c, and their initial values by A, B and C, respectively. Let a = b be the input property.

The input – output relation is a = b = 0 and c = A + B + C. Let us name the algorithm monochromatize. The algorithm can be specified as

monochromatize (a, b, c)

In each iterative step, two chameleons of the two types (equal in number) meet and change their colors to the third one. For example, if A, B, C = 4, 4, 6, then the series of meeting will result in

In each meeting, a and b each decreases by 1, and c increases by 2. The solution can be expressed as an iterative algorithm.

monochromatize (a, b, c)

--inputs : a = A, b=B, c=C, a=b

--outputs : a = b = 0, c = A+B+C

while a>0

a, b, c := a-1, b-1, c+2

The algorithm is depicted in the flowchart as below

Now let us write this algorithm using function

let rec monochromatize a b c :=

if a > 0 then

a, b, c := a-1, b-1, c+2

else

a:=0, b:=0, c:= a + b + c

return c