scala - ¿Qué es exactamente el homomorfismo monoide?

haskell functional-programming

Question

He leído sobre el homomorfismo de monoides de Morfismos, productos y coproductos de monoides y no pude entender el 100%.

El autor dice (énfasis original):

La función de length asigna de String a Int vez que conserva la estructura monoide . Dicha función, que se asigna de un monoide a otro de tal manera que se conserva, se denomina homomorfismo monoide . En general, para los monoides M y N , un homomorfismo f: M => N , y todos los valores x:M , y:M , sostienen las siguientes ecuaciones:

f(x |+| y) == (f(x) |+| f(y))
f(mzero[M]) == mzero[N]

¿Quiere decir que, dado que los tipos de datos String e Int son monoides, y la length la función corresponde a String => Int conserva la estructura monoide ( Int es un monoid), se llama homomorfismo monoide, verdad?

Answer 1

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

No , ni String ni Int son monoides. Un monoide es una tupla de 3 (S, ⊕, e) donde ⊕ es un operador binario ⊕: S × S → S , de manera que para todos los elementos a, b, c∈S se cumple que (a⊕b) c = a⊕ (b⊕c) , y e∈S es un "elemento de identidad" tal que a⊕e = e⊕a = a . String e Int son tipos, así que básicamente son conjuntos de valores, pero no 3-tuplas.

El artículo dice:

Tomemos la concatenación de String y la adición de Int como ejemplos de monoides que tienen una relación.

Así que el autor también menciona claramente los operadores binarios ( (++) en el caso de String , y (+) en el caso de Int ). Las identidades (cadena vacía en caso de String y 0 en caso de Int ) se dejan implícitas; Dejar las identidades como un ejercicio para el lector es común en el discurso informal en inglés.

Ahora, dado que tenemos dos estructuras monoides (M, ⊕, e _m ) y (N, ⊗, e _n ) , una función f: M → N ( length similar) se denomina en.wikipedia.org/wiki/Monoid#Monoid_homomorphisms dado que sostiene que f (m ₁ m ₂ ) = f (m ₁ ) ⊗f (m ₂ ) para todos los elementos m ₁ , m ₂ ∈M y esa asignación también conserva el elemento de identidad: f (e _m ) = e _n .

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 todas las String s s1 y s2 ); y
2. length "" == 0 .

Answer 2

Coloquialmente, un homomorfismo es una función que preserva la estructura. En el ejemplo de la función de length , la estructura preservada es la suma de las longitudes de las cadenas que son iguales 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 obedecen las leyes de monoides), la length se denomina homomorfismo monoide.

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

Answer 3

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:

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

Aquí hay algunos ejemplos de un 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 = adjuntando e identidad = lista vacía
• conjunto de cadenas con operación = concatenación e identidad = cadena vacía

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 decir simplemente que "conjunto de 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 entero, podríamos producir un elemento de tipo float / double).

La length método nos permite pasar de un monoide (concatenación de cadenas) a otro monoid (suma de enteros). Si dicha operación también preserva la estructura monoidea, se considera que es un homomorfismo monoide .

Preservar la estructura significa:

length(t1 |+| t2) = length(t1) |+| length(t2)
and
length(i) = i''

donde t1 y t2 representan elementos del monoide "fuente", i es la identidad del monoide "fuente", e i'' es la identidad del monoide "destino". Puede probarlo usted mismo y ver que la length es una operación de preservación de la estructura en un monoide de concatenación de cadenas, mientras que, por ejemplo, indexOf("a") no lo es.

Isomorfismo monoide

Como se demostró, la length asigna todas las cadenas a sus enteros correspondientes y forma un monoide con adición como operación y cero como identidad. Pero no podemos volver atrás: para cada cadena, podemos averiguar su longitud, pero dada una longitud no podemos reconstruir la cadena "original". Si pudiéramos, entonces la operación de "seguir adelante" combinada con la operación de "retroceder" formaría un isomorfismo monoide .

Isomorfismo significa poder ir y venir sin ninguna pérdida de información. Por ejemplo, como se indicó anteriormente, la lista forma un monoide al anexarse ​​como operación y la lista vacía como elemento de identidad. Podríamos pasar de "listar bajo el monoide adjunto" a "vector debajo del monoide anexado" y regresar sin pérdida de información, lo que significa que las operaciones .toVector y .toList forman un isomorfismo. Otro ejemplo de un isomorfismo, que Runar mencionó en su texto, es String ⟷ List[Char] .