Monade en anglais simple? (Pour le programmeur OOP sans arrière-plan FP)

743

En termes qu'un programmeur OOP comprendrait (sans aucun arrière-plan de programmation fonctionnelle), qu'est-ce qu'une monade?

Quel problème résout-il et quels sont les endroits les plus courants où il est utilisé?

ÉDITER:

Pour clarifier le type de compréhension que je cherchais, disons que vous convertissiez une application FP qui avait des monades en une application OOP. Que feriez-vous pour transférer les responsabilités des monades vers l'application OOP?


la source
10
Ce billet de blog est très bon: blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html
Pascal Cuoq
10
@ Pavel: La réponse d'Eric que nous avons ci-dessous est bien meilleure que celles de ces autres Q suggérés pour les personnes ayant un arrière-plan OO (par opposition à un arrière-plan FP).
Donal Fellows
5
@Donal: S'il s'agit d' un dupe (sur lequel je n'ai pas d'opinion), la bonne réponse doit être ajoutée à l'original. C'est-à-dire: une bonne réponse n'empêche pas la fermeture en double. S'il s'agit d'un doublon suffisamment proche, cela peut être accompli par un modérateur comme une fusion.
dmckee --- chaton ex-modérateur

Réponses:

732

MISE À JOUR: Cette question a fait l'objet d'une longue série de blogs, que vous pouvez lire sur Monads - merci pour la grande question!

En termes qu'un programmeur OOP comprendrait (sans aucun arrière-plan de programmation fonctionnelle), qu'est-ce qu'une monade?

Une monade est un "amplificateur" de types qui obéit à certaines règles et qui a certaines opérations prévues .

Tout d'abord, qu'est-ce qu'un "amplificateur de types"? J'entends par là un système qui vous permet de prendre un type et de le transformer en un type plus spécial. Par exemple, en C #, considérez Nullable<T>. Il s'agit d'un amplificateur de types. Il vous permet de prendre un type, par exemple int, et d'ajouter une nouvelle capacité à ce type, à savoir qu'il peut maintenant être nul alors qu'il ne le pouvait pas auparavant.

Comme deuxième exemple, considérez IEnumerable<T>. C'est un amplificateur de types. Il vous permet de prendre un type, par exemple, stringet d'ajouter une nouvelle capacité à ce type, à savoir que vous pouvez maintenant créer une séquence de chaînes à partir d'un nombre quelconque de chaînes simples.

Quelles sont les "certaines règles"? En bref, qu'il existe un moyen sensé pour les fonctions du type sous-jacent de travailler sur le type amplifié de telle sorte qu'elles suivent les règles normales de la composition fonctionnelle. Par exemple, si vous avez une fonction sur des entiers, dites

int M(int x) { return x + N(x * 2); }

alors la fonction correspondante sur Nullable<int>peut faire fonctionner tous les opérateurs et les appels "de la même manière" qu'avant.

