- PVSM.RU - https://www.pvsm.ru -

Комбинаторная библиотека на C#

Доброго времени суток, читатели!
В своей первой статье я бы хотел рассказать про такую интересную штуку, как комбинáторная библиотека (Combinator library). Все рассуждения постараюсь сделать максимально простыми и понятными.

Проблема

На самом деле не проблема, а попросту желание чего-нибудь интересного написать. А написать я решил систему для нахождения производных функций (статья несколько перекликается со статьями «Динамические мат. функции в C++» [1] и «Вычисление производных с помощью шаблонов на С++» [2], но я все же решил опубликовать её, так как надеюсь пролить свет на проблему несколько с другой стороны, да и все примеры будут на c#, а не на c++).
Собственно желания брать что-нибудь готовое [3] не было никакого, тем более тогда терялся бы смысл всей затеи. И родилась идея, необычная для моего неопытного ума, реализацией которой я и занялся. Чуть позже, случайно прочитав про такой паттерн функционального программирования как «Комбинаторная библиотека», я понял что именно его и реализовал. Итак, что же это такое?

Что это такое?

Комбинаторная библиотека — набор связанных сущностей, которые разделяют на примитивы и комбинаторы.

  • Примитивы — базовые, простейшие, неделимые сущности.
  • Комбинаторы — способы комбинирования сущностей в более сложные.

Так же для набора сущностей должно выполняться свойство замыкания:
«Составные сущности не должны ничем отличаться с точки зрения использования от примитивов».

Звучит довольно абстрактно?

Давайте разбираться на примере математических функций и их производных.
Для начала определим набор примитивов.
Примитивами, в данном контексте, следует сделать простейшие функции (выберу несколько на свой вкус):

  • Линейная функция
  • Константа

А для задания комбинаторов подойдут такие всем известные операции, как: сложение, умножение, вычитание и деление.

Как это работает?

Для всех примитивов определим производные сами. Далее опишем комбинаторы.
Рассмотрим комбинатор «сложение функций».
Если известна производная функции 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» [4].

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. Пруф:) [5]
В коде мы записали один в один то, о чем говорили на словах.
Круто? По моему, да!

Аналогично определим комбинатор сложения — класс 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 производной очень затратная по времени операция — дождаться её завершения у меня терпения не хватило.

Ссылки

Про комбинаторные библиотеки [6]. Статью по ссылке я предлагаю всем интересующимся функциональным программированием, в первую очередь тем, кто с ним раньше сталкивался — в ней рассказано про основные подходы в ФП, приведены примеры. ИМХО, статья грамотно составлена и интересно написана — читать одно удовольствие.

Проект на гитхабе [7]. Если вы заинтересовались статьей, можете скачать исходники проекта с гитхаба, там еще реализован комбинатор «Композиция функций», добавлены кусочно-заданные функции, написано простейшее интегрирование функций и некоторые оптимизации — в общем все, что не влезло в статью

P.S. Пока я готовил эту статью на хабре появилось еще 2 на подобные темы: «Динамические мат. функции в C++» [1] и «Вычисление производных с помощью шаблонов на С++» [2], надеюсь что моя не станет лишней и читатели воспримут её с интересом.
Просьба про грамматические и орфографические ошибки писать в личку.

Автор: semens


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/programmirovanie/13196

Ссылки в тексте:

[1] «Динамические мат. функции в C++»: http://habrahabr.ru/post/149450/

[2] «Вычисление производных с помощью шаблонов на С++»: http://habrahabr.ru/post/149470/

[3] что-нибудь готовое: http://ru.wikipedia.org/wiki/Mathematica

[4] «Identity»: http://en.wikipedia.org/wiki/Identity_function

[5] Пруф:): http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%BE%D0%B4%D0%BD%D0%B0%D1%8F_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8#.D0.9F.D1.80.D0.B0.D0.B2.D0.B8.D0.BB.D0.B0_.D0.B4.D0.B8.D1.84.D1.84.D0.B5.D1.80.D0.B5.D0.BD.D1.86.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D1.8F

[6] Про комбинаторные библиотеки: http://fprog.ru/2009/issue3/eugene-kirpichov-elements-of-functional-languages/#combinatorlibrary

[7] Проект на гитхабе: https://github.com/semens/Functions