Моноиды, полугруппы и все-все-все

http://blog.ploeh.dk/2017/10/05/monoids-semigroups-and-friends/
  • Перевод

Если ты на практике используешь ООП, то хорошо разбираешься в таких вещах, как «паттерны проектирования». А знаешь ли ты, что есть множество полезных паттернов, которые не укладываются в этот стандартный список? К сожалению, многие из них связаны с «функциональным программированием», которое, согласно легенде, сложное и заумное. Если десять раз сказать слово «моноид», можно вызвать Дьявола.


Mark Seeman расскажет о функциональном программировании просто и быстро. Для этого он начал писать цикл статей, посвященных связи между паттернами проектирования и теорией категорий. Любой ООПшник, у которого есть 15 минут свободного времени, сможет заполучить в свои руки принципиально новый набор идей и инсайтов, касающихся не только функциональщины, но и правильного объектно-ориентированного дизайна. Решающим фактором является то, что все примеры — это реальный код на C#, F# и Haskell. Этот хабрапост — перевод самого начала цикла, первых трех статей, слитых воедино для удобства понимания.


Кроме того, с Марком можно пообщаться вживую, посетив конференцию DotNext 2017 Moscow, которая состоится 12-13 ноября 2017 г. в Москве, в «Славянская Рэдиссон». Марк прочитает доклад на тему «From dependency injection to dependency rejection». Билеты можно взять здесь.


Вступление. Моноиды, полугруппы и все-все-все


Этот текст является частью новой серии о связях между паттернами проектирования и теорией категорий.
Функциональное программирование обычно критикуют за особый заумный жаргон. Термины типа зигохистоморфный препроморфизм никак не помогают донести суть новичкам. Но прежде чем бросаться камнями, вначале мы должны выйти из собственного стеклянного домика. В объектно-ориентированном проектировании используются названия типа Bridge, Visitor, SOLID, связность и другие. Слова звучат знакомо, но можете ли вы объяснить или реализовать в коде паттерн Visitor или описать, что такое «связность»?


Слово «bridge» само по себе не делает объектно-ориентированную терминологию лучше. Возможно, оно даже делает ее хуже. В конце концов, слово стало многозначным: имеем ли мы в виду настоящий физический объект, объединяющий два разных места, или разговариваем о паттерне проектирования? Конечно, на практике, мы поймем это из контекста, но это не отменяет факта — если кто-то говорит о паттерне bridge, вы совершенно ничего не поймете, если заранее не выучили его. То, что слово звучит знакомо, еще не делает его полезным.


Многие объектно-ориентированные программисты открыли для себя полезность «операции, которая возвращает тот же тип, какой она получила в качестве аргумента». Но тем не менее, такое описание, такой словарь — очень неудобны. Не лучше ли описать эту операцию одним словом? Может быть, это моноид или полугруппа?


Объектно-ориентированные озарения


В книге Domain-Driven Design Эрик Эванс рассказывает о понятии Closure of Operations. Как и следует из названия, это «операция, у возвращаемый тип которой совпадает с типами аргументов». В C# это может быть метод с сигнатурой public Foo Bar(Foo f1, Foo f2). Метод берет на вход два объекта Foo и возвращает тоже объект Foo.


Как заметил Эванс, спроектированные таким образом объекты начинают выглядеть, как если бы они формировали арифметику. Если есть операция, принимающая Foo и возвращающая Foo, что это может быть? Может быть, сложение? Умножение? Еще какая-то математическая операция?


Кое-какие enterprise разработчики просто хотят «сделать дело и двигаться дальше», их совершенно не беспокоит математика. Для них идея делать код более «математичным» кажется очень спорной. Тем не менее, даже если вам «не нравится математика», вы точно понимаете смысл сложения, умножения и т.п. Арифметика — мощная метафора, поскольку все программисты ее понимают.


В своей знаменитой книге «Test-Driven Development: By Example» Кент Бек, похоже, эксплуатировал ту же самую идею. Хотя не думаю, что он где-то напрямую об этом написал.


То, о чем писал Эванс — это моноиды, полугруппы и похожие на них концепции из абстрактной алгебры. Справедливости ради, я недавно с ним общался, и сейчас он уже отлично разбирается во всех этих вещах. Разбирался ли он в них в 2003 году, когда была написана DDD — не знаю, но я — точно нет. Моя задача здесь не тыкать пальцами, а показать, что очень умные люди вывели принципы, которые можно использовать в ООП, задолго до того, как эти принципы получили собственные имена.


