Geekly Articles each Day
📜 ⬆️ ⬇️

Fall in love with F #: Dose 1: Spirit of functional programming

Dear Habrakollegi!

Finally, I begin some presentation of functional programming ideas along with the basics of the F # language. Today we will need to do the most important thing - to understand the basic principles of functional programming and imbued with its spirit. I apologize in advance to those functionary gurus who are waiting for more meaningful lessons - but I wanted to start from the beginning. Accordingly, for a start, a life story:

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


Why? Let's see. The name “functional programming” comes from the word “function”. 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 on Pascal also consists (or can consist) of functions. That's right, only in the Pascal program, in addition to functions, there are still operators that control structures such as cycles, and, most importantly, an assignment operator . The Pascal program sets a set of steps, each of which changes a certain state of the computer's memory, calculating expressions and assigning them to variables.


In functional programming, everything is wrong. 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, for example, 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 by the next natural number. In the case of F #, we do not have the notion of a variable, and we need to construct 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 symbol fact .


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


 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 goes rec also 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 with the if function of three arguments, as it 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 order of evaluation of the conditional expression):


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

From such a record it can be seen that there is nothing but the 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 recording 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 is applied to u and so on. Abstraction allows you to get a function by expression, in other words, to write a functional constant . For example, the entry 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 such operations 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 the language the construction of an ordered pair, triples, etc. is a full-fledged data type), but you can act in the traditions of functional programming, describing the plus function like this:


 let plus xy = x+y;;

If in the first case the function type is int * int -> int (i.e., a mapping from a pair to an integer type), then in the second one - int -> (int -> int) , i.e. it will be a function of an integer type, which returns a function from integer to integer. For example, the expression (plus 1) would mean an 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 common practice to use such functions in functional programming. In particular, all standard operations can be used in a curried form by enclosing the operation in parentheses 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 exists except a function , 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 example:


 let double x = x*2.0;;

describes the multiplication function by 2, something like this:


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

What is nice is that 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 into the F # interpreter, we get:


val double: float -> float


This means that the type was automatically defined 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 a composition of two double functions, denoted as >>.


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


Homework:



')

Source: https://habr.com/ru/post/51607/

More articles:


All Articles