(C'est incroyablement vague et imprécis; vous avez demandé une explication qui ne supposait rien de la connaissance de la composition fonctionnelle.)

Quelles sont les "opérations"?

  1. Il existe une opération "unité" (parfois appelée "opération de retour", source de confusion) qui prend une valeur d'un type simple et crée la valeur monadique équivalente. Cela, en substance, fournit un moyen de prendre une valeur d'un type non amplifié et de la transformer en une valeur du type amplifié. Il pourrait être implémenté en tant que constructeur dans un langage OO.

  2. Il existe une opération de "liaison" qui prend une valeur monadique et une fonction qui peut transformer la valeur et renvoie une nouvelle valeur monadique. Bind est l'opération clé qui définit la sémantique de la monade. Il nous permet de transformer des opérations sur le type non amplifié en opérations sur le type amplifié, qui obéissent aux règles de composition fonctionnelle mentionnées précédemment.

  3. Il existe souvent un moyen de récupérer le type non amplifié du type amplifié. À proprement parler, cette opération n'est pas nécessaire d'avoir une monade. (Bien que cela soit nécessaire si vous voulez avoir une comonade . Nous ne les examinerons pas plus loin dans cet article.)

Encore une fois, prenez Nullable<T>comme exemple. Vous pouvez transformer un inten un Nullable<int>avec le constructeur. Le compilateur C # s'occupe de la plupart des "levées" annulables pour vous, mais si ce n'est pas le cas, la transformation de levée est simple: une opération, disons,

int M(int x) { whatever }

se transforme en

Nullable<int> M(Nullable<int> x) 
{ 
    if (x == null) 
        return null; 
    else 
        return new Nullable<int>(whatever);
}

Et transformer un Nullable<int>dos en un intse fait avec la Valuepropriété.

C'est la transformation de fonction qui est l'élément clé. Remarquez comment la sémantique réelle de l'opération nullable - qu'une opération sur un nullpropage null- est capturée dans la transformation. Nous pouvons généraliser cela.

Supposons que vous ayez une fonction de intà int, comme notre original M. Vous pouvez facilement en faire une fonction qui prend un intet retourne un Nullable<int>car vous pouvez simplement exécuter le résultat via le constructeur nullable. Supposons maintenant que vous ayez cette méthode d'ordre supérieur:

static Nullable<T> Bind<T>(Nullable<T> amplified, Func<T, Nullable<T>> func)
{
    if (amplified == null) 
        return null;
    else
        return func(amplified.Value);
}

Voyez ce que vous pouvez faire avec ça? Toute méthode qui prend un intet retourne un int, ou prend un intet retourne un Nullable<int>peut maintenant avoir la sémantique nullable qui lui est appliquée .

En outre: supposons que vous ayez deux méthodes

Nullable<int> X(int q) { ... }
Nullable<int> Y(int r) { ... }

et vous souhaitez les composer:

Nullable<int> Z(int s) { return X(Y(s)); }

Autrement dit, Zest la composition de Xet Y. Mais vous ne pouvez pas faire cela car Xprend un intet Yretourne un Nullable<int>. Mais puisque vous avez l'opération "bind", vous pouvez faire ce travail:

Nullable<int> Z(int s) { return Bind(Y(s), X); }

L'opération de liaison sur une monade est ce qui fait fonctionner la composition des fonctions sur les types amplifiés. Les "règles" que j'ai évoquées ci-dessus sont que la monade préserve les règles de composition des fonctions normales; que la composition avec des fonctions d'identité donne la fonction d'origine, que la composition est associative, etc.

En C #, "Bind" est appelé "SelectMany". Jetez un œil à son fonctionnement sur la monade de séquence. Nous devons avoir deux choses: transformer une valeur en séquence et lier des opérations sur des séquences. En prime, nous avons également "reconverti une séquence en valeur". Ces opérations sont:

static IEnumerable<T> MakeSequence<T>(T item)
{
    yield return item;
}
// Extract a value
static T First<T>(IEnumerable<T> sequence)
{
    // let's just take the first one
    foreach(T item in sequence) return item; 
    throw new Exception("No first item");
}
// "Bind" is called "SelectMany"
static IEnumerable<T> SelectMany<T>(IEnumerable<T> seq, Func<T, IEnumerable<T>> func)
{
    foreach(T item in seq)
        foreach(T result in func(item))
            yield return result;            
}

La règle de la monade nullable était "de combiner deux fonctions qui produisent des nullables ensemble, vérifiez si la fonction interne a pour résultat null; si c'est le cas, produisez null, si ce n'est pas le cas, puis appelez la fonction externe avec le résultat". C'est la sémantique souhaitée de nullable.

La règle de la monade de séquence est "de combiner deux fonctions qui produisent des séquences ensemble, d'appliquer la fonction externe à chaque élément produit par la fonction interne, puis de concaténer toutes les séquences résultantes ensemble". La sémantique fondamentale des monades est capturée dans les méthodes Bind/ SelectMany; c'est la méthode qui vous indique ce que signifie réellement la monade .

On peut faire encore mieux. Supposons que vous ayez une séquence d'entiers et une méthode qui accepte des entiers et aboutisse à des séquences de chaînes. Nous pourrions généraliser l'opération de liaison pour permettre la composition de fonctions qui prennent et retournent différents types amplifiés, tant que les entrées de l'une correspondent aux sorties de l'autre:

static IEnumerable<U> SelectMany<T,U>(IEnumerable<T> seq, Func<T, IEnumerable<U>> func)
{
    foreach(T item in seq)
        foreach(U result in func(item))
            yield return result;            
}

Alors maintenant, nous pouvons dire "amplifier ce tas d'entiers individuels en une séquence d'entiers. Transformez cet entier particulier en un tas de chaînes, amplifié en une séquence de chaînes. Maintenant, mettez les deux opérations ensemble: amplifiez ce tas d'entiers dans la concaténation de toutes les séquences de cordes. " Les monades vous permettent de composer vos amplifications.

Quel problème résout-il et quels sont les endroits les plus courants où il est utilisé?

C'est un peu comme demander "quels problèmes le motif singleton résout-il?", Mais je vais essayer.

Les monades sont généralement utilisées pour résoudre des problèmes tels que:

  • Je dois créer de nouvelles capacités pour ce type et toujours combiner les anciennes fonctions sur ce type pour utiliser les nouvelles capacités.
  • J'ai besoin de capturer un tas d'opérations sur les types et de représenter ces opérations comme des objets composables, de construire des compositions de plus en plus grandes jusqu'à ce que la bonne série d'opérations soit représentée, puis je dois commencer à obtenir des résultats de la chose
  • J'ai besoin de représenter proprement les opérations à effets secondaires dans un langage qui déteste les effets secondaires

C # utilise des monades dans sa conception. Comme déjà mentionné, le modèle nullable est très semblable à la "peut-être monade". LINQ est entièrement construit à partir de monades; la SelectManyméthode est ce que fait le travail sémantique de composition des opérations. (Erik Meijer aime souligner que chaque fonction LINQ pourrait en fait être implémentée par SelectMany; tout le reste n'est qu'une commodité.)

Pour clarifier le type de compréhension que je cherchais, disons que vous convertissiez une application FP qui avait des monades en une application OOP. Que feriez-vous pour transférer les responsabilités des monades dans l'application OOP?

La plupart des langages POO n'ont pas de système de type suffisamment riche pour représenter directement le modèle de monade lui-même; vous avez besoin d'un système de types qui prend en charge les types plus élevés que les types génériques. Je n'essaierais donc pas de faire ça. Au lieu de cela, j'implémenterais des types génériques qui représentent chaque monade, et implémenterais des méthodes qui représentent les trois opérations dont vous avez besoin: transformer une valeur en une valeur amplifiée, (peut-être) transformer une valeur amplifiée en une valeur, et transformer une fonction sur des valeurs non amplifiées en une fonction sur les valeurs amplifiées.

Un bon point de départ est la façon dont nous avons implémenté LINQ en C #. Étudiez la SelectManyméthode; c'est la clé pour comprendre comment fonctionne la monade de séquence en C #. C'est une méthode très simple, mais très puissante!


Suggestions de lectures complémentaires:

  1. Pour une explication plus approfondie et théoriquement solide des monades en C #, je recommande fortement l'article de mon collègue Wes Dyer ( Eric Lippert ) sur le sujet. Cet article est ce qui m'a expliqué les monades lorsqu'elles ont finalement "cliqué" pour moi.
  2. Une bonne illustration de pourquoi vous pourriez vouloir une monade autour (utilise Haskell dans ses exemples) .
  3. Sorte de "traduction" de l'article précédent en JavaScript.

Eric Lippert
la source
17
Ceci est une excellente réponse, mais ma tête est allée comme une personne. Je vais le suivre et le regarder ce week-end et vous poser des questions si les choses ne se stabilisent pas et n'ont aucun sens dans ma tête.
Paul Nathan
5
Excellente explication comme d'habitude Eric. Pour une discussion plus théorique (mais toujours très intéressante), j'ai trouvé le billet de blog de Bart De Smet sur MinLINQ utile pour relier également certaines constructions de programmation fonctionnelle à C #. community.bartdesmet.net/blogs/bart/archive/2010/01/01/…
Ron Warholic
41
Il est plus logique pour moi de dire que cela augmente les types plutôt que les amplifie .
Gabe
61
@slomojo: et je l'ai changé de nouveau pour ce que j'ai écrit et l'intention d'écrire. Si Gabe et vous voulez écrire votre propre réponse, allez-y.
Eric Lippert
24
@Eric, à vous bien sûr, mais Amplifier implique que les propriétés existantes sont boostées, ce qui est trompeur.
ocodo
341

Pourquoi avons-nous besoin de monades?

  1. Nous voulons programmer uniquement en utilisant des fonctions . ("programmation fonctionnelle" après tout -FP).
  2. Ensuite, nous avons un premier gros problème. Ceci est un programme:

    f(x) = 2 * x

    g(x,y) = x / y

    Comment pouvons-nous dire ce qui doit être exécuté en premier ? Comment pouvons-nous former une séquence ordonnée de fonctions (c'est -à- dire un programme ) en n'utilisant que des fonctions?

    Solution: composer des fonctions . Si vous voulez d'abord gpuis fécrivez f(g(x,y)). OK mais ...

  3. Plus de problèmes: certaines fonctions peuvent échouer (c. -d g(2,0). Diviser par 0). Nous n'avons aucune "exception" dans FP . Comment le résout-on?

    Solution: Permettons aux fonctions de renvoyer deux types de choses : au lieu d'avoir g : Real,Real -> Real(fonction de deux réels en réel), autorisons g : Real,Real -> Real | Nothing(fonction de deux réels en (réel ou rien)).

  4. Mais les fonctions ne devraient (pour être plus simples) retourner qu'une seule chose .

    Solution: créons un nouveau type de données à renvoyer, un " type boxe " qui renferme peut-être un réel ou tout simplement rien. Par conséquent, nous pouvons avoir g : Real,Real -> Maybe Real. OK mais ...

  5. Qu'arrive-t-il maintenant f(g(x,y))? fn'est pas prêt à consommer a Maybe Real. Et, nous ne voulons pas changer toutes les fonctions avec glesquelles nous pourrions nous connecter pour consommer a Maybe Real.

    Solution: ayons une fonction spéciale pour "connecter" / "composer" / "lier" les fonctions . De cette façon, nous pouvons, en arrière-plan, adapter la sortie d'une fonction pour alimenter la suivante.

    Dans notre cas: g >>= f(connectez / composez gpour f). Nous voulons >>=obtenir gla sortie de, l'inspecter et, au cas où ce ne serait Nothingtout simplement pas appeler fet retourner Nothing; ou au contraire, extrayez la boîte Realet nourrissez f-la. (Cet algorithme n'est que l'implémentation de >>=pour le Maybetype).

  6. De nombreux autres problèmes surviennent qui peuvent être résolus en utilisant ce même modèle: 1. Utilisez une "boîte" pour codifier / stocker différentes significations / valeurs, et avoir des fonctions comme gcelle-ci renvoient ces "valeurs encadrées". 2. Demandez à des compositeurs / éditeurs g >>= fde liens d'aider à connecter gla sortie de fl'entrée à celle-ci, afin que nous n'ayons pas à changer fdu tout.

  7. Les problèmes remarquables qui peuvent être résolus en utilisant cette technique sont:

    • avoir un état global que toutes les fonctions de la séquence de fonctions ("le programme") peuvent partager: solution StateMonad.

    • Nous n'aimons pas les «fonctions impures»: des fonctions qui produisent des sorties différentes pour la même entrée. Par conséquent, marquons ces fonctions, en les faisant retourner une valeur balisée / encadrée: IOmonad.

Bonheur total !!!!

cibercitizen1
la source
2
@DmitriZaitsev Des exceptions ne peuvent se produire que dans le "code impur" (la monade IO) à ma connaissance.
cibercitizen1
3
@DmitriZaitsev Le rôle de Nothing peut être joué par n'importe quel autre type (différent du Real attendu). Ce n'est pas la question. Dans l'exemple, la question est de savoir comment adapter des fonctions dans une chaîne lorsque la précédente peut renvoyer un type de valeur inattendu au suivant, sans chaîner ce dernier (en acceptant uniquement un réel en entrée).
cibercitizen1
3
Un autre point de confusion est que le mot "monade" n'apparaît que deux fois dans votre réponse, et seulement en combinaison avec d'autres termes - Stateet IO, sans aucun d'entre eux ainsi que la signification exacte de "monade" donnée
Dmitri Zaitsev
31
Pour moi, en tant que personne issue de la POO, cette réponse expliquait vraiment bien la motivation derrière une monade et aussi ce que la monade est en réalité (bien plus qu'une réponse acceptée). Je trouve donc cela très utile. Merci beaucoup @ cibercitizen1 et +1
akhilless
3
Je lis sur la programmation fonctionnelle de temps en temps depuis environ un an. Cette réponse, et en particulier les deux premiers points, m'a finalement fait comprendre ce que signifie réellement la programmation impérative, et pourquoi la programmation fonctionnelle est différente. Je vous remercie!
jrahhali
82

Je dirais que l'analogie OO la plus proche des monades est le " modèle de commande ".

Dans le modèle de commande, vous encapsulez une instruction ou une expression ordinaire dans un objet de commande . L'objet de commande expose une méthode d' exécution qui exécute l'instruction encapsulée. Les instructions sont donc transformées en objets de première classe qui peuvent être transmis et exécutés à volonté. Les commandes peuvent être composées afin que vous puissiez créer un objet programme en chaînant et en imbriquant des objets commande.

Les commandes sont exécutées par un objet distinct, l' invocateur . L'avantage d'utiliser le modèle de commande (plutôt que d'exécuter simplement une série d'instructions ordinaires) est que différents appelants peuvent appliquer une logique différente à la façon dont les commandes doivent être exécutées.

Le modèle de commande peut être utilisé pour ajouter (ou supprimer) des fonctionnalités linguistiques qui ne sont pas prises en charge par la langue hôte. Par exemple, dans un langage OO hypothétique sans exception, vous pouvez ajouter une sémantique d'exception en exposant les méthodes "try" et "throw" aux commandes. Lorsqu'une commande appelle throw, l'invocateur revient sur la liste (ou l'arborescence) de commandes jusqu'au dernier appel "try". Inversement, vous pouvez supprimer la sémantique d'exception d'un langage (si vous pensez que les exceptions sont mauvaises ) en interceptant toutes les exceptions levées par chaque commande individuelle et en les transformant en codes d'erreur qui sont ensuite passés à la commande suivante.

Des sémantiques d'exécution encore plus sophistiquées comme les transactions, les exécutions non déterministes ou les continuations peuvent être implémentées comme ceci dans un langage qui ne les prend pas en charge de manière native. C'est un modèle assez puissant si vous y réfléchissez.

Maintenant, en réalité, les modèles de commande ne sont pas utilisés comme une fonctionnalité de langage générale comme celle-ci. Les frais généraux liés à la transformation de chaque instruction en classe distincte entraîneraient une quantité insupportable de code standard. Mais en principe, il peut être utilisé pour résoudre les mêmes problèmes que les monades sont utilisés pour résoudre en fp.

JacquesB
la source
15
Je crois que c'est la première explication de monade que j'ai vue qui ne reposait pas sur des concepts de programmation fonctionnelle et qui la mettait en termes de POO réels. Vraiment une bonne réponse.
David K. Hess
c'est très proche de ce que sont réellement les monades dans FP / Haskell, sauf que les objets de commande eux-mêmes "savent" à quelle "logique d'invocation" ils appartiennent (et seuls ceux compatibles peuvent être enchaînés); invoker fournit juste la première valeur. Ce n'est pas comme si la commande "Imprimer" pouvait être exécutée par une "logique d'exécution non déterministe". Non, ce doit être une "logique d'E / S" (c'est-à-dire une monade IO). Mais à part ça, c'est très proche. Vous pourriez même dire que les monades ne sont que des programmes (construits à partir d'instructions de code, à exécuter plus tard). Au début, "bind" était appelé "point-virgule programmable" .
Will Ness
1
@ DavidK.Hess Je suis en effet incroyablement sceptique quant aux réponses qui utilisent la FP pour expliquer les concepts de base de la FP, et en particulier les réponses qui utilisent un langage de FP comme Scala. Bravo JacquesB!
Rétablir Monica le
62

En termes qu'un programmeur OOP comprendrait (sans aucun arrière-plan de programmation fonctionnelle), qu'est-ce qu'une monade?

Quel problème résout-elle et quels sont les endroits les plus courants où elle est utilisée? Quels sont les endroits les plus courants où elle est utilisée?

En termes de programmation OO, une monade est une interface (ou plus probablement un mixin), paramétrée par un type, avec deux méthodes, returnet bindqui décrit:

  • Comment injecter une valeur pour obtenir une valeur monadique de ce type de valeur injectée;
  • Comment utiliser une fonction qui crée une valeur monadique à partir d'une valeur non monadique, sur une valeur monadique.

Le problème qu'il résout est le même type de problème que vous attendez de n'importe quelle interface, à savoir: "J'ai un tas de classes différentes qui font des choses différentes, mais semblent faire ces différentes choses d'une manière qui a une similitude sous-jacente. Comment puis-je décrire cette similitude entre eux, même si les classes elles-mêmes ne sont pas vraiment des sous-types de quelque chose de plus proche que la classe "Object" elle-même? "

Plus précisément, l ' Monad"interface" est similaire IEnumeratorou IIteratoren ce qu'elle prend un type qui lui-même prend un type. Le principal «point» Monadest cependant de pouvoir relier des opérations basées sur le type intérieur, même au point d'avoir un nouveau «type interne», tout en conservant - ou même en améliorant - la structure d'information de la classe principale.

BMeph
la source
1
returnne serait pas réellement une méthode sur la monade, car elle ne prend pas une instance de monade comme argument. (ie: il n'y a pas ce / soi)
Laurence Gonsalves
@LaurenceGonsalves: Étant donné que j'étudie actuellement ce sujet pour ma thèse de baccalauréat, je pense que ce qui limite le plus, c'est le manque de méthodes statiques dans les interfaces en C # / Java. Vous pourriez aller loin dans la direction de la mise en œuvre de toute l'histoire de la monade, au moins liée statiquement au lieu d'être basée sur des classes de caractères. Fait intéressant, cela fonctionnerait même malgré le manque de types plus élevés.
Sebastian Graf
42

Vous avez une récente présentation " Monadologie - aide professionnelle sur l'anxiété de type " par Christopher League (12 juillet 2010), qui est assez intéressante sur des sujets de continuation et de monade.
La vidéo accompagnant cette présentation (SlideShare) est actuellement disponible sur vimeo .
La partie Monade commence environ 37 minutes, sur cette vidéo d'une heure, et commence par la diapositive 42 de sa présentation de 58 diapositives.

Il est présenté comme "le principal modèle de conception pour la programmation fonctionnelle", mais le langage utilisé dans les exemples est Scala, qui est à la fois POO et fonctionnel.
Vous pouvez en savoir plus sur Monad in Scala dans le blog " Monads - Another way to abstract computations in Scala ", de Debasish Ghosh (27 mars 2008).

Un constructeur de type M est une monade s'il prend en charge ces opérations:

# the return function
def unit[A] (x: A): M[A]

# called "bind" in Haskell 
def flatMap[A,B] (m: M[A]) (f: A => M[B]): M[B]

# Other two can be written in term of the first two:

def map[A,B] (m: M[A]) (f: A => B): M[B] =
  flatMap(m){ x => unit(f(x)) }

def andThen[A,B] (ma: M[A]) (mb: M[B]): M[B] =
  flatMap(ma){ x => mb }

Ainsi, par exemple (dans Scala):

  • Option est une monade
    unité def [A] (x: A): Option [A] = Some (x)

    def flatMap [A, B] (m: Option [A]) (f: A => Option [B]): Option [B] =
      m match {
       cas Aucun => Aucun
       cas Certains (x) => f (x)
      }
  • List est Monad
    unité def [A] (x: A): Liste [A] = Liste (x)

    def flatMap [A, B] (m: Liste [A]) (f: A => Liste [B]): Liste [B] =
      m match {
        cas Nil => Nil
        case x :: xs => f (x) ::: flatMap (xs) (f)
      }

Monad est un gros problème dans Scala en raison de la syntaxe pratique conçue pour tirer parti des structures Monad:

forcompréhension en Scala :

for {
  i <- 1 to 4
  j <- 1 to i
  k <- 1 to j
} yield i*j*k

est traduit par le compilateur en:

(1 to 4).flatMap { i =>
  (1 to i).flatMap { j =>
    (1 to j).map { k =>
      i*j*k }}}

L'abstraction clé est la flatMap, qui lie le calcul par chaînage.
Chaque appel de flatMaprenvoie le même type de structure de données (mais de valeur différente), qui sert d'entrée à la prochaine commande de la chaîne.

Dans l'extrait ci-dessus, flatMap prend en entrée une fermeture (SomeType) => List[AnotherType]et renvoie a List[AnotherType]. Le point important à noter est que tous les flatMaps prennent le même type de fermeture en entrée et retournent le même type en sortie.

C'est ce qui "lie" le thread de calcul - chaque élément de la séquence de la compréhension doit respecter cette même contrainte de type.


Si vous effectuez deux opérations (qui peuvent échouer) et passez le résultat à la troisième, comme:

lookupVenue: String => Option[Venue]
getLoggedInUser: SessionID => Option[User]
reserveTable: (Venue, User) => Option[ConfNo]

mais sans profiter de Monad, vous obtenez un code OOP alambiqué comme:

val user = getLoggedInUser(session)
val confirm =
  if(!user.isDefined) None
  else lookupVenue(name) match {
    case None => None
    case Some(venue) =>
      val confno = reserveTable(venue, user.get)
      if(confno.isDefined)
        mailTo(confno.get, user.get)
      confno
  }

alors qu'avec Monad, vous pouvez travailler avec les types réels ( Venue, User) comme toutes les opérations, et garder les trucs de vérification des options cachés, tout cela à cause des flatmaps de la syntaxe for:

val confirm = for {
  venue <- lookupVenue(name)
  user <- getLoggedInUser(session)
  confno <- reserveTable(venue, user)
} yield {
  mailTo(confno, user)
  confno
}

La partie de rendement ne sera exécutée que si les trois fonctions ont Some[X]; tout Noneserait directement retourné à confirm.


Donc:

Les monades permettent un calcul ordonné au sein de la programmation fonctionnelle, ce qui nous permet de modéliser le séquencement des actions sous une forme structurée agréable, un peu comme une DSL.

Et la plus grande puissance vient de la possibilité de composer des monades qui servent des objectifs différents, en abstractions extensibles au sein d'une application.

Ce séquencement et le filetage des actions par une monade sont effectués par le compilateur de langage qui effectue la transformation à travers la magie des fermetures.


Soit dit en passant, Monad n'est pas seulement un modèle de calcul utilisé dans FP:

La théorie des catégories propose de nombreux modèles de calcul. Parmi eux

  • le modèle Arrow des calculs
  • le modèle de calcul Monad
  • le modèle Applicatif des calculs
VonC
la source
2
J'adore cette explication! L'exemple que vous avez donné illustre magnifiquement le concept et ajoute également ce que mon humble avis manquait dans le teaser d'Eric à propos de SelectMany () étant une monade. Merci pour ça!
aoven
1
À mon humble avis, c'est la réponse la plus élégante
Polymerase
et avant tout le reste, Functor.
Will Ness
34

Pour respecter les lecteurs rapides, je commence par une définition précise en premier, je continue par une explication rapide plus "en anglais simple", puis je passe aux exemples.

Voici une définition à la fois concise et précise légèrement reformulée:

Une monade (en informatique) est officiellement une carte qui:

  • envoie chaque type Xd'un langage de programmation donné à un nouveau type T(X)(appelé "type de- Tcalculs avec des valeurs dans X");

  • équipé d'une règle pour composer deux fonctions de la forme f:X->T(Y)et g:Y->T(Z)à une fonction g∘f:X->T(Z);

  • d'une manière qui est associative au sens évident et unitaire par rapport à une fonction unitaire donnée appelée pure_X:X->T(X), à considérer comme prenant une valeur au calcul pur qui renvoie simplement cette valeur.

Donc, en termes simples, une monade est une règle à passer de n'importe quel type Xà un autre typeT(X) , et une règle à passer de deux fonctions f:X->T(Y)et g:Y->T(Z)(que vous souhaitez composer mais ne pouvez pas) à une nouvelle fonctionh:X->T(Z) . Mais ce n'est pas la composition au sens mathématique strict. Nous sommes fondamentalement en train de «plier» la composition d'une fonction ou de redéfinir la façon dont les fonctions sont composées.

De plus, nous avons besoin de la règle de composition de la monade pour satisfaire les axiomes mathématiques "évidents":

  • Associativité : Composer favec gpuis avec h(de l'extérieur) doit être identique à composer gavec hpuis avec f(de l'intérieur).
  • Propriété unitaire : Composer favec la fonction d' identité de chaque côté devrait donner f.

Encore une fois, en termes simples, nous ne pouvons pas simplement devenir fous en redéfinissant notre composition de fonctions comme nous le souhaitons:

  • Nous avons d'abord besoin de l'associativité pour pouvoir composer plusieurs fonctions d'affilée par exemple f(g(h(k(x))), et ne pas nous soucier de spécifier l'ordre de paires de fonctions de composition. Comme la règle de la monade ne prescrit que comment composer une paire de fonctions , sans cet axiome, nous aurions besoin de savoir quelle paire est composée en premier et ainsi de suite. (Notez que c'est différent de la propriété de commutativité qui fcomposait avec gétait la même que gcomposée avec f, ce qui n'est pas requis).
  • Et deuxièmement, nous avons besoin de la propriété unitaire, c'est-à-dire simplement que les identités composent trivialement comme nous les attendons. Nous pouvons donc refactoriser les fonctions en toute sécurité chaque fois que ces identités peuvent être extraites.

Donc encore une fois: une monade est la règle de l'extension de type et des fonctions de composition satisfaisant les deux axiomes - associativité et propriété unitaire.

Concrètement, vous souhaitez que la monade soit implémentée pour vous par le langage, le compilateur ou le framework qui se chargerait de composer des fonctions pour vous. Vous pouvez donc vous concentrer sur l'écriture de la logique de votre fonction plutôt que de vous soucier de la façon dont leur exécution est implémentée.

C'est essentiellement cela, en un mot.


Étant mathématicien professionnel, je préfère éviter d'appeler hla "composition" de fet g. Parce que mathématiquement, ce n'est pas le cas. L'appeler la "composition" suppose à tort que hc'est la vraie composition mathématique, ce qui n'est pas le cas. Il n'est même pas déterminé de manière unique par fet g. Au lieu de cela, c'est le résultat de la nouvelle "règle de composition" de notre monade. Ce qui peut être totalement différent de la composition mathématique réelle même si celle-ci existe!


Pour le rendre moins sec, permettez-moi d'essayer de l'illustrer par l'exemple que j'annote avec de petites sections, afin que vous puissiez aller droit au but.

Lancer d'exception comme exemples Monad

Supposons que nous voulons composer deux fonctions:

f: x -> 1 / x
g: y -> 2 * y

Mais f(0)n'est pas défini, donc une exception eest levée. Alors, comment pouvez-vous définir la valeur de composition g(f(0))? Jetez à nouveau une exception, bien sûr! Peut-être la même chose e. Peut-être une nouvelle exception mise à jour e1.

Que se passe-t-il précisément ici? Tout d'abord, nous avons besoin de nouvelles valeurs d'exception (différentes ou identiques). Vous pouvez les appeler nothingou nullou quoi que ce soit mais l'essence reste la même - elles devraient être de nouvelles valeurs, par exemple, ce ne devrait pas être un numberdans notre exemple ici. Je préfère ne pas les appeler nullpour éviter toute confusion avec la façon de nullles implémenter dans une langue spécifique. De même, je préfère éviter nothingcar il est souvent associé à nullce qui, en principe, est ce qui nulldevrait faire, cependant, ce principe est souvent plié pour des raisons pratiques.

Qu'est-ce que l'exception exactement?

C'est une question banale pour tout programmeur expérimenté mais j'aimerais laisser tomber quelques mots juste pour éteindre tout ver de confusion:

L'exception est un objet encapsulant des informations sur la façon dont le résultat non valide de l'exécution s'est produit.

Cela peut aller de la suppression des détails et du retour d'une seule valeur globale (comme NaNou null) ou de la génération d'une longue liste de journaux ou de ce qui s'est exactement passé, de l'envoyer à une base de données et de la répliquer partout dans la couche de stockage de données distribuées;)

La différence importante entre ces deux exemples extrêmes d'exception est que dans le premier cas il n'y a pas d'effets secondaires . Dans le second, il y en a. Ce qui nous amène à la question (en milliers de dollars):

Les exceptions sont-elles autorisées dans les fonctions pures?

Réponse plus courte : oui, mais uniquement lorsqu'ils n'entraînent pas d'effets secondaires.

Réponse plus longue. Pour être pure, la sortie de votre fonction doit être uniquement déterminée par son entrée. Nous modifions donc notre fonction fen envoyant 0à la nouvelle valeur abstraite eque nous appelons exception. Nous nous assurons que cette valeur ene contient aucune information extérieure qui n'est pas déterminée de manière unique par notre entrée, ce qui est x. Voici donc un exemple d'exception sans effet secondaire:

e = {
  type: error, 
  message: 'I got error trying to divide 1 by 0'
}

Et voici un avec effet secondaire:

e = {
  type: error, 
  message: 'Our committee to decide what is 1/0 is currently away'
}

En fait, cela n'a d'effets secondaires que si ce message peut éventuellement changer à l'avenir. Mais s'il est garanti de ne jamais changer, cette valeur devient uniquement prévisible et il n'y a donc aucun effet secondaire.

Pour le rendre encore plus idiot. Une fonction qui revient 42toujours est clairement pure. Mais si quelqu'un de fou décide de faire 42une variable dont la valeur pourrait changer, la même fonction cesse d'être pure dans les nouvelles conditions.

Notez que j'utilise la notation littérale de l'objet pour plus de simplicité afin de démontrer l'essence. Malheureusement, les choses sont gâchées dans des langages comme JavaScript, où il errorn'y a pas un type qui se comporte comme nous le voulons ici en ce qui concerne la composition des fonctions, alors que les types réels aiment nullou NaNne se comportent pas de cette façon mais passent plutôt par certains artificiels et pas toujours intuitifs conversions de type.

Extension de type

Comme nous voulons faire varier le message à l'intérieur de notre exception, nous déclarons vraiment un nouveau type Epour l'ensemble de l'objet d'exception, puis c'est ce que maybe numberfait, à part son nom déroutant, qui doit être de type numberou du nouveau type d'exception E, c'est donc vraiment l'union number | Ede numberet E. En particulier, cela dépend de la façon dont nous voulons construire E, ce qui n'est ni suggéré ni reflété dans le nom maybe number.

Qu'est-ce que la composition fonctionnelle?

Ce sont les fonctions de prise de fonctionnement mathématiques f: X -> Yet g: Y -> Zet la construction de leur composition en fonction h: X -> Zsatisfaisant h(x) = g(f(x)). Le problème avec cette définition se produit lorsque le résultat f(x)n'est pas autorisé comme argument de g.

En mathématiques, ces fonctions ne peuvent pas être composées sans travail supplémentaire. La solution strictement mathématique pour notre exemple ci-dessus de fet gest de supprimer 0de l'ensemble de définition de f. Avec ce nouvel ensemble de définition (nouveau type plus restrictif de x), fdevient composable avec g.

Cependant, il n'est pas très pratique en programmation de restreindre l'ensemble de définition de ce fgenre. Au lieu de cela, des exceptions peuvent être utilisées.

Ou comme une autre approche, les valeurs artificielles sont créées comme NaN, undefined, null, Infinityetc. Vous évaluez 1/0à Infinityet 1/-0à -Infinity. Et puis forcez la nouvelle valeur dans votre expression au lieu de lever l'exception. Menant à des résultats que vous pouvez ou non trouver prévisibles:

1/0                // => Infinity
parseInt(Infinity) // => NaN
NaN < 0            // => false
false + 1          // => 1

Et nous sommes de retour à des numéros réguliers prêts à passer;)

JavaScript nous permet de continuer à exécuter des expressions numériques à tout prix sans générer d'erreurs comme dans l'exemple ci-dessus. Cela signifie qu'il permet également de composer des fonctions. C'est exactement de cela qu'il s'agit - c'est une règle de composer des fonctions satisfaisant les axiomes tels que définis au début de cette réponse.

Mais la règle de la fonction de composition, découlant de l'implémentation de JavaScript pour traiter les erreurs numériques, est-elle une monade?

Pour répondre à cette question, il vous suffit de vérifier les axiomes (laissés en exercice comme ne faisant pas partie de la question ici;).

L'exception de lancement peut-elle être utilisée pour construire une monade?

En effet, une monade plus utile serait plutôt la règle prescrivant que si flève une exception pour certains x, sa composition en fait de même g. De plus, l'exception est Eunique au monde avec une seule valeur possible ( objet terminal dans la théorie des catégories). Maintenant, les deux axiomes sont vérifiables instantanément et nous obtenons une monade très utile. Et le résultat est ce qui est bien connu comme la monade peut - être .

Dmitri Zaitsev
la source
3
Bonne contribution. +1 Mais peut-être voudriez-vous supprimer "ont trouvé la plupart des explications trop longues ..." étant la vôtre la plus longue du tout. D'autres jugeront s'il s'agit d'un "anglais simple" comme l'exige la question: "anglais simple == en termes simples, d'une manière simple".
cibercitizen1
@ cibercitizen1 Merci! C'est en fait court, si vous ne comptez pas l'exemple. Le point principal est que vous n'avez pas besoin de lire l'exemple pour comprendre la définition . Malheureusement, de nombreuses explications m'obligent à lire d'abord des exemples , ce qui est souvent inutile mais, bien sûr, peut nécessiter un travail supplémentaire pour l'auteur. Si l'on se fie trop à des exemples spécifiques, il existe un risque que des détails sans importance obscurcissent l'image et la rendent plus difficile à saisir. Cela dit, vous avez des points valides, voir la mise à jour.
Dmitri Zaitsev
2
trop long et déroutant
vuimurugan
1
@seenimurugan Les suggestions d'amélioration sont les bienvenues;)
Dmitri Zaitsev
26

Une monade est un type de données qui encapsule une valeur et auquel, essentiellement, deux opérations peuvent être appliquées:

  • return x crée une valeur de type monade qui encapsule x
  • m >>= f(lire "l'opérateur de liaison") applique la fonction fà la valeur dans la monadem

Voilà ce qu'est une monade. Il y a quelques autres détails techniques , mais fondamentalement, ces deux opérations définissent une monade. La vraie question est: "Qu'est-ce qu'une monade fait ?", Et cela dépend de la monade - les listes sont des monades, Maybes sont des monades, les opérations d'E / S sont des monades. Tout ce que cela signifie lorsque nous disons que ces choses sont des monades, c'est qu'elles ont l'interface de monade de returnet >>=.

Mandrin
la source
«Qu'est-ce qu'une monade fait, et cela dépend de la monade»: et plus précisément, cela dépend de la bindfonction qui doit être définie pour chaque type monadique, n'est-ce pas? Ce serait une bonne raison de ne pas confondre liaison avec composition, car il n'y a qu'une seule définition pour la composition, alors qu'il ne peut pas y avoir qu'une seule définition pour une fonction de liaison, il y en a une par type monadique, si je comprends bien.
Hibou57
14

De wikipedia :

En programmation fonctionnelle, une monade est une sorte de type de données abstrait utilisé pour représenter des calculs (au lieu de données dans le modèle de domaine). Les monades permettent au programmeur de chaîner des actions pour construire un pipeline, dans lequel chaque action est décorée de règles de traitement supplémentaires fournies par la monade. Les programmes écrits dans un style fonctionnel peuvent utiliser des monades pour structurer des procédures qui incluent des opérations séquencées, 1 [2] ou pour définir des flux de contrôle arbitraires (comme gérer la concurrence, les continuations ou les exceptions).

Formellement, une monade est construite en définissant deux opérations (liaison et retour) et un constructeur de type M qui doit remplir plusieurs propriétés pour permettre la composition correcte des fonctions monadiques (c'est-à-dire les fonctions qui utilisent les valeurs de la monade comme arguments). L'opération de retour prend une valeur d'un type simple et la place dans un conteneur monadique de type M. L'opération de liaison effectue le processus inverse, extrayant la valeur d'origine du conteneur et la transmettant à la fonction suivante associée dans le pipeline.

Un programmeur composera des fonctions monadiques pour définir un pipeline de traitement de données. La monade agit comme un cadre, car c'est un comportement réutilisable qui décide de l'ordre dans lequel les fonctions monadiques spécifiques du pipeline sont appelées, et gère tout le travail d'infiltration requis par le calcul. [3] Les opérateurs de liaison et de retour entrelacés dans le pipeline seront exécutés après le retour du contrôle de chaque fonction monadique et prendront en charge les aspects particuliers traités par la monade.

Je pense que cela l'explique très bien.

the_drow
la source
12

Je vais essayer de faire la définition la plus courte que je puisse gérer en utilisant des termes POO:

Une classe générique CMonadic<T>est une monade si elle définit au moins les méthodes suivantes:

class CMonadic<T> { 
    static CMonadic<T> create(T t);  // a.k.a., "return" in Haskell
    public CMonadic<U> flatMap<U>(Func<T, CMonadic<U>> f); // a.k.a. "bind" in Haskell
}

et si les lois suivantes s'appliquent pour tous les types T et leurs valeurs possibles t

identité de gauche:

CMonadic<T>.create(t).flatMap(f) == f(t)

bonne identité

instance.flatMap(CMonadic<T>.create) == instance

associativité:

instance.flatMap(f).flatMap(g) == instance.flatMap(t => f(t).flatMap(g))

Exemples :

Une monade List peut avoir:

List<int>.create(1) --> [1]

Et flatMap sur la liste [1,2,3] pourrait fonctionner comme ceci:

intList.flatMap(x => List<int>.makeFromTwoItems(x, x*10)) --> [1,10,2,20,3,30]

Les itérables et les observables peuvent également être rendus monadiques, ainsi que les promesses et les tâches.

Commentaire :

Les monades ne sont pas si compliquées. La flatMapfonction ressemble beaucoup à la plus courante map. Il reçoit un argument de fonction (également appelé délégué), qu'il peut appeler (immédiatement ou plus tard, zéro ou plusieurs fois) avec une valeur provenant de la classe générique. Il s'attend à ce que la fonction passée encapsule également sa valeur de retour dans le même type de classe générique. Pour aider à cela, il fournit createun constructeur qui peut créer une instance de cette classe générique à partir d'une valeur. Le résultat de retour de flatMap est également une classe générique du même type, regroupant souvent les mêmes valeurs qui étaient contenues dans les résultats de retour d'une ou plusieurs applications de flatMap aux valeurs précédemment contenues. Cela vous permet de chaîner flatMap autant que vous le souhaitez:

intList.flatMap(x => List<int>.makeFromTwo(x, x*10))
       .flatMap(x => x % 3 == 0 
                   ? List<string>.create("x = " + x.toString()) 
                   : List<string>.empty())

Il se trouve que ce type de classe générique est utile comme modèle de base pour un grand nombre de choses. C'est (avec les jargonismes de la théorie des catégories) la raison pour laquelle les Monades semblent si difficiles à comprendre ou à expliquer. Ils sont très abstraits et ne deviennent évidemment utiles qu'une fois spécialisés.

Par exemple, vous pouvez modéliser des exceptions à l'aide de conteneurs monadiques. Chaque conteneur contiendra le résultat de l'opération ou l'erreur qui s'est produite. La fonction suivante (déléguée) dans la chaîne de rappels flatMap ne sera appelée que si la précédente a compressé une valeur dans le conteneur. Sinon, si une erreur a été compressée, l'erreur continuera de se propager à travers les conteneurs chaînés jusqu'à ce qu'un conteneur soit trouvé qui ait une fonction de gestionnaire d'erreurs attachée via une méthode appelée .orElse()(une telle méthode serait une extension autorisée)

Remarques : Les langages fonctionnels vous permettent d'écrire des fonctions qui peuvent fonctionner sur tout type de classe générique monadique. Pour que cela fonctionne, il faudrait écrire une interface générique pour les monades. Je ne sais pas s'il est possible d'écrire une telle interface en C #, mais pour autant que je sache, ce n'est pas le cas:

interface IMonad<T> { 
    static IMonad<T> create(T t); // not allowed
    public IMonad<U> flatMap<U>(Func<T, IMonad<U>> f); // not specific enough,
    // because the function must return the same kind of monad, not just any monad
}
Gorgi Kosev
la source
7

Le fait qu'une monade ait une interprétation "naturelle" en OO dépend de la monade. Dans un langage comme Java, vous pouvez traduire la monade peut-être dans le langage de vérification des pointeurs nuls, de sorte que les calculs qui échouent (c'est-à-dire ne produisent rien dans Haskell) émettent des pointeurs nuls comme résultats. Vous pouvez traduire la monade d'état dans le langage généré en créant une variable mutable et des méthodes pour changer son état.

Une monade est un monoïde dans la catégorie des endofoncteurs.

L'information que la phrase rassemble est très profonde. Et vous travaillez dans une monade avec n'importe quel langage impératif. Une monade est un langage "séquencé" spécifique au domaine. Il satisfait à certaines propriétés intéressantes qui, prises ensemble, font de la monade un modèle mathématique de "programmation impérative". Haskell facilite la définition de petits (ou grands) langages impératifs, qui peuvent être combinés de différentes manières.

En tant que programmeur OO, vous utilisez la hiérarchie des classes de votre langage pour organiser les types de fonctions ou de procédures qui peuvent être appelées dans un contexte, ce que vous appelez un objet. Une monade est également une abstraction sur cette idée, dans la mesure où différentes monades peuvent être combinées de manière arbitraire, "important" efficacement toutes les méthodes de la sous-monade dans la portée.

Sur le plan architectural, on utilise ensuite des signatures de type pour exprimer explicitement quels contextes peuvent être utilisés pour calculer une valeur.

On peut utiliser des transformateurs monades à cet effet, et il existe une collection de haute qualité de toutes les monades "standard":

  • Listes (calculs non déterministes, en traitant une liste comme un domaine)
  • Peut-être (calculs qui peuvent échouer, mais pour lesquels les rapports sont sans importance)
  • Erreur (calculs pouvant échouer et nécessiter une gestion des exceptions
  • Lecteur (calculs pouvant être représentés par des compositions de fonctions Haskell simples)
  • Writer (calculs avec "rendu" / "journalisation" séquentiels (en chaînes, html, etc.)
  • Cont (suite)
  • IO (calculs qui dépendent du système informatique sous-jacent)
  • État (calculs dont le contexte contient une valeur modifiable)

avec les transformateurs monades correspondants et les classes de type. Les classes de types permettent une approche complémentaire de la combinaison des monades en unifiant leurs interfaces, de sorte que les monades concrètes peuvent implémenter une interface standard pour la monade "kind". Par exemple, le module Control.Monad.State contient une classe MonadState sm et (State s) est une instance du formulaire

instance MonadState s (State s) where
    put = ...
    get = ...

La longue histoire est qu'une monade est un foncteur qui attache un "contexte" à une valeur, qui a un moyen d'injecter une valeur dans la monade, et qui a un moyen d'évaluer des valeurs par rapport au contexte qui lui est attaché, au moins d'une manière restreinte.

Donc:

return :: a -> m a

est une fonction qui injecte une valeur de type a dans une "action" monade de type m a.

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

est une fonction qui effectue une action de monade, évalue son résultat et applique une fonction au résultat. La chose intéressante à propos de (>> =) est que le résultat est dans la même monade. En d'autres termes, dans m >> = f, (>> =) extrait le résultat de m et le lie à f, de sorte que le résultat est dans la monade. (Alternativement, nous pouvons dire que (>> =) tire f dans m et l'applique au résultat.) Par conséquent, si nous avons f :: a -> mb, et g :: b -> mc, nous pouvons actions "séquence":

m >>= f >>= g

Ou, en utilisant "do notation"

do x <- m
   y <- f x
   g y

Le type de (>>) peut être éclairant. C'est

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

Il correspond à l'opérateur (;) dans les langages procéduraux comme C. Il permet la notation do comme:

m = do x <- someQuery
       someAction x
       theNextAction
       andSoOn

Dans la logique mathématique et philosophique, nous avons des cadres et des modèles, qui sont "naturellement" modélisés avec le monadisme. Une interprétation est une fonction qui examine le domaine du modèle et calcule la valeur de vérité (ou généralisations) d'une proposition (ou formule, sous généralisations). Dans une logique modale de nécessité, on pourrait dire qu'une proposition est nécessaire si elle est vraie dans "tous les mondes possibles" - si elle est vraie par rapport à chaque domaine admissible. Cela signifie qu'un modèle dans un langage pour une proposition peut être réifié comme un modèle dont le domaine consiste en une collection de modèles distincts (un correspondant à chaque monde possible). Chaque monade a une méthode nommée "join" qui aplatit les calques, ce qui implique que chaque action de monade dont le résultat est une action de monade peut être incorporée dans la monade.

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

Plus important encore, cela signifie que la monade est fermée lors de l'opération "d'empilement de couches". Voici comment fonctionnent les transformateurs monades: ils combinent les monades en fournissant des méthodes de type jointure pour des types comme

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

afin que nous puissions transformer une action dans (Peut-êtreT m) en une action dans m, en effondrant efficacement les couches. Dans ce cas, runMaybeT :: MaybeT ma -> m (Peut-être a) est notre méthode de type jointure. (MaybeT m) est une monade, et MaybeT :: m (Peut-être a) -> MaybeT ma est effectivement un constructeur pour un nouveau type d'action de monade dans m.

Une monade libre pour un foncteur est la monade générée par l'empilement de f, ce qui implique que chaque séquence de constructeurs pour f est un élément de la monade libre (ou, plus exactement, quelque chose ayant la même forme que l'arbre de séquences de constructeurs pour F). Les monades libres sont une technique utile pour construire des monades flexibles avec une quantité minimale de plaque de chaudière. Dans un programme Haskell, je pourrais utiliser des monades libres pour définir des monades simples pour la "programmation système de haut niveau" pour aider à maintenir la sécurité des types (j'utilise simplement les types et leurs déclarations. Les implémentations sont simples avec l'utilisation de combinateurs):

data RandomF r a = GetRandom (r -> a) deriving Functor
type Random r a = Free (RandomF r) a


type RandomT m a = Random (m a) (m a) -- model randomness in a monad by computing random monad elements.
getRandom     :: Random r r
runRandomIO   :: Random r a -> IO a (use some kind of IO-based backend to run)
runRandomIO'  :: Random r a -> IO a (use some other kind of IO-based backend)
runRandomList :: Random r a -> [a]  (some kind of list-based backend (for pseudo-randoms))

Le monadisme est l'architecture sous-jacente de ce que vous pourriez appeler le modèle "interprète" ou "commande", résumé sous sa forme la plus claire, car chaque calcul monadique doit être "exécuté", au moins trivialement. (Le système d'exécution exécute la monade IO pour nous et constitue le point d'entrée de tout programme Haskell. IO "pilote" le reste des calculs, en exécutant les actions IO dans l'ordre).

