Tutoriel pour démonter la monade Haskell Cont?

Question

Voici comment est définie la monade Cont:

 newtype Cont r a = Cont { runCont :: (a -> r) -> r }

instance Monad (Cont r) where
    return a = Cont ($ a)
    m >>= k  = Cont $ \c -> runCont m $ \a -> runCont (k a) c
 

Existe-t-il un tutoriel quelque part qui distingue cet imbécile et explique comment et pourquoi cela fonctionne? Vous ne recherchez pas un tutoriel monade, mais un tutoriel "Comment fonctionne le Cont monad".

Answer 1

La première chose à comprendre au sujet de la continuation de la monade, c'est que, fondamentalement, il n'est pas vraiment faire quoi que ce soit. C'est vrai!

L'idée de base d'une poursuite en général, c'est qu'il représente le reste d'un calcul. Disons que nous avons une expression comme ceci: foo (bar x y) z. Maintenant, extraire juste la partie entre parenthèses, bar x y--c'est la partie de l'expression total, mais ce n'est pas seulement une fonction, nous pouvons l'appliquer. Au lieu de cela, c'est quelque chose que nous avons besoin d'appliquer une fonction à l'. Ainsi, nous pouvons parler du "reste du calcul" dans ce cas, comme \a -> foo a z, ce qui, nous pouvons l'appliquer à l' bar x y de reconstruire la forme complète.

Maintenant, il se trouve que cette notion de "le reste du calcul" est utile, mais il est maladroit, car c'est quelque chose en dehors de la sous-expression nous intéresse. Pour améliorer les choses, nous pouvons nous tourner les choses à l'intérieur: extrait de la sous-expression qui nous intéresse, puis les envelopper dans une fonction qui prend un argument représentant le reste du calcul: \k -> k (bar x y).

Cette version modifiée nous donne beaucoup de souplesse, non seulement il extrait une sous-expression de son contexte, mais il nous permet de le manipuler extérieure contexte au sein de la sous-expression elle-même. Nous pouvons penser à cela comme une sorte de suspension du calcul, nous donnant un contrôle explicite sur ce qui se passe ensuite. Maintenant, comment pourrait-on généraliser? Ainsi, la sous-expression est à peu près inchangé, il faut juste laisser le remplacer par un paramètre à l'intérieur de la fonction, en nous donnant des \x k -> k x--en d'autres termes, rien de plus que la fonction de demande, inversé. On pourrait tout aussi bien écrire flip ($), ou ajouter un peu d'exotisme en langue étrangère de la saveur et de le définir comme un opérateur |>.

Maintenant, il serait simple, mais fastidieux et horriblement abrutissant, à traduire chaque pièce d'une expression de cette forme. Heureusement, il ya une meilleure façon. Comme Haskell programmeurs, quand on pense à la construction d'un calcul dans un contexte de fond la prochaine chose que nous pensons est-à - dire, est-ce une monade? Et dans ce cas, la réponse est oui, oui, il est.

Transformer cela en une monade, nous commençons avec deux blocs de construction de base:

• Pour une monade m, une valeur de type m a représente d'avoir accès à une valeur de type a dans le cadre de la monade.
• Le cœur de notre "suspendu calculs" est renversé en fonction de l'application.

Que signifie le fait d'avoir accès à quelque chose de type a dans ce contexte? Cela signifie simplement que, pour une certaine valeur en x :: a, nous avons appliqué flip ($) de x, nous donnant une fonction qui prend une fonction qui prend un argument de type a, et applique cette fonction à l' x. Disons que nous avons une suspension du calcul de portefeuille d'une valeur de type Bool. De quel type est-ce à nous donner?

> :t flip ($) True
flip ($) True :: (Bool -> b) -> b

Donc, pour reprendre les calculs, le type m a de (a -> b) -> b... ce qui est peut-être une déception, car on savait déjà que la signature d' Cont, mais l'humour moi pour l'instant.