Как все это связано


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



Они описывают бинарные операции в форме: операция, которая берет на вход два значения Foo и возвращает значение типа Foo на выходе. Обе категории описываются (интуитивно-понятными) законами. Разница в том, что законы моноидов строже, чем законы полугрупп. Не зависайте на терминологии: слово «закон» может звучать, как будто здесь замешана серьезная сложная математика, но эти «законы» — простые и интуитивные. О них мы поговорим в следующих частях (которых будет около 15 штук).


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


Резюме


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


Часть 1. Моноиды


Суть: введение в моноиды для ООП-программистов.
Данный раздел является частью цикла статей о моноидах, полугруппах и связанных с ними концепциях. Изучив этот раздел, вы поймете, что такое моноид и чем он отличается от полугруппы.



Моноиды образуют подмножество полугрупп. Правила, по которым работают моноиды, строже, чем для полугрупп. Можно даже решить, что лучше вначале разобраться с полугруппами и уже на их основе продвигаться к моноидам. Строго говоря, с точки зрения иерархии, это имеет смысл. Но я думаю, что моноиды куда более интуитивны. Увидев первый же пример моноида, сразу понимаешь, что они описывают вещи из повседневной жизни. Легко найти пример для моноида, а вот чтобы подобрать хороший пример полугруппы — придется постараться. Поэтому мы начнем именно с моноидов.


Законы моноида


Что общего имеет сложение (40 + 2) и умножение (6 * 7)?
Обе эти операции


  • ассоциативны
  • являются бинарными операциями
  • имеют нейтральный элемент

Это все, что нужно для образования моноида. Ассоциативность и существование нейтрального элемента называют «законами моноида» или «моноидными законами» (в английском языке — monoid laws). Стоит отметить, что моноид — это комбинация типа данных и операции. То есть, это не просто тип, а скорее функция (или метод), которая работает над этим типом. Например, сложение и умножение — это два разных моноида, работающих на числах.


Бинарность


Давайте начнем с самого простого. Операция является «бинарной», если она работает над двумя значениями. Возможно, при упоминании слова «бинарный» вам в первую очередь представляются бинарные данные, типа 101010, но это слово взялось из латинского языка, и означает что-то связанное с «арностью два». Астрономы тоже иногда говорят о двойных звездах (binary stars), но сейчас это слово в основном используется в контексте компьютеров: кроме бинарных данных, вы, скорее всего, слышали и о бинарных деревьях. Говоря о бинарных операциях, мы подразумеваем, что оба входящих значения имеют один и тот же тип, и что возвращаемый тип также совпадает со входящим типом. Другими словами, в C# метод типа этого является корректной бинарной операцией:


public static Foo Op(Foo x, Foo y)

Иногда, если Op является методом экземпляра класса Foo, она может выглядеть вот так:


public Foo Op (Foo foo)

С другой стороны, вот это уже не является бинарной операцией:


public static Baz Op(Foo f, Bar b)

Несмотря на то, что оно принимает два входящих аргумента, они имеют разные типы, и возвращаемый тип тоже отличается.


Поскольку все аргументы и возвращаемые значения совпадают по типу, бинарная операция представляет собой то, что Эрик Эванс в Domain-Driven Design называл Closure of Operations.


Ассоциативность


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


(2 + 3) + 4 = 2 + (3 + 4) = 2 + 3 + 4 = 9

Аналогично для умножения:


(2 * 3) * 4 = 2 * (3 * 4) = 2 * 3 * 4 = 24

Если говорить об описанном выше методе Op, ассоциативность требует, чтобы areEqual оказался равен true для следующего кода:


var areEqual = foo1.Op(foo2).Op(foo3) == foo1.Op(foo2.Op(foo3));

На левой части вначале вычислится foo1.Op(foo2), и затем результат применится к foo3. Справа первым вычислится foo2.Op(foo3), и результат станет аргументом для foo1.Op. Поскольку левая и правая части сравниваются с помощью оператора ==, ассоциативность требует, чтобы areEqual оказался равен true.


Чтобы вся эта конструкция заработала в C#, если имеется какой-то самодельный моноид Foo, у него придется перегрузить Equals и реализовать оператор ==.