Le type de jointure est également l'endroit où nous obtenons la déclaration qu'une monade est un monoïde dans la catégorie des endofoncteurs. La jointure est généralement plus importante à des fins théoriques, en raison de son type. Mais comprendre le type signifie comprendre les monades. Les types de jointure de jointure et de transformateur monade sont en fait des compositions d'endofoncteurs, au sens de composition de fonction. Pour le mettre dans un pseudo-langage de type Haskell,

Foo :: m (ma) <-> (m. M) a

pas d'hommes
la source
3

Une monade est un tableau de fonctions

(Pst: un tableau de fonctions n'est qu'un calcul).

En fait, au lieu d'un vrai tableau (une fonction dans un tableau de cellules), vous avez ces fonctions chaînées par une autre fonction >> =. Le >> = permet d'adapter les résultats de la fonction i pour alimenter la fonction i + 1, d'effectuer des calculs entre eux ou, même, de ne pas appeler la fonction i + 1.

Les types utilisés ici sont des "types avec contexte". Il s'agit d'une valeur avec une "balise". Les fonctions chaînées doivent prendre une "valeur nue" et retourner un résultat balisé. L'une des fonctions de >> = est d'extraire une valeur nue de son contexte. Il y a aussi la fonction "return", qui prend une valeur nue et la met avec une balise.

