Абстрактная алгебра в действии11.03.2022 00:31

В последнее время всё чаще я ощущаю математическое веяние в программировании. Нет, это не про интегралы с производными, а про что-то абстрактное, другое. Про то, что было всегда у нас под носом, но оставалось незамеченным. Наступит день — про это будут говорить на каждом углу. Но не сегодня. Сегодня мы с этим познакомимся.

Я думаю, многие из нас были студентами технических ВУЗов и посещали большое количество математических дисциплин, возможно, задаваясь вопросом «зачем». Одной из таких дисциплин, быть может, была алгебра. Нет, это не та книжка Мордковича, переполненная скучными задачами про многочлены и уравнения. Это сложная, объёмная наука с высоким порогом входа, которая требует огромной вовлечённости и погружения. Однако, захватывающая и интересная. Основным предметом этой науки являются так называемые алгебраические структуры. И основной интерес заключается в том, что эти структуры можно строить практически где угодно и из чего угодно. Оказывается, своё применение они могут найти и в создании новых подходов к написанию кода. Прежде чем поговорим о них, небольшое алгебраическое отступление.

Небольшое алгебраическое отступление

Сейчас мы едва коснёмся абстрактной алгебры. Затронем только основную аксиоматику и определения, которые дадут первоначальные представления о том, что вообще происходит. Здесь даже не будет теорем и доказательств.

Начнём с того, что у нас есть — некоторое произвольное множество. С понятием множества, надеюсь все знакомы. Как и с понятием отображения. Потому что отождествляя некоторое отображение $\circ : X \times X \to X$ вместе с нашим множеством, мы получаем алгебраическую структуру. То есть, алгебраическая структура — это пара $(X, \circ)$ из множества и замкнутой бинарной операции. Например, алгебраической структурой являются целые числа со сложением $(\mathbb{Z} , +)$ .

Вот тут начинается самое интересное. Очевидно, что весь сок заключается в задаваемых операциях. Именно они определяют структуру и поведение набора элементов. Конечно, нам не интересны какие-то случайные функции, поэтому нам нужно от них потребовать каких-то свойств. Иными словами, потребовать удовлетворения операции набору аксиом. Пойдём постепенно.

Например, первым естественным ограничением возьмём ассоциативность. Бинарная операция $\circ$ на множестве называется ассоциативной, если верно следующее:

$(a \circ b) \circ c = a \circ (b \circ c)$

При выполнении этой аксиомы $(X, \circ)$ уже становится полугруппой. Чем вообще полезны полугруппы? Если вдуматься в смысл ассоциативности, то это значит ровно то, что группировка для операции не важна, а значит «складывать» элементы полугруппы можно параллельно. При этом хотелось бы иметь возможность какие-то элементы игнорировать. Перейдём на следующий уровень строгости.

Элемент $e \in X$ называется единичным, если верно следующее:

$\exists ! \; e \in X : \forall x \in X \; e \circ x = x \circ e = x$

Наша полугруппа $(X, \circ)$ с единицей — уже моноид. Важно понимать, что в аксиоме не случайно два равенства: бывают единицы справа и единицы слева, но это совсем другая история.

Какие мы знаем моноиды? Опять же, целые числа — $(\mathbb{Z}, +,0), (\mathbb{Z}, *,1)$ . Но что мы всё про числа?

Моноиды на практике

Какие мы можем построить моноиды на практике?

— строки с конкантенацией;
$(List<T>, Concat (), \{\})» src=«https://habrastorage.org/getpro/habr/upload_files/5c4/289/60a/5c428960a6f613cacac18488b4f3d18b.svg» />— списки с операцией слияния списков; </p></li><li><p><img alt=$ — инты с максимизацией вместо сложения;
;

И так далее. Для начала, оформим полученные в отступлении знания в коде.

public interface ISemiGroup
{
    T Plus(T left, T right);
}

public interface IMonoid : ISemiGroup
{
    T Zero { get; }
}

Я не случайно обозвал операцию «плюсом», а единичный элемент «нулём», потому что (спойлер) в алгебре есть структуры с двумя операциями, как, например, кольцо, где «сложение» от «умножения» надо отличать. Но, не суть важно. Реализуем, например, полугруппу максимизации.

public class Max : ISemiGroup where T : IComparable
{
    public T Plus(T left, T right) =>
        left.CompareTo(right) > 0
            ? left
            : right;
}

И сделаем под это какую-нибудь dto-шку.

public record Person(string Name, int Money) : IComparable
{
    public int CompareTo(Person other) => Money.CompareTo(other.Money);
}

И вот тут появляется важная мысль. Я же не буду брать всего два человека и находить богатейшего. Нет. Мне надо обработать много людей. У меня список есть.

