Einführung
In Haskell ist es üblich, mit Effekten als Funktoren zu arbeiten, deren Objekte einige Ausdrücke sind, an denen wir im Moment interessiert sind.
Wenn wir die Art des Ausdrucks sehen,
vielleicht a , abstrahieren wir von der tatsächlichen Existenz eines
a und konzentrieren unsere ganze Aufmerksamkeit auf dieses
a . Die gleiche Geschichte mit
Liste a - Pluralwerte von
a ;
Zustand sa -
a , abhängig von einem aktuellen Zustand;
Entweder ea -
a , was einen Fehler zurückgeben kann
e .
Bevor Sie fortfahren, werden in dem Artikel verschiedene Definitionen verwendet:
type (:=) ta = ta
Zum Beispiel:
Liste:. Vielleicht: = a - dieser Ausdruck ist leicht vorstellbar, dies ist eine Liste von Werten, deren Existenz in Frage steht.
Als Beispiel werden wir vier gängige Typen verwenden:
Reader ,
State ,
Entweder ,
Vielleicht .
Kompositionen und Transformatoren
Der naheliegendste Weg, mehr als einen Effekt auf einen Ausdruck anzuwenden, besteht darin, einfach einen in den anderen einzubetten. Dies ist die übliche Zusammensetzung von Funktoren. In Kompositionen haben Effekte keine Auswirkungen aufeinander (es sei denn,
Traversable- Methoden werden über sie angewendet). Und um viele Effekte zu einem zusammenzuführen, werden Transformatoren verwendet. Jede Methode hat ihre Vor- und Nachteile:
Kompositionen:
- Es sind keine zusätzlichen Typen erforderlich, um sie zu erstellen
- Es gibt keine allgemeine Methode zum Zusammenführen von Effekten mit Functor / Applicative / Monad- Klassen
- Alles komponiert wunderbar, bis es um Monaden geht
Transformatoren:
- Ermöglichen das Zusammenführen mehrerer Effekte zu einem
- Sie benötigen jedoch einen separaten Typ (meistens einen neuen Typ).
- Mit lift können Sie Berechnungen für jede Ebene des Transformationsstapels durchführen.
- Sie können die Effekte jedoch nicht separat berücksichtigen, obwohl es spezielle Funktionen gibt
Transformatoren unterscheiden sich von Kupplungszusammensetzungen (ich weiß nicht, wie ich es anders nennen soll). Wenn Sie eine Komposition haben, können Sie daraus einen Transformator machen und umgekehrt. Docking-Schemata helfen uns dabei.
Docking-Schemata
Wenn wir uns die Typen für Monadentransformatoren genauer ansehen, können wir einige Muster identifizieren:
newtype ReaderT rma = ReaderT { runReaderT :: r -> ma } newtype MaybeT ma = MaybeT { runMaybeT :: m (Maybe a) } newtype ExceptT ema = ExceptT { runExceptT :: m (Either ea)) } newtype StateT sma = StateT { runStateT :: s -> m (a,s) }
Transformatoren beschreiben einen speziellen Fall, wie der aktuelle definitive und unbestimmte Effekt ineinander greifen sollte.
Sei nicht eindeutig und
du bist unbestimmt, versuche:
Reader: r -> ua ===> (->) r :. u := a ===> t :. u := a
Einige Effekte sind recht komplex und können durch die Zusammensetzung anderer, einfacherer Effekte definiert werden:
State: s -> u (a, s) ===> (->) s :. (,) s := a ==> t :. u :. t' := a
Wenn wir uns die ersten drei Beispiele genauer ansehen, können wir allgemeine Muster feststellen: Wenn in
Reader ein bestimmter Effekt einen unbestimmten Effekt einschließt (in Klammern gesetzt, zum Objekt eines Funktors wird), dann ist es bei
Entweder und
Vielleicht das Gegenteil - ein unbestimmter Effekt schließt einen bestimmten Effekt ein. Im Fall von
State platzieren wir den Funktor sogar zwischen zwei einfacheren definierten Effekten.
Versuchen wir, diese Muster in Typen auszudrücken:
newtype TU tua = TU (t :. u := a) newtype UT tua = UT (u :. t := a) newtype TUT tut' a = TUT (t :. u :. t' := a)
Wir haben gerade Docking-Schemata definiert - dies ist eine Zusammensetzung von Funktoren in einem Wrapper, die die Position eines bestimmten und unbestimmten Effekts angibt.
Tatsächlich entfernen Methoden für Transformatoren, deren Namen mit
run beginnen
, einfach die Hülle des Transformators und geben die Zusammensetzung der Funktoren zurück. Wir beschreiben eine solche Klasse von Typen:
class Composition t where type Primary ta :: * run :: ta -> Primary ta
Jetzt haben wir eine universelle Möglichkeit, diese Schaltungen zu betreiben:
instance Composition (TU tu) where type Primary (TU tu) a = t :. u := a run (TU x) = x instance Composition (UT tu) where type Primary (UT tu) a = u :. t := a run (UT x) = x instance Composition (TUT tu t') where type Primary (TUT tu t') a = t :. u :. t' := a run (TUT x) = x
Was ist mit Transformatoren? Hier benötigen Sie auch eine Typklasse, in der ein Docking-Schema für einen bestimmten Typ vorgeschrieben ist. Die
Einbettungsmethode wird deklariert, um den unbestimmten Effekt auf das Niveau des Transformators zu erhöhen und einen bestimmten Effekt im Transformator zu konstruieren:
class Composition t => Transformer t where type Schema (t :: * -> *) (u :: * -> *) = (r :: * -> *) | r -> tu embed :: Functor u => u ~> Schema tu build :: Applicative u => t ~> Schema tu type (:>) tua = Transformer t => Schema tua
Jetzt müssen die Instanzen deklariert werden. Beginnen Sie mit
Vielleicht und
Entweder :
instance Transformer Maybe where type Schema Maybe u = UT Maybe u embed x = UT $ Just <$> x build x = UT . pure $ x instance Transformer (Either e) where type Schema (Either e) u = UT (Either e) u embed x = UT $ Right <$> x build x = UT . pure $ x
Wir werden unseren eigenen Typ für
Reader erstellen, da er sich nicht in der
Basis befindet . Außerdem benötigt er eine Instanz der
Composition- Klasse, da es sich um einen Wrapper für den Pfeil-Funktor handelt:
newtype Reader ea = Reader (e -> a) instance Composition (Reader e) where type Primary (Reader e) a = (->) ea run (Reader x) = x instance Transformer (Reader e) where type Schema (Reader e) u = TU ((->) e) u embed x = TU . const $ x build x = TU $ pure <$> run x
Machen Sie etwas Ähnliches mit
State :
newtype State sa = State ((->) s :. (,) s := a) instance Composition (State s) where type Primary (State s) a = (->) s :. (,) s := a run (State x) = x instance Transformer (State s) where type Schema (State s) u = TUT ((->) s) u ((,) s) embed x = TUT $ \s -> (s,) <$> x build x = TUT $ pure <$> run x
Als Beispiel
Es bleibt, dies an den Problemen der realen Welt zu testen - als Beispiel werden wir ein Programm schreiben, das die korrekte Platzierung verschiedener Arten von Klammern berechnet.
Definieren Sie Typen für Klammern: Sie können geöffnet und geschlossen werden. und haben auch verschiedene Stile:
data Shape = Opened | Closed data Style = Round | Square | Angle | Curly
Andere Symbole unseres Programms sind nicht interessant:
data Symbol = Nevermind | Bracket Style Shape
Wir definieren auch eine Liste von Fehlern, auf die unser Programm stoßen kann:
data Stumble = Deadend (Int, Style)
Welche Effekte braucht unser Programm? Wir müssen eine Liste der Klammern führen, die auf die Überprüfung warten, und wir müssen beim ersten aufgetretenen Fehler anhalten. Wir machen einen Transformator:
State [(Int, Style)] :> Either Stumble := ()
Der Algorithmus ist einfach: Wir gehen die Struktur mit indizierten Klammern durch. Wenn wir nach der Passage keinen Fehler festgestellt haben und die Klammern immer noch im Status sind, hat die offene Klammer keine geschlossene:
checking :: Traversable t => t (Int, Symbol) -> Either Stumble () checking struct = run (traverse proceed struct) [] >>= \case (s : _, _) -> Left . Logjam $ s where ([], _) -> Right ()
Wir erinnern uns an jede offene Klammer, vergleichen jede geschlossene mit der zuletzt gespeicherten offenen:
proceed :: (Int, Symbol) -> State [(Int, Style)] :> Either Stumble := () proceed (_, Nevermind) = pure () proceed (n, Bracket style Opened) = build . modify . (:) $ (n, style) procceed (n, Bracket closed Closed) = build get >>= \case []-> embed $ Left . Deadend $ (n, closed) ((m, opened) : ss) -> if closed /= opened then embed . Left $ Mismatch (m, opened) (n, closed) else build $ put ss where
Fazit
Mithilfe von Docking-Schemata mit einer Zusammensetzung von Funktoren können wir sie in Transfomere umwandeln und umgekehrt. Leider funktioniert ein solcher Trick bei der Mutter der Monaden nicht - Fortsetzungen. Und das alles, weil sie sich nicht als Komposition von Funktoren vorstellen lassen, aber es ist als Komposition von Profunktoren möglich ... Und doch ist dies eine ganz andere Geschichte.
Bibliothekscode auf Github |
Hackage-Dokumentation |
Beispiel für Klammern