Monoid homomorphism and isomorphism

Question

I am reading the book 'Programming in Scala' (The red book).

In the chapter about Monoids, I understand what a Monoid homomorphism is, for example: The String Monoid M with concatenation and length function f preserves the monoid structure, and hence are homomorphic.

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

Quoting the book (From memory, so correct me if I am wrong:

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.

But I can't see an actual example for seeing this, I can only think of f as the length function, but what happens with g?

Note: I have seen this question: What are isomorphism and homomorphisms.

Hobbyhorse

Have you seen this one? #55993754 – Steinman

Aha!, not the selected answer, but this one https://mcmap.net/q/295575/-what-is-monoid-homomorphism-exactly, in Monoid isomorphism was the answer for me. So, in this case, f and g will be toVector and toList, right? – Hobbyhorse

Oh, that one was mine, thanks! :) Yes, that's right. – Steinman

@Steinman I upvoted you there ;-) – Hobbyhorse

Thanks :) It's nice to see that your answer helps people. Cheers! – Steinman

Answer 1

To see the isomorphism between String and List[Char] we have toList: String -> List[Char] and mkString: List[Char] -> String.

length is a homomorphism from the String monoid to the monoid of natural numbers with addition.

A couple of examples of endo-homomorphism of the String monoid are toUpperCase and toLowerCase.

For lists, we have a lot of homomorphisms, many of which are just versions of fold.

Sewing

Answer 2

Here is siyopao's answer expressed as ScalaCheck program

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
  }
}

which outputs

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

Centaury