Une chose intéressante à noter ici est qu'une sorte de "renversement" s'applique également à la monade type: Cont b a représente une fonction qui prend une fonction a -> b et évalue b. Comme une continuation représente "l'avenir" d'un calcul, de sorte que le type a à la signature représente dans un certain sens, "le passé".

Donc, en remplaçant (a -> b) -> b avec Cont b a, quel est le type monadique de notre bloc de construction de base de la fonction d'inversion d'application? a -> (a -> b) -> b se traduit par a -> Cont b a... le même type de signature en tant que return et, en fait, c'est exactement ce qu'il est.

À partir d'ici, à peu près tout tombe directement dans les types: Il y a essentiellement pas de meilleure façon de mettre en oeuvre >>= en plus de la mise en œuvre effective. Mais qu'en est-il réellement le faire?

À ce stade, nous en revenons à ce que j'ai dit d'abord: la continuation de la monade n'est pas vraiment faire beaucoup de chose. Quelque chose de type Cont r a est trivialement équivalent à quelque chose de juste taper a, simplement en fournissant id comme argument de la suspension du calcul. Cela pourrait conduire à se demander si, si Cont r a est une monade, mais la conversion est si trivial, ne devriez - a seul aussi être une monade? Bien sûr, cela ne fonctionne pas comme il est, car il n'y a pas de constructeur de type à définir en tant que Monad de l'instance, mais dis-nous ajouter une mince enveloppe, comme data Id a = Id a. C'est en effet une monade, à savoir l'identité de l'errance.

Qu'est - >>= faire pour l'identité de l'errance? Le type de signature est - Id a -> (a -> Id b) -> Id b, ce qui est équivalent à a -> (a -> b) -> b, ce qui est tout simple fonction de l'application à nouveau. Ayant établi l' Cont r a est trivialement équivalent à Id a, nous pouvons en déduire que dans ce cas également, (>>=) est juste en fonction de l'application.

Bien sûr, Cont r a est un fou le monde à l'envers où tout le monde a des barbichettes, de sorte que ce qui se passe réellement consiste à brouiller les choses autour de confondre les moyens afin de chaîne de deux suspensions de calculs dans un nouveau suspendu le calcul, mais en substance, il n'est pas réellement quelque chose d'inhabituel se passait! L'application de fonctions à arguments, ho hum, une autre journée dans la vie d'un programmeur fonctionnel.

Answer 2

Voici fibonacci:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Imaginez que vous avez une machine sans pile des appels - elle ne permet que la queue de la récursivité. Comment exécuter fib sur cette machine? Vous pouvez facilement réécrire la fonction linéaire, au lieu de temps exponentiel, mais qui nécessite tout petit peu de perspicacité et n'est pas mécanique.

L'obstacle à en faire la queue récursive est la troisième ligne, où il y a deux appels récursifs. Nous ne pouvons que faire un seul appel, qui a aussi pour donner le résultat. C'est ici que les continuations entrée.

Nous ferons fib (n-1) prendre paramètre supplémentaire, qui sera une fonction de la spécification de ce qui devrait être fait après le calcul de son résultat, l'appellent x. Il sera l'ajout d' fib (n-2) , bien sûr. Donc: pour calculer fib n vous calculez fib (n-1) après cela, si vous appelez le résultat x, vous calculez fib (n-2), après cela, si vous appelez le résultat y, vous revenez x+y.

En d'autres termes, vous avez à dire:

Comment faire le calcul suivant: "fib' n c = compute fib n et s'applique c pour le résultat"?

La réponse est que vous faites ce qui suit: "compute fib (n-1) et s'applique d pour le résultat", où l' d x signifie "compute fib (n-2) et s'applique e pour le résultat", où l' e y moyen c (x+y). Dans le code:

fib' 0 c = c 0
fib' 1 c = c 1
fib' n c = fib' (n-1) d
           where d x = fib' (n-2) e
                 where e y = c (x+y)

De manière équivalente, on peut utiliser des lambdas:

fib' 0 = \c -> c 0
fib' 1 = \c -> c 1
fib' n = \c -> fib' (n-1) $ \x ->
               fib' (n-2) $ \y ->
               c (x+y)