Un exemple avec peut-être . Utilisons-le pour stocker un simple entier sur lequel effectuer des calculs.

-- a * b
multiply :: Int -> Int -> Maybe Int
multiply a b = return  (a*b)

-- divideBy 5 100 = 100 / 5
divideBy :: Int -> Int -> Maybe Int
divideBy 0 _ = Nothing -- dividing by 0 gives NOTHING
divideBy denom num = return (quot num denom) -- quotient of num / denom

-- tagged value
val1 = Just 160 

-- array of functions feeded with val1
array1 = val1 >>= divideBy 2  >>= multiply 3 >>= divideBy  4 >>= multiply 3

-- array of funcionts created with the do notation
-- equals array1 but for the feeded val1
array2 :: Int -> Maybe Int
array2 n = do
       v <- divideBy 2  n
       v <- multiply 3 v
       v <- divideBy 4 v
       v <- multiply 3 v
       return v

-- array of functions, 
-- the first >>= performs 160 / 0, returning Nothing
-- the second >>= has to perform Nothing >>= multiply 3 ....
-- and simply returns Nothing without calling multiply 3 ....
array3 = val1 >>= divideBy 0  >>= multiply 3 >>= divideBy  4 >>= multiply 3

main = do
     print array1
     print (array2 160)
     print array3

