¿Qué es exactamente el homomorfismo monoide?

Pudiera darse el caso de que halles alguna incompatibilidad en tu código o proyecto, recuerda probar siempre en un ambiente de testing antes subir el código al trabajo final.

Solución:

Quiere decir que el tipo de datos String e Int son monoides.

No, ninguno String ni Int son monoides. Un monoide es una tupla de 3 (S, ⊕, e) donde ⊕ es un operador binario ⊕: S × S → S, tal que para todos los elementos a, b, c∈S sostiene eso (a⊕b) ⊕c = a⊕ (b⊕c), y e∈S es un “elemento de identidad” tal que a⊕e = e⊕a = a. String y Int son tipos, por lo que básicamente conjuntos de valores, pero no 3 tuplas.

El articulo dice:

Tomemos el String concatenación y Int adición como ejemplo monoides que tienen una relación.

Entonces, el autor claramente también menciona los operadores binarios ((++) en caso de String, y (+) en caso de Int). Las identidades (vacías string en caso de String y 0 en caso de Int) quedan implícitas; dejar las identidades como ejercicio para el lector es común en el discurso informal en inglés.

Ahora que tenemos dos estructuras monoide (M, ⊕, e_metro) y (N, ⊗, e_norte), Una función f: M → N (igual que length) se llama entonces homomorfismo monoide [wiki] dado que sostiene que f (m₁⊕m₂) = f (m₁) ⊗f (m₂) para todos los elementos metro₁, m₂∈M y ese mapeo también preserva el elemento de identidad: f (e_metro) = e_norte.

Por ejemplo length :: String -> Int es un homomorfismo monoide, ya que podemos considerar los monoides (String, (++), "") y (Int, (+), 0). Sostiene que:

1. length (s1 ++ s2) == length s1 + length s2 (para todos Strings s1 y s2); y
2. length "" == 0.

El tipo de datos no puede ser un monoide por sí solo. Para un monoide, necesita un tipo de datos T y dos cosas más:

• un operación binaria asociativa, llamémoslo |+|, que toma dos elementos de tipo T y produce un elemento de tipo T
• un elemento de identidad de tipo Tvamos a llamarlo i, de modo que para cada elemento t de tipo T lo siguiente sostiene: t |+| i = i |+| t = t

A continuación, se muestran algunos ejemplos de monoide:

• conjunto de enteros con operación = suma e identidad = cero
• conjunto de enteros con operación = multiplicación e identidad = uno
• conjunto de listas con operación = anexión e identidad = lista vacía
• conjunto de cadenas con operación = concatenación e identidad = vacío string

Homomorfismo monoide

El monoide de concatenación de cadenas se puede transformar en monoide de suma entera aplicando .length a todos sus elementos. Ambos conjuntos forman un monoide. Por cierto, recuerde que no podemos simplemente decir “un conjunto de números enteros forma un monoide”; tenemos que elegir una operación asociativa y un elemento de identidad correspondiente. Si tomamos, por ejemplo, la división como operación, rompemos la primera regla (en lugar de producir un elemento de tipo integer, podríamos producir un elemento de tipo float / double).

Método length nos permite pasar de un monoide (string concatenación) a otro monoide (suma entera). Si dicha operación también conserva la estructura monoide, se considera que es una homomorfismo monoide.

Conservar la estructura significa:

length(t1 |+| t2) = length(t1) |+| length(t2)

and

length(i) = i'

dónde t1 y t2 representan elementos del monoide “fuente”, i es la identidad del monoide “fuente”, y i' es la identidad del monoide de “destino”. Puedes probarlo tú mismo y ver que length de hecho es una operación de preservación de la estructura en un string monoide de concatenación, mientras que, por ejemplo, indexOf("a") no lo es.

Isomorfismo monoide

Como se demostró, length asigna todas las cadenas a sus números enteros correspondientes y forma un monoide con la suma como operación y el cero como identidad. Pero no podemos volver, por cada string, podemos calcular su longitud, pero dada una longitud no podemos reconstruir el “original” string. Si pudiéramos, entonces la operación de “avanzar” combinada con la operación de “retroceder” formaría una isomorfismo monoide.

Isomorfismo significa poder ir y venir sin pérdida de información. Por ejemplo, como se indicó anteriormente, la lista forma un monoide que se agrega como operación y una lista vacía como elemento de identidad. Podríamos pasar de “lista debajo de agregar” monoide a “vector debajo de agregar” monoide y viceversa sin pérdida de información, lo que significa que las operaciones .toVector y .toList juntos forman un isomorfismo. Otro ejemplo de isomorfismo, que Runar mencionó en su texto, es String ⟷ List[Char].

Coloquialmente, un homomorfismo es una función que conserva la estructura. En el ejemplo del length función la estructura preservada es la suma de las longitudes de dos cadenas siendo igual a la longitud de la concatenación de las mismas cadenas. Dado que tanto las cadenas como los enteros se pueden considerar como monoides (cuando están equipados con una identidad y una operación binaria asociativa que obedece a las leyes de los monoides) length se llama homomorfismo monoide.

Consulte también las otras respuestas para obtener una explicación más técnica.

Si te ha sido de utilidad nuestro artículo, nos gustaría que lo compartas con otros desarrolladores y nos ayudes a difundir esta información.

---

---

Utiliza Nuestro Buscador