Qu'est-ce que l'homomorphisme monoïde exactement?

Veut-il dire, le type de données String et Int sont monoïdes.

Non , ni String ni Int sont des monoïdes. Un monoïde est un 3-tuple (S, ⊕, e) où ⊕ est un opérateur binaire ⊕: S × S → S , tel que pour tous les éléments a, b, c∈S il tient que (a⊕b) ⊕c = a⊕ (b⊕c) , et e∈S est un "élément d'identité" tel que a⊕e = e⊕a = a . String et Int sont des types, donc essentiellement des ensembles de valeurs, mais pas 3-tuples.

L'article dit:

Prenons la concaténation de String et l' ajout d' Int comme exemples de monoïdes qui ont une relation.

Ainsi, l'auteur mentionne clairement aussi les opérateurs binaires ( (++) dans le cas de String , et (+) dans le cas de Int ). Les identités (chaîne vide dans le cas de String et 0 dans le cas de Int ) sont laissées implicites; laisser les identités comme un exercice pour le lecteur est courant dans le discours informel en anglais.

Maintenant que nous avons deux structures monoïdes (M, ⊕, e _m ) et (N, ⊗, e _n ) , une fonction f: M → N (comme la length ) est alors appelée un homomorphisme monoïde [wiki] étant donné qu'elle tient que f (m ₁ ⊕m ₂ ) = f (m ₁ ) ⊗f (m ₂ ) pour tous les éléments m ₁ , m ₂ ∈M et cette cartographie préserve également l'élément d'identité: f (e _m ) = e _n .

Par exemple length :: String -> Int est un homomorphisme monoïde, puisque nous pouvons considérer les monoides ( String , (++) , "" ) et ( Int , (+) , 0 ) . Il soutient que:

1. length (s1 ++ s2) == length s1 + length s2 (pour toutes les String s s1 et s2 ); et
2. length "" == 0 .

Le type de données ne peut pas être un monoïde à lui seul. Pour un monoïde, vous avez besoin d'un type de données T et de deux autres choses:

• une opération binaire associative , appelons-la |+| , qui prend deux éléments de type T et produit un élément de type T
• un élément d'identité de type T , appelons-le i , tel que pour tout élément t de type T ce qui suit est vrai: t |+| i = i |+| t = t

Voici quelques exemples de monoïde:

• ensemble d'entiers avec opération = addition et identité = zéro
• ensemble d'entiers avec opération = multiplication et identité = un
• ensemble de listes avec opération = ajout et identité = liste vide
• ensemble de chaînes avec opération = concaténation et identité = chaîne vide

Homomorphisme monoïde

Le monoïde de concaténation de chaîne peut être transformé en monoïde d'addition d'entiers en appliquant .length à tous ses éléments. Ces deux ensembles forment un monoïde. Au fait, rappelez-vous que nous ne pouvons pas simplement dire "un ensemble d'entiers forme un monoïde"; nous devons choisir une opération associative et un élément d'identité correspondant. Si nous prenons par exemple la division comme opération, nous cassons la première règle (au lieu de produire un élément de type entier, nous pourrions produire un élément de type float / double).

La length méthode nous permet de passer d'un monoïde (concaténation de chaînes) à un autre monoïde (addition d'entiers). Si une telle opération préserve également la structure monoïde, elle est considérée comme un homomorphisme monoïde .

Préserver la structure signifie:

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

and

length(i) = i'

où t1 et t2 représentent des éléments du monoïde "source", i est l'identité du monoïde "source", et i' est l'identité du monoïde "destination". Vous pouvez l'essayer vous-même et voir que length est en effet une opération de préservation de la structure sur un monoïde de concaténation de chaîne, alors que par exemple indexOf("a") ne l'est pas.

Isomorphisme monoïde

Comme démontré, la length mappe toutes les chaînes à leurs entiers correspondants et forme un monoïde avec l'addition comme opération et zéro comme identité. Mais nous ne pouvons pas revenir en arrière - pour chaque chaîne, nous pouvons déterminer sa longueur, mais étant donné une longueur, nous ne pouvons pas reconstruire la chaîne "originale". Si nous le pouvions, alors l'opération «aller de l'avant» combinée à l'opération «revenir en arrière» formerait un isomorphisme monoïde .

L'isomorphisme signifie pouvoir aller et venir sans aucune perte d'information. Par exemple, comme indiqué précédemment, la liste forme un monoïde sous l'ajout comme opération et une liste vide comme élément d'identité. Nous pourrions passer de "liste sous appendice" monoïde à "vecteur sous appendice" monoïde et .toVector sans aucune perte d'information, ce qui signifie que les opérations .toVector et .toList forment ensemble un isomorphisme. Un autre exemple d'isomorphisme, que Runar a mentionné dans son texte, est String ⟠· List[Char] .

Familièrement, un homomorphisme est une fonction qui préserve la structure. Dans l'exemple de la fonction length , la structure conservée est la somme des longueurs de à chaînes égales à la longueur de la concaténation des mêmes chaînes. Puisque les chaînes et les entiers peuvent être considérés comme des monoïdes (lorsqu'ils sont équipés d'une identité et d'une opération binaire associative obéissant aux lois monoïdes), la length est appelée un homomorphisme monoïde.

Voir aussi les autres réponses pour une explication plus technique.

scala> ( strMonoid.op("abc","def").toList ).toString == ( lcMonoid.op("abc".toList,"def".toList) ).toString
res7: Boolean = true