Juste pour montrer que les monades sont un tableau de fonctions avec des opérations d'assistance, considérez l'équivalent de l'exemple ci-dessus, en utilisant simplement un véritable tableau de fonctions

type MyMonad = [Int -> Maybe Int] -- my monad as a real array of functions

myArray1 = [divideBy 2, multiply 3, divideBy 4, multiply 3]

-- function for the machinery of executing each function i with the result provided by function i-1
runMyMonad :: Maybe Int -> MyMonad -> Maybe Int
runMyMonad val [] = val
runMyMonad Nothing _ = Nothing
runMyMonad (Just val) (f:fs) = runMyMonad (f val) fs

Et il serait utilisé comme ceci:

print (runMyMonad (Just 160) myArray1)
cibercitizen1
la source
1
Super propre! Donc, bind est juste un moyen d'évaluer un tableau de fonctions avec contexte, en séquence, sur une entrée avec contexte :)
Musa Al-hassy
>>=est opérateur
user2418306
1
Je pense que l'analogie «tableau de fonctions» ne clarifie pas grand-chose. Si \x -> x >>= k >>= l >>= mest un tableau de fonctions, il en est de même h . g . f, qui n'implique pas du tout les monades.
duplode du
on pourrait dire que les foncteurs , qu'ils soient monadiques, applicatifs ou simples, concernent «l'application embellie» . 'applicative' ajoute le chaînage, et 'monad' ajoute la dépendance (c'est-à-dire créer l'étape de calcul suivante en fonction des résultats d'une étape de calcul précédente).
Will Ness
3

En termes OO, une monade est un récipient fluide.

L'exigence minimale est une définition class <A> Somethingqui prend en charge un constructeur Something(A a)et au moins une méthodeSomething<B> flatMap(Function<A, Something<B>>)

On peut dire que cela compte également si votre classe monad a des méthodes avec signature Something<B> work()qui préservent les règles de la classe - le compilateur cuit dans flatMap au moment de la compilation.

Pourquoi une monade est-elle utile? Parce que c'est un conteneur qui permet des opérations en chaîne qui préservent la sémantique. Par exemple, Optional<?>conserve la sémantique de IsPresent pour Optional<String>, Optional<Integer>, Optional<MyClass>, etc.

À titre d'exemple grossier,

Something<Integer> i = new Something("a")
  .flatMap(doOneThing)
  .flatMap(doAnother)
  .flatMap(toInt)

Notez que nous commençons par une chaîne et terminons par un entier. Plutôt cool.

Dans OO, cela peut prendre un peu de main, mais toute méthode sur Quelque chose qui retourne une autre sous-classe de Quelque chose répond au critère d'une fonction de conteneur qui renvoie un conteneur du type d'origine.

C'est ainsi que vous conservez la sémantique - c'est-à-dire que la signification et les opérations du conteneur ne changent pas, elles enveloppent et améliorent simplement l'objet à l'intérieur du conteneur.

Rob
la source
2

Les monades d'usage courant sont l'équivalent fonctionnel des mécanismes de gestion des exceptions de la programmation procédurale.

Dans les langages procéduraux modernes, vous placez un gestionnaire d'exceptions autour d'une séquence d'instructions, dont chacune peut lever une exception. Si l'une des instructions lève une exception, l'exécution normale de la séquence d'instructions s'arrête et est transférée vers un gestionnaire d'exceptions.

Les langages de programmation fonctionnels, cependant, évitent philosophiquement les fonctionnalités de gestion des exceptions en raison de leur nature "goto". La perspective de la programmation fonctionnelle est que les fonctions ne devraient pas avoir d '«effets secondaires» comme des exceptions qui perturbent le déroulement du programme.

En réalité, les effets secondaires ne peuvent pas être exclus dans le monde réel en raison principalement des E / S. Les monades dans la programmation fonctionnelle sont utilisées pour gérer cela en prenant un ensemble d'appels de fonction chaînés (dont l'un pourrait produire un résultat inattendu) et en transformant tout résultat inattendu en données encapsulées qui peuvent toujours circuler en toute sécurité à travers les appels de fonction restants.

