Différentes façons de voir une monade

29

Tout en apprenant Haskell, j'ai fait face à de nombreux tutoriels essayant d'expliquer ce que sont les monades et pourquoi les monades sont importantes dans Haskell. Chacun d'eux a utilisé des analogies, il serait donc plus facile de saisir le sens. À la fin de la journée, je me retrouve avec 3 vues différentes de ce qu'est une monade:

Vue 1: Monade comme étiquette

Parfois, je pense qu'une monade comme une étiquette à un type spécifique. Par exemple, une fonction de type:

myfunction :: IO Int

myfunction est une fonction qui, chaque fois qu'elle est effectuée, produira une valeur Int. Le type du résultat n'est pas Int mais IO Int. Ainsi, IO est une étiquette de la valeur Int avertissant l'utilisateur de savoir que la valeur Int est le résultat d'un processus où une action IO a été effectuée.

Par conséquent, cette valeur Int a été marquée comme valeur provenant d'un processus avec IO, par conséquent, cette valeur est "sale". Votre processus n'est plus pur.

Vue 2: Monade comme un espace privé où des choses désagréables peuvent se produire.

Dans un système où tous les processus sont purs et stricts, vous devez parfois avoir des effets secondaires. Ainsi, une monade n'est qu'un petit espace qui vous permet de faire des effets secondaires désagréables. Dans cet espace, vous êtes autorisé à échapper au monde pur, à devenir impur, à faire votre processus et à revenir avec une valeur.

Vue 3: Monade comme dans la théorie des catégories

C'est le point de vue que je ne comprends pas complètement. Une monade n'est qu'un foncteur de la même catégorie ou d'une sous-catégorie. Par exemple, vous avez les valeurs Int et en tant que sous-catégorie IO Int, qui sont les valeurs Int générées après un processus IO.

Ces vues sont-elles correctes? Quel est le plus précis?

Oni
la source
5
# 2 n'est pas ce qu'est une monade en général. En fait, il est à peu près limité aux E / S et non à une vue utile (cf. Ce que n'est pas une monade ). De plus, «strict» est généralement utilisé pour nommer une propriété que Haskell ne possède pas (à savoir une évaluation stricte). Soit dit en passant, les monades ne changent pas cela non plus (encore une fois, ce n'est pas une monade).
3
Techniquement, seul le troisième est correct. La monade est endofuncteur, pour laquelle une opération spéciale est définie - promotion et reliure. Les monades sont nombreuses - une liste de monades est un exemple parfait pour obtenir l'intuition derrière les monades. les installations de lecture sont encore meilleures. Assez surprenant, les monades sont utilisables comme outils pour enfiler implicitement l'état dans un langage fonctionnel pur. Ce n'est pas une propriété déterminante des monades: c'est une coïncidence, que le thread d'état peut être implémenté dans leurs termes. La même chose s'applique à IO.
permeakra
Common Lisp a son propre compilateur dans le langage. Haskell a des monades.
Will Ness

Réponses:

33

