Ist mein Verständnis von Monoid gültig?

8
___ answer32359764 ___

von Wolfram:

  

Ein Monoid ist eine Menge, die unter einer assoziativen binären Operation geschlossen ist und ein Identitätselement I in S hat, so dass für alle a in S, Ia = aI = a gilt.

aus Wiki:

  

In der abstrakten Algebra, einem Zweig der Mathematik, ist ein Monoid eine algebraische Struktur mit einer einzigen assoziativen binären Operation und einem Identitätselement.

damit Ihre Intuition mehr oder weniger richtig ist.

Sie sollten nur daran denken, dass es nicht für einen "benutzerdefinierten Satz" in Haskell definiert ist, sondern für einen Typ. Die Unterscheidung ist klein (weil Typen in der Typentheorie den Mengen in der Mengenlehre sehr ähnlich sind), aber die Typen, für die Sie eine Monoid-Instanz definieren können, müssen keine Typen sein, die mathematische Mengen darstellen.

Mit anderen Worten: Ein Typ beschreibt die Menge aller Werte dieses Typs. Monoid ist eine "Schnittstelle", die besagt, dass jeder Typ, der behauptet, an dieser Schnittstelle zu haften, einen Identitätswert bereitstellen muss, eine binäre Operation, die zwei Werte dieses Typs kombiniert, und es gibt einige Gleichungen, die alle generischen Monoid-Operationen erfüllen sollen funktionieren wie beabsichtigt (z. B. die generische Summierung einer Liste von Monoidwerten) und keine unlogischen / inkonsistenten Ergebnisse liefern.

Beachten Sie auch, dass das Vorhandensein eines identity-Elements in diesem Set (type) erforderlich ist, damit ein Typ eine Instanz der Monoid-Klasse ist.

Zum Beispiel bilden natürliche Zahlen unter beiden Hinzufügungen ein Monoid (identity = %code% ):

%Vor%

sowie Multiplikation (identity = %code% ):

%Vor%

listet auch ein Monoid unter %code% (identity = %code% ) auf:

%Vor%

Außerdem bilden Funktionen vom Typ %code% ein Monoid unter Zusammensetzung (identity = %code% )

%Vor%

Es ist also wichtig, daran zu denken, dass es bei Monoid nicht um Typen geht, die Mengen darstellen, sondern um Typen, die sozusagen als Mengen betrachtet werden.

als Beispiel für eine fehlerhafte Monoid-Instanz, betrachten Sie:

%Vor%

Wenn Sie nun %code% eine Liste von %code% -Werten versuchen, erhalten Sie immer %code% als Ergebnis, weil der Identitätswert %code% und die Binäroperation %code% nicht gut zusammenspielen:

%Vor%     
___ answer32359971 ___

Auf einer grundlegenden Ebene haben Sie Recht - es ist nur eine API für einen binären Operator, den wir mit %code% bezeichnen.

Der Wert des Monoidkonzepts steht jedoch in Beziehung zu anderen Typen und Klassen. Kulturell haben wir entschieden, dass %code% der natürliche Weg ist, zwei Dinge des gleichen Typs zusammenzufügen / anzuhängen.

Betrachten Sie dieses Beispiel:

%Vor%

Die Funktion %code% ist extrem polymorph - %code% kann ein String, ByteString oder Text sein, um nur einige Möglichkeiten zu nennen. Außerdem ist es in jedem Fall genau das, was Sie erwarten - es fügt %code% an die Zeichenkette 'Hallo' an.

Darüber hinaus gibt es viele Algorithmen, die an alles arbeiten, was sich ansammeln kann, und das sind gute Kandidaten für die Verallgemeinerung zu einem Monoid. Betrachten Sie zum Beispiel die Funktion %code% aus der Klasse %code% :

%Vor%

Nicht nur, dass %code% die Idee der Faltung über eine Struktur verallgemeinert, sondern ich kann verallgemeinern, wie die Akkumulation durchgeführt wird, indem die richtige Monoid-Instanz ersetzt wird.

Wenn ich eine faltbare Struktur %code% habe, die Ints enthält, kann ich %code% mit dem %code% -Monoid verwenden, um die Summe der Ints zu erhalten, oder mit %code% , um das Produkt usw. zu erhalten.

