scala - ¿Qué es exactamente el homomorfismo monoide?
haskell functional-programming (3)
¿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 deInt
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
1
m
2
) = f (m
1
) ⊗f (m
2
)
para todos los elementos
m
1
, m
2
∈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:
-
length (s1 ++ s2) == length s1 + length s2
(para todas lasString
ss1
ys2
); y -
length "" == 0
.
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 deString
aInt
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 monoidesM
yN
, un homomorfismof: M => N
, y todos los valoresx: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?
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.
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 tipoT
y produce un elemento de tipoT
-
un
elemento
de
identidad
de tipo
T
, llamémosloi
, de modo que para cada elementot
de tipoT
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]
.