Что такое структура полугруппы

Полугруппа

В математике, полугруппой называют множество с заданной на нем ассоциативной бинарной операцией.

Примеры полугрупп

Две полугруппы S и T называются изоморфными, если существует биекция f : S → T, такая что Две такие полугруппы считаются неразличимыми для полугрупповой теории.

Структура полугруппы

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

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

Подмножество A полугруппы S называется подполугруппой, если оно замкнуто относительно полугрупповой операции, т. е. AA есть подмножество A. Если A непусто и AS (SA) лежит в A, то A называют правым (левым) идеалом. Если A является одновременно левым и правым иделом, то его называют двусторонним идеалом, или просто идеалом.

Частным случаем полугрупп являются полугруппы с делением, в которых для каждых двух элементов a и b определено правое (a/b) и левое (b\a) частное.

ar:نصف زمرة cs:Pologrupa eo:Duongrupo (algebro) hu:Félcsoport nl:Halfgroep pl:Półgrupa sk:Pologrupa sl:Polgrupa sr:Полугрупа sv:Semigrupp

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Резюме

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

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

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

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

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

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

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

Бинарность

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

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

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

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

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

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

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

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

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

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

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

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

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

Резюме

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

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

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

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

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

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

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

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

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

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

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

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

Строки

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

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

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

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

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

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

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

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

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

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

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

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

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

Резюме

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

Заключение

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

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

Источник

Полугруппа

Идентичность и ноль

Подполугруппы и идеалы

Если A является одновременно левым и правым идеалом, то он называется идеалом (или двусторонним идеалом ).

Подмножество, обладающее тем свойством, что каждый элемент коммутирует с любым другим элементом полугруппы, называется центром полугруппы. [4] Центр полугруппы на самом деле является подполугруппой. [5]

Гомоморфизмы и сравнения

Коэффициенты и деления

Следующие понятия [8] вводят идею о том, что одна полугруппа содержится в другой.

Оба эти отношения транзитивны.

Бесконечные обобщения коммутативных полугрупп иногда рассматривались разными авторами. [заметка 3]

Источник

Полугруппы можно рассматривать как частный случай магмы, где операция ассоциативна, или как обобщение группы, не требуя наличия элемента идентичности или инверсий. [примечание 1] Как и в случае групп или магм, полугрупповая операция не обязательна. коммутативный, так Икс·у не обязательно равно у·Икс; хорошо известный пример ассоциативной, но некоммутативной операции: матричное умножение. Если операция полугруппы коммутативна, то полугруппа называется коммутативная полугруппа или (реже, чем в аналогичный случай групп) его можно назвать абелева полугруппа.

Формальное изучение полугрупп началось в начале 20 века. Первые результаты включают Теорема Кэли для полугрупп реализуя любую полугруппу как полугруппа преобразований, в котором произвольные функции заменяют роль биекций из теории групп. Глубокий результат в классификации конечных полугрупп Теория Крона – Родса, аналогично Разложение Жордана – Гёльдера для конечных групп. Некоторые другие методы изучения полугрупп, например Отношения Грина, не похожи ни на что в теории групп.

Теория конечных полугрупп имела особое значение в теоретическая информатика с 1950-х годов из-за естественной связи между конечными полугруппами и конечные автоматы через синтаксический моноид. В теория вероятности, полугруппы связаны с Марковские процессы. [1] В других областях Прикладная математика, полугруппы являются фундаментальными моделями для линейные инвариантные во времени системы. В уравнения в частных производных, полугруппа связана с любым уравнением, пространственная эволюция которого не зависит от времени.

Источник