Implizite statische Besetzung (Zwang) in Haskell

9

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 = 1sowie Definitionen wie ausdrücken x := 2*y - 2.

Das Ziel ist:

  1. 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
  2. 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 - 1da :=sie eine Definition einer Variablen und nicht einen gesamten Ausdruck auf der linken Seite enthalten sollte.

Maciej Bendkowski
quelle
1
Vielleicht könnten Sie eine class FromVar emit einer Methode verwenden fromVar :: Variable -> eund Instanzen für und bereitstellen Expressionund Variabledann Ihre Variablen polymorphe Typen x :: FromVar e => eusw. haben. Ich habe nicht getestet, wie gut dies funktioniert, da ich gerade auf meinem Telefon bin.
Mor A.
Ich bin mir nicht sicher, wie die FromVarTypklasse helfen würde. Ich möchte explizite Casts vermeiden, während ich Expreine Instanz von behalte Num. Ich habe die Frage bearbeitet und ein Beispiel für eine Notation hinzugefügt, die ich erreichen möchte.
Maciej Bendkowski

Antworten:

8

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:

class HasVar e where fromVar :: Variable -> e

instance HasVar Variable where fromVar = id
instance HasVar Expression where ...

Dann, anstatt Dinge zu gießen, machen Sie die Dinge polymorph. Wenn v :: forall e. HasVar e => eja, kann es sowohl als Ausdruck als auch als Variable verwendet werden.

example :: (forall e. HasVar e => e) -> Definition
example v = (v := v)  -- v can be used as both Variable and Expression

 where

  (:=) :: Variable -> Expression -> Definition

Skelett, um den folgenden Code zu erstellen: https://gist.github.com/Lysxia/da30abac357deb7981412f1faf0d2103

computation :: Solver ()
computation = do
  V x <- variable
  V t <- variable
  t |:=| x^2 - 1
  solve (t |==| 0)
Li-yao Xia
quelle
Interessant, danke! Ich überlegte, für einen kurzen Moment sowohl Variablen als auch Ausdrücke hinter existenziellen Typen zu verstecken, lehnte die Idee jedoch ab, da sie eine zusätzliche Notation einführte V. Anfangs wollte ich das nicht, aber vielleicht war ich zu schnell, um es zu verwerfen ... Wahrscheinlich kann ich das Undurchsichtige nicht loswerden V. Wie kann ich eine Instanz von erstellen V (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.
Maciej Bendkowski
1
Sie können sich w :: Variableirgendwie eine schnappen und sich darauf bewerben fromVar: variable = (\w -> V (fromVar w)) <$> (_TODO_ :: Solver Variable).
Li-yao Xia
1
Und Vkönnte mit improvisierten Typen vermieden werden, aber das ist immer noch WIP. Oder wir können variabledie Fortsetzung mit einem polymorphen Argument explizit anstatt indirekt über machen (>>=).
Li-yao Xia