Pour obtenir réelle de Fibonacci usage de l'identité: fib' n id. Vous pouvez penser que la ligne fib (n-1) $ ... passe ses résultats x à la suivante.

Les trois dernières lignes de l'odeur d'un do bloc, et en fait

fib' 0 = return 0
fib' 1 = return 1
fib' n = do x <- fib' (n-1)
            y <- fib' (n-2)
            return (x+y)

est le même, jusqu'à newtypes, par définition de la monade Cont. Remarque des différences. Il y a \c -> au début, au lieu de x <- ... y ... $ \x -> et c au lieu de return.

Essayez d'écrire factorial n = n * factorial (n-1) dans une queue récursive style à l'aide de la CPS.

Comment est - >>= travail? m >>= k est équivalent à

do a <- m
   t <- k a
   return t

Faire de la traduction, dans le même style que dans fib', vous obtenez

\c -> m $ \a ->
      k a $ \t ->
      c t

la simplification \t -> c t de c

m >>= k = \c -> m $ \a -> k a c

L'ajout de newtypes vous obtenez

m >>= k  = Cont $ \c -> runCont m $ \a -> runCont (k a) c

ce qui est en haut de cette page. C'est complexe, mais si vous savez comment traduire entre do de la notation et de l'utilisation directe, vous n'avez pas besoin de connaître la définition exacte de l' >>=! La Continuation de la monade est beaucoup plus clair si vous cherchez à faire des blocs.

Les monades et les continuations

Si vous regardez cette utilisation de la liste de l'errance...

do x <- [10, 20]
   y <- [3,5]
   return (x+y)

[10,20] >>= \x ->
  [3,5] >>= \y ->
    return (x+y)

([10,20] >>=) $ \x ->
  ([3,5] >>=) $ \y ->
    return (x+y)

qui ressemble continuation! En fait, (>>=) lorsque vous appliquez un argument de type (a -> m b) -> m b qui Cont (m b) a. Voir sigfpe la Mère de toutes les monades pour les explications. J'avais considère cela comme une bonne continuation monade tutoriel, si ce n'était pas probablement dire que c'.

Depuis les suites et les monades sont donc fortement liées dans les deux sens, je pense que ce qui s'applique aux monades s'applique aux poursuites: seulement travailler dur va vous apprendre d'eux, et non pas de la lecture de certains burrito la métaphore ou l'analogie.

Answer 3

EDIT: L'article a migré vers le lien ci-dessous.

J'ai rédigé un didacticiel traitant directement de ce sujet et qui, j'espère, vous sera utile. (Cela a certainement contribué à consolider ma compréhension!) Il est un peu long de s'intégrer facilement dans un sujet de débordement de pile, je l'ai donc migré vers le Wiki Haskell.

S'il vous plaît voir: MonadCont sous le capot

Answer 4

Je pense que la meilleure façon d'obtenir une poignée sur l' Cont monade est de comprendre comment utiliser son constructeur. Je vais supposer la définition suivante pour l'instant, bien que les réalités de l' transformers colis sont légèrement différentes:

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

Cela donne:

Cont :: ((a -> r) -> r) -> Cont r a

afin de créer une valeur de type Cont r a, nous avons besoin de donner une fonction à l' Cont:

value = Cont $ \k -> ...

Maintenant, k lui-même est de type a -> r, et le corps de la lambda doit être de type r. Une chose évidente à faire est d'appliquer k pour une valeur de type a, et obtenir une valeur de type r. Nous pouvons le faire, oui, mais c'est vraiment l'une des nombreuses choses que nous pouvons faire. Rappelez-vous que value n'ont pas besoin d'être polymorphe en r, il peut être de type Cont String Integer , ou quelque chose de concret. Donc:

• On pourrait s'appliquent k pour plusieurs valeurs de type a, et de combiner les résultats d'une certaine manière.
• On pourrait s'appliquent k pour une valeur de type a, observer le résultat, et ensuite décider d'appliquer l' k de quelque chose d'autre sur cette base.
• Nous pourrions ignorer k tout à fait et juste de produire une valeur de type r - mêmes.