var people = new List
{
    new("Bob", 1000),
    new("Tim", 1239),
    new("Jeff", 2000000000)
};

То есть, мы структуры можем использовать для разного рода агрегаций например. Поэтому для полугруппы даже можно было бы написать такое расширение.

public static class SemiGroupExtension
{
    public static T Sum(this ISemiGroup semiGroup, IEnumerable elements) =>
        elements.Aggregate(semiGroup.Plus);
}

Ну тогда теперь очевидно, что надо делать.

var max = new Max();
var richest = max.Sum(people);

Магия! Но, какая-то примитивная магия. Пока что. Какая следующая популярная агрегация у нас есть? Среднее! Оказывается его вычисление можно распараллелить. Это не такая очевидная мысль, но если задуматься… Из чего оно складывается: из количества значений и их суммы. То есть эти два параметра нужно разделить и отслеживать. Тогда мы получим структуру аналогичную $(\mathbb{Z}^2,+,(0,0))$ . Оформим эту мысль.

public class AveragedValue
{
    private double _sum;
    private int _count;

    public AveragedValue() : this(0, 0)
    {
    }

    public AveragedValue(double sum, int count = 1)
    {
        _sum = sum;
        _count = count;
    }

    public double Get() => _sum / _count;

    public static AveragedValue operator +(AveragedValue av1, AveragedValue av2)
    {
        var newCount = av1._count + av2._count;
        var newSum = av1._sum + av2._sum;

        return new AveragedValue(newSum, newCount);
    }
}

public class Avg : IMonoid
{
    public AveragedValue Plus(AveragedValue left, AveragedValue right) => left + right;

    public AveragedValue Zero => new ();
}

Уже неплохо. Но какие-нибудь реальные задачи хотелось бы. И как раз про такую вспомнил. Надо было сделать текстовый фильтр для поля в таблице, но, вот незадача, условий было много и выходило что-то уродливое:

public bool Fits(string text) =>
    text ... ||
    text ... ||
    text ... ||
    ...;

А если заказчик захочет другой фильтр на другое поле? Или большей гибкости фильтра? Не хочется плодить что-то в стиле average javascript enjoyer, поэтому посмотрим на задачу под другим углом. Фильтр, вообще говоря, это предикат, то есть булева функция, или, строго говоря, отображение из заданного типа в множество логических значений. И если «складывать» предикаты логическим ИЛИ, то мы получим моноид!

public class Any : IMonoid>
{
    public Predicate Zero => _ => false;

    public Predicate Plus(Predicate left, Predicate right) =>
        x => left(x) || right(x);
}

Тогда, например, можно написать что-то такое. Всё разнести по сервисам, контейнерам и будет красиво.

var predicates = new List>
{
    x => x >= '0' && x <= '9',
    x => x >= 'A' && x <= 'Z',
    x => x >= 'a' && x <= 'z'
};
var anyMonoid = new Any();
var digitOrLetter = anyMonoid.Sum(predicates);

Вообще, мы можем построить более интересный моноид на словарях и операции слияния. Однако, установим, что значения словаря образуют хотя бы полугруппу, поскольку конфликт будет разрешаться сложением элементов. Тогда, получится что-то вроде этого.

public class MapMonoid : IMonoid>
{
    private readonly ISemiGroup _valueSemiGroup;

    public MapMonoid(ISemiGroup valueSemiGroup)
    {
        _valueSemiGroup = valueSemiGroup;
    }
    
    public Dictionary Zero => new();
    
    public Dictionary Plus(Dictionary left, Dictionary right)
    {
        var result = Zero;
        foreach (var (key, value) in left.Concat(right))
        {
            result[key] = result.ContainsKey(key)
                ? _valueSemiGroup.Plus(result[key], value)
                : value;
        }
        
        return result;
    }
}

Как это использовать? Например, у нас есть список строк.

var strings = new List {"foo", "foo", "foo", "bar", "bar", "baz", "pipi", "pupu"};

Мы можем с помощью него например сгруппировать строки по их числу вхождений или найти слова одинаковой длины. Или что-нибудь, что вы придумаете.

var dicts = strings
    .Select(x => new Dictionary {{x, 1}});
var anotherDicts = strings
    .Select(x => new Dictionary>
    {
        {x.Length, new List {x}}
    });

После суммирования с помощью соответствующих полугрупп (числа со сложением, списки с соединением) получим такой вывод.

Итого

Существует огромное количество различных алгебраических структур. Их свойства помогают решать задачи компьютерных наук лаконичным, а может даже и эффективным способом. Про более неочевидные вещи могу написать в ещё одной статье. Мы задействовали только определения, а какой прорыв случится, когда в ход пойдут теоремы, боюсь представить. Когда-нибудь, программисты перестанут говорить: «Математика не нужна».