幺半群同态和同构

Question

我正在看书'Programming in Scala'（红皮书）。

在有关Monoids的章节中，我了解了什么是Monoid同态，例如：The String Monoid M with concatenation and length function f preserves the monoid structure, and因此是同态的。

M.op(f(x), f(y)) == M.op(f(x) + f(y))
// "Lorem".length + "ipsum".length == ("Lorem" + "ipsum").length

引用书中的内容（凭记忆，如有错误请指正：

When this happens in both directions, it is named Monoid isomorphisim, that means that for monoids M, N, and functions f, g, f andThen g and g andThen f are the identity function. For example the String Monoid and List[Char] Monoid with concatenation are isomorphic.

但是我看不到实际的例子，我只能把f想成length函数，但是g会发生什么？

注意：我看到这个问题：。

Answer 1

要查看 String 和 List[Char] 之间的同构，我们有 toList: String -> List[Char] 和 mkString: List[Char] -> String。

length是字符串幺半群到自然数加法幺半群的同态。

String 幺半群的两个内同态示例是 toUpperCase 和 toLowerCase。

对于列表，我们有很多同态，其中许多只是 fold.

的版本

Answer 2

这里是siyopao用ScalaCheck程序表达的回答

object IsomorphismSpecification extends Properties("f and g") {
  val f: String => List[Char] = _.toList
  val g: List[Char] => String = _.mkString

  property("isomorphism") = forAll { (a: String, b: List[Char]) =>
    (f andThen g)(a) == a && (g andThen f)(b) == b
  }
}

输出

+ f and g.isomorphism: OK, passed 100 tests.

幺半群同态和同构

Monoid homomorphism and isomorphism

scala

functional-programming

monoids

isomorphism

homomorphism