Нейтральный элемент


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


Единица — это значение, которое «ничего не делает». Например, для сложения — это 0, поскольку добавление нуля ничего не делает с исходным значением, не изменяет его:


0 + 42 = 42 + 0 = 42

Простое упражнение: догадайтесь, чем является единица для умножения.


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


var hasIdentity =
    Foo.Identity.Op(foo) == foo.Op(Foo.Identity) &&
    foo.Op(Foo.Identity) == foo;

Существует пара моноидов, работающих над булевскими значениями: all и any. Как думаете, как они работают? Какие у них единицы?


Поразмышлять над all и any (или нагуглить их) вы можете в качестве упражнения. В следующих разделах я покажу другие, более интересные моноиды. В этом хабрапосте рассматриваются только строки, списки и последовательности — остальные статьи все еще пишутся.


В сущности, если есть тип данных, который «ведет себя как число», скорей всего можно сделать из него моноид. Сложение — один из лучших кандидатов, ведь его проще всего понять, и не нужно связываться с вещами типа единиц измерения. Например, в .NET Base Class Library существует структура TimeSpan, имеющая метод Add. Оператор == у нее тоже имеется. С другой стороны, у TimeSpan нет метода Multiply, поскольку — что будет результатом умножения двух периодов? Квадратное время?


Резюме


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


(Кстати, единица для умножения — это единица (1), all — это булевский and, а any — булевский or.)


Часть 2. Моноид строк, списков и последовательностей


Суть: строки, списки и последовательности, по сути, являются одним и тем же моноидом.
Данный раздел является частью цикла статей о моноидах.
Вкратце, моноид — это ассоциативная бинарная операция с нейтральным элементом (известным как единица, или в английской терминологии —identity).


Последовательности


В C# ленивые последовательности значений моделируются с помощью IEnumerable<T>. Можно комбинировать пару последовательностей, добавляя одну к другой:


xs.Concat(ys)

Здесь xs и ys — экземпляры IEnumerable<T>. Метод расширения Concat объединяет последовательности. Он имеет следующую сигнатуру: IEnumerable<T> Concat<T>(IEnumerable<T>, IEnumerable<T>), поэтому является бинарной операцией. Если мы выясним, что он ассоциативен и имеет единицу, то докажем, что это — моноид.


Последовательности ассоциативны, потому что последовательность вычисления не изменяет результата. Ассоциативность — свойство моноида, поэтому один из способов продемонстрировать его — использовать property-based testing.


[Property(QuietOnSuccess = true)]
public void ConcatIsAssociative(int[] xs, int[] ys, int[] zs)
{
    Assert.Equal(
        xs.Concat(ys).Concat(zs),
        xs.Concat(ys.Concat(zs)));
}

Этот автотест использует FsCheck (да, в C# он тоже работает!) для демонстрации ассоциативности Concat. Чтобы упростить дело, xs, ys и zs объявяются как массивы. Это нужно потому, что FsCheck нативно знает, как создавать массивы, а вот встроенной поддержки IEnumerable<T> не имеет. Конечно, можно было бы посоздавать iEnumerable<T> самостоятельно, с помощью FsCheck API, но это усложнит пример, а ничего нового не добавит. Свойство ассоциативности выполняется и для других чистых реализаций IEnumerable<T>. Если не верите — попробуйте.


Операция Concat имеет единицу. Единица — это пустая последовательность, что подтверждается следующим тестом:


[Property(QuietOnSuccess = true)]
public void ConcatHasIdentity(int[] xs)
{
    Assert.Equal(
        Enumerable.Empty<int>().Concat(xs),
        xs.Concat(Enumerable.Empty<int>()));
    Assert.Equal(
        xs,
        xs.Concat(Enumerable.Empty<int>()));
}

Иначе говоря, если в начало или конец любой последовательности приклеить пустую последовательность, то изначальная последовательность не изменится.


Поскольку Concat — ассоциативная бинарная операция с единицей, она является моноидом. Доказано. ◼


Связные списки и другие коллекции


Приведенные выше тесты с использованием FsCheck показали, что Concat — это моноид над массивами. Это свойство сохраняется для всех чистых реализаций IEnumerable<T>.


В Haskell ленивые последовательности моделируется в виде связных списков. Они ленивы уже потому, что все выражения в Haskell являются таковыми по умолчанию. Законы моноидов выполняются и для списков в Haskell:


λ> ([1,2,3] ++ [4,5,6]) ++ [7,8,9]
[1,2,3,4,5,6,7,8,9]
λ> [1,2,3] ++ ([4,5,6] ++ [7,8,9])
[1,2,3,4,5,6,7,8,9]

λ> [] ++ [1,2,3]
[1,2,3]
λ> [1,2,3] ++ []
[1,2,3]

В Haskell оператор ++ — примерно то же, что Concat в C#, но эту операцию принято называть сложением или присоединением (append), а не конкатенацией (concat).


В F# связные списки инициализируются агрессивно (не лениво), поскольку все выражения в F# являются таковыми по умолчанию. Списки, тем не менее, продолжают быть моноидами, поскольку все свойства моноида все еще выполняются:


> ([1; 2; 3] @ [4; 5; 6]) @ [7; 8; 9];;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]
> [1; 2; 3] @ ([4; 5; 6] @ [7; 8; 9]);;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

