9

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

In the book FPiS it explains:

enter image description here enter image description here

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?

softshipper
  • 32,463
  • 51
  • 192
  • 400
  • Because you can convert one into the other while preserving structure. That's pretty much the definition. – Bergi May 30 '17 at 15:31
  • 4
    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. – pedrofurla May 30 '17 at 17:05

2 Answers2

6

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.

OlivierBlanvillain
  • 7,701
  • 4
  • 32
  • 51
  • 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. – pedrofurla May 30 '17 at 17:01
  • @OlivierBlanvillain 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? – softshipper May 31 '17 at 06:52
  • What is a monoid structure? – softshipper May 31 '17 at 07:00
  • Why it play an important role in refactoring? – softshipper May 31 '17 at 07:07
  • Because you can safely refactor your code using transformation such as the `.length` one. See edit for the defs. – OlivierBlanvillain May 31 '17 at 07:30
  • Why `"foo".length + "bar".length == ("foo" + "bar").length` preserve to structure? Here the function length is transforming from `String` to `Int` right? – softshipper May 31 '17 at 08:02
  • 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.", – OlivierBlanvillain May 31 '17 at 08:09
  • 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? – softshipper May 31 '17 at 08:24
  • Preservation is between lhs and rhs, were "preserved" means "equal". – OlivierBlanvillain May 31 '17 at 09:20
  • Aha ok. I've got it. Thanks – softshipper May 31 '17 at 09:56
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.
Cactus
  • 27,075
  • 9
  • 69
  • 149
  • Can you please explain what is a `monoid homomorphism`, please provide more example. – softshipper May 31 '17 at 06:54
  • With `f(x) ⊗ f(y)` I would get to the element of `B`? – softshipper May 31 '17 at 08:04
  • @zero_coding: yes, both `f(x)`, `f(y)` and `f(x) ⊗ f(y)` are in `B`. – Cactus May 31 '17 at 08:13
  • Awesome, thanks so much. What does the symbol mean ⊗? – softshipper May 31 '17 at 08:17
  • 2
    `⊕` 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. – Cactus May 31 '17 at 09:12