Schließlich bietet %code% Bequemlichkeit. Zum Beispiel gibt es eine Fülle von verschiedenen Set-Implementierungen, aber für alle von ihnen %code% ist immer die Vereinigung von zwei Sets %code% und %code% (vom selben Typ). Dies ermöglicht es mir, Code zu schreiben, der von der zugrunde liegenden Implementierung des Satzes unabhängig ist, wodurch mein Code vereinfacht wird. Dasselbe kann für viele andere Datenstrukturen gesagt werden, z. Sequenzen, Bäume, Karten, Prioritätswarteschlangen usw.

    
___ tag123haskell ___ Haskell ist eine funktionale Programmiersprache mit starker statischer Typisierung, verzögerungsfreier Auswertung, umfangreicher Parallelitäts- und Parallelitätsunterstützung und einzigartigen Abstraktionsfunktionen. ___ tag123operators ___ Operatoren sind Symbole, die in fast allen Programmier- und Codierungssprachen vorkommen, um Berechnungen und Vergleiche von Daten durchzuführen. ___ qstnhdr ___ Ist mein Verständnis von Monoid gültig? ___ tag123monoids ___ Ein Monoid ist eine Menge, die unter einer assoziativen binären Operation geschlossen wird und ein Identitätselement I ∈ hat, so dass für alle a ∈ S, Ia = aI = a gilt. Beachten Sie, dass seine Elemente im Gegensatz zu einer Gruppe keine Inversen aufweisen müssen. Es kann auch als eine Halbgruppe mit einem Identitätselement betrachtet werden. ___ tag123binaryoperators ___ Verwenden Sie dieses Tag für Fragen, die mit Operatoren zu tun haben, die als binäre Operatoren identifiziert werden, d. h. Operatoren, die mit den beiden Operanden arbeiten. ___ answer32359670 ___

Aus Wikipedia :

  

In der abstrakten Algebra, einem Zweig der Mathematik, ist ein Monoid eine algebraische Struktur mit einer einzigen assoziativen binären Operation und einem Identitätselement.

Ich denke, dein Verständnis ist richtig. Aus Programmiersicht ist Monoid eine Schnittstelle mit zwei "Methoden", die implementiert werden müssen.

Das einzige Stück, das in Ihrer Beschreibung fehlt, ist die "Identität", ohne die Sie eine Halbgruppe .

Alles, was eine "Null" oder ein "Leer" hat und eine Art, zwei Werte zu kombinieren, kann ein Monoid sein. Zu beachten ist, dass es möglich sein kann, dass ein Satz / Typ auf mehrere Arten zu einem Monoid gemacht wird, zum Beispiel Zahlen über %code% mit Identität %code% oder %code% mit Identität %code% .

    
___
Reygoch 02.09.2015, 17:17
quelle

3 Antworten

8

Aus Wikipedia :

  

In der abstrakten Algebra, einem Zweig der Mathematik, ist ein Monoid eine algebraische Struktur mit einer einzigen assoziativen binären Operation und einem Identitätselement.

Ich denke, dein Verständnis ist richtig. Aus Programmiersicht ist Monoid eine Schnittstelle mit zwei "Methoden", die implementiert werden müssen.

Das einzige Stück, das in Ihrer Beschreibung fehlt, ist die "Identität", ohne die Sie eine Halbgruppe .

Alles, was eine "Null" oder ein "Leer" hat und eine Art, zwei Werte zu kombinieren, kann ein Monoid sein. Zu beachten ist, dass es möglich sein kann, dass ein Satz / Typ auf mehrere Arten zu einem Monoid gemacht wird, zum Beispiel Zahlen über addition mit Identität 0 oder multiplication mit Identität 1 .

    
ryachza 02.09.2015, 17:34
quelle
5

von Wolfram:

  

Ein Monoid ist eine Menge, die unter einer assoziativen binären Operation geschlossen ist und ein Identitätselement I in S hat, so dass für alle a in S, Ia = aI = a gilt.

aus Wiki:

  

In der abstrakten Algebra, einem Zweig der Mathematik, ist ein Monoid eine algebraische Struktur mit einer einzigen assoziativen binären Operation und einem Identitätselement.

damit Ihre Intuition mehr oder weniger richtig ist.

