Властелин структур09.04.2022 08:31

Собственно в методе Reduce и происходит то, что было описано. Чтобы гарантировать агрегацию, мы говорим: map происходит в некий моноид, и сама агрегация проводится через расширение Sum, известное по прошлой статье. А затем сужаем моноид до группы чтобы Remove событиям сопоставлять «реверс» объекта.

Пощупаем наш каталог.

var stringsCatalogue = new Catalogue()
    .Add("abc")
    .Nothing()
    .Remove("c")
    .Remove("a")
    .Add("ed");

IntAddGroup.cs

private struct IntAddGroup : IGroup
{
    public int Plus(int left, int right) => left + right;

    public int Zero => 0;

    public int Inverse(int item) => -item;
}

В самом каталоге мы как-то манипулировали со строками. Получим например длину строки после манипуляций

stringsCatalogue.Reduce(s => s.Length); // 3

Согласен, пока потребность в каталоге не очень мотивирована, но зато отчётливо видно, что оно работает. Ок, а что если мы захотим например на основе этих записей собрать строку, которая получится в результате таких операций? Да, у строк есть конкатенация, но с ней получается только моноид. Трудно придумать так называемый «минус» для строк. Конечно, интуитивно мы представляем себе что-то вроде:

"abc" - "c" == "ab"

Но вот что делать, если попался кейс "abc" - "d", или "" - "", или "" - "xyz"? Ответа на вопрос в таких условиях не существует, но, как это обычно бывает выход есть всегда.

У многих к этому моменту могла возникнуть идея раскручивать историю о множествах. Мы знаем, что string это IEnumerable, и получается начать отталкиваться от проведения аналогии с множествами, и раскрутить её до коллекции.

Однако, множества с операцией объединения образуют лишь коммутативный моноид (оставлю доказательство этого утверждения в качестве упражнения читателю). Мы можем получить абелеву группу, если вместо объединения возьмём симметрическую разницу, но поведение этой операции немного не то.

Оказывается, что если мы будем отдельно вести учёт включений и исключений, то и вовсе добьёмся желаемого поведения. Делается это через представление множества в виде пары двух множеств: слева элементы, которые надо включить; справа, которые надо исключить.

PairedHashSet.cs

public record PairedSet(HashSet First, HashSet Second)
{
    public PairedSet() : this(new(), new())
    {
    }

    public PairedHashSet(IEnumerable single) : this(new(single), new())
    {
    }
}

public static class PairedSetExtensions
{
    public static HashSet ToHashSet(this PairedSet pairedSet)
    {
        var (first, second) = pairedSet;
        return first.Except(second);
    }
}

public static class HashSetExtensions
{
    public static HashSet Except(this HashSet first, HashSet second)
    {
        var result = new HashSet(first);
        result.ExceptWith(second);
        return result;
    }
    
    public static HashSet Union(this HashSet first, HashSet second)
    {
        var result = new HashSet(first);
        result.UnionWith(second);
        return result;
    }
}

public struct PairedHashSetGroup : IGroup>
{
    public PairedHashSet Plus(PairedHashSet left, PairedHashSet right)
    {
        var (left1, left2) = left;
        var (right1, right2) = right;
        var newLeft = left1.Except(right2).Union(right1.Except(left2));
        var newRight = left2.Except(right1).Union(right2.Except(left1));
        return new PairedHashSet(newLeft, newRight);
    }

    public PairedHashSet Zero => new ();
    
    public PairedHashSet Inverse(PairedHashSet item)
    {
        var (first, second) = item;
        return new PairedHashSet(second, first);
    }
}

Такая логика очень просто переносится на списки, при чём мы можем выбрать — исключать с конца списка или с его начала.

PairedList.cs

public record PairedList(List First, List Second)
{
    public PairedList() : this(new(), new())
    {
    }

    public PairedList(IEnumerable single) : this(new(single), new())
    {
    }
}

public static class PairedListExtensions
{
    public static List ToList(this PairedList pairedList)
    {
        var (first, second) = pairedList;
        return first.Except(second);
    }
}

public static class ListExtensions
{
    public static List Union(this List list, List items)
    {
        var result = new List(list);
        result.AddRange(items);
        return result;
    }
    
