Les flèches sont exactement équivalentes aux foncteurs applicatifs ?

Question

Selon le célèbre article Les idiomes sont inconscients, les flèches sont méticuleuses, les monades sont libertines. le pouvoir expressif des flèches (sans classes de types supplémentaires) devrait se situer strictement entre les foncteurs applicatifs et les monades : les monades sont équivalentes à ArrowApply et Applicative devraient être équivalentes à ce que l'article appelle des "flèches statiques". Cependant, je ne vois pas très bien ce que signifie la restriction de ce caractère "statique".

En jouant avec les trois classes de types en question, j'ai pu construire une équivalence entre les foncteurs applicatifs et les flèches, que je présente ci-dessous dans le contexte de l'équivalence bien connue entre les flèches et les foncteurs applicatifs. Monad y ArrowApply . Cette construction est-elle correcte ? (J'ai prouvé la plupart des lois des flèches avant de s'en lasser). Cela ne signifie-t-il pas que Arrow y Applicative sont exactement les mêmes ?

{-# LANGUAGE TupleSections, NoImplicitPrelude #-}
import Prelude (($), const, uncurry)

-- In the red corner, we have arrows, from the land of * -> * -> *
import Control.Category
import Control.Arrow hiding (Kleisli)

-- In the blue corner, we have applicative functors and monads,
-- the pride of * -> *
import Control.Applicative
import Control.Monad

-- Recall the well-known result that every monad yields an ArrowApply:
newtype Kleisli m a b = Kleisli{ runKleisli :: a -> m b}

instance (Monad m) => Category (Kleisli m) where
    id = Kleisli return
    Kleisli g . Kleisli f = Kleisli $ g <=< f

instance (Monad m) => Arrow (Kleisli m) where
    arr = Kleisli . (return .)
    first (Kleisli f) = Kleisli $ \(x, y) -> liftM (,y) (f x)

instance (Monad m) => ArrowApply (Kleisli m) where
    app = Kleisli $ \(Kleisli f, x) -> f x

-- Every arrow arr can be turned into an applicative functor
-- for any choice of origin o
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)

-- Arrplicatives over ArrowApply are monads, even
instance (ArrowApply arr) => Monad (Arrplicative arr o) where
    return = pure
    Arrplicative ax >>= f =
        Arrplicative $ (ax >>> arr (runArrplicative . f)) &&& id >>> app

-- Every applicative functor f can be turned into an arrow??
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

Answer 1

Chaque applicatif produit une flèche et chaque flèche produit un applicatif, mais ils ne sont pas équivalents. Si vous avez une flèche arr et un morphisme arr a b il ne s'ensuit pas que l'on puisse générer un morphisme arr o (a \to b) qui reproduit sa fonctionnalité. Ainsi, si vous faites un aller-retour avec l'applicatif, vous perdez certaines fonctionnalités.

Les applicatifs sont des foncteurs monoïques. Les flèches sont des profoncteurs qui sont aussi des catégories, ou de manière équivalente, des monoïdes dans la catégorie des profoncteurs. Il n'y a pas de lien naturel entre ces deux notions. Veuillez excuser ma désinvolture : En Hask, il s'avère que la partie foncteur du pro-foncteur dans une flèche est un foncteur monoïde, mais cette construction oublie nécessairement la partie "pro".

Lorsque vous passez des flèches aux applicatifs, vous ignorez la partie d'une flèche qui prend en compte les entrées et vous n'utilisez que la partie qui traite des sorties. De nombreuses flèches intéressantes utilisent la partie entrée d'une manière ou d'une autre et donc, en les transformant en applicatifs, vous renoncez à des éléments utiles.

Cela dit, en pratique, je trouve que l'applicatif est une abstraction plus agréable à utiliser et qu'il fait presque toujours ce que je veux. En théorie, les flèches sont plus puissantes, mais je ne les utilise pas en pratique.

Answer 2

Comparons le foncteur applicatif IO avec les flèches de Kleisli de la monade IO.

Vous pouvez avoir une flèche qui imprime une valeur lue par une flèche précédente :

runKleisli ((Kleisli $ \() -> getLine) >>> Kleisli putStrLn) ()

Mais on ne peut pas faire ça avec les foncteurs applicatifs. Avec les foncteurs applicatifs, tous les effets se produisent avant appliquer la fonction-dans-le-functeur aux arguments-dans-le-functeur. La fonction dans le foncteur ne peut pas utiliser la valeur d'un argument dans le foncteur pour "moduler" son propre effet, pour ainsi dire.

Answer 3

