Тип данных не может быть моноидом сам по себе. Для моноида вам понадобится тип данных 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].

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

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

trait Monoid[T] {
def op(a: T, b: T): T
def zero: T
}

val strMonoid = new Monoid[String] {
  def op(a: String, b: String): String = a ++ b
  def zero: String = ""
}

val lcMonoid = new Monoid[List[Char]] {
  def op(a: List[Char], b: List[Char]): List[Char] = a ::: b
  def zero = List.empty[Char]
}

гомоморфизм через функцию f

f{M.op(x,y)} = N.op(f(x),g(y))

for example, using toList available on String

//in REPL
scala> strMonoid.op("abc","def").toList == lcMonoid.op("abc".toList,"def".toList)
res4: Boolean = true

изоморфизм через функции f и g

учитывая двунаправленный гомоморфизм между моноидами M и N,

f{M.op(x,y)} = N.op(f(x),f(y))
g{N.op(x,y)} = M.op(g(x),g(y))

И если оба (f и Затем g) и (g и Затем f) являются идентифицирующими функциями, то моноиды M и N изоморфны через f и g

g{f{M.op(x,y)}} = g{N.op(f(x),f(y))} = M.op(g(f(x)),g(f(y))) = M.op(x,y)

например, использование toList доступно на String и toString доступно на List[Char] (где toList andThen toString и toString andThen toList - функции идентификации)

scala> ( strMonoid.op("abc","def").toList ).toString == ( lcMonoid.op("abc".toList,"def".toList) ).toString
res7: Boolean = true