[Oop] Monade en anglais ordinaire? (Pour le programmeur POO sans arrière-plan FP)


Answers

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

En termes qu'un programmeur POO comprendrait (sans 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 .

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érons Nullable<T> . C'est un amplificateur de types. Il vous permet de prendre un type, disons int , et d'ajouter une nouvelle fonctionnalité à ce type, à savoir, que maintenant il peut être null quand il ne pouvait pas auparavant.

Comme deuxième exemple, considérons IEnumerable<T> . C'est un amplificateur de types. Il vous permet de prendre un type, disons, une string , et d'ajouter une nouvelle fonctionnalité à ce type, à savoir, que vous pouvez maintenant faire une séquence de chaînes de n'importe quel nombre de chaînes uniques.

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

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

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

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

Quelles sont les "opérations"?

  1. Opération de retour (également unité ) - opération unaire qui prend une valeur d'un type simple et la place dans un conteneur en utilisant le constructeur - créant une valeur monadique. Ceci, en substance, fournit un moyen de prendre une valeur d'un type non amplifié et de le transformer en une valeur du type amplifié.
  2. Opération de liaison - l'opération de liaison binaire prend comme arguments une valeur monadique et une fonction qui peut transformer la valeur et renvoie une nouvelle valeur monadique.
    • L'opérateur de liaison déroule la valeur brute, incorporée dans sa valeur monadique d'entrée, et la transmet à la fonction.
    • La fonction crée ensuite une nouvelle valeur monadique, qui peut être transmise aux prochains opérateurs de liaison composés dans le pipeline.
    • Cela permet de transformer des opérations sur le type non amplifié en opérations sur le type amplifié, qui obéit aux règles de composition fonctionnelle mentionnées précédemment.
  3. Un moyen de sortir le type non amplifié du type amplifié. (Ce dernier point n'est pas strictement nécessaire pour une monade mais il est fréquent qu'une telle opération existe.)

Encore une fois, prenez Nullable<T> comme exemple. Vous pouvez transformer un int en Nullable<int> avec le constructeur. Le compilateur C # prend soin de la plupart des "levages" pour vous, mais si ce n'est pas le cas, la transformation de levage est simple: une opération, disons,

int M(int x) { whatever }

est transformé en

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

Et transformer un Nullable<int> en un int est fait avec la propriété Value .

C'est la transformation de la fonction qui est le bit clé. Notez comment la sémantique réelle de l'opération nullable - qu'une opération sur un null propage le null - est capturée dans la transformation. Nous pouvons généraliser cela. Supposons que vous ayez une fonction de int à int , comme notre M origine. Vous pouvez facilement transformer cela en une fonction qui prend un int et renvoie un Nullable<int> parce que vous pouvez simplement exécuter le résultat via le constructeur Nullable. Supposons maintenant que vous avez cette méthode d'ordre supérieur:

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 int et renvoie un int , ou prend un int et retourne un Nullable<int> peut maintenant avoir la sémantique Nullable qui lui est appliquée .

En outre: supposons que vous avez deux méthodes

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

et vous voulez les composer:

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

C'est-à-dire que Z est la composition de X et Y Mais vous ne pouvez pas faire cela parce que X prend un int , et Y retourne 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 de fonctions sur les types amplifiés. Les "règles" que j'ai manipulées ci-dessus sont que la monade préserve les règles de la composition normale des fonctions; la composition avec des fonctions d'identité aboutit à la fonction originale, cette composition est associative, etc.

En C #, "Bind" s'appelle "SelectMany". Jetez un oeil à la façon dont cela fonctionne sur la séquence monad. Nous devons avoir trois choses: transformer une valeur en une séquence, transformer une séquence en une valeur et lier des opérations sur des séquences. Ces opérations sont:

IEnumerable<T> MakeSequence<T>(T item)
{
    yield return item;
}
T Single<T>(IEnumerable<T> sequence)
{
    // let's just take the first one
    foreach(T item in sequence) return item; 
}
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 ensemble des valeurs nulles, vérifier si la valeur intérieure donne null, sinon produire une valeur nulle, sinon, appeler la fonction externe avec le résultat". C'est la sémantique désiré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 dit ce que la monade signifie vraiment.

