Falling in Love with F #: Dose 1: The Spirit of Functional Programming

When I was young and taught programming in the first year of the Faculty of Applied Mathematics of the Moscow Aviation Institute, one of the students could not understand what X: = X + 1 means. “How so, how can X be equal to X + 1?” I had to explain to him how this is possible, and at that moment the functional programmer died in him ...

Why? Let's figure it out. The name “functional programming” comes from the word “function”. A functional program is built from functions. Actually, the program itself is also a function that can be applied to the input data and get the result.

“So what?” You say. - The program in Pascal also consists (or may consist) of functions. That's right, only in the program on Pascal, in addition to functions, there are also operators that control constructs such as loops, and, most importantly, the assignment operator . A program in Pascal sets a set of steps, each of which changes a certain state of the computer memory, calculating expressions and assigning them to variables.

In functional programming, this is not so. There are only functions, and all data is immutable . The entire program is built from a combination of functions that operate on data, processing some values ​​into others.

Consider an example: a factorial calculation function . In an imperative language, such as C #, the function will look like this:

public int fact(int n)
{
    int f = 1;
    for (int i = 2; i <= n; i++)
    {
        f = f * i;
    }
    return f;
}

We start the battery, and in the cycle we multiply it successively by the next natural number. In the case of F #, we do not have the concept of a variable, and we need to build a definition only using a combination of functions:

let rec fact n =
  if n = 1 then 1
  else n*fact(n-1)
     in fact 5;;

This expression calculates factorial 5. The main calculated expression here is fact 5 , and everything written before it determines the value of the fact symbol .

Generally speaking, the meaning of the let construct is to give a synonym name to some expression. For instance,

let x = 1 in
  let y = x+2 in
    x+5*y;;

Here, the names x and y are defined only in the context of the expression located after the word in - therefore, such an expression is completely analogous to the expression 1 + 5 * (1 + 2).

In our case, after let there is also rec to show that the definition of the function is recursive. The function itself is defined as a pure composition of other functions: a conditional function (indeed, in this case, the if statement could be replaced by an if function of three arguments, as was done, for example, in Excel), multiplication, subtraction, and the fact function itself. In fact, you can rewrite the definition like this (here, for clarity, I omit some points related to the procedure for calculating the conditional expression):

let rec fact n = iff ((=) n 1) 1 ((*) n (fact ((-) n 1)));;

It can be seen from such a record that there is nothing here but a composition of functions. In fact, in pure functional programming there are only two operations: application (applying a function to an argument) and abstraction (the ability to construct a function from an expression). Sequential writing of several functions of the form fguv means ((fg) u) v, i.e. the application is carried out from left to right, first f is applied to g, the result should be a function that applies to u and so on. Abstraction allows you to get a function by expression, in other words, write a functional constant . For example, the notation fun x -> x * 2 means a function that, by an integer argument, returns its double value.

Consider another important concept - currying . All functions in functional programming are single, i.e. have one argument. I wonder how in this case to be with operations such as addition?

There are two options. You can consider addition as a function of an ordered pair , for example

let plus' (x,y) = x+y;;

(at the same time, an attentive reader noticed that in a language the construction of an ordered pair, triple, etc. is a full-fledged data type), but you can act in the tradition of functional programming, describing the plus function as follows:

let plus x y = x+y;;

If in the first case the function type is int * int -> int (i.e., mapping from a pair to an integer type), then in the second - int -> (int -> int) , i.e. it will be a function from an integer type that returns a function from integer to integer. For example, the expression (plus 1) will mean the increment function, i.e. increasing the argument by 1. The record plus 1 2 will be considered as (plus 1) 2, i.e. first we get the increment function, and then apply it to the number 2, getting the desired result. The plus function is called the curried addition function, and it is customary to use such functions in functional programming. In particular, all standard operations can be used in curried form by enclosing the operation in brackets and using a prefix notation, for example:

(+) 1 2;;
let incr = (+)1;;

So, we understood the following basic principles of functional programming: everything is a function , nothing but a function exists , there is no assignment operator and variables . Let's understand one more principle: functions are full-fledged entities (first-class citizens), you can pass functions as parameters, describe functional constants and operate with functions. For instance:

let double x = x*2.0;;

describes the function of multiplying by 2, something like this:

public double doub(double x)
{
    return x * 2.0;
}

What is nice - in F # there is almost never a need to specify the types of parameters and values ​​- they are obtained automatically due to the work of the type inference system. In particular, if we introduce the above definition of the double function in the F # interpreter, we get:

val double: float -> float

This means that the type was automatically detected as a function from float to float.

Consider the following expression:

let double x = x*2.0 in 
 let quad = (double >> double) in quad 5.0;;

Here we first describe the double function, then another quad function, which is the composition of two double functions, denoted as >>.

At the end of the lesson, I would like to offer you some tasks and questions as a homework for reflection.

Homework:

• Define a function to find the roots of the quadratic equation.
• Implement a functional program to find the sum of the numbers from 1 to 100. The sum of the squares of these numbers.
• In your opinion, which of the factorial calculation functions described in this lesson is “better” - implemented in C # or F #?
• Describe the currying function, which returns a corresponding function in a curried form using a two-place non-curried function (i.e., a function of a pair of values).
• Describe the decarring function that is inverse to what was required in clause 4