    public static List Except(this List first, List second)
    {
        var result = new List(first);
        second.ForEach(item =>
        {
            var li = result.LastIndexOf(item);
            if (li > -1)
            {
                result.RemoveAt(li);
            }
        });
        return result;
    }
}

PairedListGroup.cs

public struct PairedListGroup : IGroup>
{
    public PairedList Plus(PairedList left, PairedList right)
    {
        var (left1, left2) = left;
        var (right1, right2) = right;
        var newLeft = left1.Except(right2).Union(right1.Except(left2));
        var newRight = left2.Except(right1).Union(right2.Except(left1));
        return new PairedList(newLeft, newRight);
    }

    public PairedList Zero => new ();
    
    public PairedList Inverse(PairedList item)
    {
        var (first, second) = item;
        return new PairedList(second, first);
    }
}

PairedEnumerable.cs

И теперь, вернувшись к нашему каталогу, мы можем проверить всё описанное.

var chars = stringsCatalogue.Reduce, PairedListGroup>(
    s => new PairedList(s)
).ToList();
Console.WriteLine(string.Join("", chars)); // bed

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

// немного расширим список конструкторов
public record PairedList(List First, List Second)
{
    ...
    public PairedList(T item) : this(new List {item})
    {
    }
}

И тогда можно написать такое расширение к каталогу.

public static class CatalogueExtensions
{
    public static List Collect(this Catalogue catalogue) =>
        catalogue.Reduce, PairedListGroup>(
            x => new PairedList(x)
        ).ToList();
}

Такое сработает даже для какой-нибудь dto’шки.

public record SomeDto(int Number, bool Flag, string Field)
{
}

Сделаем для неё каталог и поиграемся с ним.

var someDtosCatalogue = new Catalogue()
    .Add(new SomeDto(1, false, "asa"))
    .Add(new SomeDto(2, true, "asa"))
    .Remove(new SomeDto(1, false, "asa"));

Элементарно, размер коллекции (не каталога).

someDtosCatalogue.Reduce(_ => 1)

Можно взять саму коллекцию и что-то с ней сделать.

var someDtosObjects = someDtosCatalogue.Collect();
someDtosObjects.ForEach(Console.WriteLine);
// SomeDto { Number = 2, Flag = True, Field = asa }

Или потрогать логи.

var logs = someDtosCatalogue.ToList();
logs.ForEach(Console.WriteLine);
// Add { Data = SomeDto { Number = 1, Flag = False, Field = asa } }
// Add { Data = SomeDto { Number = 2, Flag = True, Field = asa } }
// Remove { Data = SomeDto { Number = 1, Flag = False, Field = asa } }

Что-то на группах сильно задержались, пора двигаться дальше.

Кольцо

С древних времён до наших дней дошёл очень известный и интересный факт. Если имеется прямоугольный треугольник со сторонами , то они удовлетворяют равенству . Данное утверждение — это теорема Пифагора, знакомая, наверно, почти каждому школьнику.

При этом у людей всегда был интерес к рассмотрению в рамках этой теоремы таких прямоугольных треугольников, у которых стороны целые. Какое-то время спустя возникло описание всех таких треугольников, но прогресс на этом не останавливается.

Любого математика и программиста, на мой взгляд, объединяет желание обобщать. И прогресс пошёл в сторону обобщения по показателю степени: оказывается, что написанная выше формула — это частный случай Диофантова уравнения . И в 1637 году, математик Пьер Ферма сформулировал свою Великую Теорему, которая говорит о том, что таких целых троек не найти для натуральных и базировались на изучении делимости в множествах вида . В результате рассмотрения таких множеств математики пришли к выводу, что их элементы ведут себя как целые числа, и возникла необходимость в обобщении их арифметики. Так возникло понятие кольца.

Кольцо (коммутативное) — это множество с двумя бинарными операциями и  такое, что:

public interface IRing : IGroup
{
    T One { get; }
    
    T Times(T left, T right);
}

Дальнейшие примеры будут менее приближенными к реальности, может быть даже в какой-то степени игрушечными, но не менее занимательными и интересными.

