La théorie de Monad et Haskell

un avertissement rapide: je suis un peu chancelant sur la théorie des catégories en général, alors que j'ai l'impression que vous avez au moins une certaine familiarité avec elle. J'espère que je ne vais pas en faire trop d'un hachage de ce...

est-ce que quelqu'un connaît un tutoriel qui commence par la théorie des catégories et explique IO, état, liste des monades dans ces termes?

tout d'Abord, ignorer IO pour l'instant, c'est plein de magie noire. Il fonctionne comme un modèle de calculs impératifs pour les mêmes raisons que State fonctionne pour la modélisation de calculs stateful, mais à la différence de ce dernier IO est une boîte noire sans moyen de déduire la structure monadique de l'extérieur.

le fonctionnement est habituellement montré avec le type: (A -> b) -> (m A -> m b) j'ai inclus le deuxième support juste pour souligner la symétrie.

mais, ceci est un endofunctor, donc ne devrait pas le domaine et arrivée être le même comme cela?:

je soupçonne que vous êtes une mauvaise interprétation de la façon dont les variables de type dans Haskell se rapportent aux concepts de la théorie des catégories.

tout d'abord, oui, qui spécifie un endofuncteur, sur la catégorie des types Haskell. Une variable de type telle que a n'est cependant rien dans cette catégorie; c'est une variable qui est (implicitement) universellement quantifiée sur tous les objets de la catégorie. Ainsi, le type (a -> b) -> (a -> b) décrit seulement endofuncteurs qui mappent chaque objet à lui-même .

"1519320920 de Type" constructeurs de décrire une fonction injective sur des objets, où les éléments du constructeur de l'arrivée ne peut pas être décrite par tous les moyens, sauf que l'application d'un constructeur de type. Même si deux types de constructeurs produisent des résultats isomorphiques, les types résultants restent distincts. Notez que les constructeurs de type ne sont pas, dans le cas général, des foncteurs.

la variable de type m dans la signature du foncteur, représente alors un constructeur de type à un argument. Hors contexte, cela serait normalement considéré comme une quantification universelle, mais c'est incorrect dans ce cas car aucune fonction de ce type ne peut exister. La définition de la classe de type lie plutôt m et permet la définition de telles fonctions pour les constructeurs de type spécifiques .

la fonction résultante, alors, dit que pour tout type constructeur m qui a fmap défini, pour deux objets a et b et un morphisme entre eux, nous pouvons trouver un morphisme entre les types donnés en appliquant m à a et b .

notez que bien que ce qui précède, bien sûr, définit un endofuncteur sur Hask , il n'est même pas assez général loin pour décrire tous tels endofuncteurs.

mais les transformations naturelles réelles que nous utilisons ont le type:

a -> m

m a - > (a - >m b) - > m B

S'agit-il des sous-ensembles de la forme générale ci-dessus? et pourquoi sont-elles des transformations naturelles?

Eh bien, non, ils ne le sont pas. Une transformation naturelle est à peu près une fonction (et non un functor) entre les functeurs. Les deux naturel les transformations qui spécifient un monad m ressemblent à I -> M où I est le functeur d'identité, et M ∘ M -> M où ∘ est la composition de functeur. Dans Haskell, nous n'avons pas de bonne façon de travailler directement avec un véritable foncteur d'identité ou avec une composition de foncteur. Au lieu de cela, nous rejetons la fonction d'identité pour obtenir juste (Functor m) => a -> m a pour la première, et écrivons l'application de constructeur de type imbriquée comme (Functor m) => m (m a) -> m a pour la seconde.

La première, c'est évidemment return ; la seconde est une fonction appelée join , qui ne fait pas partie de la classe type. Cependant, join peut être écrit en termes de (>>=) , et ce dernier est plus souvent utile dans la programmation quotidienne.

---

en ce qui concerne les monades spécifiques, si vous voulez une description plus mathématique, voici un croquis rapide d'un exemple:

pour certains types fixes, considérons deux functors F et G où F(x) = (S, x) et G(x) = S -> x (il devrait être évident qu'il s'agit bien de functors valides).

ces fonctions sont aussi des adjoints; considérons les transformations naturelles unit :: x -> G (F x) et counit :: F (G x) -> x . L'élargissement des définitions nous donne unit :: x -> (S -> (S, x)) et counit :: (S, S -> x) -> x . Les types suggèrent application de fonction non pressé et la construction de tuples; n'hésitez pas à vérifier que ces travaux comme prévu.