(J'ai posté le texte ci-dessous sur mon blog avec une introduction détaillée)

Tom Ellis a suggéré de réfléchir à un exemple concret impliquant l'entrée/sortie de fichiers. Comparons donc trois approches à l'aide des trois classes de types. Pour simplifier les choses, nous ne nous intéresserons qu'à deux opérations : lire une chaîne de caractères dans un fichier et écrire une chaîne de caractères dans un fichier. Les fichiers seront identifiés par leur chemin d'accès :

type FilePath = String

E/S monadiques

Notre première interface d'E/S est définie comme suit :

data IOM    
instance Monad IOM
readFile  FilePath  IOM String
writeFile  FilePath  String  IOM ()

Grâce à cette interface, nous pouvons par exemple copier un fichier d'un chemin à un autre :

copy  FilePath  FilePath  IOM ()
copy from to = readFile from >>= writeFile to

Cependant, nous pouvons faire bien plus que cela : le choix des fichiers que nous manipulons peut dépendre des effets en amont. Par exemple, la fonction ci-dessous prend un fichier index qui contient un nom de fichier, et le copie dans le répertoire cible donné :

copyIndirect  FilePath  FilePath  IOM ()
copyIndirect index target = do
    from  readFile index
    copy from (target / to)

D'un autre côté, cela signifie qu'il n'y a aucun moyen de connaître à l'avance l'ensemble des noms de fichiers qui seront manipulés par une valeur donnée. action IOM . Par "immédiat", j'entends la capacité d'écrire une fonction pure fileNames :: IOM [FilePath] .

Bien sûr, pour les monades non basées sur l'OI (telles que celles pour lesquelles nous disposons d'une sorte de fonction d'extracteur ), cette distinction devient un peu plus floue, mais il est toujours logique de penser à essayer d'extraire des informations sans évaluer les effets de la monade (ainsi, par exemple, nous pourrions demander "que pouvons-nous savoir d'un Reader sans avoir une valeur de type à portée de main ? ").

La raison pour laquelle nous ne pouvons pas vraiment faire d'analyse statique dans ce sens sur les monades est que la fonction du côté droit d'un bind se trouve dans l'espace des fonctions Haskell et, en tant que telle, est complètement opaque.

Essayons donc de restreindre notre interface à un simple foncteur applicatif.

E/S applicatives

data IOF    
instance Applicative IOF
readFile  FilePath  IOF String
writeFile  FilePath  String  IOF ()

Desde IOF n'est pas une monade, il n'y a aucun moyen de composer readFile y writeFile Par conséquent, tout ce que nous pouvons faire avec cette interface, c'est soit lire à partir d'un fichier et post-traiter purement son contenu, soit écrire dans un fichier ; mais il n'y a aucun moyen d'écrire le contenu d'un fichier dans un autre.

Que diriez-vous de changer le type de writeFile ?

writeFile  FilePath  IOF (String  ())

Le principal problème de cette interface est que, même si elle permet d'écrire quelque chose comme

copy  FilePath  FilePath  IOF ()
copy from to = writeFile to * readFile from

cela conduit à toutes sortes de problèmes désagréables parce que String () est un modèle horrible pour écrire une chaîne de caractères dans un fichier, car il brise la transparence référentielle. Par exemple, que voulez-vous que le contenu de out.txt après avoir exécuté ce programme ?

( write  [write "foo", write "bar", write "foo"]) $ writeFile "out.txt"

Deux approches des E/S fléchées

Tout d'abord, il convient d'éliminer deux interfaces d'E/S basées sur des flèches qui n'apportent rien de nouveau (en fait, elles ne peuvent rien apporter) : Kleisli IOM y Applicarrow IOF .

La flèche de Kleisli de IOM modulo currying, est :

readFile  Kleisli IOM FilePath String
writeFile  Kleisli IOM (FilePath, String) ()

Desde writeFile contient toujours le nom du fichier et son contenu, nous pouvons toujours écrire copyIndirect (en utilisant la notation des flèches pour plus de simplicité). Notez comment le ArrowApply exemple de Kleisli IOM n'est même pas utilisé.

copyIndirect  Kleisli IOM (FilePath, FilePath) ()
copyIndirect = proc (index, target)  do
    from  readFile  index
    s  readFile  from
    writeFile  (to, s)

El Applicarrow de IOF serait :

readFile  FilePath  Applicarrow IOF () String
writeFile  FilePath  String  Applicarrow IOF () ()

qui, bien sûr, présente toujours le même problème d'incapacité à composer. readFile y writeFile .

Une interface E/S fléchée appropriée

Au lieu de transformer IOM o IOF en une flèche, et si nous partions de zéro et essayions de créer quelque chose entre les deux, en termes d'utilisation des fonctions Haskell et de création d'une flèche ? Prenons l'interface suivante :

data IOA      
instance Arrow IOA
readFile  FilePath  IOA () String
writeFile  FilePath  IOA String ()

Parce que writeFile prend le contenu du côté entrée de la flèche, nous pouvons toujours implémenter copy :

copy  FilePath  FilePath  IOA () ()
copy from to = readFile from >>> writeFile to

Cependant, l'autre argument de writeFile est purement fonctionnelle, et donc elle ne peut pas dépendre de la sortie de e.g. readFile donc copyIndirect ne peut pas être mis en œuvre avec ce Interface de la flèche.

Si nous retournons cet argument, cela signifie également que, bien que nous ne puissions pas savoir à l'avance ce qui sera écrit dans un fichier (avant d'exécuter la procédure complète d'enregistrement de l'enregistrement), nous ne pouvons pas savoir ce qui sera écrit dans un fichier. IOA ), mais nous pouvons déterminer de manière statique l'ensemble des noms de fichiers qui seront modifiés.

Conclusion

Les monades sont opaques à l'analyse statique et les foncteurs applicatifs ne permettent pas d'exprimer les dépendances de données en temps dynamique. Il s'avère que les flèches peuvent fournir un point d'équilibre entre les deux : en choisissant soigneusement les entrées purement fonctionnelles et les entrées fléchées, il est possible de créer une interface qui permet une interaction parfaite entre le comportement dynamique et l'accessibilité à l'analyse statique.