___ qstntxt ___

Ich habe einen Datentyp wie folgt mit einer entsprechenden %code% -Instanz gesehen:

%Vor%

Sie können den vollständigen Code in einem Gist auf Github finden.

So kann %code% verwendet werden:

%Vor%

%code% endet als ein Baum, der folgendermaßen aussieht:

%Vor%

%code% kann verwendet werden, um Sequenzen von %code% Operationen ( %code% und %code% ) in eine AST umzuwandeln. Dieser AST kann dann in andere %code% interpretiert werden.

Hier ist zum Beispiel eine Übersetzung von %code% in eine %code% , die sicherstellt, dass die angehängte Zeichenfolge optimal geschieht:

%Vor%

Das ist wirklich nett. Es ist bequem, dass wir sicher sein können, dass %code% anhängen in der richtigen Reihenfolge geschieht. Wir müssen uns nicht um das links-assoziierte %code% s kümmern.

Was mich jedoch beunruhigt, ist, dass die %code% -Instanz für %code% keine legale %code% -Instanz ist.

Nehmen Sie zum Beispiel das erste %code% Gesetz:

%Vor%

Wenn wir %code% be %code% zulassen, erhalten wir Folgendes:

%Vor%

Sie können sehen, dass %code% nicht gleich %code% ist. Die anderen %code% -Gesetze gelten auch aus ähnlichen Gründen nicht.

Hascellers sind in der Regel gegen unrechtmäßige Instanzen. Aber ich denke, das ist ein besonderer Fall. Wir versuchen nur, eine Struktur aufzubauen, die in ein anderes %code% interpretiert werden kann. Im Fall von %code% können wir sicherstellen, dass die %code% -Gesetze für %code% in der Funktion %code% gelten.

1. Ist es jemals in Ordnung, diese Arten von nicht-rechtmäßigen Instanzen zu verwenden, um einen AST aufzubauen?
2. Gibt es bestimmte Probleme, auf die bei der Verwendung dieser Arten von nicht-rechtmäßigen Instanzen geachtet werden muss?
3. Gibt es eine alternative Möglichkeit, Code zu schreiben, der so etwas wie %code% verwendet? Eine Möglichkeit, die Interpretation einer monoidalen Struktur zu ermöglichen, anstatt %code% direkt auf einem Typ zu verwenden?

___ tag123haskell ___ Haskell ist eine funktionale Programmiersprache mit starker statischer Typisierung, verzögerungsfreier Auswertung, umfangreicher Parallelitäts- und Parallelitätsunterstützung und einzigartigen Abstraktionsfunktionen. ___ answer45885875 ___

  

Ist es jemals in Ordnung, diese Arten von nicht-rechtmäßigen Instanzen zu verwenden, um einen AST aufzubauen?

Dies ist eine Frage der Meinung. (Ich bin fest im 'Niemals' Camp.)

  

Gibt es bestimmte Probleme, auf die bei der Verwendung dieser Arten von nicht-rechtmäßigen Instanzen geachtet werden muss?

• kognitive Belastung für potenzielle Benutzer und zukünftige Betreuer
• potentielle Fehler, weil wir den Typ an einem Ort verwenden, der Annahmen auf der Basis des (der) gebrochenen Gesetzes (n) macht

Bearbeiten, um Fragen in Kommentaren zu beantworten:

  

Wären Sie in der Lage, konkrete Beispiele dafür zu finden, wie sie die kognitive Belastung der Benutzer erhöhen?

Stellen Sie sich vor, wie verärgert Sie wären, wenn jemand das in C machen würde:

%Vor%

Jetzt müssen wir den Umfang dieser Pseudo-While-Definition und ihrer Implikationen verfolgen. Es ist ein Nicht-Haskell-Beispiel, aber ich denke, das Prinzip ist das gleiche. Wir sollten nicht erwarten, dass die Semantik von %code% in einer bestimmten Quelldatei anders ist, genauso wie wir nicht erwarten sollten, dass die Semantik von %code% für einen bestimmten Datentyp unterschiedlich ist.

Wenn wir sagen, dass etwas ein X ist, dann sollte es ein X sein, weil Leute die Semantik von X verstehen. Das Prinzip hier ist erzeugt keine Ausnahmen zu gut verstandenen Konzepten .

Ich denke, dass der Gebrauch von rechtmäßigen Abstraktionen (wie Monoid) in erster Linie dazu dient, die Notwendigkeit zu verringern, dass Programmierer eine Vielzahl unterschiedlicher Semantiken lernen und sich daran erinnern müssen. Jede von uns geschaffene Ausnahme untergräbt dieses Ziel. In der Tat macht es es noch schlimmer; wir müssen uns an die Abstraktion erinnern und darüber hinaus alle Ausnahmen beachten. (Nebenbei, ich bewundere aber diejenigen, die Englisch als Zweitsprache gelernt haben.)

  