Nous pouvons faire encore mieux. Supposons que vous ayez une séquence d'ints, et une méthode qui prend en entrée et qui donne des suites 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:

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 groupe d'entiers individuels dans une séquence d'entiers." Transformer cet entier particulier en un groupe de cordes, amplifié à une séquence de chaînes.Maintenant ensemble les deux opérations: amplifier ce groupe 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 communs où il est utilisé?

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

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

  • J'ai besoin de faire de nouvelles fonctionnalités pour ce type tout en combinant les anciennes fonctions de ce type pour utiliser les nouvelles fonctionnalité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, construisant des compositions de plus en plus grandes jusqu'à ce que j'ai juste la bonne série d'opérations représentées, et puis je dois commencer à obtenir des résultats
  • Je dois représenter proprement les opérations secondaires dans un langage qui déteste les effets secondaires

(Notez que ce sont essentiellement trois façons de dire la même chose.)

C # utilise des monades dans sa conception. Comme déjà mentionné, le modèle nullable est très proche de la "peut-être monade". LINQ est entièrement construit à partir de monades; la méthode SelectMany est ce que fait le travail sémantique de la composition des opérations. (Erik Meijer aime souligner que chaque fonction LINQ pourrait effectivement ê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 étiez en train de convertir une application de PF qui avait des monades en une application POO. Que feriez-vous pour transférer les responsabilités des monades dans l'application POO?

La plupart des langages OOP ne disposent pas d'un système de type assez riche pour représenter directement le modèle de monad; vous avez besoin d'un système de type qui supporte les types qui sont des types plus élevés que les types génériques. Donc je n'essaierais pas de faire ça. J'implémenterais plutôt 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, transformer une valeur amplifiée en valeur et transformer une fonction sur des valeurs non amplifiées en une fonction valeurs amplifiées.

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

Pour une explication plus approfondie et théorique des monades en C #, je recommande fortement l'article de mon collègue Wes Dyer sur le sujet. Cet article est ce qui m'a expliqué les monades quand elles ont finalement "cliqué" sur moi.

Les merveilles des monades

Les illustrations sont empruntées à:
JavaScript Awesomely descriptive avec présentation des monades par Michal Nowak
et
Une Monade Hyperturtle fait de Pretty Pictures article par Jonathan Vincent Toups .

Question

En termes qu'un programmeur POO comprendrait (sans 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 communs où il est utilisé?

MODIFIER:

Pour clarifier le type de compréhension que je cherchais, disons que vous étiez en train de convertir une application de PF qui avait des monades en une application POO. Que feriez-vous pour transférer les responsabilités des monades à l'application POO?




En termes qu'un programmeur POO comprendrait (sans 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 utilisés? Les endroits les plus communs sont-ils utilisés?

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, return et bind qui décrivent:

  • Comment injecter une valeur pour obtenir une valeur monadique de ce type de valeur injectée;
  • Comment utiliser une fonction qui fait 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 auquel vous vous attendez d'une 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 similarité sous-jacente. 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 «l'objet» lui-même?

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




See my answer to "What is a monad?"

It begins with a motivating example, works through the example, derives an example of a monad, and formally defines "monad".

It assumes no knowledge of functional programming and it uses pseudocode with function(argument) := expression syntax with the simplest possible expressions.

This C++ program is an implementation of the pseudocode monad. (For reference: M is the type constructor, feed is the "bind" operation, and wrap is the "return" operation.)

#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;
}



Je dirais que l'analogie OO la plus proche des monades est le " pattern pattern ".

Dans le modèle de commande, vous enveloppez une instruction ou une expression ordinaire dans un objet de commande . L'objet de commande expose une méthode execute qui exécute l'instruction enveloppée. Ainsi, les déclarations sont 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 enchaînant et en imbriquant des objets de commande.

