What are isomorphism and homomorphisms

Question

I tried to understand isomorphism and homomorphisms in context of programming and need some help.

In the book FPiS it explains:

Let start with a homomorphisms:

"foo".length + "bar".length == ("foo" + "bar").length

Here, length is a function from String to Int that preserves the monoid structure.

• Why is that a homomorphisms?

• Why it preserve the monoid structure?

• Is for example map on list function a homomorphisms?

About isomorphism, I have following explaination that I took it from a book:

A monoid isomorphism between M and N has two homomorphisms f and g, where both f andThen g and g andThen f are an identity function. For example, the String and List[Char] monoids with concatenation are isomorphic. The two Boolean monoids (false, ||) and (true, &&) are also isomorphic, via the ! (negation) function.

Why (false, ||), (true, &&) and String and List[Char] monoids with concatenation are isomorphism?

Answer 1

Why is that a homomorphisms?

By definition.

Why it preserve the monoid structure?

Because of the == in the expression above.

Is for example map on list function a homomorphisms?

Yes. Replace "foo" and "bar" by two lists, and .length by .map(f). It's then easy to see (and prove) that the equation holds.

Why (false, ||), (true, &&) and String and List[Char] monoids with concatenation are isomorphism?

By definition. The proof is trivial, left as an exercise. (Hint: take the definition of an isomorphism, replace all abstract objects with concrete objects, prove that the resulting mathematical expression is correct)

---

Edit: Here are the few definitions you asked in comments:

• Homomorphism: a transformation of one set into another that preserves in the second set the relations between elements of the first. Formally f: A → B where bothA and B have a * operation such that f(x * y) = f(x) * f(y).

• Monoid: algebraic structure with a single associative binary operation and an identity element. Formally (M, *, id) is a Monoid iff (a * b) * c == a * (b * c) && a * id == a && id * a == a for all a, b, c in M.

Answer 2

"foo".length + "bar".length == ("foo" + "bar").length

To be precise, this is saying that length is a monoid homomorphism between the monoid of strings with concatenation, and the monoid of natural numbers with addition. That these two structures are monoids are easy to see if you put in the effort.

The reason length is a monoid homomorphism is because it has the properties that "".length = 0 and x.length ⊕ y.length = (x ⊗ y).length. Here, I've deliberately used two different symbols for the two monoid operations, to stress the fact that we are either applying the addition operation on the results of applying length vs the string concatenation operation on the two arguments before applying length. It is just unfortunate notation that the example you're looking at uses the same symbol + for both operations.

Edited to add: The question poster asked for some further details on what exactly is a monoid homomorphism.

OK, so suppose we have two monoids (A, ⊕, a) and (B, ⊗, b), meaning A and B are our two carriers, ⊕ : A × A → A and ⊗ : B × B → B are our two binary operators, and a ∈ A and b ∈ B are our two neutral elements. A monoid homomorphism between these two monoids is a function f : A → B with the following properties:

• f(a) = b, i.e. if you apply f on the neutral element of A, you get the neutral element of B
• f(x ⊕ y) = f(x) ⊗ f(y), i.e. if you apply f on the result of the operator of A on two elements, it is the same as applying it twice, on the two A elements, and then combining the results using the operator of B.

The point is that the monoid homomorphism is a structure-preserving mapping (which is what a homomorphism is; break down the word to its ancient Greek roots and you will see that it means 'same-shaped-ness').

OK, you asked for examples, here are some examples!

• The one from the above example: length is a monoid homomorphism from the free monoid (A, ·, ε)* to (ℕ, +, 0)
• Negation is a monoid homomorphism from (Bool, ∨, false) to (Bool, ∧, true) and vice verse.
• exp is a monoid homomorphism from (ℝ, +, 0) to (ℝ\{0}, *, 1)
• In fact, every group homomorphism is also, of course, a monoid homomorphism.