Wie Muster gegen Typklasse, deren Instanz rekursive Datentypen sind Muster?

Question

Diese Frage ist eine Folge auf How to pattern match against a typeclass value?.

Ich beginne ein Haustier-Projekt mit Logik erster Ordnung und habe mich entschieden, Haskell für diesen Zweck zu verwenden. Meine erste Hürde ist eine ‚Formel der Logik ersten Ordnung‘ zu definieren, damit der Datentyp:

data Formula v = Belong v v      -- x in y 
       | Bot        -- False 
       | Imply (Formula v) (Formula v) -- p -> q 
       | Forall v (Formula v)   -- forall x, p 

Allerdings ist mir nur ungern Code zu schreiben, basierend auf den Details der Implementierung, und würde eher abstrahiert die Details, in Fall, dass ich meine Meinung, oder für den Fall ändern will ich Funktionalität mit einer alternativen Implementierung wieder zu verwenden, damit die typeclass:

class FirstOrder m where 
    belong :: v -> v -> m v 
    bot  :: m v 
    imply  :: m v -> m v -> m v 
    forall :: v -> m v -> m v 
    asFormula :: m v -> Formula v 

ich die letzte Funktion asFormula um die ViewPatterns zu verwenden, hinzugefügt habe (wie in dem obigen Link vorgeschlagen), um Muster für die Werte dieser Typklasse zuordnen zu können.

Jetzt nehme ich eine einfache Funktion definieren möchten:

subst :: (FirstOrder m) => (v -> w) -> m v -> m w 

, welche Variablen in einer Formel gemäß einer bestimmten Zuordnung f::v -> w (fühlt sich an wie fmap) ersetzt, so dass die Formel belong x y auf belong (f x) (f y) abgebildet usw. dann ViewPatterns mit:

subst f (asFormula -> Belong x y) = belong (f x) (f y) 

so weit, so gut ...

jedoch bei dem Versuch, subst f p->q = (subst f p) -> (subst f q) schreiben:

subst f (asFormula -> Imply p q) = imply (subst f p) (subst f q) 

ich eine Art Fehlermeldung erhalten, die es durchaus Sinn macht zu denken kommen: das Pattern-Matching bindet p und q auf Elemente vom Typ Formula v in Bezug auf die gewünschte Art gegen m v.

Jetzt kann ich das Problem zu sehen, und auch durch das Hinzufügen einer fromFormula Funktion zum typeclass auf den Typen m v zu konvertieren zurück, aber ich denke das ist verrückt von einer Performance-Sicht denkt, könnte es von Möglichkeiten zur Lösung (genauso verrückt wie asFormula wohlgemerkt), ein riesiger Preis zu zahlen, um den Code generisch zu halten.

Also hier bin ich jetzt, versuche, eine einfache Funktion durch strukturelle Rekursion auf einer freien Algebra (rekursive Datentyp) zu definieren, aber mein Wunsch, die Implementierungsdetails wegzusortieren (und schreiben Code aus Typklasse statt Datentyp) mich in eine scheinbar unmögliche Position bringen.

Gibt es einen Ausweg, oder sollte ich einfach Abstraktion vergessen und mit dem rekursiven Datentyp arbeiten?

Answer 1

Dies sieht wie eine Übergeneralisierung aus, aber ignorieren wir das trotzdem.

Sie können das mit expliziten F- (Co-) Algebren und Fixpunkten lösen.Dann

data FormulaF v k 
    = Belong v v      -- x in y 
    | Bot        -- False 
    | Imply (k v) (k v)    -- p -> q 
    | Forall v (k v)     -- forall x, p 

newtype Formula v = Formula (FormulaF v Formula)  
    -- fixed point. You might not need it, but it's nice to have. 
    -- 

, können Sie

class FirstOrder m where 
    belong :: v -> v -> m v 
    bot  :: m v 
    imply  :: m v -> m v -> m v 
    forall :: v -> m v -> m v 
    asFormula :: m v -> FormulaF v m 

und

subst :: (FirstOrder m) => (v -> w) -> m v -> m w 
subst f (asFormula -> Belong x y) = belong (f x) (f y) 
subst f (asFormula -> Imply p q) = imply (subst f p) (subst f q) 

jetzt sollte, arbeiten, weil asFormula nicht die ganze m v in eine volle Formel rekursiv umwandeln, aber es verwandelt sich in ein FormulaF v m sieht wie eine Formel oberflächlich (der allererste Konstruktor Sie Muster übereinstimmen, wie Imply), aber tief im Inneren immer noch aussehen s als m v.

Wenn Sie diesen generellen Ansatz wirklich verfolgen wollen, sollten Sie sich vielleicht , F-Algebren und F-Coalgebren sowie deren assoziierte Kata-/Ana-/Hylo-/Para-/was auch immer Morphismen ansehen.

Schließlich würde ich vorschlagen, zu vermeiden, zu versuchen, OOP Entwurfsmuster in FP anzupassen. Manchmal kann man etwas schuhen, aber es kann oft unidiomatisch sein. Zum Beispiel sind wir in Haskell ziemlich gewohnt, Typen mit einer festen Anzahl von Konstruktoren (aber eine offene Menge von Funktionen, die auf ihnen arbeiten), genau wie in OOP-Schnittstellen haben eine feste Anzahl von Methoden (aber eine offene Reihe von Unterklassen) . Man kann versuchen, dies zu verallgemeinern, aber es ist komplex und sollte nur bei Bedarf durchgeführt werden.