Explication du foncteur applicatif en termes catégoriques - foncteurs monoïdaux

40

J'aimerais comprendre Applicativeen termes de théorie des catégories.

La documentation de ce documentApplicative indique qu’il s’agit d’ un foncteur fort monoïdal laxiste .

Premièrement, la page Wikipedia sur les foncteurs monoïdaux indique qu’un foncteur monoïdal est laxiste ou fort . Il me semble donc que l'une ou l'autre des sources est fausse ou qu'elle utilise les termes différemment. Quelqu'un peut-il expliquer cela?

Deuxièmement, quelles sont les catégories monoïdales qui Applicativesont des foncteurs monoïdaux? Je suppose que les foncteurs sont des endo-foncteurs de la catégorie standard de Haskell (objets = types, morphismes = fonctions), mais je n'ai aucune idée de la structure monoïdale de cette catégorie.

Merci pour l'aide.

Petr Pudlák
la source

Réponses:

35

Il y a en fait deux utilisations du mot "force" en jeu ici.

  • Un endofoncteur fort sur une catégorie monoïdale ( C , , I ) en est un qui vient avec une transformation naturelle σ : A F ( B ) F ( A B ) , satisfaisant certaines conditions de cohérence en ce qui concerne l'associateur que je vais passer sous silence. Cette condition est parfois aussi prononcée " F a une force".F:CC(C,,I)σ:AF(B)F(AB)F

  • A lax monoidal foncteur est un foncteur entre deux catégories monoïdales ( C , , I ) et ( D , , J ) avec des transformations naturelles de : F ( A ) F (F:C(C,,je)(,,J) et i : J F ( I )φ:F(UNE)F(B)F(UNEB)je:JF(je), satisfaisant encore une condition de cohérence vis-à-vis des associateurs.

  • A foncteur forte monoidal est celui dans lequel & phiv et i sont des isomorphismes naturels. C'est, F ( A F:Cφje , avec φ et son inverse Décrivant la isomorphisme.F(UNEB)F(UNE)F(B)φ

Un foncteur applicatif, au sens des programmes Haskell, est un endofoncteur monoïdale de laxisme avec une force , avec la structure monoïdale en question étant les produits cartésiens. C’est la raison pour laquelle vous obtenez le terme à consonance paradoxale "foncteur fort monoïdal laxiste".

En passant, dans une catégorie fermée cartésienne, ayant une force équivaut à l'existence d'une transformation naturelle m a p : (F . C'est-à-dire qu'avoir une force signifie que l'action funorale peut être définie comme une fonction d'ordre supérieur dans le langage de programmation.munep:(UNEB)(F(UNE)F(B))

Enfin, si vous êtes intéressé par la théorie des types de foncteurs applicatifs de style Haskell, je viens de bloguer à ce sujet.

Neel Krishnaswami
la source
1
Merci d'avoir répondu. Dois-je bien comprendre que toutes les instances de Functoront une force (produit WRT), simplement parce qu'elles sont définies en utilisant fmaple langage? De plus, ce qui me laisse perplexe sur le fait que votre définition de et i soit inversée par rapport à la fois à votre article de blog et à l'article de Wikipedia - s'agit-il d'une faute de frappe? J'ai essayé de définir utiliser comme , ce qui est clairement nécessaire . φjepureipure' = \v -> fmap (\() -> v) (i ())i :: (Applicative f) => () -> f ()
Petr Pudlák
1
J'ai eu une faute de frappe dans cette réponse - maintenant corrigé. Et oui, toutes les instances de Functorsont fortes (par rapport au produit).
Neel Krishnaswami
Pourriez-vous également préciser où se trouve Monad? Si je comprends bien, il s’agit également d’un endofoncteur monoïdal.
egdmitry
@egdmitry Monoidal , pas monadal . Cela signifie que nous traitons avec un endofoncteur d’une catégorie monoïdale (dans ce cas, est monoïdal par rapport au produit cartésien, c’est-à-dire des paires). Hask
Kirelagin
Puis-je proposer d'utiliser le mot strengthy pour éviter choc de la notation avec « forte »? C'est une variante dialectale «forte» écossaise (utilisée de manière particulièrement pertinente ici), utilisée pour la première fois dans la Bible de Wycliffe.
Fosco
3

Pour comprendre l’application, telle qu’indiquée par une monade, je souhaite signaler la construction suivante:

Le lemme de Yoneda implique qu'il existe un isomorphisme entre et n a t ( H o m ( A , B ) , F B ) . Dans la catégorie des types Haskell, il s'agit de la cartographie a ( g F ( g ) ( a ) ) de type F A B A , puis en appliquant la carte des flèches des foncteurs à la fonction résultante - si les composants de la transformation naturelle sens comme des flèches - et abstraiteFUNEnunet(Hom(UNE,B),FB)

une(gF(g)(une))
Evaluer en F A
FUNEBUNEFB.
FUNE nouveau, nous obtenons une cartographie de type F A FFUNE Maintenant, si le foncteur est livré avec une 'jointure' monadique, mappant de F F B à F B , et si nous commutons autour des abstractions lambda et donc des deux premiers emplacements d'arguments, nous pouvons obtenir une fonction de type F
FUNEFBUNEFFB.
FFBFB
FBUNEFUNEFB,
LjeFtM2 je
Nikolaj-K
la source