Les commandes sont exécutées par un objet distinct, l' invocateur . L'avantage de l'utilisation du modèle de commande (plutôt que d'exécuter simplement une série d'instructions ordinaires) est que différents invokers 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 de langue qui ne sont pas prises en charge par le langage hôte. Par exemple, dans un langage OO hypothétique sans exceptions, 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 effectue un retour arrière dans la liste (ou l'arborescence) des commandes jusqu'au dernier appel "try". Inversement, vous pouvez supprimer la sémantique d'exception d'une langue (si vous pensez que les exceptions sont mauvaises ) en interceptant toutes les exceptions émises par chaque commande et en les transformant en codes d'erreur qui sont ensuite transmis à la commande suivante.

Des sémantiques d'exécution encore plus fantaisistes comme des transactions, des exécutions non déterministes ou des continuations peuvent être implémentées de la sorte dans un langage qui ne le supporte pas nativement. 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 caractéristique générale du langage comme celle-ci. L'overhead de transformer chaque déclaration en classe distincte conduirait à 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 dans fp.




Whether a monad has a "natural" interpretation in OO depends on the monad. In a language like Java, you can translate the maybe monad to the language of checking for null pointers, so that computations that fail (ie, produce Nothing in Haskell) emit null pointers as results. You can translate the state monad into the language generated by creating a mutable variable and methods to change its state.

A monad is a monoid in the category of endofunctors.

The information that sentence puts together is very deep. And you work in a monad with any imperative language. A monad is a "sequenced" domain specific language. It satisfies certain interesting properties, which taken together make a monad a mathematical model of "imperative programming". Haskell makes it easy to define small (or large) imperative languages, which can be combined in a variety of ways.

As an OO programmer, you use your language's class hierarchy to organize the kinds of functions or procedures that can be called in a context, what you call an object. A monad is also an abstraction on this idea, insofar as different monads can be combined in arbitrary ways, effectively "importing" all of the sub-monad's methods into the scope.

Architecturally, one then uses type signatures to explicitly express which contexts may be used for computing a value.