Les vues # 1 et # 2 sont incorrectes en général.

  1. N'importe quel type de données * -> *peut fonctionner comme une étiquette, les monades sont bien plus que cela.
  2. (À l'exception de la IOmonade) les calculs au sein d'une monade ne sont pas impurs. Ils représentent simplement des calculs que nous percevons comme ayant des effets secondaires, mais ils sont purs.

Ces deux malentendus proviennent de la concentration sur la IOmonade, qui est en fait un peu spéciale.

J'essaierai de développer un peu le # 3, sans entrer dans la théorie des catégories si possible.


Calculs standard

Tous les calculs dans un langage de programmation fonctionnelle peuvent être considérés comme des fonctions avec un type de source et un type de cible: f :: a -> b. Si une fonction a plus d'un argument, nous pouvons la convertir en fonction à un argument par curry (voir aussi le wiki Haskell ). Et si nous avons juste une valeur x :: a(fonction avec 0 arguments), on peut le convertir en une fonction qui prend un argument du type d'unité : (\_ -> x) :: () -> a.

Nous pouvons construire des programmes plus complexes à partir de programmes plus simples en composant ces fonctions à l'aide de l' .opérateur. Par exemple, si nous avons f :: a -> bet g :: b -> cnous obtenons g . f :: a -> c. Notez que cela fonctionne aussi pour nos valeurs converties: si nous l'avons x :: aet le convertissons en notre représentation, nous obtenons f . ((\_ -> x) :: () -> a) :: () -> b.

Cette représentation a des propriétés très importantes, à savoir:

  • Nous avons une fonction très spéciale - la fonction d' identitéid :: a -> a pour chaque type a. C'est un élément d'identité par rapport à .: fest égal à la fois à f . idet à id . f.
  • L'opérateur de composition de fonction .est associatif .

Calculs monadiques

Supposons que nous voulons sélectionner et travailler avec une catégorie spéciale de calculs, dont le résultat contient quelque chose de plus que la seule valeur de retour. Nous ne voulons pas spécifier ce que "quelque chose de plus" signifie, nous voulons garder les choses aussi générales que possible. La façon la plus générale de représenter «quelque chose de plus» est de la représenter comme une fonction de type - un type mde type * -> *(c'est-à-dire qu'elle convertit un type en un autre). Donc, pour chaque catégorie de calculs avec laquelle nous voulons travailler, nous aurons une fonction de type m :: * -> *. (Dans Haskell, mest [], IO, Maybe, etc.) et la catégorie volonté contient toutes les fonctions de types a -> m b.

Maintenant, nous aimerions travailler avec les fonctions d'une telle catégorie de la même manière que dans le cas de base. Nous voulons pouvoir composer ces fonctions, nous voulons que la composition soit associative, et nous voulons avoir une identité. Nous avons besoin:

  • Pour avoir un opérateur (appelons-le <=<) qui compose des fonctions f :: a -> m bet g :: b -> m cen quelque chose comme g <=< f :: a -> m c. Et, il doit être associatif.
  • Pour avoir une fonction d'identité pour chaque type, appelons-la return. Nous voulons également que ce f <=< returnsoit la même chose que fla même chose que return <=< f.

Tout ce m :: * -> *pour quoi nous avons de telles fonctions returnet <=<est appelé une monade . Il nous permet de créer des calculs complexes à partir de calculs plus simples, tout comme dans le cas de base, mais maintenant les types de valeurs de retour sont transformés par m.

(En fait, j'ai un peu abusé du terme catégorie ici. Dans le sens de la théorie des catégories, nous ne pouvons appeler notre construction une catégorie qu'après avoir su qu'elle obéit à ces lois.)

Monades à Haskell

Dans Haskell (et dans d'autres langages fonctionnels), nous travaillons principalement avec des valeurs, pas avec des fonctions de types () -> a. Ainsi, au lieu de définir <=<pour chaque monade, nous définissons une fonction (>>=) :: m a -> (a -> m b) -> m b. Une telle définition alternative est équivalente, nous pouvons l'exprimer en >>=utilisant <=<et vice versa (essayez comme un exercice, ou voyez les sources ). Le principe est moins évident maintenant, mais il reste le même: nos résultats sont toujours de types m aet nous composons des fonctions de types a -> m b.

Pour chaque monade que nous créons, nous ne devons pas oublier de vérifier cela returnet d' <=<avoir les propriétés que nous recherchons: associativité et identité gauche / droite. Exprimé en utilisant returnet >>=ils sont appelés les lois de la monade .

Un exemple - listes

Si nous choisissons md'être [], nous obtenons une catégorie de fonctions de types a -> [b]. Ces fonctions représentent des calculs non déterministes, dont les résultats peuvent être une ou plusieurs valeurs, mais également aucune valeur. Cela donne naissance à la soi-disant monade de liste . La composition de f :: a -> [b]et g :: b -> [c]fonctionne comme suit: g <=< f :: a -> [c]signifie calculer tous les résultats possibles de type [b], appliquer gà chacun d'eux et rassembler tous les résultats dans une seule liste. Exprimé à Haskell

return :: a -> [a]
return x = [x]
(<=<) :: (b -> [c]) -> (a -> [b]) -> (a -> [c])
g (<=<) f  = concat . map g . f

ou en utilisant >>=

(>>=) :: [a] -> (a -> [b]) -> [b]
x >>= f  = concat (map f x)

Notez que dans cet exemple, les types de retour étaient [a]donc il était possible qu'ils ne contiennent aucune valeur de type a. En effet, pour une monade, le type de retour ne doit pas avoir de telles valeurs. Certaines monades ont toujours (comme IOou State), mais d'autres non, comme []ou Maybe.

La monade IO

Comme je l'ai mentionné, la IOmonade est quelque peu spéciale. Une valeur de type IO asignifie une valeur de type aconstruite en interagissant avec l'environnement du programme. Donc (contrairement à toutes les autres monades), nous ne pouvons pas décrire une valeur de type en IO autilisant une construction pure. Voici IOsimplement une balise ou une étiquette qui distingue les calculs qui interagissent avec l'environnement. C'est (le seul cas) où les vues # 1 et # 2 sont correctes.

Pour la IOmonade:

  • Composition f :: a -> IO bet g :: b -> IO cmoyens: calcul fqui interagit avec l'environnement, puis calcul gqui utilise la valeur et calcule le résultat en interaction avec l'environnement.
  • returnajoute simplement le IO"tag" à la valeur (nous "calculons" simplement le résultat en gardant l'environnement intact).
  • Les lois de monade (associativité, identité) sont garanties par le compilateur.

Quelques notes:

  1. Puisque les calculs monadiques ont toujours le type de résultat de m a, il n'y a aucun moyen de "s'échapper" de la IOmonade. La signification est la suivante: une fois qu'un calcul interagit avec l'environnement, vous ne pouvez pas construire à partir de lui un calcul qui ne fonctionne pas.
  2. Lorsqu'un programmeur fonctionnel ne sait pas comment faire quelque chose de manière pure, il peut (en dernier recours) programmer la tâche par un calcul avec état dans la IOmonade. C'est pourquoi IOest souvent appelé le bac à péché d' un programmeur .
  3. Notez que dans un monde impur (au sens de la programmation fonctionnelle), la lecture d'une valeur peut également changer l'environnement (comme consommer les entrées de l'utilisateur). C'est pourquoi les fonctions comme getChardoivent avoir un type de résultat IO something.
Petr Pudlák
la source
3
Très bonne réponse. Je précise que cela IOn'a pas de sémantique particulière du point de vue de la langue. Ce n'est pas spécial, il se comporte comme n'importe quel autre code. Seule l'implémentation de la bibliothèque d'exécution est spéciale. En outre, il existe un moyen spécial de s'échapper ( unsafePerformIO). Je pense que c'est important parce que les gens pensent souvent IOcomme un élément de langage spécial ou une balise déclarative. Ce n'est pas.
usr
2
@usr Bon point. J'ajouterais que unsafePerformIO est vraiment dangereux et ne devrait être utilisé que par des experts. Il vous permet de tout casser, par exemple, vous pouvez créer une fonction coerce :: a -> bqui convertit deux types (et planter votre programme dans la plupart des cas). Voir cet exemple - vous pouvez même convertir une fonction en Intetc.
Petr Pudlák
Une autre monade "magique spéciale" serait ST, qui vous permet de déclarer des références à la mémoire que vous pouvez lire et écrire comme bon vous semble (bien que seulement dans la monade), puis vous pouvez extraire un résultat en appelantrunST :: (forall s. GHC.ST.ST s a) -> a
sara
5

Vue 1: Monade comme étiquette

"Par conséquent, cette valeur Int a été marquée comme valeur provenant d'un processus avec IO, cette valeur est donc" sale "."

"IO Int" n'est pas en général une valeur Int (bien qu'elle puisse être dans certains cas comme "return 3"). Il s'agit d'une procédure qui génère une valeur Int. Différentes exécutions de cette "procédure" peuvent donner des valeurs Int différentes.

Une monade m, est un "langage de programmation" embarqué (impératif): dans ce langage il est possible de définir quelques "procédures". Une valeur monadique (de type ma), est une procédure dans ce "langage de programmation" qui sort une valeur de type a.

Par exemple:

foo :: IO Int

est une procédure qui génère une valeur de type Int.

Ensuite:

bar :: IO (Int, Int)
bar = do
  a <- foo
  b <- foo
  return (a,b)

est une procédure qui produit deux Ints (éventuellement différents).

Chacune de ces "langues" prend en charge certaines opérations:

  • deux procédures (ma et mb) peuvent être "concaténées": vous pouvez créer une procédure plus grande (ma >> mb) composée de la première puis de la seconde;

  • de plus la sortie (a) de la première peut affecter la seconde (ma >> = \ a -> ...);

  • une procédure (return x) peut donner une valeur constante (x).

Les différents langages de programmation intégrés diffèrent sur les choses gentilles qu'ils prennent en charge, telles que:

  • donnant des valeurs aléatoires;
  • "bifurquer" (la [] monade);
  • exceptions (lancer / attraper) (La monade soit Soit);
  • prise en charge explicite de continuation / callcc;
  • envoyer / recevoir des messages à d'autres "agents";
  • créer, définir et lire des variables (locales à ce langage de programmation) (la monade ST).
ysdx
la source
1

Ne confondez pas un type monadique avec la classe monade.

Un type monadique (c'est-à-dire un type étant une instance de la classe monade) résoudrait un problème particulier (en principe, chaque type monadique résout un problème différent): État, aléatoire, peut-être, IO. Tous sont des types avec contexte (ce que vous appelez "label", mais ce n'est pas ce qui fait d'eux une monade).

Pour chacun d'eux, il faut "enchaîner les opérations avec choix" (une opération dépend du résultat de la précédente). Ici intervient la classe monade: demandez à votre type (résoudre un problème donné) d'être une instance de la classe monade et le problème de chaînage est résolu.

Voir Que résout la classe monade?

cibercitizen1
la source