An la contiguïté donne lieu à une monade par la composition des foncteurs, donc en prenant G Pip et en élargissant la définition, on obtient G (F x) = S -> (S, x), qui est la définition de la monade State . Le unit pour la contiguïté est bien sûr return ; et vous devriez pouvoir utiliser counit pour définir join .

Ce la page est exactement ce que fait. Je pense que votre principale confusion est que la classe ne fait pas vraiment le type A functor, mais elle définit un functor de la catégorie des types Haskell dans la catégorie de ce type.

suivant la notation de la liaison, en supposant que F est un foncteur Haskell, cela signifie qu'il y a un foncteur de la catégorie de Hask à la catégorie de F.

grossièrement parlant, Haskell fait sa théorie des catégories tout en une seule catégorie, dont les objets sont des types Haskell et dont les flèches sont des fonctions entre ces types. Ce n'est certainement pas un langage universel pour modéliser la théorie des catégories.

un foncteur (mathématique) est une opération qui transforme des choses dans une catégorie en choses dans une autre, peut-être entièrement différente. Un endofunctor est alors un functor qui se trouve avoir la même source et catégories ciblées. Dans Haskell, un functor est une opération de transformation des choses dans la catégorie des types Haskell en d'autres choses aussi dans la catégorie des types Haskell, il est donc toujours un endofuncteur.

