Доброго времени суток, читатели!
В своей первой статье я бы хотел рассказать про такую интересную штуку, как комбинáторная библиотека (Combinator library). Все рассуждения постараюсь сделать максимально простыми и понятными.
Проблема
На самом деле не проблема, а попросту желание чего-нибудь интересного написать. А написать я решил систему для нахождения производных функций (статья несколько перекликается со статьями «Динамические мат. функции в C++» и «Вычисление производных с помощью шаблонов на С++», но я все же решил опубликовать её, так как надеюсь пролить свет на проблему несколько с другой стороны, да и все примеры будут на c#, а не на c++).
Собственно желания брать что-нибудь готовое не было никакого, тем более тогда терялся бы смысл всей затеи. И родилась идея, необычная для моего неопытного ума, реализацией которой я и занялся. Чуть позже, случайно прочитав про такой паттерн функционального программирования как «Комбинаторная библиотека», я понял что именно его и реализовал. Итак, что же это такое?
Что это такое?
Комбинаторная библиотека — набор связанных сущностей, которые разделяют на примитивы и комбинаторы.
- Примитивы — базовые, простейшие, неделимые сущности.
- Комбинаторы — способы комбинирования сущностей в более сложные.
Так же для набора сущностей должно выполняться свойство замыкания:
«Составные сущности не должны ничем отличаться с точки зрения использования от примитивов».
Звучит довольно абстрактно?
Давайте разбираться на примере математических функций и их производных.
Для начала определим набор примитивов.
Примитивами, в данном контексте, следует сделать простейшие функции (выберу несколько на свой вкус):
- Линейная функция
- Константа
А для задания комбинаторов подойдут такие всем известные операции, как: сложение, умножение, вычитание и деление.
Как это работает?
Для всех примитивов определим производные сами. Далее опишем комбинаторы.
Рассмотрим комбинатор «сложение функций».
Если известна производная функции f и производная функции g, то несложно найти производную суммы двух этих функций: (f + g)' = f' + g'.
То есть мы формируем правило: производная суммы функций — есть сумма их производных.
Аналогично определим и остальные комбинаторы.
Окей, вроде Америку пока не открыли, осталось разобраться, как же это выразить в коде.
Практика
Ключевым классом всей системы будет абстрактный класс Function:
public abstract class Function
{
public abstract double Calc(double x);
public abstract Function Derivative();
}
Всё просто, функция должна «уметь считать» свое значение в точке x, а также «знать» свою производную.
Далее, реализуем выбранные нами функции.
Сначала константу:
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;
}
И линейнуй функцию, а точнее простейший её вид: f(x) = x. В математике такое отображение называется тождественным, поэтому класс назовем «Identity».
public class Identity : Function
{
public override double Calc(double val)
{
return val;
}
public override Function Derivative()
{
return new Constant(1);
}
}
Уже тут можно заметить связь этих двух классов, а именно — производная тождественной функции есть константа 1.
Давайте теперь определим класс для комбинаторов. Из-за свойства замкнутости он должен уметь делать все тоже, что и примитивы, поэтому логично унаследовать его от класса Function.
Назовем этот класс Operator и сделаем его также абстрактным.
public abstract class Operator : Function
{
protected Operator(Function a, Function b)
{
leftFunc = a;
rightFunc = b;
}
protected readonly Function leftFunc;
protected readonly Function rightFunc;
}
А также, для примера, определим комбинатор «умножение», остальные определяются аналогично.
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();
}
}
Надеюсь, все понятно, мы в явном виде описали правило построения функции методом умножения одной функции на вторую.
Чтобы найти значение такой функции в точке х, надо найти значение одной в точке х, затем второй, а потом перемножить эти значения.
Производная произведения двух функций определяется так: (f * g)' = f' * g + g' * f. Пруф:)
В коде мы записали один в один то, о чем говорили на словах.
Круто? По моему, да!
Аналогично определим комбинатор сложения — класс Addition, код его в данной статье приводить не буду, он почти полностью повторяет код для умножения.
Давайте теперь попробуем с помощью данных методов записать функцию 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
Вау, как круто!
Десерт
На самом деле не круто. Я бы застрелился, если бы для любой, даже самой простой функции, мне приходилось бы писать нечто подобное. К счастью, нам поможет синтаксический сахар С#.
Допишем в класс Function следующие методы.
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;
}
Что нам это дает? А то, что теперь вместо:
new Addition(new Constant(2), new Identity())
можно написать так:
2 + new Identity()
Выглядит уже немножко получше.
Определим подобные операторы для остальных операций (*, +, -).
Теперь для того чтобы каждый раз не создавать новый объект функции, напишем статический класс, в который поместим некоторые часто используемый функции. Этот класс я назвал Funcs.
Также я определил еще пару функций, таких как синус, косинус и экспонента. Вот что получилось:
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;
}
Как видите, последние 6 функций я определил как комбинации «примитивных функций».
Теперь можно попробовать еще раз определить функцию f(x) = 2x + 3.
var f = 2 * Funcs.Id + 3;
var x = f.Calc(2) // x будет равно 7
var y = f.Derivative().Calc(2) // у будет равно 2
Ну как? По моему пользоваться такой системой стало намного проще.
Заключение
Какие плюсы и минусы у такого подхода?
Явным плюсом является расширяемость. Действительно, не составит труда дописать свою функцию, к примеру — логарифмическую, и через производную включить в общую систему классов.
К минусам относится быстрое разрастание функции при нахождении производной, к примеру для функции f(x) = x ^ 100 (х в степени 100) нахождение 10 производной очень затратная по времени операция — дождаться её завершения у меня терпения не хватило.
Ссылки
Про комбинаторные библиотеки. Статью по ссылке я предлагаю всем интересующимся функциональным программированием, в первую очередь тем, кто с ним раньше сталкивался — в ней рассказано про основные подходы в ФП, приведены примеры. ИМХО, статья грамотно составлена и интересно написана — читать одно удовольствие.
Проект на гитхабе. Если вы заинтересовались статьей, можете скачать исходники проекта с гитхаба, там еще реализован комбинатор «Композиция функций», добавлены кусочно-заданные функции, написано простейшее интегрирование функций и некоторые оптимизации — в общем все, что не влезло в статью
P.S. Пока я готовил эту статью на хабре появилось еще 2 на подобные темы: «Динамические мат. функции в C++» и «Вычисление производных с помощью шаблонов на С++», надеюсь что моя не станет лишней и читатели воспримут её с интересом.
Просьба про грамматические и орфографические ошибки писать в личку.
Автор: semens