One can use monad transformers for this purpose, and there is a high quality collection of all of the "standard" monads:

  • Lists (non-deterministic computations, by treating a list as a domain)
  • Maybe (computations that can fail, but for which reporting is unimportant)
  • Error (computations that can fail and require exception handling
  • Reader (computations that can be represented by compositions of plain Haskell functions)
  • Writer (computations with sequential "rendering"/"logging" (to strings, html etc)
  • Cont (continuations)
  • IO (computations that depend on the underlying computer system)
  • State (computations whose context contains a modifiable value)

with corresponding monad transformers and type classes. Type classes allow a complementary approach to combining monads by unifying their interfaces, so that concrete monads can implement a standard interface for the monad "kind". For example, the module Control.Monad.State contains a class MonadState sm, and (State s) is an instance of the form

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

The long story is that a monad is a functor which attaches "context" to a value, which has a way to inject a value into the monad, and which has a way to evaluate values with respect to the context attached to it, at least in a restricted way.

Alors:

return :: a -> m a

is a function which injects a value of type a into a monad "action" of type m a.

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

is a function which takes a monad action, evaluates its result, and applies a function to the result. The neat thing about (>>=) is that the result is in the same monad. In other words, in m >>= f, (>>=) pulls the result out of m, and binds it to f, so that the result is in the monad. (Alternatively, we can say that (>>=) pulls f into m and applies it to the result.) As a consequence, if we have f :: a -> mb, and g :: b -> mc, we can "sequence" actions:

m >>= f >>= g

Or, using "do notation"

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

The type for (>>) might be illuminating. It is

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

It corresponds to the (;) operator in procedural languages like C. It allows do notation like:

m = do x <- someQuery
       someAction x
       theNextAction
       andSoOn

In mathematical and philosopical logic, we have frames and models, which are "naturally" modelled with monadism. An interpretation is a function which looks into the model's domain and computes the truth value (or generalizations) of a proposition (or formula, under generalizations). In a modal logic for necessity, we might say that a proposition is necessary if it is true in "every possible world" -- if it is true with respect to every admissible domain. This means that a model in a language for a proposition can be reified as a model whose domain consists of collection of distinct models (one corresponding to each possible world). Every monad has a method named "join" which flattens layers, which implies that every monad action whose result is a monad action can be embedded in the monad.

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

More importantly, it means that the monad is closed under the "layer stacking" operation. This is how monad transformers work: they combine monads by providing "join-like" methods for types like

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

so that we can transform an action in (MaybeT m) into an action in m, effectively collapsing layers. In this case, runMaybeT :: MaybeT ma -> m (Maybe a) is our join-like method. (MaybeT m) is a monad, and MaybeT :: m (Maybe a) -> MaybeT ma is effectively a constructor for a new type of monad action in m.

A free monad for a functor is the monad generated by stacking f, with the implication that every sequence of constructors for f is an element of the free monad (or, more exactly, something with the same shape as the tree of sequences of constructors for f). Free monads are a useful technique for constructing flexible monads with a minimal amount of boiler-plate. In a Haskell program, I might use free monads to define simple monads for "high level system programming" to help maintain type safety (I'm just using types and their declarations. Implementations are straight-forward with the use of combinators):

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))

Monadism is the underlying architecture for what you might call the "interpreter" or "command" pattern, abstracted to its clearest form, since every monadic computation must be "run", at least trivially. (The runtime system runs the IO monad for us, and is the entry point to any Haskell program. IO "drives" the rest of the computations, by running IO actions in order).

The type for join is also where we get the statement that a monad is a monoid in the category of endofunctors. Join is typically more important for theoretical purposes, in virtue of its type. But understanding the type means understanding monads. Join and monad transformer's join-like types are effectively compositions of endofunctors, in the sense of function composition. To put it in a Haskell-like pseudo-language,

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




From a practical point of view (summarizing what has been said in many previous answers and related articles), it seems to me that one of the fundamental "purposes" (or usefulness) of the monad is to leverage the dependencies implicit in recursive method invocations aka function composition (ie when f1 calls f2 calls f3, f3 needs to be evaluated before f2 before f1) to represent sequential composition in a natural way, especially in the context of a lazy evaluation model (that is, sequential composition as a plain sequence, eg "f3(); f2(); f1();" in C - the trick is especially obvious if you think of a case where f3, f2 and f1 actually return nothing [their chaining as f1(f2(f3)) is artificial, purely intended to create sequence]).

This is especially relevant when side-effects are involved, ie when some state is altered (if f1, f2, f3 had no side-effects, it wouldn't matter in what order they're evaluated; which is a great property of pure functional languages, to be able to parallelize those computations for example). The more pure functions, the better.

I think from that narrow point of view, monads could be seen as syntactic sugar for languages that favor lazy evaluation (that evaluate things only when absolutely necessary, following an order that does not rely on the presentation of the code), and that have no other means of representing sequential composition. The net result is that sections of code that are "impure" (ie that do have side-effects) can be presented naturally, in an imperative manner, yet are cleanly separated from pure functions (with no side-effects), which can be evaluated lazily.

This is only one aspect though, as warned here .




In OO terms, a monad is a fluent container.

The minimum requirement is a definition of class <A> Something that supports a constructor Something(A a) and at least one method Something<B> flatMap(Function<A, Something<B>>)

Arguably, it also counts if your monad class has any methods with signature Something<B> work() which preserves the class's rules -- the compiler bakes in flatMap at compile time.

Why is a monad useful? Because it is a container that allows chain-able operations that preserve semantics. For example, Optional<?> preserves the semantics of isPresent for Optional<String> , Optional<Integer> , Optional<MyClass> , etc.

As a rough example,

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

Note we start with a string and end with an integer. Pretty cool.

In OO, it might take a little hand-waving, but any method on Something that returns another subclass of Something meets the criterion of a container function that returns a container of the original type.

That's how you preserve semantics -- ie the container's meaning and operations don't change, they just wrap and enhance the object inside the container.




Vous avez une présentation récente " Monadologie - aide professionnelle sur l'anxiété de type " par Christopher League (12 juillet 2010), ce qui est assez intéressant sur des sujets de continuation et de monade.
La vidéo avec 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 avec la diapositive 42 de sa présentation de diapositives 58.

Il est présenté comme "le modèle de conception principal pour la programmation fonctionnelle", mais le langage utilisé dans les exemples est Scala, qui est à la fois OOP et fonctionnel.
Vous pouvez lire plus sur Monad dans Scala dans l'article de blog " Monades - Une autre façon d'abstraire des calculs dans Scala ", de Debasish Ghosh (27 mars 2008).

Un constructeur de type M est une monade s'il supporte 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 (à Scala):

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

    def flatMap[A,B](m:Option[A])(f:A =>Option[B]): Option[B] =
      m match {
       case None => None
       case Some(x) => f(x)
      }
  • List est Monad
    def unit[A] (x: A): List[A] = List(x)

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

Les monades sont une grosse affaire dans Scala en raison de la syntaxe pratique construite pour tirer parti des structures Monad:

for compréhension à Scala :

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

est traduit par le compilateur pour:

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

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

Dans l'extrait ci-dessus, flatMap prend en entrée une fermeture (SomeType) => List[AnotherType] et renvoie une 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 dans la for-comprehension doit honorer cette même contrainte de type.

Si vous prenez 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 fonctionnent, et garder le truc de vérification d'Option caché, 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 rendement ne sera exécutée que si les trois fonctions ont Some[X] ; aucun None serait directement retourné pour confirm .

Alors:

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

Et la plus grande puissance vient avec la capacité de composer des monades qui servent des buts différents, dans des abstractions extensible dans une application.

Ce séquençage et le filetage des actions par une monade est fait par le compilateur de langage qui fait la transformation à travers la magie des fermetures.

En passant, Monad n'est pas seulement un modèle de calcul utilisé dans FP: voir ce blog .

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

  • le modèle de calcul de Arrow
  • le modèle de calcul de Monad
  • le modèle Applicatif de calculs



Pour respecter les lecteurs rapides, je commence par une définition précise d'abord, continuez avec une explication plus rapide de "l'anglais simple", puis passez aux exemples.

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

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

  • envoie chaque type X d'un langage de programmation donné à un nouveau type T(X) (appelé le "type de T -computations 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 associative dans le 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 pour passer de n'importe quel type X à un autre type T(X) , et une règle pour passer de deux fonctions f:X->T(Y) et g:Y->T(Z) (que vous aimeriez composer mais ne peut pas) à une nouvelle fonction h:X->T(Z) . Ce qui, cependant, n'est pas la composition au sens mathématique strict. Nous sommes fondamentalement en train de «plier» la composition de la 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 f avec g puis avec h (de l'extérieur) devrait être la même chose que composer g avec h et ensuite avec f (de l'intérieur).
  • Propriété unitaire : Composer f avec la fonction d' identité de chaque côté devrait donner f .

Encore une fois, en termes simples, nous ne pouvons pas devenir fous redéfinir la composition de notre fonction comme nous l'aimons:

  • Nous avons d'abord besoin de l'associativité pour pouvoir composer plusieurs fonctions à la suite, par exemple f(g(h(k(x))) , et ne pas nous soucier de spécifier les paires de fonctions de composition d'ordre. une paire de fonctions , sans cet axiome, nous aurions besoin de savoir quelle paire est composée en premier et ainsi de suite (notez qu'elle est différente de la propriété de commutativité que f composée avec g était la même que g composée avec f , ce qui n'est pas nécessaire ).
  • Et deuxièmement, nous avons besoin de la propriété unitaire, qui est simplement de dire que les identités composent trivialement la façon dont nous les attendons. Nous pouvons donc refactoriser en toute sécurité les fonctions à chaque fois que ces identités peuvent être extraites.

Donc encore une fois en bref: 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.

En termes pratiques, vous voulez que la monade soit implémentée pour vous par le langage, le compilateur ou le framework qui prendrait soin des fonctions de composition pour vous. Vous pouvez donc vous concentrer sur l'écriture de la logique de votre fonction plutôt que sur la façon dont leur exécution est implémentée.

C'est essentiellement cela, en un mot.

En tant que mathématicien professionnel, je préfère éviter d'appeler h la «composition» de f et g . Parce que mathématiquement, ça ne l'est pas. L'appeler la "composition" suppose à tort que h est la vraie composition mathématique, ce qu'elle n'est pas. Il n'est même pas uniquement déterminé par f et g . Au lieu de cela, c'est le résultat de la nouvelle «règle de composition» des fonctions de notre monade. Ce qui peut être totalement différent de la composition mathématique réelle même si celle-ci existe!

La Monade n'est pas un foncteur ! Un foncteur F est une règle pour passer du type X au type F(X) et des fonctions (morphisme) entre les types X et Y aux fonctions entre F(X) et F(Y) (envoyer des objets aux objets et leurs morphismes aux morphismes théorie des catégories). Au lieu de cela, une monade envoie une paire de fonctions f et g à une nouvelle h .

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

Exception jetant comme exemples Monad

Supposons que nous voulions composer deux fonctions:

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

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

Qu'est-ce qui se passe précisément ici? Premièrement, nous avons besoin de nouvelles valeurs d'exception (différentes ou identiques). Vous pouvez les appeler nothing ou null ou n'importe quoi, mais l'essence reste la même - ils devraient être de nouvelles valeurs, par exemple, il ne devrait pas être un number dans notre exemple ici. Je préfère ne pas les appeler null pour éviter la confusion avec la façon dont null ne peut être implémenté dans une langue spécifique. De même, je préfère ne nothing éviter parce qu'il est souvent associé à la null , ce qui, en principe, est ce que null devrait faire, cependant, ce principe se plie souvent pour toutes les raisons pratiques.

Qu'est-ce que l'exception exactement?

C'est une question triviale pour tout programmeur expérimenté, mais je voudrais laisser tomber quelques mots juste pour éteindre tout ver de confusion:

Exception est un objet encapsulant des informations sur la façon dont le résultat d'exécution invalide s'est produit.

Cela peut aller de jeter tous les détails et renvoyer une seule valeur globale (comme NaN ou null ) ou générer une longue liste de journaux ou ce qui s'est exactement passé, l'envoyer à une base de données et la répliquer partout dans la couche de stockage de données distribuée;

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 la seconde il y a. Ce qui nous amène à la question (mille dollars):

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

Réponse plus courte : Oui, mais seulement quand ils ne conduisent pas à des effets secondaires.

Réponse plus longue Pour être pur, la sortie de votre fonction doit être déterminée uniquement par son entrée. Nous modifions donc notre fonction f en envoyant 0 à la nouvelle valeur abstraite e que nous appelons exception. Nous nous assurons que la valeur e ne contient aucune information extérieure qui ne soit pas uniquement déterminée par notre entrée, 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 donc il n'y a pas d'effet secondaire.

Pour le rendre encore plus idiot. Une fonction qui revient 42 est clairement pure. Mais si quelqu'un fou décide de faire une 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 d'objet pour la simplicité pour démontrer l'essence. Malheureusement, les choses sont gâchées dans des langages comme JavaScript, où l' error n'est 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 comme null ou NaN ne se comportent pas comme ça. conversions de type pas toujours intuitives.

Type d'extension

Comme nous voulons faire varier le message à l'intérieur de notre exception, nous déclarons vraiment un nouveau type E pour tout l'objet d'exception, puis c'est ce que fait le maybe number , en dehors de son nom confus, qui doit être soit de type number ou le nouveau type d'exception E , donc c'est vraiment le number | E union number | E number | E de number et E In particular, it depends on how we want to construct E , which is neither suggested nor reflected in the name maybe number .

What is functional composition?

It is the mathematical operation taking functions f: X -> Y and g: Y -> Z and constructing their composition as function h: X -> Z satisfying h(x) = g(f(x)) . The problem with this definition occurs when the result f(x) is not allowed as argument of g .

In mathematics those functions cannot be composed without extra work. The strictly mathematical solution for our above example of f and g is to remove 0 from the set of definition of f . With that new set of definition (new more restrictive type of x ), f becomes composable with g .

However, it is not very practical in programming to restrict the set of definition of f like that. Instead, exceptions can be used.

Or as another approach, artificial values are created like NaN , undefined , null , Infinity etc. So you evaluate 1/0 to Infinity and 1/-0 to -Infinity . And then force the new value back into your expression instead of throwing exception. Leading to results you may or may not find predictable:

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

And we are back to regular numbers ready to move on ;)

JavaScript allows us to keep executing numerical expressions at any costs without throwing errors as in the above example. That means, it also allows to compose functions. Which is exactly what monad is about - it is a rule to compose functions satisfying the axioms as defined at the beginning of this answer.

But is the rule of composing function, arising from JavaScript's implementation for dealing with numerical errors, a monad?

To answer this question, all you need is to check the axioms (left as exercise as not part of the question here;).

Can throwing exception be used to construct a monad?

Indeed, a more useful monad would instead be the rule prescribing that if f throws exception for some x , so does its composition with any g . Plus make the exception E globally unique with only one possible value ever ( terminal object in category theory). Now the two axioms are instantly checkable and we get a very useful monad. And the result is what is well-known as the maybe monad .




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. C'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 g , puis f , écrivez simplement f(g(x,y)) . OK mais ...

  3. Plus de problèmes: certaines fonctions peuvent échouer (ie g(2,0) , diviser par 0). Nous n'avons aucune "exception" dans FP . Comment pouvons-nous le résoudre?

    Laisser les fonctions renvoyer deux sortes de choses : au lieu d'avoir g : Real,Real -> Real (fonction de deux réels en un réel), admettons g : Real,Real -> Real | Nothing g : Real,Real -> Real | Nothing (fonction de deux réels en (réel ou rien)).

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

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

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

    Solution: avons une fonction spéciale pour "connecter" / "composer" / "lien" fonctions . De cette façon, nous pouvons, dans les coulisses, adapter la sortie d'une fonction pour alimenter la suivante.

    Dans notre cas: g >>= f (connecter / composer g à f ). Nous voulons >>= obtenir la sortie de g , l'inspecter et, dans le cas contraire, ne pas appeler f et retourner Nothing ; ou au contraire, extraire le Real encadré et nourrir f avec lui. (Cet algorithme est juste l'implémentation de >>= pour le type Maybe ).

  6. Beaucoup d'autres problèmes surgissent 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 g qui renvoient ces "valeurs encadrées". 2. Avoir des compositeurs / lieurs g >>= f pour aider à connecter la sortie de g l'entrée f , donc nous n'avons pas besoin de changer f du 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 donnent des résultats différents pour la même entrée. Par conséquent, marquons ces fonctions, en leur faisant retourner une valeur étiquetée / encadrée: IO monad.