Как уже было сказано, кольца обобщают арифметику целых чисел, то есть, их разумно вводить в тех случаях, когда нужно обобщить умножение. Поэтому хотелось бы иметь дело с не числовыми структурами.

Начнём издалека, со знакомства с таким понятием, как гомоморфизм. Гомоморфизм — это отображение между двумя структурами, которое сохраняет операцию. Например, есть две структуры: и Тогда, отображение называется гомоморфизмом, если

Самое главное для понимания то, что гомоморфизм — это абстрактная штука, целый класс отображений. Потому что они бывают сюръективные, инъективные, в себя и т. д.

Самым важным гомоморфизмом является изоморфизм (биекция, сохраняющая операцию). Но почему? Потому что помимо того, что у двух структур одинаковое поведение операции, есть взаимно-однозначное соответствие между ними. А значит не важно, с элементами какой структуры работать для описания её свойств, потому что мы всегда можем прыгать туда-сюда.

Например, вещественные числа по сложению образуют группу, и положительные вещественные по умножению тоже. Между ними существует изоморфизм (поэлементная нотация отображения).

И надо ли нам рассматривать каждую группу по отдельности, когда можно описать одну, а потом сказать, что вторая это первая с точностью до изоморфизма? Вопрос риторический.

Есть также другой интересный класс гомоморфизмов, это эндоморфизмы. Эндоморфизм — это гомоморфизм в себя. Множество всех эндоморфизмов структуры обозначается , а если  — абелева группа, то  — кольцо. Для этого сложение надо определить поточечно, а в качестве умножения взять композицию функций.

public struct End : IRing>
    where G : struct, IGroup
{
    public Func Plus(Func left, Func right) => 
        x => default(G).Plus(left(x), right(x));

    public Func Zero => _ => default(G).Zero;

    public Func Inverse(Func item) =>
        x => default(G).Inverse(x);

    public Func One => x => x;

    public Func Times(Func left, Func right) =>
        x => left(right(x));
}

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

RingExtensions.cs

public static class RingExtensions
{
    public static T Power(this IRing ring, T item, int n)
    {
        var result = item;
        for (var i = 1; i < n; i++)
        {
            result = ring.Times(result, item);
        }

        return result;
    }
}

var end = default(End, PairedHashSetGroup>);
var id = end.One;
Func, PairedHashSet> x2 = 
    s => new (s.ToHashSet().Select(i => i * 2));
var idPlusX2 = end.Plus(id, x2);
var pows = end.Power(idPlusX2, 6)(new (1)); // {1, 2, 4, 8, 16, 32, 64}

Полукольцо

Как и в случае с группой у кольца есть свой «полу» аналог. Всё также есть тройка , но требуют от неё других вещей:

•  — коммутативный моноид;

•  — моноид;

• Умножение дистрибутивно относительно сложения;

• Для всех элементов полукольца выполняется поглощающее свойство нуля: .

public interface ISemiRing : IMonoid
{
    T One { get; }

    T Times(T left, T right);
}

То есть, в отличие от кольца у нас не требуют обратного элемента по сложению, а требование для нуля вытекает как раз из отсутствия формального минуса. Здесь можно посмотреть примеры структур, где оно не выполняется.

Каких-то общих размышлений о полукольце не будет. Просто скажу, что у него есть много практических применений. Например, в этой книжке научно обосновывается (с точки зрения математики) и детально описывается тот факт, что широкий класс задач на графах можно решить более менее унифицированным способом за счёт обобщения матричного умножения и адаптации матрицы инцидентности к нужному умножению.

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

