Introducing functional programming

In functional programming, we write functions without side effects the way we write in Mathematics. The variable in the code function represents the value of the function parameter, and it similar to the mathematical function. The idea is that a programmer defines the functions that contain the expression, definition, and the parameters that can be expressed by a variable in order to solve problems.

After a programmer builds the function and sends the function to the computer, it's the computer's turn to do its job. In general, the role of the computer is to evaluate the expression in the function and return the result. We can imagine that the computer acts like a calculator since it will analyze the expression from the function and yield the result to the user in a printed format. The calculator will evaluate a function which are composed of variables passed as parameters and expressions which form the body of the function. Variables are substituted by their values in the expression. We can give simple expression and compound expressions using algebraic operators. Since expressions without assignments never alter the value, sub expressions needs to be evaluated only once.

Suppose we have the expression 3 + 5 inside a function. The computer will definitely return 8 as the result right after it completely evaluates it. However, this is just a simple example of how the computer acts in evaluating an expression. In fact, a programmer can increase the ability of the computer by creating a complex definition and expression inside the function. Not only can the computer evaluate the simple expression, but it can also evaluate the complex calculation and expression.

Understanding definitions, scripts, and sessions

As we discussed earlier about a calculator that will analyze the expression from the function, let's imagine we have a calculator that has a console panel like a computer does. The difference between that and a conventional calculator is that we have to press Enter instead of = (equal to) in order to run the evaluation process of the expression. Here, we can type the expression and then press Enter . Now, imagine that we type the following expression:

3 x 9 

Immediately after pressing Enter , the computer will print 27 in the console, and that's what we are expecting. The computer has done a great job of evaluating the expression we gave. Now, let's move to analyzing the following definitions. Imagine that we type them on our functional calculator:

square a = a * a 
max a b  = a, if a >= b 
         = b, if b > a 

We have defined the two definitions, square and max. We can call the list of definitions script. By calling the square function followed by any number representing variable a, we will be given the square of that number. Also, in the max definition, we serve two numbers to represent variables a and b, and then the computer will evaluate this expression to find out the biggest number between the variables.

By defining these two definitions, we can use them as a function, which we can call session, as follows:

square (1 + 2) 

The computer will definitely print 9 after evaluating the preceding function. The computer will also be able to evaluate the following function:

max 1 2 

It will return 2 as the result based on the definition we defined earlier. This is also possible if we provide the following expression:

square (max 2 5) 

Then, 25 will be displayed in our calculator console panel.

We can also modify a definition using the previous definition. Suppose we want to quadruple an integer number and take advantage of the definition of the square function; here is what we can send to our calculator:

quad q = square q * square q 
quad 10 

The first line of the preceding expression is a definition of the quad function. In the second line, we call that function, and we will be provided with 10000 as the result.

The script can define the variable value; for instance, take a look at the following:

radius = 20 

So, we should expect the computer to be able to evaluate the following definition:

area = (22 / 7) * square (radius) 

Using substitution and simplification to evaluate the expression

Using a mathematical method called reduction, we can evaluate expressions by substitution variables or expressions to simplify the expressions until no more substitution on reduction is possible. Let's take our preceding expression, square (1 + 2) , and look at the following reduction process:

square (1 + 2) -> square 3 (addition) 
               -> 3 x 3    (square) 
               -> 9        (multiply) 

First, we have the symbol -> to indicate the reduction. From the sequence, we can discover the reduction process-in other words, the evaluation process. In the first line, the computer will run the 1 + 2 expression and substitute it with 3 in order to reduce the expression. Then, it will reduce the expression in the second line by simplifying square 3 to 3 x 3 expressions. Lastly, it will simplify 3 x 3 and substitute it with 9, which is the result of that expression.

Actually, an expression can have more than one possibility in the reduction. The preceding reduction process is one of the possibilities of a reduction process. We can also create other possibilities, like the following:

square (1 + 2) -> (1 + 2) x (1 + 2) (square) 
               -> 3 x (1 + 2)       (addition)  
               -> 3 x 3             (addition) 
               -> 9                 (multiply) 

In the preceding sequence, firstly, we can see that the rule for a square is applied. The computer then substitutes 1 + 2 in line 2 and line 3. Lastly, it multiplies the number in the expression.