[si vous suivez la Littérature Mathématique, techniquement, l'opération "(a - >b)->(m a - > m b) "n'est que la partie Flèche de l'endofuncteur m, et "m" est la partie objet ]

Quand Haskellers parler de travailler "dans une monade" signifie vraiment travailler dans la catégorie Kleisli de la monade. La catégorie Kleisli d'une monade est une bête complètement déroutante au début, et nécessite normalement au moins deux couleurs d'encre pour donner une bonne explication, alors prenez la tentative suivante pour ce qu'elle est et vérifiez quelques références (malheureusement Wikipedia est inutile ici pour tous sauf les définitions droites).

supposons que vous ayez un monad 'm' sur la catégorie C des types Haskell. Son Kleisli category Kl(m) a les mêmes objets que C, à savoir les types Haskell, mais une flèche a ~(f)~> B en Kl(m) est une flèche A- (F)-> mb en C. (j'ai utilisé une ligne squiggly dans ma flèche Kleisli pour distinguer les deux). Pour rappel: les objets et les flèches du Kl(C) sont aussi des objets et des flèches du C mais les flèches pointent vers des objets différents en Kl (C) qu'en C. Si cela ne vous semble pas étrange, relisez-le avec plus de soin!

concrètement, considérez le peut-être monad. Son Kleisli catégorie est juste la collection de Haskell types, et ses flèches un ~(f)~> b sont des fonctions de a -(f)-> Peut-être que b. Ou de considérer l' (État s) monade dont les flèches sont un ~(f)~> b sont des fonctions de a -(f)-> (État s b) == a(f)-> (s->(s,b)). Dans tous les cas, vous écrivez toujours une flèche en forme de sigle pour faire quelque chose au type de nom de code de vos fonctions.

[Note que l'État n'est pas une monade, parce que l'État est * -> * -> *, de sorte que vous devez fournir l'un des tapez des paramètres pour en faire une monade mathématique.]

So far So good, je l'espère, mais supposons que vous souhaitez composer des flèches un ~(f)~> b et b ~(g)~> c. Ce sont vraiment des Haskell fonctions a -(f)-> mo et b -(g)-> mc que vous ne pouvez pas composer parce que les types ne correspondent pas. La solution mathématique est d'utiliser la "multiplication" transformation naturelle u:mm->m de la monade comme suit: a ~f)~> b ~(g)~> c == a -(f)-> mo -(mg)-> mmc(u_c)-> mc pour obtenir une flèche->mc qui est une flèche Kleisli A ~(f; g)~ > c au besoin.

peut-être qu'un exemple concret aide ici. Dans le Monad peut-être, vous ne pouvez pas composer des fonctions f : A -> peut-être B et g : B - > peut-être c directement, mais en soulevant g à

Maybe_g :: Maybe b -> Maybe (Maybe c)
Maybe_g Nothing = Nothing
Maybe_g (Just a) = Just (g a)

et en utilisant le "évident "

u :: Maybe (Maybe c) -> Maybe c
u Nothing = Nothing
u (Just Nothing) = Nothing
u (Just (Just c)) = Just c

vous pouvez former la composition u . Maybe_g . f qui est la fonction a -> peut-être c que vous vouliez.

dans le (les États) monad, c'est similaire, mais messier: étant Donnés deux monadique des fonctions d'une ~(f)~> b et b ~(g)~> c qui sont vraiment un -(f)-> (s->(s,b)) et b -(g)-> (s->(s,c)) sous le capot, vous les composer en soulevant g dans

State_s_g :: (s->(s,b)) -> (s->(s,(s->(s,c))))
State_s_g p s1 = let (s2, b) = p s1 in (s2, g b)

puis vous appliquez la' multiplication 'transformation naturelle u, qui est

u :: (s->(s,(s->(s,c)))) -> (s->(s,c))
u p1 s1 = let (s2, p2) = p1 s1 in p2 s2

qui (en quelque sorte) enferme l'état final de f dans l'état initial de g .

à Haskell, il s'avère pour être un peu une façon non naturelle de travailler, il y a donc la fonction (>>=) qui fait essentiellement la même chose que u, mais d'une manière qui le rend plus facile à mettre en œuvre et à utiliser. c'est important: (>>=) n'est pas la transformation naturelle 'u'. Vous pouvez définir chacun en termes de l'autre, donc ils sont équivalents, mais ils ne sont pas la même chose. La version Haskell de 'u' est écrite join .

l'autre chose manquante de ce la définition des catégories Kleisli est l'identité sur chaque objet: a ~(1_a)~> a qui est vraiment a -(n_a) -> ma où n est la transformation naturelle de l '"unité". Ceci est écrit return dans Haskell, et ne semble pas causer autant de confusion.

j'ai appris la théorie des catégories avant de venir à Haskell, et j'ai moi aussi eu des difficultés avec le décalage entre ce que les mathématiciens appellent une monade et ce à quoi ils ressemblent à Haskell. Ce n'est pas plus facile de l'autre côté!

Je ne suis pas sûr de comprendre quelle était la question, mais oui, vous avez raison, monad dans Haskell est défini comme un triple:

m :: * -> * -- this is endofunctor from haskell types to haskell types!
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b

mais la définition commune de la théorie des catégories est un autre triple:

m :: * -> *
return :: a -> m a
join ::  m (m a) -> m a

c'est un peu confus mais il n'est pas si difficile de montrer que ces deux définitions sont égales. Pour ce faire, nous devons définir join en termes de (>>=) (et vice versa). Première étape:

join :: m (m a) -> m a
join x = ?

cela nous donne x :: m (m a) .

Tout ce que nous pouvons faire avec quelque chose qui ont le type m _ est de mettre (>>=) à elle:

(x >>=) :: (m a -> m b) -> m b

maintenant nous avons besoin de quelque chose comme second argument pour ( > > = ), et aussi, du type de jointure nous avons la contrainte (x >>= y) :: ma .

Ainsi y ici aura le type y :: ma -> ma et id :: a -> a s'adapte très bien:

join x = x >>= id

(>>=) :: ma -> (a -> mb) -> m b
(>>=) x y = ?

où x :: m a et y :: a -> m b . Pour obtenir m b de x et y nous avons besoin de quelque chose du type a .

Malheureusement, nous ne pouvons pas extraire a de m a . Mais nous pouvons le substituer à autre chose (rappelez-vous, monad est aussi un foncteur):

fmap :: (a -> b) -> m a -> m b
fmap y x :: m (m b)

et il convient parfaitement comme argument pour join : (>>=) x y = join (fmap y x) .

la meilleure façon de regarder les monades et les effets computationnels est de commencer par où Haskell a obtenu la notion de monades pour les effets computationnels de, et puis regarder Haskell après vous comprenez que. Voir cet article en particulier: Notions de calcul et monades , par E. Moggi.

Voir Aussi L'article précédent de Moggi qui montre comment les monades fonctionnent pour le calcul lambda seul: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.2787

le fait que les monades capturent la substitution, entre autres choses (http://blog.sigfpe.com/2009/12/where-do-monads-come-from.html), et la substitution est la clé du calcul lambda, devrait donner un bon indice quant à la raison pour laquelle ils ont tant de pouvoir expressif.

bien que les monades proviennent à l'origine de la théorie des catégories, cela ne signifie pas que la théorie des catégories est le seul contexte abstrait dans lequel vous pouvez les voir. Un point de vue différent est donné par sémantique opérationnelle . Pour une introduction, regardez mon tutoriel .

une façon de regarder IO est de le considérer comme une sorte étrange de monade d'état. Rappelez-vous que la monade d'état ressemble à:

data State s a = State (s -> (s, a))

où l'argument" s " est le type de données que vous voulez faire passer à travers le calcul. De plus, cette version de "State" n'a pas d'actions "get" et "put" et nous n'exportons pas le constructeur.

imaginez maintenant un type

data RealWorld = RealWorld ......

cela n'a pas de définition réelle, mais théoriquement un valeur du type RealWorld tient l'état de l'univers entier en dehors de l'ordinateur. Bien sûr, nous ne pouvons jamais avoir une valeur de type RealWorld, mais vous pouvez imaginer quelque chose comme:

getChar :: RealWorld -> (RealWorld, Char)

en d'autres termes la fonction" getChar " prend un État de l'univers avant que le bouton du clavier ait été pressé, et renvoie la touche pressée plus l'état de l'univers après que la touche ait été pressée. Bien sûr, le problème est que l'état précédent du monde est toujours disponible pour être référencé, ce qui ne peut pas se produire dans la réalité.

mais maintenant nous écrivons ceci:

type IO = State RealWorld

getChar:: Io Char

théoriquement, tout ce que nous avons fait est envelopper la version précédente de "getChar" comme une action d'état. Mais ce faisant, nous ne pouvons plus accéder aux valeurs du "monde réel" parce qu'elles sont enveloppées dans la monade de l'état.

donc quand un programme Haskell il veut changer une ampoule il prend possession de l'ampoule et applique une fonction "rotation" à la valeur du monde réel à L'intérieur de IO.

pour moi, jusqu'à présent, l'explication qui se rapproche le plus de relier les monades dans la théorie des catégories et les monades dans Haskell est que les monades sont un monid dont les objets ont le type a->m B. Je peux voir que ces objets sont très proches d'un endofuncteur et donc la composition de telles fonctions sont liées à une séquence impérative d'énoncés de programme. Les fonctions qui renvoient des fonctions IO sont également valables en code fonctionnel pur jusqu'à ce que la fonction interne soit appelée de l'extérieur.

cet élément d'identification est "a -> M a" qui correspond très bien mais l'élément de multiplication est la composition de la fonction qui devrait être:

(>=>) :: Monad m = > (a - > m b) - > (b - > m C) - > (A - > m C)

ce n'est pas tout à fait la composition de fonction, mais assez proche (je pense que pour obtenir la composition de fonction vraie nous avons besoin d'une fonction complémentaire qui transforme m b en a, puis nous obtenons la composition de fonction si nous appliquons ceux-ci par paires?), Je ne suis pas tout à fait sûr de savoir comment pour en arriver là:

(>>=) :: Monad m = > m a - > (A - > m b) - > m B

j'ai le sentiment que j'ai pu voir une explication de cela dans tout ce que j'ai lu, sans en comprendre la signification la première fois, donc je vais faire un peu de relecture pour essayer de (re)trouver une explication de cela.

l'autre chose que je voudrais faire est de lier ensemble toutes les différentes explications de la théorie des catégories: endofunctor+2 naturel transformations, catégorie Kleisli, un monoïde dont les objets sont des monoïdes et ainsi de suite. Pour moi la chose qui semble lier toutes ces explications, c'est qu'ils sont à deux niveaux. C'est-à-dire que, normalement, nous traitons les objets de catégorie comme des boîtes noires où nous impliquons leurs propriétés à partir de leurs interactions externes, mais ici, il semble qu'il y ait un besoin d'aller un niveau à l'intérieur des objets pour voir ce qui se passe? Nous pouvons expliquer les monades sans cela, mais seulement si nous acceptons des constructions apparemment arbitraires.

Martin

voir cette question: les opérations de chaînage sont-elles la seule chose que la classe monad résout?

dans cela, j'explique ma vision que nous devons différencier entre la classe Monad et les types individuels qui résolvent des problèmes individuels. La classe Monad, à elle seule, ne résout que le problème important de "enchaîner les opérations avec le choix" et met cette solution à la disposition des types en étant l'instance (au moyen de l ' "héritage").

d'un autre côté, si un type donné qui résout un problème donné fait face au problème de" enchaîner les opérations avec le choix " alors, il devrait être fait une instance (héritée) de la classe Monad.

le fait est que les problèmes ne sont pas résolus simplement en étant une monade. Ce serait comme dire que les "roues" résolvent beaucoup de problèmes, mais en fait les "roues" ne résolvent qu'un problème, et les choses avec des roues résolvent beaucoup de problèmes différents.