Monades avec Join () au lieu de Bind ()

Question

Les monades sont généralement expliqué virages return et bind. Cependant, je comprends que vous pouvez aussi mettre en oeuvre bind en termes de join (et fmap?)

Dans les langages de programmation manquent de première classe de fonctions, bind est atrocement difficile à utiliser. join, en revanche, semble assez facile.

Je ne suis pas complètement sûr de comprendre comment join fonctionne, cependant. Évidemment, il a l' [Haskell] type

joindre :: Monad m => m (m, x) -> m x

Pour la liste monade, c'est trivialement et évidemment concat. Mais pour une monade, ce qui, du point de vue opérationnel, cette méthode fait faire? Je vois ce qu'il fait pour le type de signatures, mais je suis à essayer de comprendre comment allais-je écrire quelque chose comme ceci, par exemple, en Java ou similaire.

(En fait, c'est simple: je ne le ferais pas. Parce que les génériques est cassé. ;-) Mais dans le principe, la question est toujours debout...)

---

Oups. Il ressemble à ce qui a été demandé avant:

Monade fonction join

Quelqu'un pourrait esquisser certaines implémentations de la commune de monades l'aide d' return, fmap et join? (I. e., ne pas mentionner >>= à tous.) Je pense que peut-être qui pourrait l'aider à s'enfoncer dans mon stupide cerveau...

Answer 1

Sans plomberie les profondeurs de la métaphore, pourrais-je vous suggérer de lire un typique monade m "stratégie pour produire une", de sorte que le type m value est une classe de première "stratégie pour produire une valeur". Les différentes notions de calcul ou externe interaction besoin de différents types de stratégie, mais la notion générale exige une certaine structure régulière pour faire sens:

• si vous avez déjà une valeur, alors vous avez une stratégie pour produire une valeur (return :: v -> m v) composé de rien d'autre que la production de la valeur que vous avez;
• si vous avez une fonction qui transforme une sorte de valeur dans un autre, vous pouvez soulever des stratégies (fmap :: (v -> u) -> m v -> m u), juste en attente pour la stratégie à fournir sa valeur, puis de la transformer;
• si vous avez une stratégie pour produire une stratégie pour produire une valeur, alors vous pouvez construire une stratégie pour produire une valeur (join :: m (m v) -> m v) qui suit l'extérieur de la stratégie jusqu'à ce qu'il produit à l'intérieur de la stratégie, puis suit que l'intérieur de la stratégie de la valeur.

Prenons un exemple: feuille étiquetée arbres binaires...

data Tree v = Leaf v | Node (Tree v) (Tree v)

...représentent des stratégies pour produire des trucs en jetant une pièce de monnaie. Si la stratégie est - Leaf v, il y a votre v; si la stratégie est - Node h t, vous jetez une pièce de monnaie et de continuer par la stratégie d' h si la pièce montre des "chefs", t si c'est "queues".

instance Monad Tree where
  return = Leaf

Une stratégie de production de la stratégie est un arbre avec des arbres étiquetés feuilles: à la place de chacune de ces feuilles, il suffit d'une greffe dans l'arbre sous lequel il...

  join (Leaf tree) = tree
  join (Node h t)  = Node (join h) (join t)

...et bien sûr, nous avons fmap qui vient de relabels feuilles.

instance Functor Tree where
  fmap f (Leaf x)    = Leaf (f x)
  fmap f (Node h t)  = Node (fmap f h) (fmap f t)

Voici une stratégie pour produire une stratégie pour produire une Int.

Jetez une pièce de monnaie: si c'est "chefs", de jeter une pièce de choisir entre deux stratégies (production, respectivement, "jeter une pièce de monnaie pour la production de 0 ou de production de 1" ou "produire 2"); si c'est la "queue" en produire une troisième ("jeter une pièce de monnaie pour la production de 3 ou de jeter une pièce de monnaie pour 4 ou 5").

Clairement joins pour faire une stratégie de production de l' Int.

Ce que nous allons utiliser est le fait qu'une "stratégie pour produire une valeur" peut elle-même être considérée comme une valeur. En Haskell, l'incorporation de stratégies comme des valeurs est silencieux, mais en anglais, j'utilise les guillemets pour distinguer à l'aide d'une stratégie de simplement en parler. L' join opérateur exprime la stratégie "d'une certaine manière de produire la suite, une stratégie", ou "si vous sont dit d'une stratégie, vous pouvez alors utiliser cela".

(Méta. Je ne suis pas sûr de savoir si cette "stratégie" est assez générique façon de penser et de monades et de la valeur/le calcul de la distinction, ou si c'est juste un autre minable métaphore. Je trouve que les feuilles étiquetées d'arbres tels que les types sont une source utile de l'intuition, qui est peut-être pas une surprise, car ils sont le gratuit monades, avec juste assez de structure pour être monades, mais pas plus.)

PS Le type de "lier"

(>>=) :: m v -> (v -> m w) -> m w

dit: "si vous avez une stratégie pour produire une v, et pour chaque valeur v d'un suivi sur la stratégie pour produire une w, alors vous avez une stratégie pour produire une w". Comment peut-on capturer qu'en termes de join?

mv >>= v2mw = join (fmap v2mw mv)

On peut reclasser nos v-la production de stratégie en v2mw, la production au lieu de chaque v de la valeur de l' w-la production de la stratégie qui en découle: prêt — à - join!

Answer 2

join = concat -- []
join f = \x -> f x x -- (e ->)
join f = \s -> let (f', s') = f s in f' s' -- State
join (Just (Just a)) = Just a; join _ = Nothing -- Maybe
join (Identity (Identity a)) = Identity a -- Identity
join (Right (Right a)) = Right a; join (Right (Left e)) = Left e; 
                                  join (Left e) = Left e -- Either
join ((a, m), m') = (a, m' `mappend` m) -- Writer
join f = \k -> f (\f' -> f' k) -- Cont

Answer 3

appelant fmap (f::a->m b) (x::m a) produit des valeurs (y::m (m b)) il est donc tout à fait naturel d'utiliser join pour obtenir le retour à des valeurs (z::m b).

Puis lier est définie simplement comme bind ma f = join (fmap f ma), atteignant ainsi l' Kleisly composition de fonctions d' (::a->m b) de la variété, qui est ce qu'il est réellement:

ma `bind` (f >=> g) = (ma `bind` f) `bind` g
                    = (`bind` g) . (`bind` f) $ ma 
                    = join (fmap g (join (fmap f ma)))

Answer 4

OK, donc c'est vraiment pas la bonne forme pour répondre à votre question, mais je vais noter mes pensées dans le cas où il l'éclaire de quelqu'un d'autre. (J'en doute...)

Si une monade peut être considéré comme un "conteneur", puis les deux return et join ont assez évident de la sémantique. return génère un 1-élément conteneur, et join tourne un conteneur de conteneurs dans un seul conteneur. Rien de difficile à ce sujet.

Donc concentrons-nous sur les monades qui sont plus naturellement considérés comme des "actions". Dans ce cas, m x est une action qui donne une valeur de type x lorsque vous "exécuter" il. return x n'a rien de spécial, et puis cède x. fmap f effectue une action qui donne un x, et construit une action qui calcule x , puis applique f , et retourne le résultat. Pour l'instant, donc bon.

Il est assez évident que si l' f génère lui-même une action, puis vous vous retrouvez avec est - m (m x). C'est, d'une action qui calcule une autre action. Dans un sens, c'est peut-être encore plus simple pour envelopper votre esprit autour de l' >>= fonction qui prend une action et une "fonction qui produit une action" et ainsi de suite.

Donc, logiquement parlant, il semble join permettrait de lancer la première action, de prendre les mesures qu'il produit, puis exécutez le. (Ou plutôt, join serait de retour une action qui fait ce que je viens de décrire, si vous voulez couper les cheveux.)

Qui semble être l'idée centrale. Pour mettre en oeuvre join, vous souhaitez exécuter une action, qui vous donne une autre action, et que vous exécutez. (Que ce soit "exécuter" arrive à dire pour cette monade.)

Compte tenu de cette idée, je peux prendre un coup de couteau à l'écriture de quelques join implémentations:

join Nothing = Nothing
join (Just mx) = mx

Si l'action extérieure est Nothing, rendement Nothing, sinon retour à l'intérieur de l'action. Puis de nouveau, Maybe est plus d'un contenant qu'une action, donc, nous allons essayer quelque chose d'autre...

newtype Reader s x = Reader (s -> x)

join (Reader f) = Reader (\ s -> let Reader g = f s in g s)

C'était... indolore. Un Reader est vraiment juste une fonction qui prend un état global, et seulement alors, retourne son résultat. Donc, pour dépiler, vous appliquez l'état global de l'action extérieure, qui retourne un nouveau Reader. Vous pouvez ensuite appliquer l'état pour cette fonction interne ainsi.

Dans un sens, c'est peut-être plus facile que de la manière habituelle:

Reader f >>= g = Reader (\ s -> let x = f s in g x)

Maintenant, qui est le lecteur de fonction, et qui est la fonction qui calcule le prochain lecteur...?

Maintenant, nous allons essayer la bonne vieille State monade. Ici, chaque fonction prend un état initial en entrée mais aussi renvoie un nouvel état avec sa sortie.

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

join (State f) = State (\ s0 -> let (s1, State g) = f s0 in g s1)

Ce n'était pas trop dur. Il s'agit essentiellement d'exécution, suivi de la course.

Je vais arrêter de taper maintenant. Hésitez pas à signaler tous les défauts et les fautes de frappe dans mes exemples... :-/

Answer 5

J'ai trouvé beaucoup d'explications de monades qui disent "vous n'avez pas de savoir quelque chose au sujet de la catégorie de la théorie, vraiment, il suffit de penser de monades comme les burritos / combinaisons spatiales / whatever".

Vraiment, l'article qui a permis de démystifier les monades m'a juste dit que les catégories ont été, décrit les monades (y compris le rejoindre et de se lier) en termes de catégories, et ne vous embêtez pas avec n'importe quel faux métaphores:

• http://en.wikibooks.org/wiki/Haskell/Category_theory

Je pense que l'article est très lisible sans trop de connaissances en maths requis.