Что такое моноидный гомоморфизм?

Question

Я читал о моноидном гомоморфизме из Моноидные морфизмы, продукты и сопутствующие продукты и не мог понять 100%.

Автор говорит (выделено оригиналом):

Функция length отображается от String до Int при сохранении моноидной структуры .Такая функция, которая отображает один моноид в другой таким сохраняющим образом, называется моноидным гомоморфизмом .В целом, для моноидов M и N, гомоморфизма f: M => N и всех значений x:M, y:M справедливы следующие уравнения:

f(x |+| y) == (f(x) |+| f(y))

f(mzero[M]) == mzero[N]

Имеет ли он в видучто, поскольку типы данных String и Int являются моноидами, а функция length отображает String => Int с сохранением моноидной структуры (Int является моноидом), это называется гомоидизмом моноидов, верно?

Answer 1

Имеет ли он в виду, что тип данных String и Int являются моноидными.

Нет , ни String, ни Int не являются моноидами.Моноид представляет собой 3-кортеж (S, ⊕, e) , где ⊕ - бинарный оператор ⊕: S × S → S , такой что для всех элементов a,b, c∈S утверждает, что (a⊕b) ⊕c = a⊕ (b⊕c) , а e∈S является «элементом идентичности», такимчто a⊕e = e⊕a = a .String и Int являются типами, поэтому в основном это наборы значений, но не три кортежа.

В статье говорится:

Давайте возьмем Stringконкатенация и Int сложение в качестве примера моноиды , имеющие отношение.

Таким образом, автор явно также упоминает бинарные операторы ((++) в случае String и (+) в случае Int).Тождества (пустая строка в случае String и 0 в случае Int) неявные;оставление идентичностей в качестве упражнения для читателя часто встречается в неформальном английском дискурсе.

Теперь, учитывая, что у нас есть две моноидные структуры (M, ⊕, e _m ) и (N, ⊗, e _n ) , тогда функция f: M → N (например, length) называется моноидный гомоморфизм [wiki] , учитывая, что f (m ₁ ⊕m ₂ ) = f (m ₁ ) ⊗f (m ₂ ) для всех элементов m ₁ , m ₂ ∈M , и это отображение также сохраняетединичный элемент: f (e _m ) = e _n .

Например, length :: String -> Int является моноидным гомоморфизмом, поскольку мы можем рассмотретьмоноиды (String, (++), "") и (Int, (+), 0) .Он гласит:

1. length (s1 ++ s2) == length s1 + length s2 (для всех String s s1 и s2);и
2. length "" == 0.

Answer 2

Тип данных не может быть моноидом сам по себе. Для моноида вам нужен тип данных T и еще две вещи:

• ассоциативная двоичная операция , назовем ее |+|, которая принимает два элемента типа T и создает элемент типа T
• элемент идентификации типа T, назовем его i, так что для каждого элемента t типа T выполняется следующее: t |+| i = i |+| t = t

Вот несколько примеров моноида:

• набор целых чисел с операцией = сложение и тождество = ноль
• набор целых чисел с операцией = умножение и тождество = один
• набор списков с операцией = добавление и тождество = пустой список
• набор строк с операцией = объединение и тождество = пустая строка

моноидный гомоморфизм

Моноид конкатенации строк можно преобразовать в моноид сложения целых чисел, применив .length ко всем его элементам. Оба этих набора образуют моноид. Кстати, помните, что мы не можем просто сказать «множество целых чисел образует моноид»; мы должны выбрать ассоциативную операцию и соответствующий элемент идентичности. Если мы возьмем, например, деление как операция, мы нарушаем первое правило (вместо создания элемента типа integer мы можем создать элемент типа float / double).

Метод length позволяет нам перейти от моноида (конкатенация строк) к другому моноиду (сложение целых чисел). Если такая операция также сохраняет моноидную структуру, она считается моноидным гомоморфизмом .

Сохранение структуры означает:

length(t1 |+| t2) = length(t1) |+| length(t2)

and

length(i) = i'

, где t1 и t2 представляют элементы моноида "источник", i - идентификатор моноида "источник", а i' - идентификатор моноида "назначения". Вы можете попробовать это сами и увидеть, что length действительно является структурно-сохраняющей операцией на моноиде конкатенации строк, в то время как, например, indexOf("a") нет.

Моноидный изоморфизм

Как показано, length отображает все строки в соответствующие им целые числа и образует моноид с добавлением в качестве операции и нулем в качестве тождества. Но мы не можем вернуться назад - для каждой строки мы можем выяснить ее длину, но, учитывая длину, мы не можем восстановить «исходную» строку. Если бы мы могли, тогда операция «идти вперед» в сочетании с операцией «идти назад» сформировала бы моноидный изоморфизм .

Изоморфизм означает способность идти туда и обратно без потери информации. Например, как указывалось ранее, список образует моноид при добавлении в качестве операции и пустой список в качестве элемента идентичности. Мы можем перейти от «список при добавлении» к моноиду «вектор при добавлении» и обратно без потери информации, что означает, что операции .toVector и .toList вместе образуют изоморфизм. Другой пример изоморфизма, о котором Рунар упоминал в своем тексте, это String ⟷ List[Char].

Answer 3

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

См. Также другие ответы для более технического объяснения.