> [] @ [1; 2; 3];;
val it : int list = [1; 2; 3]
> [1; 2; 3] @ [];;
val it : int list = [1; 2; 3]

В F# оператором конкатенации является @, а не ++, но его поведение точно такое же, как в Haskell. ◼


Строки


Никогда не задумывались, почему текстовые значения называются string в большинстве языков программирования? В конце концов, string в английском языке — это веревка, такая длинная гибкая штука, сделанная из волокон.


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


На самом деле, в Haskell тип String — это не что-то хитрое, а синоним для [Char] (это значит: список значений Char). Поэтому все, что вы можете делать со списками любых других типов, можно делать и со String:


λ> "foo" ++ []
"foo"
λ> [] ++ "foo"
"foo"
λ> ("foo" ++ "bar") ++ "baz"
"foobarbaz"
λ> "foo" ++ ("bar" ++ "baz")
"foobarbaz"

Совершенно очевидно, что ++ для String является моноидом в Haskell.


Точно так же, в .NET, System.String реализует IEnumerable<char>. По аналогии можно догадаться, что они окажутся моноидами — и это почти так. Давайте посмотрим, они точно ассоциативны:


[Property(QuietOnSuccess = true)]
public void PlusIsAssociative(string x, string y, string z)
{
    Assert.Equal(
        (x + y) + z,
        x + (y + z));
}

В C# оператор + действительно определен для string, и, как видно по этому тесту на FsCheck, он ассоциативен. И он почти имеет единицу. Что является эквивалентом пустому списку в мире строк? Конечно, пустая строка:


[Property(QuietOnSuccess = true)]
public void PlusHasIdentity(NonNull<string> x)
{
    Assert.Equal("" + x.Get, x.Get + "");
    Assert.Equal(x.Get, x.Get + "");
}

Пришлось вручную объяснить FsCheck, что использовать null не нужно. Как всегда, null вставляет палки в колеса в любые рассуждения о коде.


Проблема здесь в том, что "" + null и null + "" возвращают одно и то же значение — "", и оно не равно входящему значению (null). Другими словами, "" не является настоящей единицей для оператора +, потому что существует вот этот специальный случай. (И кстати, null также не является единицей, поскольку null + null возвращает… ""! Ну конечно, он возвращает именно это…). Тем не менее, это особенность реализации. В качестве упражнения, попробуйте придумать метод (расширения) на C#, который сделал бы string правильным моноидом, несмотря на наличие null. Как только вы его придумаете, это сразу покажет, что конкатенация строк является моноидом в .NET точно так же, как и в Haskell. ◼


Свободный моноид


Вспомните, как в предыдущих статьях мы показали, что и сложение, и умножение чисел являются моноидами. Существует еще как минимум один моноид над числами, и это — последовательность. Если существует обобщенная последовательность (IEnumerable<T>), она может содержать все, что угодно, включая числа.


Представьте, что есть два числа, 3 и 4, и хочется объединить их, но еще пока непонятно — каким именно образом вы будете их объединять. Чтобы отложить решение, можно положить оба числа в единичный массив (в английском языке это называется singleton array — массив с одним элементом, и это не имеет ничего общего с паттерном Singleton):


var three = new[] { 3 };
var four = new[] { 4 };