Le flux de contrôle est conservé mais l'événement inattendu est encapsulé et géré en toute sécurité.

David K. Hess
la source
2

Une explication simple des Monades avec une étude de cas de Marvel est ici .

Les monades sont des abstractions utilisées pour séquencer des fonctions dépendantes qui sont efficaces. Efficace ici signifie qu'ils retournent un type sous la forme F [A] par exemple Option [A] où Option est F, appelé constructeur de type. Voyons cela en 2 étapes simples

  1. La composition ci-dessous est transitive. Donc passer de A à CI peut composer A => B et B => C.
 A => C   =   A => B  andThen  B => C

entrez la description de l'image ici

  1. Cependant, si la fonction renvoie un type d'effet comme l'option [A], c'est-à-dire A => F [B], la composition ne fonctionne pas car pour aller à B, nous avons besoin de A => B mais nous avons A => F [B].
    entrez la description de l'image ici

    Nous avons besoin d'un opérateur spécial, "bind" qui sait fusionner ces fonctions qui renvoient F [A].

 A => F[C]   =   A => F[B]  bind  B => F[C]

La fonction "bind" est définie pour le F spécifique .

Il existe également un "retour" , de type A => F [A] pour tout A , défini pour ce F spécifique également. Pour être une Monade, F doit avoir ces deux fonctions définies pour lui.

