Kann ich eine Liste von Erfolgen modellieren, indem ich das Versagen kurzzuschließe durch die Komposition von applikativen Funktoren?

Question

Der Benutzer 'singpolyma' fragte auf reddit nach, ob es eine allgemeine Struktur gibt, die folgendem zugrunde liegt:

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

Es wurde ein Free-Monad vorgeschlagen, aber ich fragte mich, ob dies allgemeiner über applikative Funktoren modelliert werden könnte. In Abstrahieren mit Applikatoren zeigt uns Bazerman, dass die Summe zweier applikativer Funktoren ebenfalls ein applikativer Funktor ist, mit Bias nach links/rechts, vorausgesetzt, wir haben eine natürliche Transformation in Richtung des Bias. Das klingt so, als ob das das ist, was wir brauchen! Also begann ich mit meinem Vorschlag, stieß dann aber schnell auf Probleme. Kann jemand Lösungen für diese Probleme sehen?:

---

Zunächst starten wir mit der Definition der Summe zweier Funktoren. Ich habe hier angefangen, weil wir Summentypen modellieren wollen - entweder Erfolge oder Erfolge und ein Scheitern.

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

Und die beiden Funktoren, mit denen wir arbeiten wollen, sind:

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

Success ist einfach - es ist im Wesentlichen Const [a]. Allerdings bin ich mir bei Failure e nicht sicher. Es ist kein applikativer 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

Dann können wir die Summe dieser Funktoren definieren, mit einer natürlichen Transformation von rechts nach links (also einem Linksbias):

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 bricht alles zusammen.

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

Die Unfähigkeit, ein Failure zu erzeugen, scheint das Problem zu sein. Darüber hinaus ist selbst ein hackiges Verwenden von keine Option, weil dies im Fall, dass InR (Success ...) <*> InL (Failure ...) aufgerufen wird, ausgewertet wird.

Ich habe das Gefühl, dass mir etwas fehlt, aber ich habe keine Ahnung, was es ist.

Ist dies machbar?

Answer 1

Ich bin mir ziemlich sicher, dass die "richtige" Antwort ist, e zu einem Monoid zu machen, auch wenn dir die Idee in der Reddit-Diskussion nicht gefallen hat.

Betrachte Failure "oops" [(*1),(*2),(*3)] <*> Failure "doh" [1,2,3] Sollte das Ergebnis "oops" oder "doh" als Fehler haben? Indem wir das e zu einem Monoid machen, erfassen wir die Tatsache, dass es keine kanonische Wahl gibt, und lassen den Verbraucher sein Gift wählen (sei es First, Last, [] usw.)

Beachten Sie, dass diese Lösung, ähnlich wie die Darstellung (Maybe e, [a]), nicht korrekt mit Streaming/potenziell unendlichen Daten umgeht, da sie streng ist, ob wir ein Scheitern haben, das die Liste beendet.

Eine andere Kodierung würde Fixpunkte von Applikativen verwenden, wie im Nachfolgebeitrag beschrieben (http://comonad.com/reader/2013/algebras-of-applicatives/).

Dann nehmen Sie die dort präsentierte Listendarstellung (FixF (ProductF Embed (Sum (Const ()))) a) und ändern Sie sie, indem Sie Ihren Fehler-Monoid an die Einheitsposition stecken, um folgendes zu erhalten:

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

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

Beachten Sie auch, dass bei Ansatz des Fixpunkts, wenn wir das Äquivalent von Success [(*1),(*2),(*3)] <*> Failure "doh" [1,2,3,4,5] haben, erhalten wir eine Success mit drei Elementen zurück (d. h. wir sind wirklich nicht streng in Fehler), während bei Ihrem Vorschlag erhalten wir eine Failure mit drei Elementen und den Fehler aus der fünf Elemente fehlschlagende Liste. So sind die Kompromisse von Streaming vs. streng.

Schließlich und am einfachsten können wir einfach type FailList e = Product (Const (First e)) ZipList nehmen, um Standard-Applicative-Mechanismen zu verwenden und etwas sehr ähnliches zum ursprünglichen Datentyp zu erhalten.

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))

This is because you can always add a failure to a list of successes ;)

You may also use this type class instead of Natural f g:

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

Have no idea what it means category-theory-wise.