Как мы раньше доказали, последовательности являются моноидами, поэтому можно спокойно комбинировать их:


var combination = three.Concat(four);

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


Например, мы решили, что нужно получить сумму чисел:


var sum = combination.Aggregate(0, (x, y) => x + y);

(Да, я в курсе, что существует метод Sum, но сейчас наша цель — разобраться в деталях). Этот Aggregate принимает первым аргументом значение seed, а вторым — функцию для комбинирования.


А вот так можно получить произведение:


var product = combination.Aggregate(1, (x, y) => x * y);

Заметьте, что в обоих случаях значение seed является единицей для соответствующей моноидальной операции: 0 — для сложения, 1 — для умножения. Точно так же, функция аггрегации использует ту бинарную операцию, которая относится к соответствующему моноиду.


Интересно, что это называется «свободным моноидом», аналогично «свободным монадам». В обоих случаях можно собрать все данные, интерпретируя их не сразу, а позже — и потом сгрузить все эти данные в один из многих заранее заготовленных «вычислителей».


Резюме


Многие типы коллекций, такие как последовательности и массивы в .NET или списки в F# и Haskell, являются моноидами над конкатенацией. В Haskell строки являются списками, поэтому строковая конкатенация автоматически является моноидом. В .NET оператор + для строк является моноидом, но только если притвориться, что null не существует. Тем не менее, все они являются вариациями одного и того же моноида.


Хорошо, что C# использует + для конкатенации строк, поскольку, как было показано в предыдущей части, сложение — наиболее интуитивное и «естественное» из всех моноидов. Вы знаете школьную арифметику, поэтому можете мгновенно понять метафору сложения. Тем не менее, моноид — это больше, чем метафора. Это абстракция, которая описывает специальные бинарные операции, одна из которых (так получилось) является сложением. Это генерализация концепции — и это абстракция, которую вы уже знаете.


Заключение


На этом мы завершаем эту статью. Впереди еще очень много информации, которая будет публиковаться так же, как в оригинале — в виде последовательных постов на Хабре, связанных обратными ссылками. Здесь и далее: оригиналы статей — © Mark Seemann 2016, переводы делаются силами JUG.ru Group, переводчик — Олег Чирухин.


Напоминаем, что пообщаться с автором можно вживую, посетив конференцию DotNext 2017 Moscow, которая состоится 12-13 ноября 2017 г. в Москве, в «Славянская Рэдиссон». Марк прочитает доклад на тему «From dependency injection to dependency rejection». Билеты можно взять здесь.