Mais qu'est-ce que cela signifie? Qu'est - k à la fin? Eh bien, en bloc, nous pourrions avoir quelque chose comme ceci:

flip runCont id $ do
  v <- thing1
  thing2 v
  x <- Cont $ \k -> ...
  thing3 x
  thing4

Voici la partie amusante: nous pouvons, dans nos esprits et un peu de manière informelle, de diviser le faire en deux lors de la survenance de l' Cont constructeur, et pense au reste de l'ensemble du calcul après comme une valeur en soi. Mais, ce qu'il est dépend de ce qu' x est, donc, c'est vraiment une fonction à partir d'une valeur x de type a pour un résultat de valeur:

restOfTheComputation x = do
  thing3 x
  thing4

En fait, c' restOfTheComputation est grosso modo ce qu' k . En d'autres termes, vous appelez k avec une valeur qui devient le résultat x de votre Cont calcul, le reste du calcul s'exécute, puis l' r produit serpente dans votre lambda comme le résultat de l'appel d' k. Donc:

• si vous avez appelé, k plusieurs fois, le reste du calcul va se faire rouler plusieurs fois, et les résultats peuvent être combinés toutefois vous le souhaitez.
• si vous n'avez pas d'appel k , le reste de l'ensemble du calcul sera ignorée et l'enfermant runCont appel va juste vous donner en retour quelle que soit la valeur de type r vous avez réussi à synthétiser. C'est, à moins qu'une autre partie du calcul est l'appel que vous de leur k, et de vous embêter avec le résultat...

Si vous êtes toujours avec moi, à ce stade, il devrait être facile de voir ce qui pourrait être assez puissant. Pour faire le point un peu, nous allons mettre en œuvre certaines standard type de classes.

instance Functor (Cont r) where
  fmap f (Cont c) = Cont $ \k -> ...

Nous nous sommes donné un Cont de la valeur avec bind résultat x de type a, et une fonction f :: a -> b, et nous voulons faire une Cont de la valeur avec bind résultat f x de type b. Ainsi, pour définir la liaison de résultats, il suffit d'appeler k...

  fmap f (Cont c) = Cont $ \k -> k (f ...

Attendez, comment pouvons-nous obtenir x ? Bien, ça va impliquer c, dont nous n'avons pas encore utilisé. Rappelez-vous comment c fonctionne: étant donné une fonction, puis appelle la fonction avec son lier résultat. Nous voulons appeler notre fonction avec f appliquée à lier résultat. Donc:

  fmap f (Cont c) = Cont $ \k -> c (\x -> k (f x))

Tada! Ensuite, Applicative:

instance Applicative (Cont r) where
  pure x = Cont $ \k -> ...

C'est facile. Nous voulons la liaison résultat à l' x nous obtenons.

  pure x = Cont $ \k -> k x

Maintenant, <*>:

  Cont cf <*> Cont cx = Cont $ \k -> ...

Ce un peu plus délicat, mais utilise essentiellement les mêmes idées que dans fmap: de la première à obtenir la fonction à partir de la première Cont, en faisant un lambda pour l'appeler:

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> ...

Alors d'obtenir la valeur x à partir de la seconde, et font fn x le lier résultat:

  Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> cx (\x -> k (fn x)))

Monad est à peu près le même, mais requiert runCont , soit à un cas ou à laisser décompresser le newtype.

Cette réponse est déjà assez long, donc je ne vais pas aller en ContT (en bref: c'est exactement le même que Cont! La seule différence est dans la nature de l'constructeur de type, la mise en œuvre de tout sont identiques) ou callCC (utile combinator qui fournit un moyen pratique d'ignorer k, la mise en œuvre de la sortie précoce à partir d'un sous-bloc).

Pour une simple et plausible de l'application, essayez de Edward Z. Yang blog de la mise en œuvre de étiquetés break et continue dans les boucles for.