Доброго времени суток, Хабражители!
В своей первой статье я бы хотел рассказать про такую интересную штуку, как комбинáторная библиотека (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++» и «Вычисление производных с помощью шаблонов на С++», надеюсь что моя не станет лишней и хабражители воспримут её с интересом.
Просьба про грамматические и орфографические ошибки писать в личку.