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 functionsf, g
,f andThen g
andg andThen f
are theidentity
function. For example theString
Monoid andList[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.
A monoid homomorphism is a map between monoids that preserves the monoid operation and maps the identity element of the first monoid to that of the second monoid (the identity element is a 0-ary operation). A group homomorphism is a map between groups that preserves the group operation.
Here are some examples of a monoid: set of integers with operation = addition and identity = zero. set of integers with operation = multiplication and identity = one. set of lists with operation = appending and identity = empty list. set of strings with operation = concatenation and identity = empty string.
A function κ:F→G κ : F → G is called a homomorphism if it satisfies equalities (#) and (##). A homomorphism κ:F→G κ : F → G is called an isomorphism if it is one-to-one and onto. Two rings are called isomorphic if there exists an isomorphism between them.
A bijective monoid homomorphism is called a monoid isomorphism. Two monoids are said to be isomorphic if there is a monoid isomorphism between them.
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
.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With