C # combinator library
Good day, Habrazhiteli!
In my first article I would like to tell you about such an interesting thing as the Combinator library. I will try to make all the arguments as simple and clear as possible.
In fact, not a problem, but simply the desire to write something interesting. And I decided to write a system for finding derivatives of functions (the article echoes the articles Dynamic Mathematical Functions in C ++ and the Calculation of Derivatives Using C ++ Templates , but I decided to publish it because I hope to shed light on The problem is somewhat different, and all the examples will be in c #, not c ++).
Actually there was no desire to take anything ready , all the more then the meaning of the whole undertaking would be lost. And an idea was born, unusual for my inexperienced mind, the implementation of which I started. A little later, accidentally reading about such a functional programming pattern as the “Combinatorial Library”, I realized that it was him who implemented it. So what is it?
Combinatorial library - a set of related entities that are divided into primitives and combinators.
Also for a set of entities, the closure property must be satisfied:
"Compound entities should not differ in terms of use from primitives."
Let's look at the example of mathematical functions and their derivatives.
First, we define a set of primitives.
Primitives, in this context, should make the simplest functions (choose a few to your taste):
And for the task of combinators suitable such well-known operations such as: addition, multiplication, subtraction and division.
')
For all primitives, we define the derivatives themselves. Next, we describe the combinators.
Consider the combinator "addition of functions."
If the derivative of the function f and the derivative of the function g are known, then it is easy to find the derivative of the sum of these two functions: (f + g) '= f' + g '.
That is, we form the rule: the derivative of the sum of functions is the sum of their derivatives.
Similarly, we define the other combinators.
Okay, like America has not yet opened, it remains to figure out how to express it in code.
The key class of the whole system will be the abstract class Function :
Everything is simple, the function should “be able to count” its value at the point x, as well as “know” its derivative.
Next, we implement the functions we have chosen.
First constant:
And a linear function, or rather its simplest form: f (x) = x. In mathematics, this mapping is called the identity, so the class is called “Identity” .
Already here one can notice the connection between these two classes, namely, the derivative of the identity function is a constant 1.
Let's now define a class for combinators. Because of its closed nature, it must be able to do everything the same as primitives, so it is logical to inherit it from the Function class.
Let's call this class Operator and make it also abstract.
And also, for example, we define the combinator "multiplication", the rest are determined in the same way.
I hope everything is clear, we explicitly described the rule for constructing a function by multiplying one function by the second.
To find the value of such a function at x, it is necessary to find the value of one at x, then the second, and then multiply these values.
The derivative of the product of two functions is defined as: (f * g) '= f' * g + g '* f. Proof :)
In the code, we wrote one to one what was spoken about in words.
Cool? Yes, I think so!
Similarly, we define an addition combinator - Addition class, I will not give it in this article, it almost repeats the code for multiplication.
Let's now try using these methods to write the function f (x) = 2x + 3.
Wow, how cool!
Not really cool. I would shoot myself if for any, even the simplest of functions, I would have to write something like that. Fortunately, C # syntax sugar will help us.
We add the following methods to the Function class.
What does this give us? And the fact that now instead of:
We define similar operators for the remaining operations (*, +, -).
Now, in order not to create a new function object each time, we will write a static class in which we place some frequently used functions. I called this class Funcs .
I also defined a couple more functions, such as sine, cosine and exponent. Here's what happened:
As you can see, I defined the last 6 functions as combinations of “primitive functions”.
Now you can try again to determine the function f (x) = 2x + 3.
Well, how? In my opinion, using such a system has become much easier.
What are the pros and cons of this approach?
The obvious advantage is extensibility. Indeed, it will not be difficult to add its own function, for example, logarithmic, and through the derivative be included in the general system of classes.
The disadvantage is the rapid expansion of the function while finding the derivative, for example, for the function f (x) = x ^ 100 (x to the power of 100) finding 10 derivative is a very time-consuming operation - I did not have the patience to wait for its completion.
About combinatorial libraries . I offer the article under the link to anyone interested in functional programming, first of all, to those who have come across it before - it tells about the main approaches in the OP, examples are given. IMHO, the article is written correctly and interestingly written - it is a pleasure to read.
Project on githaba . If you are interested in the article, you can download the project sources from the github, the Combination of Functions combinator is still implemented there, piecewise-defined functions are added, the simplest integration of functions and some optimizations are written - in general, everything that didn't fit into the article
PS While I was preparing this article on Habré 2 more appeared on similar topics: “Dynamic mat. functions in C ++ " and " Calculation of derivatives using templates in C ++ " , I hope that mine will not be superfluous and habrazhiteli will take it with interest.
Request for grammar and spelling errors to write in a personal.
In my first article I would like to tell you about such an interesting thing as the Combinator library. I will try to make all the arguments as simple and clear as possible.
Problem
In fact, not a problem, but simply the desire to write something interesting. And I decided to write a system for finding derivatives of functions (the article echoes the articles Dynamic Mathematical Functions in C ++ and the Calculation of Derivatives Using C ++ Templates , but I decided to publish it because I hope to shed light on The problem is somewhat different, and all the examples will be in c #, not c ++).
Actually there was no desire to take anything ready , all the more then the meaning of the whole undertaking would be lost. And an idea was born, unusual for my inexperienced mind, the implementation of which I started. A little later, accidentally reading about such a functional programming pattern as the “Combinatorial Library”, I realized that it was him who implemented it. So what is it?
What it is?
Combinatorial library - a set of related entities that are divided into primitives and combinators.
- Primitives - basic, simple, indivisible entities.
- Combinators are ways to combine entities into more complex ones.
Also for a set of entities, the closure property must be satisfied:
"Compound entities should not differ in terms of use from primitives."
Sounds pretty abstract?
Let's look at the example of mathematical functions and their derivatives.
First, we define a set of primitives.
Primitives, in this context, should make the simplest functions (choose a few to your taste):
- Linear function
- Constant
And for the task of combinators suitable such well-known operations such as: addition, multiplication, subtraction and division.
')
How it works?
For all primitives, we define the derivatives themselves. Next, we describe the combinators.
Consider the combinator "addition of functions."
If the derivative of the function f and the derivative of the function g are known, then it is easy to find the derivative of the sum of these two functions: (f + g) '= f' + g '.
That is, we form the rule: the derivative of the sum of functions is the sum of their derivatives.
Similarly, we define the other combinators.
Okay, like America has not yet opened, it remains to figure out how to express it in code.
Practice
The key class of the whole system will be the abstract class Function :
public abstract class Function { public abstract double Calc(double x); public abstract Function Derivative(); } Everything is simple, the function should “be able to count” its value at the point x, as well as “know” its derivative.
Next, we implement the functions we have chosen.
First constant:
public class Constant : Function { public Constant(double val) { value = val; } public override double Calc(double val) { return value; } public override Function Derivative() { return new Constant(0); } private readonly double value; }
And a linear function, or rather its simplest form: f (x) = x. In mathematics, this mapping is called the identity, so the class is called “Identity” .
public class Identity : Function { public override double Calc(double val) { return val; } public override Function Derivative() { return new Constant(1); } }
Already here one can notice the connection between these two classes, namely, the derivative of the identity function is a constant 1.
Let's now define a class for combinators. Because of its closed nature, it must be able to do everything the same as primitives, so it is logical to inherit it from the Function class.
Let's call this class Operator and make it also abstract.
public abstract class Operator : Function { protected Operator(Function a, Function b) { leftFunc = a; rightFunc = b; } protected readonly Function leftFunc; protected readonly Function rightFunc; }
And also, for example, we define the combinator "multiplication", the rest are determined in the same way.
public class Multiplication : Operator { public Multiplication(Function a, Function b) : base(a, b) { } public override double Calc(double val) { return leftFunc.Calc(val) * rightFunc.Calc(val); } public override Function Derivative() { return leftFunc.Derivative() * rightFunc + leftFunc * rightFunc.Derivative(); } }
I hope everything is clear, we explicitly described the rule for constructing a function by multiplying one function by the second.
To find the value of such a function at x, it is necessary to find the value of one at x, then the second, and then multiply these values.
The derivative of the product of two functions is defined as: (f * g) '= f' * g + g '* f. Proof :)
In the code, we wrote one to one what was spoken about in words.
Cool? Yes, I think so!
Similarly, we define an addition combinator - Addition class, I will not give it in this article, it almost repeats the code for multiplication.
Let's now try using these methods to write the function f (x) = 2x + 3.
var f = new Addition(new Multiplication(new Constant(2), new Identity()), new Constant(3)); var x = f.Calc(2) // x 7 var y = f.Derivative().Calc(2) // 2
Wow, how cool!
Dessert
Not really cool. I would shoot myself if for any, even the simplest of functions, I would have to write something like that. Fortunately, C # syntax sugar will help us.
We add the following methods to the Function class.
public static Function operator +(Function a, Function b) { return new Addition(a, b); } public static Function operator +(double k, Function b) { return new Constant(k) + b; }
What does this give us? And the fact that now instead of:
new Addition(new Constant(2), new Identity()) You can write this:
2 + new Identity() Looks a little better already.
We define similar operators for the remaining operations (*, +, -).
Now, in order not to create a new function object each time, we will write a static class in which we place some frequently used functions. I called this class Funcs .
I also defined a couple more functions, such as sine, cosine and exponent. Here's what happened:
public static class Funcs { public static readonly Function Id = new Identity(); public static readonly Function Exp = new Exponenta(); public static readonly Function Zero = new Constant(0); public static readonly Function Sin = new Sinus(); public static readonly Function Cos = new Cosinus(); public static readonly Function Tan = Sin / Cos; public static readonly Function Ctg = Cos / Sin; public static readonly Function Sh = (Exp - 1 / Exp) / 2; public static readonly Function Ch = (Exp + 1 / Exp) / 2; public static readonly Function Tgh = Sh / Ch; public static readonly Function Cth = Sh / Ch; }
As you can see, I defined the last 6 functions as combinations of “primitive functions”.
Now you can try again to determine the function f (x) = 2x + 3.
var f = 2 * Funcs.Id + 3; var x = f.Calc(2) // x 7 var y = f.Derivative().Calc(2) // 2
Well, how? In my opinion, using such a system has become much easier.
Conclusion
What are the pros and cons of this approach?
The obvious advantage is extensibility. Indeed, it will not be difficult to add its own function, for example, logarithmic, and through the derivative be included in the general system of classes.
The disadvantage is the rapid expansion of the function while finding the derivative, for example, for the function f (x) = x ^ 100 (x to the power of 100) finding 10 derivative is a very time-consuming operation - I did not have the patience to wait for its completion.
Links
About combinatorial libraries . I offer the article under the link to anyone interested in functional programming, first of all, to those who have come across it before - it tells about the main approaches in the OP, examples are given. IMHO, the article is written correctly and interestingly written - it is a pleasure to read.
Project on githaba . If you are interested in the article, you can download the project sources from the github, the Combination of Functions combinator is still implemented there, piecewise-defined functions are added, the simplest integration of functions and some optimizations are written - in general, everything that didn't fit into the article
PS While I was preparing this article on Habré 2 more appeared on similar topics: “Dynamic mat. functions in C ++ " and " Calculation of derivatives using templates in C ++ " , I hope that mine will not be superfluous and habrazhiteli will take it with interest.
Request for grammar and spelling errors to write in a personal.
Source: https://habr.com/ru/post/149630/
All Articles