Total bonheur




A monad is an array of functions

(Pst: an array of functions is just a computation).

Actually, instead of a true array (one function in one cell array) you have those functions chained by another function >>=. The >>= allows to adapt the results from function i to feed function i+1, perform calculations between them or, even, not to call function i+1.

The types used here are "types with context". This is, a value with a "tag". The functions being chained must take a "naked value" and return a tagged result. One of the duties of >>= is to extract a naked value out of its context. There is also the function "return", that takes a naked value and puts it with a tag.

An example with Maybe . Let's use it to store a simple integer on which make calculations.

-- 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

Just to show that monads are array of functions with helper operations, consider the equivalent to the above example, just using a real array of functions

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

And it would be used like this:

print (runMyMonad (Just 160) myArray1)



From wikipedia :

In functional programming, a monad is a kind of abstract data type used to represent computations (instead of data in the domain model). Monads allow the programmer to chain actions together to build a pipeline, in which each action is decorated with additional processing rules provided by the monad. Programs written in functional style can make use of monads to structure procedures that include sequenced operations, wikipedia [2] or to define arbitrary control flows (like handling concurrency, continuations, or exceptions).

Formally, a monad is constructed by defining two operations (bind and return) and a type constructor M that must fulfill several properties to allow the correct composition of monadic functions (ie functions that use values from the monad as their arguments). The return operation takes a value from a plain type and puts it into a monadic container of type M. The bind operation performs the reverse process, extracting the original value from the container and passing it to the associated next function in the pipeline.

