究竟什么是幺半群同态？

Question

我从 Monoid Morphisms, Products, and Coproducts 那里读到有关幺半群同态的内容，但无法 100% 理解。

作者说（强调原创）：

The length function maps from String to Int while preserving the monoid structure. Such a function, that maps from one monoid to another in such a preserving way, is called a monoid homomorphism. In general, for monoids M and N, a homomorphism f: M => N, and all values x:M, y:M, the following equations hold:
f(x |+| y) == (f(x) |+| f(y))

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

他的意思是，因为数据类型 String 和 Int 是幺半群，函数 length 映射 String => Int 保留幺半群结构（Int是一个幺半群），就叫幺半群同态吧？

Answer 1

Does he mean, the datatype String and Int are monoid.

没有，String和Int都不是幺半群。幺半群是一个三元组 (S, ⊕, e) 其中 ⊕ 是二元运算符 ⊕ : S×S → S，这样对于所有元素 a, b, c∈S 它认为 (a⊕b)⊕c=a⊕(b⊕ c)，并且 e∈S 是一个 "identity element" 这样 a⊕e=e⊕a=a . String 和 Int 是类型，所以基本上是一组值，但不是三元组。

文章说：

Let's take the String concatenation and Int addition as example monoids that have a relationship.

所以作者显然也提到了二元运算符（(++) 在 String 的情况下，(+) 在 Int 的情况下）。标识（在 String 的情况下为空字符串，在 Int 的情况下为 0）是隐式的；将身份留作 reader 的练习在非正式英语话语中很常见。

现在我们有两个幺半群结构 (M, ⊕, e_m) 和 (N, ⊗, e_n), 函数f : M → N（如 length）然后被称为 monoid homomorphism [wiki]，因为它认为 f(m₁⊕m₂)=f(m₁)⊗f(m₂) 对所有元素m₁, m₂∈M 并且该映射还保留标识元素：f(e_m)=e_n.

例如 length :: String -> Int 是一个幺半群同态，因为我们可以考虑幺半群 (String, (++), "") 和 (Int, (+), 0)。它认为：

length (s1 ++ s2) == length s1 + length s2（对于所有 Strings s1 和 s2）；和
length "" == 0.

Answer 2

数据类型本身不能是幺半群。对于幺半群，您需要一个数据类型 T 和另外两件事：

一个关联二元运算，我们称之为|+|，它接受两个T类型的元素并产生一个T类型的元素]
一个 类型 T 的标识元素 ，我们称它为 i，这样对于 T 类型的每个元素 t =] 以下成立：t |+| i = i |+| t = t

这里有一些幺半群的例子：

运算 = 加法且身份 = 零的整数集
运算 = 乘法且恒等式 = 一个的整数集
操作=追加且身份=空列表的列表集
操作 = 串联且标识 = 空字符串的字符串集

幺半群同态

通过将 .length 应用于其所有元素，可以将字符串连接幺半群转换为整数加法幺半群。这两个集合形成一个幺半群。顺便说一句，记住我们不能只说 "set of integers forms a monoid"；我们必须选择一个关联操作和一个相应的标识元素。如果我们采取例如作为运算的除法，我们打破了第一条规则（我们可能会生成 float/double 类型的元素，而不是生成整数类型的元素）。

方法length 允许我们从一个幺半群（字符串连接）到另一个幺半群（整数加法）。如果这样的操作也保留幺半群结构，则它被认为是幺半群同态。

保留结构意味着：

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

and

length(i) = i'

其中 t1 和 t2 表示 "source" 幺半群的元素，i 是 "source" 幺半群的身份，i' 是 "destination" 幺半群的恒等式。您可以自己尝试一下，看看 length 确实是对字符串连接幺半群的结构保留操作，而例如indexOf("a") 不是。

幺半群同构

如前所述，length 将所有字符串映射到它们对应的整数，并形成一个以加法为运算、以零为标识的幺半群。但是我们不能回头——对于每个字符串，我们可以算出它的长度，但是给定一个长度我们不能重建 "original" 字符串。如果可以，那么 "going forward" 的操作与 "going back" 的操作结合将形成 幺半群同构 。

同构意味着能够在不丢失任何信息的情况下来回移动。例如，如前所述，列表在追加操作和空列表作为标识元素的情况下形成一个幺半群。我们可以从 "list under appending" 幺半群到 "vector under appending" 幺半群并返回而不会丢失任何信息，这意味着操作 .toVector 和 .toList 一起形成同构。 Runar 在他的文章中提到的同构的另一个例子是 String ⟷ List[Char].

Answer 3

通俗地说，同态是一种保留结构的函数。在 length 函数的示例中，保留的结构是两个字符串的长度之和等于相同字符串的串联长度。由于字符串和整数都可以被视为幺半群（当配备身份和遵守幺半群定律的关联二元运算时）length 称为幺半群同态。

另请参阅其他答案以获得更技术性的解释。

Answer 4

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 andThen g) 和 (g andThen 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)

例如，使用 String 上可用的 toList 和 List[Char] 上可用的 toString（其中 toList andThen toString 和 toString andThen toList 是恒等函数)

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

究竟什么是幺半群同态？

What is monoid homomorphism exactly?

haskell

functional-programming

scala

category-theory

monoids

同态通过函数 f

通过函数 f 和 g 实现同构