public class SquareMatrix : IEnumerable.Vector>
    where S : struct, ISemiRing
{
    private readonly int _size;
    private readonly List _rows = new();

    public SquareMatrix(int size)
    {
        _size = size;
        for (var i = 0; i < _size; i++)
        {
            _rows.Add(new Vector(
                Enumerable.Repeat(default(S).Zero, _size)
            ));
        }
    }

    public SquareMatrix(int size, params IEnumerable[] rows)
    {
        _size = size;
        _rows.AddRange(rows.Select(x => new Vector(x)));
    }

    public T this[int i, int j]
    {
        get => _rows[i][j];
        set => _rows[i][j] = value;
    }

    public SquareMatrix Transpose()
    {
        var columns = Enumerable
            .Range(0, _size)
            .Select(i => _rows.Select(col => col[i]));
        return new (_size, columns.ToArray());
    }

    public SquareMatrix Product(SquareMatrix that)
    {
        var transposed = that.Transpose();
        var rows = this
            .Select(x => transposed.Select(x.Dot));
        return new (_size, rows.ToArray());
    }

    public SquareMatrix Power(int n)
    {
        var result = this;
        for (var i = 1; i < n; i++)
        {
            result = result.Product(this);
        }

        return result;
    }

    public IEnumerator GetEnumerator() => _rows.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    public override string ToString() =>
        new StringBuilder()
            .AppendJoin('\n', _rows.Select(row =>
                new StringBuilder()
                    .Append('|')
                    .AppendJoin(", ", row)
                    .Append('|')))
            .ToString();

    public class Vector : IEnumerable
    {
        private readonly List _items;

        public Vector(IEnumerable items)
        {
            _items = new List(items);
        }

        public T this[int index]
        {
            get=> _items[index];
            set => _items[index] = value;
        }

        public T Dot(Vector that) => _items
            .Zip(that._items)
            .Select(pair => default(S).Times(pair.First, pair.Second))
            .Sum();

        public IEnumerator GetEnumerator() => _items.GetEnumerator();

        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    }
}

И, например, в полукольце , решается задача о нахождении размера самого короткого пути между вершинами и  за  или меньше шагов. В полукольце же решается аналогичная задача для нахождения размера самого длинного пути.

MinPlus.cs

public struct MinPlus : ISemiRing
{
    public double Plus(double left, double right) => Min(left, right);

    public double Zero => double.PositiveInfinity;
    
    public double One => 0;

    public double Times(double left, double right) => left + right;
}

MaxPlus.cs

public struct MaxPlus : ISemiRing
{
    public double Plus(double left, double right) => Max(left, right);

    public double Zero => double.NegativeInfinity;
    
    public double One => 0;

    public double Times(double left, double right) => left + right;
}

Проверим для начала, насколько корректно работает возведение в степень в полукольце целых чисел.

SquareMatrix testMatrix = new(3,
    new[] {1, 0, 3},
    new[] {0, 5, 0},
    new[] {2, 0, 6}
);
Console.WriteLine(testMatrix.Power(4));

Действительно, получилась матрица

Теперь рассмотрим следующий граф для примера

Как уже говорилось ранее, мы можем решать задачи, обобщая матричное умножение. В случае двух упомянутых ранее задач, всё что надо сделать это вычислить .

public class WeightedGraph
{
    private readonly int _size;
    private readonly Dictionary> _adjancencyList = new();

    public WeightedGraph(int size, params (int, List<(int Vertex, double Weight)>)[] adjancencyList)
    {
        _size = size;
        adjancencyList.ToList()
            .ForEach(x => _adjancencyList[x.Item1] = x.Item2);
    }

    private SquareMatrix GetAdjacencyMatrix() 
        where S : struct, ISemiRing
    {
        var adjancencyMatrix = new SquareMatrix(_size);
        for (var i = 0; i < _size; i++)
        {
            adjancencyMatrix[i, i] = default(S).One;
        }

        foreach (var key in _adjancencyList.Keys)
        {
            foreach (var (vertex, weight) in _adjancencyList[key])
            {
                adjancencyMatrix[key, vertex] = weight;
            }
        }

        return adjancencyMatrix;
    }
    
    public double GetShortestPath(int i, int j, int k) => 
        GetAdjacencyMatrix()
            .Power(k)[i, j];

    public double GetLongestPath(int i, int j, int k) =>
        GetAdjacencyMatrix()
            .Power(k)[i, j];
}

var weightedGraph = new WeightedGraph(4,
    (0, new() {(1, 3), (2, 8), (3, 12)}),
    (1, new() {(2, 2), (3, 10)}),
    (2, new() {(3, 3)})
);

Console.WriteLine(weightedGraph.GetShortestPath(0, 3, 3)); // 8
Console.WriteLine(weightedGraph.GetLongestPath(0, 3, 2)); // 13