Oder wie kann es zu möglichen Fehlern führen?

einige Bibliothek:

%Vor%

mein Code:

%Vor%

ein anderer Programmierer (oder ich in ein paar Monaten):

%Vor%

  

Gibt es eine alternative Möglichkeit, Code zu schreiben, der so etwas wie Foo verwendet?

Ich würde wahrscheinlich nur den Konstruktor verwenden, um zu konstruieren:

%Vor%

oder machen Sie einen Operator:

%Vor%     

___ answer45887133 ___

Dies wird für meisten nicht-trivialen Datenstrukturen angezeigt. Die einzigen Ausnahmen, die mir von oben in den Sinn kommen, sind (einige) Trie-ähnliche Strukturen.

1. Ausbalancierte Baumdatenstrukturen erlauben mehrere Ausbalancierungen der meisten Werte. Dies gilt für AVL-Bäume, rot-schwarze Bäume, B-Bäume, 2-3 Finger-Bäume, etc.

2. Datenstrukturen, die um das "Umbauen" herum entworfen wurden, wie Hood-Melville-Warteschlangen, ermöglichen variable Mengen an Duplizierung innerhalb von Strukturen, die die meisten Werte repräsentieren.

3. Datenstrukturen, die effiziente Prioritätswarteschlangen implementieren, ermöglichen Mehrfachanordnungen von Elementen.

4. Hash-Tabellen ordnen Elemente unterschiedlich an, je nachdem, wann Kollisionen auftreten.

Keine dieser Strukturen kann ohne diese Flexibilität asymptotisch so effizient sein. Die Flexibilität bricht jedoch immer Gesetze unter strengster Interpretation. In Haskell ist der einzige gute Weg, dies zu bewältigen, indem man das Modulsystem verwendet, um sicherzustellen, dass niemand das Problem erkennen kann. In experimentell abhängigen Sprachen haben Forscher an Dingen wie der Beobachtungstyptheorie und der Homotopietypentheorie gearbeitet, um bessere Wege zu finden, über "Gleichheit" zu sprechen, aber diese Forschung ist weit davon entfernt, praktisch zu werden.

    

___ tag123interpreter ___ Ein Interpreter ist ein Programm, das in einer Programmiersprache geschriebene Anweisungen ausführt, d. h. ausführt. Der Tag [Dolmetscher] sollte bei Fragen zur Programmierung von Dolmetschern oder für Fragen zum detaillierten Innenleben von Dolmetschern angewendet werden. Verwenden Sie [interpreter-pattern] (möglicherweise mit diesem Tag) für Fragen zum Entwurfsmuster der Gang of Four. ___ answer45886102 ___

Zitieren diese Antwort zu einer ähnlichen Frage :

  

Man kann sich das von diesem alternativen Standpunkt aus vorstellen: das Gesetz (a & lt; & gt; b) & lt; & gt; c = a & lt; & gt; (b & lt; & gt; c) spezifiziert nicht, welche Gleichheit verwendet werden sollte, d. h. welche spezifische Beziehung das = bezeichnet. Es ist naheliegend, es im Hinblick auf die strukturelle Gleichheit zu betrachten, aber beachten Sie, dass sehr wenige Typklassengesetze tatsächlich der strukturellen Gleichheit gerecht werden (zB versuchen, fmap id = id für [] im Gegensatz zu forall x zu beweisen. Fmap id x = id x) .

Zum Beispiel ist es meistens in Ordnung, wenn Sie die Konstruktoren von %code% nicht exportieren und nur Funktionen exportieren, die sich aus Sicht der Benutzer so verhalten, als wäre %code% ein Monoid. Aber die meiste Zeit ist es möglich, eine Repräsentation zu finden, die strukturell ein Monoid ist, in der Praxis gut genug, aber vielleicht nicht so allgemein (unten kann man sich nicht beliebig nach der Tatsache neu zuordnen, weil Interpretation mit Konstruktion vermischt ist). p> %Vor%

( %code% )

Hier ist eine weitere SO-Frage, wo eine nicht-strukturelle Struktur ( %code% ) ) wird zuerst betrachtet.

    

___ tag123abstractsyntaretre ___ Abstrakte Syntaxbäume (ASTs) repräsentieren die rekursive Struktur eines formalen Dokuments (Programmquellcode). ___ 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. ___ tag123typeclass ___ Type-Klassen in Haskell sind ein Sprachmechanismus zur Unterstützung von Ad-hoc-Polymorphismen. Sie existieren auch in Scala, Coq und Isabelle. ___