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

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

Я читал о моноидном гомоморфизме из моноидных морфизмов, продуктов и копроизведений и не мог понять 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 является моноидом), это называется гомоидизмом моноидов, верно?

4b9b3361

ОТВЕТЫ

Ответ 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 являются типами, поэтому в основном это наборы значений, но не 3-кортежи.

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

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

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

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

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

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

Ответ 2

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

  • ассоциативная бинарная операция, пусть она называется |+| , который берет два элемента типа T и производит элемент типа T
  • единичный элемент типа T, назовем его i, так что для каждого элемента t типа T выполняется следующее: t |+| я = я |+| t = t t |+| я = я |+| 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].

Ответ 3

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

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