A programmer will compose monadic functions to define a data-processing pipeline. The monad acts as a framework, as it's a reusable behavior that decides the order in which the specific monadic functions in the pipeline are called, and manages all the undercover work required by the computation.[3] The bind and return operators interleaved in the pipeline will be executed after each monadic function returns control, and will take care of the particular aspects handled by the monad.

I believe it explains it very well.







Monads in typical usage are the functional equivalent of procedural programming's exception handling mechanisms.

In modern procedural languages, you put an exception handler around a sequence of statements, any of which may throw an exception. If any of the statements throws an exception, normal execution of the sequence of statements halts and transfers to an exception handler.

Functional programming languages, however, philosophically avoid exception handling features due to the "goto" like nature of them. The functional programming perspective is that functions should not have "side-effects" like exceptions that disrupt program flow.

In reality, side-effects cannot be ruled out in the real world due primarily to I/O. Monads in functional programming are used to handle this by taking a set of chained function calls (any of which might produce an unexpected result) and turning any unexpected result into encapsulated data that can still flow safely through the remaining function calls.

The flow of control is preserved but the unexpected event is safely encapsulated and handled.




I'll try to make the shortest definition I can manage using OOP terms:

A generic class CMonadic<T> is a monad if it defines at least the following methods:

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
}

and if the following laws apply for all types T and their possible values t