JUG.ru Group 1 359,02
Конференции для взрослых. Java, .NET, JS и др. 18+
Поделиться публикацией
Комментарии 19
  • +5
    Спасибо, хороший материал, и перевод.
    • +2
      Это еще только начало материала :)
      • 0

        Прошу не ограничиваться этой статьёй, ждём все, что есть!)

        • +1
          Как-то странно. Ко мне пришло несколько человек с просьбой дать разрешение на переводы. Я разрешил, но только после того, как мне напишут на хабре в личку. С тех пор никто не написал. Теперь непонятно что делать, вдруг они сейчас у себя в темной пещере тексты переводят, а я им статью запорю. Подожду недельку-другую, потом продолжу.
          • 0

            Долгое ожидание может смениться делами, которые "съедят" время.

    • –3
      И всё же «ты» вместо «вы» неприятно режет ухо.
      • +1
        Не смог понять что такое свободный моноид из-за этого:
        Моноид (не путать с монадой) — это бинарная операция, которая удовлетворяет двум законам моноида: операция должна быть ассоциативной и должен существовать нейтральный элемент (единица).
        Существует еще как минимум один моноид над числами, и это — последовательность.

        Т.е. последовательность — это бинарная операция? Как это вообще?
        • +2
          ну вот так :)

          моноид — это комбинация бинарной операции (например, конкатенации методом Concat) и типа данных над которым она работает (например, строки или массивы). Ну знаете, как в классическом ООП, класс — это абстрактный тип данных и набор операций над ним :)

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

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

          Откуда может взяться последовательность? Либо склейкой уже готовых последовательностей, либо надо собрать их из отдельных элементов. Первый случай — очевидный, по поводу второго в тексте есть заготовленный пример:

          var three = new[] { 3 };
          var four = new[] { 4 };
          var combination = three.Concat(four);

          Если последовательность — это то, что всегда получается в результате применения моноида конкатенации, значит последовательность и есть моноид конкатенации. Точно так же как с квадратом, алгоритм построения квадарата и есть квадрат.

          Поэтому в тексте они употреблены как синонимы — вероятно, с целью упростить формулировку

          А свобода тут в том, что в комбинации (тип данных + операция + данные), операция — не захардкожена, мы можем ее поменять потом. Паттерн стратегия
          • +1
            Если последовательность — это то, что всегда получается в результате применения моноида конкатенации, значит последовательность и есть моноид конкатенации.
            По такой логике выходит, что если в результате применения моноида суммы целых чисел всегда получается целое число, то целое число и есть моноид суммы целых чисел? Тогда целое число есть и моноид умножения целых чисел тоже? Из чего можно подумать об эквивалентности этих моноидов :)

            А в целом, с учетом Вашего комментария и ссылки из статьи, стало понятнее, спасибо!
        • +2
          Интересно. Непонятно только, зачем это всё — каково практическое применение?

          Я недавно применил моноиды (правда я не знал, что в ФП так называются сами операции, а не множества значений, получающихся в результате применения этой операции) со сложными типами данных, для того, что бы иметь возможность сделать «конструктор» программ (последовательность композиции операций задавалась конфигом). Но никакие из свойств моноидов я не применял и не представляю, как применить. :)
          • 0
            У автора есть множество статей в его блоге: blog.ploeh.dk
            где он обсуждает практические применения. К сожалению, зачастую, из-за терминологии звучат они как борщ из заумных слов. Наверное, поэтому он и начал писать эту серию постов, чтобы священные тексты начали поддаваться расшифровке.

            Я по-возможности буду тащить на Хабр самое ценное из брейндампов автора, но есть момент: он пишет целыми сериями, и переводить отдельный пост не имеет смысла. Нужно переводить сразу всю серию.

            ну и как всегда <маркетинг>можно прийти на конфу DotNext и задать ему такие вопросы лично</маркетинг>
            • +4

              Применение — Map Reduce.
              Есть какая-то дичь (например, набор всех постов в твитере, или зарплаты сотрудников, или что угодно другое) — мапим дичь в моноидный тип (какой-то тип для отчётов)
              Далее, имея все бонусы моноида, редьюсим (агрегируем до отчёта по всем постам в твитере).


              Бонусы моноидного типа данных — халявная параллелизация в кластере.
              Плюс инкрементируемость. Т.е. если вы уже посчитали отчёт за период 2000-2017 и он лежит в моноидном типе достаточно посчитать отчёт за 2018 и "прибавить" к уже посчитанному.

            • +2
              Вот ведь, только сейчас понял, что у меня все время путались ассоциативность с коммутативностью :)
              • +2
                >> Изучив этот раздел, вы поймете, что такое моноид и чем он отличается от полугруппы.
                Не нашел где написано в чем отличие от полугруппы.
                • +1
                  Тем что в моноиде есть элемент нейтральный относительно опрации.
                • +4
                  Одно из самых полезных применений моноида — в дереве отрезков, которое для отрезка [1, n] хранит в узлах результаты операции только на некоторых подотрезках (длины 2^k, не пересекающихся друг с другом на каждом значении длины), а за счёт свойств моноида результат на произвольном подотрезке можно получить за O(log n), потому что любой подотрезок оказывается полностью покрыт <= 4 сохранёнными в дереве подотрезками, и нужно только найти в дереве эти результаты и выполнить над ними операцию. Ну, и обновление элемента тоже за O(log n), потому что он входит в такое количество сохранённых в дереве подотрезков.
                  • +2
                    «Closure of Operations» похоже можно перевести как «Замкнутость относительно операции». Например, множество натуральных чисел замкнуто относительно операции сложения, то есть сумма двух натуральных чисел является натуральным числом. Но при этом множество простых чисел не замкнуто относительно сложения.
                    • 0
                      А можете объяснить пожалуйста, почему единица для all — это булевский and, а any — булевский or?
                      • 0
                        Немного не так. Моноид с названием
                        all: ({True, False},(and)) нейтральный элемент True;
                        any: ({True, False},(or)) нейтральный элемент False.

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

                      Самое читаемое