В последнее время всё чаще я ощущаю математическое веяние в программировании. Нет, это не про интегралы с производными, а про что-то абстрактное, другое. Про то, что было всегда у нас под носом, но оставалось незамеченным. Наступит день - про это будут говорить на каждом углу. Но не сегодня. Сегодня мы с этим познакомимся.
Я думаю, многие из нас были студентами технических ВУЗов и посещали большое количество математических дисциплин, возможно, задаваясь вопросом "зачем". Одной из таких дисциплин, быть может, была алгебра. Нет, это не та книжка Мордковича, переполненная скучными задачами про многочлены и уравнения. Это сложная, объёмная наука с высоким порогом входа, которая требует огромной вовлечённости и погружения. Однако, захватывающая и интересная. Основным предметом этой науки являются так называемые алгебраические структуры. И основной интерес заключается в том, что эти структуры можно строить практически где угодно и из чего угодно. Оказывается, своё применение они могут найти и в создании новых подходов к написанию кода. Прежде чем поговорим о них, небольшое алгебраическое отступление.
Небольшое алгебраическое отступление
Сейчас мы едва коснёмся абстрактной алгебры. Затронем только основную аксиоматику и определения, которые дадут первоначальные представления о том, что вообще происходит. Здесь даже не будет теорем и доказательств.
Начнём с того, что у нас есть 
- некоторое произвольное множество. С понятием множества, надеюсь все знакомы. Как и с понятием отображения. Потому что отождествляя некоторое отображение 
вместе с нашим множеством, мы получаем алгебраическую структуру. То есть, алгебраическая структура - это пара 
из множества и замкнутой бинарной операции. Например, алгебраической структурой являются целые числа со сложением 
.
Вот тут начинается самое интересное. Очевидно, что весь сок заключается в задаваемых операциях. Именно они определяют структуру и поведение набора элементов. Конечно, нам не интересны какие-то случайные функции, поэтому нам нужно от них потребовать каких-то свойств. Иными словами, потребовать удовлетворения операции набору аксиом. Пойдём постепенно.
Например, первым естественным ограничением возьмём ассоциативность. Бинарная операция 
на множестве 
называется ассоциативной, если верно следующее:
При выполнении этой аксиомы 
уже становится полугруппой. Чем вообще полезны полугруппы? Если вдуматься в смысл ассоциативности, то это значит ровно то, что группировка для операции не важна, а значит "складывать" элементы полугруппы можно параллельно. При этом хотелось бы иметь возможность какие-то элементы игнорировать. Перейдём на следующий уровень строгости.
Элемент 
называется единичным, если верно следующее:
Наша полугруппа 
с единицей 
- уже моноид. Важно понимать, что в аксиоме не случайно два равенства: бывают единицы справа и единицы слева, но это совсем другая история.
Какие мы знаем моноиды? Опять же, целые числа - 
. Но что мы всё про числа?
Моноиды на практике
Какие мы можем построить моноиды на практике?
- строки с конкантенацией;
- списки с операцией слияния списков;
- инты с максимизацией вместо сложения;
;
И так далее. Для начала, оформим полученные в отступлении знания в коде.
public interface ISemiGroup<T>
{
T Plus(T left, T right);
}
public interface IMonoid<T> : ISemiGroup<T>
{
T Zero { get; }
}Update: Как правильно заметил @Googolplex, полученные интерфейсы это type classes. Это замечание привело к переосмыслению кода в статье и его доработке. Идея осталась той же, реализация чуть улучшена. Суть заключается в том, что данные интерфейсы мы можем имплентировать не через классы, а структуры. Таким образом, мы сможем снизить стоимость вызова их функций и использовать ad-hoc полиморфизм.
Я не случайно обозвал операцию "плюсом", а единичный элемент "нулём", потому что (спойлер) в алгебре есть структуры с двумя операциями, как, например, кольцо, где "сложение" от "умножения" надо отличать. Но, не суть важно. Реализуем, например, моноид максимизации.
public struct Max<T> : IMonoid<T> where T : IComparable<T>, new()
{
public T Zero => new();
public T Plus(T left, T right) =>
left.CompareTo(right) > 0
? left
: right;
}И сделаем под это какую-нибудь dto-шку.
public record Person(string Name, int Money) : IComparable<Person>
{
public Person() : this("", int.MinValue)
{
}
public int CompareTo(Person other) => Money.CompareTo(other.Money);
}И вот тут появляется важная мысль. Я же не буду брать всего два человека и находить богатейшего. Нет. Мне надо обработать много людей. У меня список есть.
var people = new List<Person>
{
new("Bob", 1000),
new("Tim", 1239),
new("Jeff", 2000000000)
};То есть, мы структуры можем использовать для разного рода агрегаций например. Поэтому, используя моноиды, даже можно было бы написать такое расширение.
public static class EnumerableExtensions
{
public static T Sum<T, M>(this IEnumerable<T> collection, M monoid = default)
where M : struct, IMonoid<T> =>
collection.Aggregate(monoid.Zero, monoid.Plus);
}Ну тогда теперь очевидно, что надо делать.
var richest = people.Sum<Person, Max<Person>>();Магия! Но, какая-то примитивная магия. Пока что. Какая следующая популярная агрегация у нас есть? Среднее! Оказывается его вычисление можно распараллелить. Это не такая очевидная мысль, но если задуматься... Из чего оно складывается: из количества значений и их суммы. То есть эти два параметра нужно разделить и отслеживать. Тогда мы получим структуру аналогичную 
. Оформим эту мысль.
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 == 0
? 0
: _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 struct Avg : IMonoid<AveragedValue>
{
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 struct Any<T> : IMonoid<Predicate<T>>
{
public Predicate<T> Zero => _ => false;
public Predicate<T> Plus(Predicate<T> left, Predicate<T> right) =>
x => left(x) || right(x);
}Тогда, например, можно написать что-то такое. Всё разнести по сервисам, контейнерам и будет красиво.
var predicates = new List<Predicate<char>>
{
x => x >= '0' && x <= '9',
x => x >= 'A' && x <= 'Z',
x => x >= 'a' && x <= 'z'
};
var digitOrLetter = predicates.Sum<Predicate<char>, Any<char>>();Вообще, мы можем построить более интересный моноид на словарях и операции слияния. Однако, установим, что значения словаря образуют хотя бы полугруппу, поскольку конфликт будет разрешаться сложением элементов. Тогда, получится что-то вроде этого.
public struct MapMonoid<K, V, S> : IMonoid<Dictionary<K, V>>
where S : struct, ISemiGroup<V>
{
public Dictionary<K, V> Zero => new();
public Dictionary<K, V> Plus(Dictionary<K, V> left, Dictionary<K, V> right)
{
var valueSemiGroup = default(S);
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<string> {"foo", "foo", "foo", "bar", "bar", "baz", "pipi", "pupu"};Мы можем с помощью него например сгруппировать строки по их числу вхождений или найти слова одинаковой длины. Или что-нибудь, что вы придумаете.
var dicts = strings
.Select(x => new Dictionary<string, int> {{x, 1}});
var anotherDicts = strings
.Select(x => new Dictionary<int, List<string>>
{
{x.Length, new List<string> {x}}
});Проведём их суммирование с помощью соответствующих полугрупп (числа со сложением, списки с соединением).
private struct IntSemiGroup : ISemiGroup<int>
{
public int Plus(int left, int right) => left + right;
}
private struct ListSemiGroup<T> : ISemiGroup<List<T>>
{
public List<T> Plus(List<T> left, List<T> right)
{
var result = new List<T>(left);
result.AddRange(right);
return result;
}
}var map = dicts
.Sum<Dictionary<string, int>, MapMonoid<string, int, IntSemiGroup>>();
var anotherMap = anotherDicts
.Sum<Dictionary<int, List<string>>, MapMonoid<int, List<string>, ListSemiGroup<string>>>();И получим такой вывод.
Итого
Существует огромное количество различных алгебраических структур. Их свойства помогают решать задачи компьютерных наук лаконичным, а может даже и эффективным способом. Про более неочевидные вещи могу написать в ещё одной статье. Мы задействовали только определения, а какой прорыв случится, когда в ход пойдут теоремы, боюсь представить. Когда-нибудь, программисты перестанут говорить: "Математика не нужна".
Ещё я веду telegram канал StepOne, где оставляю небольшие заметки про разработку и мир IT.