left identity:

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

right identity

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

associativity:

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

Exemples :

A List monad may have:

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

And flatMap on the list [1,2,3] could work like so:

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

Iterables and Observables can also be made monadic, as well as Promises and Tasks.

Commentary :

Monads are not that complicated. The flatMap function is a lot like the more commonly encountered map . It receives a function argument (also known as delegate), which it may call (immediately or later, zero or more times) with a value coming from the generic class. It expects that passed function to also wrap its return value in the same kind of generic class. To help with that, it provides create , a constructor that can create an instance of that generic class from a value. The return result of flatMap is also a generic class of the same type, often packing the same values that were contained in the return results of one or more applications of flatMap to the previously contained values. This allows you to chain flatMap as much as you want:

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

It just so happens that this kind of generic class is useful as a base model for a huge number of things. This (together with the category theory jargonisms) is the reason why Monads seem so hard to understand or explain. They're a very abstract thing and only become obviously useful once they're specialized.

For example, you can model exceptions using monadic containers. Each container will either contain the result of the operation or the error that has occured. The next function (delegate) in the chain of flatMap callbacks will only be called if the previous one packed a value in the container. Otherwise if an error was packed, the error will continue to propagate through the chained containers until a container is found that has an error handler function attached via a method called .orElse() (such a method would be an allowed extension)

