Warum sind ArrowApply und Monads im Gegensatz zu Arrow und Applicative gleichbedeutend mit gegenseitigem Nachgeben?

8

Hier ist der SO-Beitrag, auf den ich mich beziehen werde .Außerdem werde ich in dieser Frage dieselben Schnipsel wie das OP verwenden, um die Materialien nicht zu trennen .

Es ist allgemein bekannt, dass eine ArrowApplyInstanz eine Monade ergibt und umgekehrt:

newtype ArrowMonad a b = ArrowMonad (a () b)

instance Arrow a => Functor (ArrowMonad a) where
    fmap f (ArrowMonad m) = ArrowMonad $ m >>> arr f

instance Arrow a => Applicative (ArrowMonad a) where
   pure x = ArrowMonad (arr (const x))
   ArrowMonad f <*> ArrowMonad x = ArrowMonad (f &&& x >>> arr (uncurry id))

instance ArrowApply a => Monad (ArrowMonad a) where
    ArrowMonad m >>= f = ArrowMonad $
        m >>> arr (\x -> let ArrowMonad h = f x in (h, ())) >>> app

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

instance Monad m => Category (Kleisli m) where
    id = Kleisli return
    (Kleisli f) . (Kleisli g) = Kleisli (\b -> g b >>= f)

instance Monad m => Arrow (Kleisli m) where
    arr f = Kleisli (return . f)
    first (Kleisli f) = Kleisli (\ ~(b,d) -> f b >>= \c -> return (c,d))
    second (Kleisli f) = Kleisli (\ ~(d,b) -> f b >>= \c -> return (d,c))

Und bis ich auf den oben genannten Beitrag gestoßen bin , hatte ich das Gefühl, dass dieser Ausschnitt ein plausibler Beweis für die Gleichwertigkeit ArrowApplyund MonadKlassen ist. Das Wissen, dass Arrow und Applicative tatsächlich nicht gleichwertig sind, und der folgende Ausschnitt haben mich neugierig gemacht auf den vollständigen Beweis der Gleichwertigkeit von Monadund ArrowApply:

newtype Arrplicative arr o a = Arrplicative{ runArrplicative :: arr o a }

instance (Arrow arr) => Functor (Arrplicative arr o) where
    fmap f = Arrplicative . (arr f .) . runArrplicative

instance (Arrow arr) => Applicative (Arrplicative arr o) where
    pure = Arrplicative . arr . const

    Arrplicative af <*> Arrplicative ax = Arrplicative $
        arr (uncurry ($)) . (af &&& ax)

newtype Applicarrow f a b = Applicarrow{ runApplicarrow :: f (a -> b) }

instance (Applicative f) => Category (Applicarrow f) where
    id = Applicarrow $ pure id
    Applicarrow g . Applicarrow f = Applicarrow $ (.) <$> g <*> f

instance (Applicative f) => Arrow (Applicarrow f) where
    arr = Applicarrow . pure
    first (Applicarrow f) = Applicarrow $ first <$> f

> Wenn Sie also eine Rundreise durch die Anwendung machen, verlieren Sie einige Funktionen. Es ist offensichtlich, ob die Beispiele bereitgestellt werden, aber ich verstehe nicht, wie beim "Roundtripping" durch Monad alle ArrowApply-Funktionen erhalten bleiben, da wir anfangs einen Pfeil hatten, der von einer Eingabe abhängt ( a b c), aber am Ende haben wir Ein Pfeil, der in einen Wrapper gezwungen wird, dessen Eingabetyp der Einheitentyp ist ( ArrowMonad (a () b)).

Es ist offensichtlich, dass ich hier etwas furchtbar Falsches mache, aber ich kann nicht genau verstehen, was.

Was ist der vollständige Beweis dafür, dass ArrowApplyundMonad sind gleichwertig?

Was bedeuten die Beispiele für die Ungleichwertigkeit von ArrowundApplicative erklären erklären ? Verallgemeinert einer den anderen?

Wie ist die Interpretation dieser ganzen Situation in der Pfeilrechnung und der Kategorietheorie?

Ich würde mich sowohl über vollständige Erklärungen als auch über Tipps freuen, die dazu beitragen könnten, selbst einen plausiblen Beweis zu erstellen.

Zhiltsoff Igor
quelle

Antworten:

3

da wir anfangs einen Pfeil hatten, der von einer Eingabe abhängt ( a b c), aber am Ende haben wir einen Pfeil, der in einen Wrapper gezwungen wird, dessen Eingabetyp der Einheitentyp ist ( ArrowMonad (a () b))

Ich denke, dies ist der zentrale Punkt der Verwirrung, und tatsächlich ist es verwirrend. Ich stelle mir Pfeile gerne als Morphismen in einer kartesischen monoidalen Kategorie vor, in der man das nicht bekommen würde, aber schon ist die ArrowKlasse dank arr- was dir einen Funktor von Hask in die Kategorie gibt - tatsächlich restriktiver . Etwas überraschend bedeutet dies jedoch auch, dass Sie eine Zuordnung in die andere Richtung erhalten: Jeder Pfeil kann durch eine Funktion ersetzt werden, die lediglich einen Pfeil mit trivialer Domäne ergibt. Konkret,

arrAsFunction :: Arrow k => k x y -> (x -> k () y)
arrAsFunction φ x = φ <<< arr (const x)

Ok, das allein wäre nicht zu bahnbrechend - vielleicht haben wir hier nur einige Informationen verworfen? - aber ArrowApplydamit ist eigentlich ein Isomorphismus : Sie können den ursprünglichen Pfeil über zurückbekommen

retrieveArrowFromFunction ::  k x y .
          ArrowApply k => (x -> k () y) -> k x y
retrieveArrowFromFunction f = arr f' >>> app
 where f' :: x -> (k () y, ())
       f' x = (f x, ())

... was genau in der Monad (ArrowMonad a)Instanz verwendet wird.

Das Ergebnis lautet also: Indem arrSie verlangen, dass Sie eine beliebige Haskell-Funktion in die Kategorie einbetten können, wird erzwungen, dass die Kategorie im Wesentlichen auf Funktionen mit einem Wrapper um das Ergebnis hinausläuft, IOW so etwas wie Kleisli-Pfeile.

Schauen Sie sich einige andere kategorietheoretische Hierarchien an, um festzustellen, dass dies kein grundlegendes Merkmal kartesischer monoidaler Kategorien ist, sondern ein Artefakt des Haskk- Funktors. ZB in eingeschränkten Kategorien habe ich die Standardklassen genau gespiegelt, mit PreArrowder Klasse der kartesischen monoidalen Kategorien, aber absichtlich arrherausgehalten und nicht spezifisch für Hask gemacht , weil dies die Fähigkeiten der Kategorie zu sehr beeinträchtigt und bewirkt, dass es fast gleichwertig mit Hask- Kleisli ist.

links herum
quelle
Vielen Dank für Ihre Antwort - es macht jetzt viel mehr Sinn! Gibt es einen Grund, warum dieser Teil mit dem Isomorphismus oft nicht berücksichtigt wird, wenn von ArrowApply / Monad-Äquivalenz gesprochen wird? Oder habe ich einfach eine intuitive Spur mit einem strengen Beweis verwechselt?
Zhiltsoff Igor
Nun, "Monaden sind gleichbedeutend mit Pfeilen, die den Typ Isomorphismus ABA → (1 ↝ B ) erfüllen " ... das ist genau dort in der Zusammenfassung des ahnungslosen / akribischen / promiskuitiven Papiers. Warum diese POV normalerweise nicht so oft diskutiert wird, weiß ich nicht.
Links um den