Problem
Betrachten Sie das folgende Entwurfsproblem in Haskell. Ich habe eine einfache, symbolische EDSL, in der ich Variablen und allgemeine Ausdrücke (multivariate Polynome) wie z x^2 * y + 2*z + 1
. Darüber hinaus möchte ich bestimmte symbolische Gleichungen beispielsweise über Ausdrücke x^2 + 1 = 1
sowie Definitionen wie ausdrücken x := 2*y - 2
.
Das Ziel ist:
- Haben Sie einen separaten Typ für Variablen und allgemeine Ausdrücke - bestimmte Funktionen können auf Variablen und nicht auf komplexe Ausdrücke angewendet werden. Zum Beispiel kann ein Definitionsoperator kann vom Typ sein
, und es soll nicht möglich sein , einen komplexen Ausdruck als seine linken Seite Parameter zu übergeben (obwohl es sollte möglich sein , eine Variable als seine rechten Seite Parameter zu übergeben, ohne explizite Gießen ) .
:=
(:=) :: Variable -> Expression -> Definition
- Haben Sie Ausdrücke eine Instanz von
Num
, damit es möglich ist, ganzzahlige Literale in Ausdrücke umzuwandeln und eine bequeme Notation für allgemeine algebraische Operationen wie Addition oder Multiplikation zu verwenden, ohne einige zusätzliche Wrapper-Operatoren einzuführen.
Mit anderen Worten, ich möchte eine implizite und statische Umwandlung (Zwang) von Variablen in Ausdrücke. Jetzt weiß ich, dass es in Haskell keine impliziten Typumwandlungen gibt. Dennoch sind bestimmte objektorientierte Programmierkonzepte (in diesem Fall einfache Vererbung) im Typensystem von Haskell entweder mit oder ohne Spracherweiterungen ausdrückbar . Wie kann ich beide oben genannten Punkte erfüllen, während ich eine einfache Syntax behalte? Ist es überhaupt möglich?
Diskussion
Es ist klar, dass das Hauptproblem hier die Typbeschränkung ist Num
, z
(+) :: Num a => a -> a -> a
Grundsätzlich ist es möglich, einen einzelnen (verallgemeinerten) algebraischen Datentyp sowohl für Variablen als auch für Ausdrücke zu schreiben. Dann könnte man so schreiben :=
, dass der Ausdruck auf der linken Seite diskriminiert wird und nur ein variabler Konstruktor akzeptiert wird, ansonsten mit einem Laufzeitfehler. Dies ist jedoch keine saubere, statische Lösung (dh zur Kompilierungszeit) ...
Beispiel
Idealerweise möchte ich eine leichte Syntax wie z
computation = do
x <- variable
t <- variable
t |:=| x^2 - 1
solve (t |==| 0)
Insbesondere möchte ich die Notation verbieten,
t + 1 |:=| x^2 - 1
da :=
sie eine Definition einer Variablen und nicht einen gesamten Ausdruck auf der linken Seite enthalten sollte.
class FromVar e
mit einer Methode verwendenfromVar :: Variable -> e
und Instanzen für und bereitstellenExpression
undVariable
dann Ihre Variablen polymorphe Typenx :: FromVar e => e
usw. haben. Ich habe nicht getestet, wie gut dies funktioniert, da ich gerade auf meinem Telefon bin.FromVar
Typklasse helfen würde. Ich möchte explizite Casts vermeiden, während ichExpr
eine Instanz von behalteNum
. Ich habe die Frage bearbeitet und ein Beispiel für eine Notation hinzugefügt, die ich erreichen möchte.Antworten:
Um Polymorphismus anstelle von Subtypisierung zu nutzen (weil das alles ist, was Sie in Haskell haben), denken Sie nicht, dass "eine Variable ein Ausdruck ist", sondern "sowohl Variablen als auch Ausdrücke haben einige Operationen gemeinsam". Diese Operationen können in eine Typklasse eingeordnet werden:
Dann, anstatt Dinge zu gießen, machen Sie die Dinge polymorph. Wenn
v :: forall e. HasVar e => e
ja, kann es sowohl als Ausdruck als auch als Variable verwendet werden.Skelett, um den folgenden Code zu erstellen: https://gist.github.com/Lysxia/da30abac357deb7981412f1faf0d2103
quelle
V
. Anfangs wollte ich das nicht, aber vielleicht war ich zu schnell, um es zu verwerfen ... Wahrscheinlich kann ich das Undurchsichtige nicht loswerdenV
. Wie kann ich eine Instanz von erstellenV (forall e . HasVar e => e)
? In Coq würde ich Typberechnungen und Mustervergleich für einen induktiven Typ verwenden, aber es ist unklar, wie dies in Haskell erreicht werden kann.w :: Variable
irgendwie eine schnappen und sich darauf bewerbenfromVar
:variable = (\w -> V (fromVar w)) <$> (_TODO_ :: Solver Variable)
.V
könnte mit improvisierten Typen vermieden werden, aber das ist immer noch WIP. Oder wir könnenvariable
die Fortsetzung mit einem polymorphen Argument explizit anstatt indirekt über machen(>>=)
.