Notes : Functional languages allow you to write functions that can operate on any kind of a monadic generic class. For this to work, one would have to write a generic interface for monads. I don't know if its possible to write such an interface in C#, but as far as I know it isn't:

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
}



These are all really verbose answers. In a nutshell, consider this:

a => b => c 

If c needs to invoke a method like c.foo() then b needs to make sure it always provides that type to c

In order to do that, we wrap b in a function called a monad. The monad has the try/catch or if/else logic to keep things running smoothly.

A super common example is if c expected a list to iterate. If b fails and returns Nil/None/undefined/0/false, etc then c is screwed. So it's failing return would be [] .




A monad is a data type that encapsulates a value, and to which, essentially, two operations can be applied:

  • return x creates a value of the monad type that encapsulates x
  • m >>= f (read it as "the bind operator") applies the function f to the value in the monad m

That's what a monad is. There are a few more technicalities , but basically those two operations define a monad. The real question is, "What a monad does ?", and that depends on the monad — lists are monads, Maybes are monads, IO operations are monads. All that it means when we say those things are monads is that they have the monad interface of return and >>= .







In terms that an OOP programmer would understand (without any functional programming background), what is a monad?

There is no such explanation that I know of, and the suggestion that one exists belies arrogance on the part of OOP programmers.

What problem does it solve and what are the most common places it's used?

Monads solve many different problems with a unified interface, which is why they're useful. The main thing they're used for is laziness - they allow lazy functions with side effects, which is important for FFI and the like. They also are commonly used for error handling and parsing.

To clarify the kind of understanding I was looking for, let's say you were converting an FP application that had monads into an OOP application. What would you do to port the responsibilities of the monads to the OOP app?

Puisque la paresse n'est pas courante dans la POO, la plupart du temps, ils ne sont pas pertinents. Vous pouvez toutefois transférer la gestion des erreurs monadiques.