Ich arbeite derzeit an einem einfachen Interpreter für eine Programmiersprache und habe einen Datentyp wie diesen:
data Expr
= Variable String
| Number Int
| Add [Expr]
| Sub Expr Expr
Und ich habe viele Funktionen, die einfache Dinge tun wie:
-- Substitute a value for a variable
substituteName :: String -> Int -> Expr -> Expr
substituteName name newValue = go
where
go (Variable x)
| x == name = Number newValue
go (Add xs) =
Add $ map go xs
go (Sub x y) =
Sub (go x) (go y)
go other = other
-- Replace subtraction with a constant with addition by a negative number
replaceSubWithAdd :: Expr -> Expr
replaceSubWithAdd = go
where
go (Sub x (Number y)) =
Add [go x, Number (-y)]
go (Add xs) =
Add $ map go xs
go (Sub x y) =
Sub (go x) (go y)
go other = other
Aber in jeder dieser Funktionen muss ich den Teil, der den Code rekursiv aufruft, mit nur einer kleinen Änderung an einem Teil der Funktion wiederholen. Gibt es eine Möglichkeit, dies allgemeiner zu tun? Ich möchte diesen Teil lieber nicht kopieren und einfügen:
go (Add xs) =
Add $ map go xs
go (Sub x y) =
Sub (go x) (go y)
go other = other
Und ändern Sie jedes Mal einen einzelnen Fall, da es ineffizient erscheint, Code wie diesen zu duplizieren.
Die einzige Lösung, die ich finden könnte, besteht darin, eine Funktion zu haben, die zuerst eine Funktion für die gesamte Datenstruktur und dann rekursiv für das Ergebnis wie folgt aufruft:
recurseAfter :: (Expr -> Expr) -> Expr -> Expr
recurseAfter f x =
case f x of
Add xs ->
Add $ map (recurseAfter f) xs
Sub x y ->
Sub (recurseAfter f x) (recurseAfter f y)
other -> other
substituteName :: String -> Int -> Expr -> Expr
substituteName name newValue =
recurseAfter $ \case
Variable x
| x == name -> Number newValue
other -> other
replaceSubWithAdd :: Expr -> Expr
replaceSubWithAdd =
recurseAfter $ \case
Sub x (Number y) ->
Add [x, Number (-y)]
other -> other
Aber ich denke, es sollte wahrscheinlich schon einen einfacheren Weg geben, dies zu tun. Vermisse ich etwas
Add :: Expr -> Expr -> Expr
stattAdd :: [Expr] -> Expr
undSub
ganz loswerden .recurseAfter
heißtana
in der Verkleidung. Vielleicht möchten Sie sich Anamorphismen und ansehenrecursion-schemes
. Davon abgesehen denke ich, dass Ihre endgültige Lösung so kurz wie möglich ist. Der Wechsel zu den offiziellenrecursion-schemes
Anamorphismen spart nicht viel.Antworten:
Herzlichen Glückwunsch, Sie haben gerade Anamorphismen wiederentdeckt!
Hier ist Ihr Code, der so umformuliert wurde, dass er mit dem
recursion-schemes
Paket funktioniert . Leider ist es nicht kürzer, da wir eine Kesselplatte brauchen, damit die Maschinen funktionieren. (Es könnte einen automatischen Weg geben, um das Boilerplate zu vermeiden, z. B. mit Generika. Ich weiß es einfach nicht.)Unten wird Ihr
recurseAfter
durch den Standard ersetztana
.Wir definieren zunächst Ihren rekursiven Typ sowie den Funktor, dessen Fixpunkt er ist.
Dann verbinden wir die beiden mit einigen Instanzen, damit wir uns
Expr
in das Isomorphe entfaltenExprF Expr
und es zurückfalten können.Schließlich passen wir Ihren ursprünglichen Code an und fügen einige Tests hinzu.
Eine Alternative könnte darin bestehen,
ExprF a
nur zu definieren und dann abzuleitentype Expr = Fix ExprF
. Dies spart einen Teil der oben genannten Kesselplatte (z. B. die beiden Instanzen) auf Kosten der VerwendungFix (VariableF ...)
anstelleVariable ...
der analogen für die anderen Konstruktoren.Man könnte dies weiter mildern, indem man Mustersynonyme verwendet (allerdings auf Kosten von etwas mehr Boilerplate).
Update: Ich habe endlich das Automagic-Tool mit der Vorlage Haskell gefunden. Dies macht den gesamten Code ziemlich kurz. Beachten Sie, dass der
ExprF
Funktor und die beiden oben genannten Instanzen noch unter der Haube vorhanden sind und wir sie weiterhin verwenden müssen. Wir sparen nur den Aufwand, sie manuell definieren zu müssen, aber das allein spart viel Aufwand.quelle
Expr
explizit definieren , anstatt so etwastype Expr = Fix ExprF
?Fix
+ den echten Konstruktor. Die Verwendung des letzten Ansatzes mit TH-Automatisierung ist besser, IMO.Als alternativer Ansatz ist dies auch ein typischer Anwendungsfall für das
uniplate
Paket. Es kannData.Data
Generika anstelle von Template Haskell verwenden, um das Boilerplate zu generieren. Wenn Sie alsoData
Instanzen für Folgendes ableitenExpr
:dann wendet die
transform
Funktion vonData.Generics.Uniplate.Data
eine Funktion rekursiv auf jedes verschachtelte anExpr
:Beachten Sie, dass
replaceSubWithAdd
insbesondere die Funktionf
so geschrieben ist, dass sie eine nicht rekursive Substitution durchführt.transform
macht es rekursiv inx :: Expr
, so dass es der Helferfunktion dieselbe Magie verleiht wieana
in @ chis Antwort:Dies ist nicht kürzer als die Template Haskell-Lösung von @ chi. Ein möglicher Vorteil besteht darin, dass
uniplate
einige zusätzliche Funktionen bereitgestellt werden, die hilfreich sein können. Wenn Sie beispielsweisedescend
anstelle von verwendentransform
, werden nur die unmittelbaren untergeordneten Elemente transformiert, wodurch Sie steuern können, wo die Rekursion stattfindet, oder Sie könnenrewrite
das Ergebnis von Transformationen erneut transformieren, bis Sie einen festen Punkt erreichen. Ein möglicher Nachteil ist, dass "Anamorphismus" viel cooler klingt als "uniplate".Vollständiges Programm:
quelle