Ainsi, nous pouvons construire une fonction efficace A => F [B] à partir de toute fonction pure A => B ,

 A => F[B]   =   A => B  andThen  return

mais un F donné peut également définir ses propres fonctions spéciales "intégrées" opaques de tels types qu'un utilisateur ne peut pas se définir lui-même (dans un langage pur ), comme

  • "aléatoire" ( Range => Random [Int] )
  • "print" ( String => IO [()] )
  • "essayez ... attrapez", etc.
Ira
la source
2

Je partage ma compréhension des Monades, qui peuvent ne pas être théoriquement parfaites. Les monades concernent la propagation du contexte . Monad est, vous définissez un contexte pour certaines données (ou types de données), puis définissez comment ce contexte sera transporté avec les données tout au long de son pipeline de traitement. Et définir la propagation du contexte consiste principalement à définir comment fusionner plusieurs contextes (du même type). L'utilisation de Monads signifie également que ces contextes ne sont pas accidentellement supprimés des données. D'un autre côté, d'autres données sans contexte peuvent être introduites dans un contexte nouveau ou existant. Ensuite, ce concept simple peut être utilisé pour garantir l'exactitude du temps de compilation d'un programme.

Gulshan
la source
1

Voir ma réponse à "Qu'est-ce qu'une monade?"