From the preceding two examples, we can conclude that the expression can be evaluated using simple substitution and simplification, the basic rule of mathematics. We can also see that the expression is a representation of the value, not the value itself. However, the expression will be in the normal form if it can't be reduced anymore.

Understanding the functions used for functional programming

Functional programming uses a technique of emphasizing functions and their application instead of commands and their execution. Most values in functional programming are function values. Let's take a look at the following mathematical notation:

f :: A -> B 

From the preceding notation, we can say that function f is a relation of each element stated there, which is A and B. We call A, the source type, and B, the target type. In other words, the notation of A -> B states that A is an argument where we have to input the value, and B is a return value or the output of the function evaluation.

Consider that x denotes an element of A and x + 2 denotes an element of B, so we can create the mathematical notation as follows:

f(x) = x + 2 

In mathematics, we use f(x) to denote a functional application. In functional programming, the function will be passed as an argument and will return the result after the evaluation of the expression.

We can construct many definitions for one and the same function. The following two definitions are similar and will triple the input passed as an argument:

triple y = y + y + y 
triple' y = 3 * y 

As we can see, triple and triple' have different expressions. However, they are the same functions, so we can say that triple = triple'. Although we have many definitions to express one function, we will find that there is only one definition that will prove to be the most efficient in the procedure of evaluation in the sense of the reducing the expression we discussed previously. Unfortunately, we cannot determine which one is the most efficient from our preceding two definitions since that depends on the characteristic of the evaluation mechanism.

Forming the definition

Now, let's go back to our discussion on definitions at the beginning of this chapter. We have the following definition in order to retrieve the value from the case analysis:

max a b  = a, if a >= b 
         = b, if b > a 

There are two expressions in this definition, distinguished by a Boolean-value expression. This distinguisher is called guards, and we use them to evaluate the value of True or False. The first line is one of the alternative result values for this function. It states that the return value will be a if the expression a >= b is True. In contrast, the function will return value b if the expression b >= a is True. Using these two cases, a >= b and b >= a, the max value depends on the value of a and b. The order of the cases doesn't matter. We can also define the max function using the special word otherwise. This word ensures that the otherwise case will be executed if no expression results in a True value. Here, we will refactor our max function using the word otherwise:

max a b  = a, if a >= b 
         = b, otherwise 

From the preceding function definition, we can see that if the first expression is False, the function will return b immediately without performing any evaluation. In other words, the otherwise case will always return True if all previous guards return False.

Another special word usually used in mathematical notations is where. This word is used to set the local definition for the expression of the function. Let's take a look at the following example:

f x y = (z + 2) * (z + 3) 
        where z = x + y 

In the preceding example, we have a function f with variable z, whose value is determined by x and y. There, we introduce a local z definition to the function. This local definition can also be used along with the case analysis we have discussed earlier. Here is an example of the conjunction local definition with the case analysis:

f x y = x + z, if x > 100 
      = x - z, otherwise 
        where z = triple(y + 3) 

In the preceding function, there is a local z definition, which qualifies for both x + z and x - z expressions. As we discussed earlier, although the function has two equal to (=) signs, only one expression will return the value.

Currying

Currying is a simple technique of changing structure arguments by sequence. It will transform a n-ary function into n unary function. It is a technique which was created to circumvent limitations of Lambda functions which are unary functions. Let's go back to our max function again and get the following definition:

max a b  = a, if a >= b 
         = b, if b > a 

We can see that there is no bracket in the max a b function name. Also, there is no comma-separated a and b in the function name. We can add a bracket and a comma to the function definition, as follows:

max' (a,b)  = a, if a >= b 
            = b, if b > a 

At first glance, we find the two functions to be the same since they have the same expression. However, they are different because of their different types. The max' function has a single argument, which consists of a pair of numbers. The type of max' function can be written as follows:

max' :: (num, num) -> num 

On the other hand, the max function has two arguments. The type of this function can be written as follows:

max :: num -> (num -> num) 

The max function will take a number and then return a function from single number to many numbers. From the preceding max function, we pass the variable a to the max function, which returns a value. Then, that value is compared to variable b in order to find the maximum number.