Sie sollten nur daran denken, dass es nicht für einen "benutzerdefinierten Satz" in Haskell definiert ist, sondern für einen Typ. Die Unterscheidung ist klein (weil Typen in der Typentheorie den Mengen in der Mengenlehre sehr ähnlich sind), aber die Typen, für die Sie eine Monoid-Instanz definieren können, müssen keine Typen sein, die mathematische Mengen darstellen.

Mit anderen Worten: Ein Typ beschreibt die Menge aller Werte dieses Typs. Monoid ist eine "Schnittstelle", die besagt, dass jeder Typ, der behauptet, an dieser Schnittstelle zu haften, einen Identitätswert bereitstellen muss, eine binäre Operation, die zwei Werte dieses Typs kombiniert, und es gibt einige Gleichungen, die alle generischen Monoid-Operationen erfüllen sollen funktionieren wie beabsichtigt (z. B. die generische Summierung einer Liste von Monoidwerten) und keine unlogischen / inkonsistenten Ergebnisse liefern.

Beachten Sie auch, dass das Vorhandensein eines identity-Elements in diesem Set (type) erforderlich ist, damit ein Typ eine Instanz der Monoid-Klasse ist.

Zum Beispiel bilden natürliche Zahlen unter beiden Hinzufügungen ein Monoid (identity = 0 ):

%Vor%

sowie Multiplikation (identity = 1 ):

%Vor%

listet auch ein Monoid unter ++ (identity = [] ) auf:

%Vor%

Außerdem bilden Funktionen vom Typ a -> a ein Monoid unter Zusammensetzung (identity = id )

%Vor%

Es ist also wichtig, daran zu denken, dass es bei Monoid nicht um Typen geht, die Mengen darstellen, sondern um Typen, die sozusagen als Mengen betrachtet werden.

als Beispiel für eine fehlerhafte Monoid-Instanz, betrachten Sie:

%Vor%

Wenn Sie nun mconcat eine Liste von MyInt -Werten versuchen, erhalten Sie immer MyInt 0 als Ergebnis, weil der Identitätswert 0 und die Binäroperation * nicht gut zusammenspielen:

%Vor%     
Erik Allik 02.09.2015 17:40
quelle
3

Auf einer grundlegenden Ebene haben Sie Recht - es ist nur eine API für einen binären Operator, den wir mit <> bezeichnen.

Der Wert des Monoidkonzepts steht jedoch in Beziehung zu anderen Typen und Klassen. Kulturell haben wir entschieden, dass <> der natürliche Weg ist, zwei Dinge des gleichen Typs zusammenzufügen / anzuhängen.

Betrachten Sie dieses Beispiel:

%Vor%

Die Funktion greet ist extrem polymorph - x kann ein String, ByteString oder Text sein, um nur einige Möglichkeiten zu nennen. Außerdem ist es in jedem Fall genau das, was Sie erwarten - es fügt x an die Zeichenkette 'Hallo' an.

Darüber hinaus gibt es viele Algorithmen, die an alles arbeiten, was sich ansammeln kann, und das sind gute Kandidaten für die Verallgemeinerung zu einem Monoid. Betrachten Sie zum Beispiel die Funktion foldMap aus der Klasse Foldable :

%Vor%

Nicht nur, dass foldMap die Idee der Faltung über eine Struktur verallgemeinert, sondern ich kann verallgemeinern, wie die Akkumulation durchgeführt wird, indem die richtige Monoid-Instanz ersetzt wird.

Wenn ich eine faltbare Struktur t habe, die Ints enthält, kann ich foldMap mit dem Sum -Monoid verwenden, um die Summe der Ints zu erhalten, oder mit Product , um das Produkt usw. zu erhalten.

Schließlich bietet <> Bequemlichkeit. Zum Beispiel gibt es eine Fülle von verschiedenen Set-Implementierungen, aber für alle von ihnen s <> t ist immer die Vereinigung von zwei Sets s und t (vom selben Typ). Dies ermöglicht es mir, Code zu schreiben, der von der zugrunde liegenden Implementierung des Satzes unabhängig ist, wodurch mein Code vereinfacht wird. Dasselbe kann für viele andere Datenstrukturen gesagt werden, z. Sequenzen, Bäume, Karten, Prioritätswarteschlangen usw.

    
ErikR 02.09.2015 17:52
quelle