Il commence par un exemple motivant, passe par l'exemple, dérive un exemple de monade et définit formellement «monade».

Il ne suppose aucune connaissance de la programmation fonctionnelle et utilise un pseudocode avec function(argument) := expressionsyntaxe avec les expressions les plus simples possibles.

Ce programme C ++ est une implémentation de la monade pseudocode. (Pour référence: Mest le constructeur de type, feedest l'opération "bind" et wrapest l'opération "return".)

#include <iostream>
#include <string>

template <class A> class M
{
public:
    A val;
    std::string messages;
};

template <class A, class B>
M<B> feed(M<B> (*f)(A), M<A> x)
{
    M<B> m = f(x.val);
    m.messages = x.messages + m.messages;
    return m;
}

template <class A>
M<A> wrap(A x)
{
    M<A> m;
    m.val = x;
    m.messages = "";
    return m;
}

class T {};
class U {};
class V {};

M<U> g(V x)
{
    M<U> m;
    m.messages = "called g.\n";
    return m;
}

M<T> f(U x)
{
    M<T> m;
    m.messages = "called f.\n";
    return m;
}

int main()
{
    V x;
    M<T> m = feed(f, feed(g, wrap(x)));
    std::cout << m.messages;
}
Jordan
la source
0

D'un point de vue pratique (résumant ce qui a été dit dans de nombreuses réponses précédentes et articles connexes), il me semble que l'un des «buts» (ou l'utilité) fondamentaux de la monade est de tirer parti des dépendances implicites dans les invocations de méthodes récursives aka composition de la fonction (c'est-à-dire lorsque f1 appelle f2 appelle f3, f3 doit être évalué avant f2 avant f1) pour représenter la composition séquentielle de manière naturelle, en particulier dans le contexte d'un modèle d'évaluation paresseux (c'est-à-dire, la composition séquentielle comme une séquence simple , par exemple "f3 (); f2 (); f1 ();" en C - l'astuce est particulièrement évidente si vous pensez à un cas où f3, f2 et f1 ne retournent en fait rien [leur chaînage comme f1 (f2 (f3)) est artificiel, purement destiné à créer une séquence]).

Ceci est particulièrement pertinent lorsque des effets secondaires sont impliqués, c'est-à-dire lorsqu'un état est modifié (si f1, f2, f3 n'avaient pas d'effets secondaires, peu importe l'ordre dans lequel ils sont évalués; ce qui est une grande propriété de pure langages fonctionnels, pour pouvoir paralléliser ces calculs par exemple). Plus les fonctions sont pures, mieux c'est.

Je pense que de ce point de vue étroit, les monades pourraient être considérées comme du sucre syntaxique pour les langues qui favorisent l'évaluation paresseuse (qui n'évaluent les choses qu'en cas de nécessité absolue, en suivant un ordre qui ne repose pas sur la présentation du code), et qui n'ont pas d'autres moyens de représenter la composition séquentielle. Le résultat net est que les sections de code qui sont "impures" (c'est-à-dire qui ont des effets secondaires) peuvent être présentées naturellement, de manière impérative, mais sont clairement séparées des fonctions pures (sans effets secondaires), qui peuvent être évalué paresseusement.

Ce n'est qu'un aspect cependant, comme averti ici .

novis
la source
0

L'explication la plus simple à laquelle je peux penser est que les monades sont un moyen de composer des fonctions avec des résultats embellis (alias Kleisli composition). Une fonction "embelli" a la signature a -> (b, smth)aet bsont des types (pensez Int, Bool) qui peuvent être différents les uns des autres, mais pas nécessairement - et smthc'est le "contexte" ou l '"embellissement".

Ce type de fonctions peut également être écrit a -> m bmest équivalent à "l'embellissement" smth. Ce sont donc des fonctions qui renvoient des valeurs dans leur contexte (pensez aux fonctions qui enregistrent leurs actions, où smthest le message de journalisation; ou aux fonctions qui effectuent des entrées / sorties et leurs résultats dépendent du résultat de l'action IO).

Une monade est une interface ("typeclass") qui fait dire à l'implémenteur comment composer de telles fonctions. L'implémenteur doit définir une fonction de composition (a -> m b) -> (b -> m c) -> (a -> m c)pour tout type mqui souhaite implémenter l'interface (il s'agit de la composition de Kleisli).

Donc, si nous disons que nous avons un type de tuple (Int, String)représentant les résultats des calculs sur les Ints qui enregistrent également leurs actions, avec (_, String)étant "l'embellissement" - le journal de l'action - et deux fonctions increment :: Int -> (Int, String)et twoTimes :: Int -> (Int, String)nous voulons obtenir une fonction incrementThenDouble :: Int -> (Int, String)qui est la composition des deux fonctions qui prend également en compte les journaux.

Sur l'exemple donné, une implémentation monade des deux fonctions s'applique à la valeur entière 2 incrementThenDouble 2(qui est égale à twoTimes (increment 2)) retournerait (6, " Adding 1. Doubling 3.")pour des résultats intermédiaires increment 2égaux (3, " Adding 1.")et twoTimes 3égaux à(6, " Doubling 3.")

De cette fonction de composition de Kleisli, on peut dériver les fonctions monadiques habituelles.

Coquelicot rouge
la source