.NET
Raiting:
5

"Patterns" of functional programming


image
Many people represent functional programming as something very complex and "science-intensive", and representatives of the OP-community - aesthetic philosophers living in an ivory tower.

Until recently, such a view of things really was not far from the truth: we say FP, we mean Haskel and the theory of categories. Recently, the situation has changed and the functional paradigm is gaining momentum in web development, not without the help of F #, Scala and React. Let's take a look at the "patterns" of functional programming that are useful for solving everyday problems from the point of view of the OOP paradigm.

OOP is widely spread in the development of applied software for more than a decade. We are all familiar with SOLID and GOF. What will be their functional equivalent? .. Functions! Functional programming is simply "different" and offers other solutions.

image
Basic principles of functional design (design)
<img align="left" src="https://habrastorage.org/web/804/c4c/866/804c4c8667da4362b0d05feb88c62b18.jpg">
Functions as first-class objects
In contrast to the "classic" OOP (the first versions of C ++, C #, Java) functions in the FP are independent objects and should not belong to any class. It is convenient to represent the function as a magic railway tunnel: you feed apples to the entrance, and on the output you get bananas (apple -> banana).

The syntax of F # emphasizes that functions and values ​​are equal in rights:

let z = 1
let add = x + y // int -> int ->int
Composition as the main "building material"
image

If we have two functions, one transforming apples into bananas (apple -> banana), and another banana in cherry (banana -> cherry), combining them we get the functions of converting apples into cherries (apple -> cherry). From the point of view of the programmer, there is no difference in obtaining this function with the help of a composition or written manually, most importantly its signature.

The composition is applicable both at the level of very small functions, and at the level of the whole application. You can represent the business process as a chain of use cases and compile them into the httpRequest -> httpResponse function. Of course, this is only possible for synchronous operations, but for asynchronous ones there is reactive functional programming, which makes it possible to do the same.

image

One can imagine a composition of functions as a fractal. The definition of a fractal in the strict sense does not coincide with the definition of a composition. By presenting a fractal, you can visualize how your control flow consists of composed functions, consisting of composed functions, consisting of ...
Template (Composite) in OOP can also be thought of as a "fractal", but the linker works with data structures, not transformations.
Types ! = classes
<img align = "left" src = "https://habrastorage.org/web/116/700/4b1/1167004b1126401ba7464782f6411c6a.gif"> The type system in FP has more in common with set theory than with classes from OOP. int - that type. But the type need not be a primitive. Customer is also a type. Functions can accept input and return functions. Int -> int is also a type. So the "type" is the name for a certain set.

Types can also be arranged. Most of the functional NL works with an algebraic type system that is different from the class system in OOP.
Multiplication (logical "and", record type in F #)
At first glance this may seem strange, but it makes sense. If we take a lot of people and many dates, "multiplying" them we get many birthdays.

type Birthday = Person * Date
Addition (logical "or", discriminated union type in F #)
type PaymentMethod =
| Cash
| Cheque of ChequeNumber
| Card of CardType * CardNumber
Discriminated union is a complex name. It is easier to imagine this type as a choice. For example, you can choose to pay for goods in cash, by bank transfer or by credit card. There is nothing in common between these options, besides, they are all a way of payment.
Once, we used "unions" to model the object model.
 Entity Framework can work with such types from the box, you just need just add id . <Tgsrbq>
Aspiration for "completeness"
image

Let's look at the function of "divide 12 into". Its signature int -> int and it's a lie! If we pass 0 to the input, the function throws an exception. Instead, we can replace the signature withNonZeroInteger -> int or int -> int option.

image

The OP pushes you to a more rigorous and complete description of the signatures of functions. If the functions do not throw exceptions, you can use the signature and type system as documentation. You can also use the type system to create a Domain Model and a description of Business Rules. In this way, you can ensure that operations that are not valid in the real world will not be compiled in the application, which provides more reliable protection than unit tests. More information about this approach can be found in a separate article .
Functions as arguments
image

Hardcoded data is considered a bad form in programming, instead we pass them as parameters (method arguments). In the FP, we move on. Why not parametrize and behavior?

image

Instead of a function with one argument, we describe a function with two. Now it does not matter what this list is and where we output the data (to the console or to the log).

let printList anAction aList =
for i in aList do
anAction i
Let's go further. Consider an imperative example in C #. Obviously, in this code there is a duplication (identical cycles). In order to eliminate duplication it is necessary to allocate the general and to allocate the general in function:

<code lang="cs">public static int Product(int n)
{
    int product = 1; // initialize
    for (int i = 1; i <= n; i ++) // loop
{
        product * = i; // action
}

    return product; // return value
}

public static int Sum(int n)
{
    int sum = 0; // initialize
    for (int i = 1; i <= n; i ++) // loop
{
sum += i;
}

    return sum; // return value
} </code>
In F #, there is already a fold function for working with sequences:

let product n =
let initialValue = 1
let action productSoFar x = productSoFar * x

[1..n] |> List.fold action initialValue

let sum n =
let initialValue = 0
let action sumSoFar x = sumSoFar+x

[1..n] |> List.fold action initialValue
But, excuse me, in C # there is Agregate, which does the same! Congratulations, LINQ is written in a functional style :)
<blockquote> I recommend the Eric Lippert article series on monads in C # . With the tenth part the explanation of the "monadic" nature of SelectMany
Functions as interfaces
Suppose we have an interface.

<code lang="cs">interface IBunchOfStuff
{
int DoSomething(int x);
    string DoSomethingElse (int x); // one interface is one thing
    void DoAThirdThing (string x); // need to separate
}
</code>
If we take SRP and ISP and raise them to the absolute, all interfaces will contain only one function.

<code lang="cs">interface IBunchOfStuff
{
int DoSomething(int x);
}
</code>
Then it's just a function of int -> int. In F #, you do not need to declare an interface to make functions interchangeable, they are interchangeable "out of the box" simply by their signature. Thus, the pattern "let DoSomethingWithStuff strategy x =
strategy x The pattern "<a href =" https://en.wikipedia.org/wiki/%D0%94%D0%B5%D0%BA%D0%BE%D1%80%D0%B0%D1%82%D0% BE% D1% 80 _ (% D1% 88% D0% B0% D0% B1% D0% BB% D0% BE% D0% BD_% D0% BF% D1% 80% D0% BE% D0% B5% D0% BA % D1% 82% D0% B8% D1% 80% D0% BE% D0% B2% D0% B0% D0% BD% D0% B8% D1% 8F) " rel=""> The decorator
" is implemented using the composition of functions
image
let isEvenWithLogging = log >> isEven >> log // int -> bool
Here the author omits the questions of semantics for simplicity of presentation. When modeling real object models of one signature, the function is not always sufficient. <Tgsrbq>
Correcting and partial application
So, using only one composition, we can design entire applications. Bad news: the composition works only with functions from one parameter . Good news: in <b> all functions are functions of one parameter.

image

Note that the signature int -> int -> int does not contain parentheses by any chance. You can treat addition as a function of two arguments of type int, which returns a value of type int or as a function of one argument, returning a functional type int -> int. The return function will be called the adder on the basis of n, where n is the number passed by the argument to the first function. Repeating this operation recursively it is possible to convert a function from any number of arguments into functions from one argument.

<blockquote> Such transformations are possible not only for compiled functions in programming, but also for mathematical functions. The possibility of such a transformation was first noted in the works of Gottlob Frege, systematically studied by Moses Sheinfinkel in the 1920s, and the name was given by Haskella Curry, the developer of combinatorial logic, in which the reduction to the functions of one argument is fundamental. <Tgsrbq>
The ability to convert functions from many arguments to a function from one argument is natural for functional APIs, so the compiler will not mind if you pass only one value to calculate the sum.

let three = 1 + 2
let three = (+) 1 2
let three = ((+) 1) 2
let add1 = (+) 1
let three = add1 2
This is called partial application. In functional AP, partial application of replaces the principle of injecting dependencies (Dependency Injection )

// this function requires dependency
let getCustomerFromDatabase connection (customerId:CustomerId) =
from connection
select customer
where customerId = customerId

// and this one is gone
let getCustomer1 = getCustomerFromDatabase myConnection
Continuations
Often, the solutions that are put into the implementation are not flexible enough. Let's return to the example with division. Who said I want the function to throw exceptions? Maybe I should be better " special case "

<code lang="cs">int Divide(int top, int bottom)
{
if (bottom == 0)
{
        // who decided that you need to throw an exception?
throw new InvalidOperationException("div by 0");
}
else
{
return top/bottom;
}
}
</code>
Instead of solving for the user, we can provide a solution to him:

<code lang="cs">void Divide(int top, int bottom, Action ifZero, Action<int> ifSuccess)
{
if (bottom == 0)
{
ifZero();
}
else
{
ifSuccess( top/bottom );
}
}
</code>
If you've ever written an asynchronous code, you're probably familiar with the "Pyramid of Doom"

image

Extensions allow you to fix this code and get rid of nesting levels. For this it is necessary to encapsulate a conditional transfer to a function:

let ifSomeDo f opt =
if opt.IsSome then
f opt.Value
else
None
And rewrite the code using the continuations

let example input =
doSomething input
|> ifSomeDo doSomethingElse
|> ifSomeDo doAThirdThing
|> ifSomeDo (fun z -> Some z)
Monads
Monads - this is one of the "terrible" words of the OP. First of all, due to the fact that usually explanations begin with the category theory . The second - because of the fact that the "monad" - this is a very abstract concept, which does not have a direct analogy with the objects of the real world. I'm a big supporter of the "from private to general" approach. Having understood the practical use of a concrete example, it is easier to move on to a more complete and abstract definition.

image

Knowing about the "continuations", let's return to the analogy with the rails and the tunnel. The function in which the argument is passed and the two "extensions" can be represented as a fork.
But such functions are not linked: (
image
The function bind
image
let bind nextFunction optionInput =
match optionInput with
    // pass the result of execution of the previous function in case of success
| Some s -> nextFunction s
    // or just throw the value of None further
| None -> None
The code of the death pyramid can be rewritten with the help of bind

// it was
let example input =
let x = doSomething input
if x.IsSome then
let y = doSomethingElse (x.Value)
if y.IsSome then
let z = doAThirdThing (y.Value)
if z.IsSome then
let result = z.Value
Some result
else
None
else
None
else
None

// became
let bind f opt =
match opt with
| Some v -> f v
| None -> None

let example input =
doSomething input
|> bind doSomethingElse
|> bind doAThirdThing
|> bind (fun z -> Some z)
By the way, this is called "monadic bind". Tell your friends, lovers of Haskell, that you know what "monadic bind" is and you will be accepted into a secret society :)

Bind can be used to concatenate asynchronous operations ( promises in JS are arranged just like this)

image
Bind for error handling
<blockquote> If you have a vague feeling that the description of the monoid Either goes on, so it is
Consider the code in C #. He looks pretty good: everything is brief and understandable. However, there is no error handling in it. Indeed, what can go wrong?

<code lang="cs">string UpdateCustomerWithErrorHandling()
{
var request = receiveRequest();
validateRequest(request);
canonicalizeEmail(request);
db.updateDbFromRequest(request);
smtpServer.sendEmail(request.Email)
return "OK";
} </code>
We all know that you need to process errors. Let's add processing.

<code lang="cs">string UpdateCustomerWithErrorHandling()
{
var request = receiveRequest();
var isValidated = validateRequest(request);
if (!isValidated)
{
return "Request is not valid"
}

canonicalizeEmail(request);
try
{
var result = db.updateDbFromRequest(request);
if (!result)
{
return "Customer record not found"
}
}
catch
{
return "DB error: Customer record not updated"
}

if (!smtpServer.sendEmail(request.Email))
{
log.Error "Customer email not sent"
}

return "OK";
} </code>
Instead of six understandable now 18 not understandable lines. This is 200% extra lines of code. In addition, the linear logic of the method is now noisy with branching and early outputs.

Using bind, you can abstract the error handling logic. This is how the method will look without error handling, if it is rewritten to F #:
image
And here this code but already with error handling :
image

For more details, see this separate report .
The functors
I did not really like the description of functors in Scott. Read the article " functors, applicative functors and monads in pictures "
Monoids
Unfortunately, simple analogies are not suitable for explaining monoids. Get ready for math.
image
I warned, so, the math

1 + 2 = 3
1 + (2 + 3) = (1 + 2) + 3
1 + 0 = 1
0 + 1 = 1
And a little more

2 * 3 = 6
2 * (3 * 4) = (2 * 3) * 4
1 * 2 = 2
2 * 1 = 2
What do these examples have in common?

There are some objects, in this case numbers, and the way they interact. And the result of interaction is also a number (closed).
The order of interaction is not important (associativity).
In addition, there is some special element, the interaction with which does not change the original object (the neutral element).

<blockquote> For a more stringent definition, refer to Wikipedia . The article discusses only a few examples of the use of monoids in practice. <Tgsrbq>
Closed
Allows you to switch from pairwise operations to operations on lists

1 * 2 * 3 * 4
[ 1; 2; 3; 4 ] |> List.reduce (*)
Associativity
The application of the principle of "divide and conquer", "freebie" parallelization. If our processor has 2 cores and we need to calculate the value1 + 2 + 3 + 4. We can calculate 1 + 2 on the first core, a3 + 4 on the second, and add the result. More consecutive calculations - more cores.
The neutral element
Creduce has several problems: what to do with empty lists? What if we have an odd number of elements? Correctly, add a neutral element to the list.
<blockquote> By the way, in mathematics there is often a definition of a monoid as of the semigroup with the neutral element. If there is no neutral element, then you can try to define it in order to take advantage of the monoid. <Tgsrbq>
Map / Reduce
If your objects are not monoids, try to convert them. The famous distributed computing model Google is nothing more than the exploitation of monoids.

image
Papay 17 october 2017, 14:37
Vote for this post
Bring it to the Main Page
 

Comments

Leave a Reply

B
I
U
S
Help
Avaible tags
  • <b>...</b>highlighting important text on the page in bold
  • <i>..</i>highlighting important text on the page in italic
  • <u>...</u>allocated with tag <u> text shownas underlined
  • <s>...</s>allocated with tag <s> text shown as strikethrough
  • <sup>...</sup>, <sub>...</sub>text in the tag <sup> appears as a superscript, <sub> - subscript
  • <blockquote>...</blockquote>For  highlight citation, use the tag <blockquote>
  • <code lang="lang">...</code>highlighting the program code (supported by bash, cpp, cs, css, xml, html, java, javascript, lisp, lua, php, perl, python, ruby, sql, scala, text)
  • <a href="http://...">...</a>link, specify the desired Internet address in the href attribute
  • <img src="http://..." alt="text" />specify the full path of image in the src attribute