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?

Chemurgy

Because you can convert one into the other while preserving structure. That's pretty much the definition. – Esquibel

This question neither is off-topic or unclear. Don't get the close votes here. As a side comment: not understanding the topic at hand doesn't make it unclear or off-topic. – Leis

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.

Agueda

I was going to give a similar answer and provide the concrete explanations the OP was asking. But I won't! Your answer is better. – Leis

@Agueda First of all, thanks for your answer. But maybe I should ask, what is a homomorphisms exactly? How it does related to functional programming? What does it mean preserve to structure? Can you show me, how to proof (false, ||) that is a isomorphism? – Chemurgy

What is a monoid structure? – Chemurgy

Why it play an important role in refactoring? – Chemurgy

Because you can safely refactor your code using transformation such as the .length one. See edit for the defs. – Agueda

Why "foo".length + "bar".length == ("foo" + "bar").length preserve to structure? Here the function length is transforming from String to Int right? – Chemurgy

Right. The structure of an integer is it's value, the value is preserved through the transformation, therefore the structure is preserved through the transformation. This is what I mean by the "Because of the == in the expression above.", – Agueda

I can not see why the structure get preserve? At the beginning I have a String and after transformation I have Int, the String does not get preserve. Where can you see the preservation? – Chemurgy

Preservation is between lhs and rhs, were "preserved" means "equal". – Agueda

Aha ok. I've got it. Thanks – Chemurgy

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.

Chavarria

Can you please explain what is a monoid homomorphism, please provide more example. – Chemurgy

With f(x) ⊗ f(y) I would get to the element of B? – Chemurgy

@zero_coding: yes, both f(x), f(y) and f(x) ⊗ f(y) are in B. – Chavarria

Awesome, thanks so much. What does the symbol mean ⊗? – Chemurgy

⊕ and ⊗ are the two monoidal operations. The point of the notation is to always make clear when we are talking about the operation of A (⊕) and when about the operation of B (⊗). My analysis professor from uni would say there are + signs in two different colors in your original example. – Chavarria