Kann ich eine Liste von Erfolgen mit Kurzschlussfehlern über die Zusammensetzung von Anwendungsfunktoren modellieren?

Question

Der Benutzer ‚singpolyma‘ asked on reddit wenn es einige allgemeine Struktur zugrunde liegen:

data FailList a e = Done | Next a (FailList a e) | Fail e 

Ein freies Monade vorgeschlagen wurde, aber ich fragte mich, ob dies generell über applicative functors modelliert werden konnten. In Abstracting with Applicatives zeigt uns Bazerman, dass die Summe von zwei anwendungsbezogenen Funktoren auch ein anwendungsbezogener Funktor ist, mit einer Ausrichtung nach links/rechts, vorausgesetzt, wir haben eine natürliche Transformation in der Richtung der Verzerrung. Das klingt, als ob wir es brauchen! Also habe ich meinen Vorschlag gestartet, bin dann aber schnell auf Probleme gestoßen. Kann jemand Lösungen für diese Probleme ?:

---

Zum einen sehen wir mit der Definition der Summe zweier functors starten. Ich habe hier angefangen, weil wir Sum-Typen modellieren wollen - entweder Erfolge oder Erfolge und einen Misserfolg.

data Sum f g a = InL (f a) | InR (g a) 

Und die beiden functors wir arbeiten wollen, sind:

data Success a = Success [a] 
data Failure e a = Failure e [a] 

Success ist gerade nach vorne - es im Wesentlichen Const [a] ist. Aber Failure e bin ich nicht so sicher. Es ist kein anwendungsspezifischer Funktor, weil pure keine Definition hat. Es ist jedoch eine Instanz von Apply:

instance Functor Success where 
    fmap f (Success a) = Success a 

instance Functor (Failure e) where 
    fmap f (Failure e a) = Failure e a 

instance Apply (Failure e) where 
    (Failure e a) <.> (Failure _ b) = Failure e a 

instance Apply Success where 
    (Success a) <.> (Success b) = Success (a <> b) 

instance Applicative Success where 
    pure = const (Success []) 
    a <*> b = a <.> b 

Als nächstes wir die Summe dieser functors definieren können, mit einer natürlichen Transformation von rechts (so eine linke bias) nach links:

instance (Apply f, Apply g, Applicative g, Natural g f) => Applicative (Sum f g) where 
    pure x = InR $ pure x 
    (InL f) <*> (InL x) = InL (f <*> x) 
    (InR g) <*> (InR y) = InR (g <*> y) 
    (InL f) <*> (InR x) = InL (f <.> eta x) 
    (InR g) <*> (InL x) = InL (eta g <.> x) 

Und das einzige, was wir jetzt tun müssen, ist unsere natürliche Transformation zu definieren, und hier kommt alles zusammen.

instance Natural Success (Failure e) where 
    eta (Success a) = Failure ???? a 

Die Unfähigkeit, ein Failure scheint zu sein, das Problem zu schaffen. Darüber hinaus ist sogar hacky und mit ⊥ ist keine Option, denn diese wird ausgewertet werden, wenn Sie InR (Success ...) <*> InL (Failure ...) haben.

Ich fühle mich wie ich etwas vermisse, aber ich habe keine Ahnung, was es ist.

Kann dies getan werden?

Answer 1

Ich bin mir ziemlich sicher, dass die "richtige" Antwort darin besteht, e ein Monoid zu machen, so wie Sie die Idee auf der reddit Diskussion nicht gemocht haben.

Betrachten Failure "oops" [(*1),(*2),(*3)] <*> Failure "doh" [1,2,3] Sollte das Ergebnis "oops" oder "doh" als Fehler haben?Indem die e ein Monoid wir die Tatsache erfassen, dass es keine kanonische Wahl, und lassen Sie die Verbraucher ihr Gift holen (sei es First, Last, [], etc.)

Beachten Sie, dass diese Lösung, ähnlich wie die (Maybe e, [a]) Darstellung, behandelt nicht richtig Streaming/potenziell unendliche Daten, da es strikt ist, ob wir einen Fehler haben, der die Liste beendet.

Eine andere Codierung würde Fixpoints von Anwendungen verwenden, wie im folgenden Post (http://comonad.com/reader/2013/algebras-of-applicatives/).

Dann nehmen Sie die Listendarstellung dargebotener (FixF (ProductF Embed (Sum (Const()))) a) und es ändern, indem Sie Ihre Fehler Monoid in der Einheit Position kleben, erhalten folgendes:

Monid mon => FixF (ProductF Embed (Sum (Const mon))) a

Und beachten Sie, dass Sie ein verwenden können Maybe anstelle von einem Monoid erhalten genau ein FailList, aber genauso wie mit FailList erhalten Sie dann keine anwendbare Instanz kostenlos, es sei denn Sie schreiben eine, die den richtigen Weg angibt, Fehler zu kombinieren.

Beachten Sie auch, dass mit dem Fixpoint Ansatz, wenn wir das Äquivalent von Success [(*1),(*2),(*3)] <*> Failure "doh" [1,2,3,4,5] haben, dann bekommen wir wieder ein Success mit drei Elementen (dh sind wir wirklich nicht strikt in failure), während in dem Ansatz, den Sie vorschlagen, erhalten wir eine Rück Failure mit drei Elemente und der Fehler aus der Liste der fünf Elementfehler. Das sind die Kompromisse zwischen Streaming und Strict.

Schließlich, und am einfachsten, können wir einfach type FailList e = Product (Const (First e)) ZipList verwenden, um Standardanwendungsmaschinen zu verwenden und etwas sehr nah an den ursprünglichen Datentyp zu bekommen.

Answer 2

{-# LANGUAGE FlexibleInstances #-} 

instance Applicative (Sum Success (Failure e)) where 
    pure x = InL $ pure x 
    (InL f) <*> (InL x) = InL (f <*> x) 
    (InR (Failure e fs)) <*> (InR (Failure _ gs)) = InR (Failure e (fs <*> gs)) 
    (InR (Failure e fs)) <*> (InL (Success gs)) = InR (Failure e (fs <*> gs)) 
    (InL (Success gs)) <*> (InR (Failure e fs)) = InR (Failure e (gs <*> fs)) 

Dies ist, weil Sie immer einen Fehler zu einer Liste der Erfolge hinzufügen können;)

Sie auch diese Art Klasse statt Natural f g verwenden:

class Transplant f g where 
    transplant :: f a -> g b -> f b 

instance Transplant (Failure e) Success where 
    transplant (Failure e _) (Success a) = Failure e a 

Haben Sie keine Ahnung, was es bedeutet Kategorie-Theorie-weise.