Comment et pourquoi fonctionne la monade Haskell Cont?

Question

Voici comment est défini le Cont monade:

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 

Pourriez-vous expliquer comment et pourquoi cela fonctionne? Qu'est-ce que ça fait?

Answer 1

La première chose à se rendre compte au sujet de la monade de continuation est que, fondamentalement, ce n'est pas vraiment faire rien du tout. C'est vrai!

L'idée de base d'une continuation en général est qu'elle représente le reste d'un calcul. Disons que nous avons une expression comme celle-ci: foo (bar x y) z. Maintenant, extrayez juste la partie entre parenthèses, bar x y - ceci est partie de l'expression totale, mais ce n'est pas seulement une fonction que nous pouvons appliquer. Au lieu de cela, c'est quelque chose que nous devons appliquer une fonction à. Donc, nous pouvons parler du "reste du calcul" dans ce cas comme étant \a -> foo a z, que nous pouvons appliquer à bar x y pour reconstruire le formulaire complet.

Maintenant, il arrive que ce concept du "reste du calcul" soit utile, mais c'est difficile de travailler avec, puisque c'est quelque chose en dehors de la sous-expression que nous considérons. Pour que les choses fonctionnent mieux, nous pouvons inverser les choses: extraire la sous-expression qui nous intéresse, puis l'enrouler 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 flexibilité - non seulement elle extrait une sous-expression de son contexte, mais elle nous permet également de manipuler ce contexte externe dans la sous-expression . Nous pouvons le considérer comme une sorte de calcul suspendu, nous donnant un contrôle explicite sur ce qui se passe ensuite. Maintenant, comment pourrions-nous généraliser cela? Eh bien, la sous-expression est à peu près inchangé, alors remplaçons-le par un paramètre à la fonction inside-out, nous donnant \x k -> k x - en d'autres termes, rien de plus que l'application , inversée. Nous pourrions tout aussi bien écrire flip ($), ou ajouter un peu d'une saveur de langue étrangère exotique et le définir comme un opérateur |>. Maintenant, il serait simple, quoique fastidieux et horriblement obfusant, de traduire chaque morceau d'une expression à cette forme. Heureusement, il y a un meilleur moyen. En tant que programmeurs Haskell, quand nous pensons construire un calcul dans un contexte de contexte la prochaine chose que nous pensons est dire, est-ce une monade? Et dans ce cas, la réponse est oui, oui c'est.

Pour en faire une monade, nous commençons par deux éléments de base:

• Pour une monade m, une valeur de type m a représente l'accès à une valeur de type a dans le contexte de la monade .
• Le cœur de nos "calculs suspendus" est l'application de la fonction retournée.

Qu'est-ce que cela signifie d'avoir accès à quelque chose de type a dans ce contexte?Cela signifie simplement que, pour une valeur x :: a, nous avons appliqué flip ($) à , en nous donnant une fonction qui prend une fonction qui prend un argument de type a, et applique cette fonction à x. Supposons que nous ayons un calcul suspendu contenant une valeur de type Bool. Quel type cela nous donne-t-il?

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

Donc, pour les calculs en suspension, le type m a correspond à (a -> b) -> b ... qui est peut-être une déception, puisque nous savions déjà la signature pour Cont, mais l'humour moi pour l'instant.

Une chose intéressante à noter ici est qu'une sorte de « renversement » applique également au type de la monade: Cont b a représente une fonction qui prend une fonction a -> b et évalue à b. En tant que continuation représente "l'avenir" d'un calcul, de sorte que le type a dans la signature représente dans un certain sens "le passé". Donc, en remplaçant (a -> b) -> b par Cont b a, quel est le type monadique pour notre bloc de base de l'application de la fonction inverse? a -> (a -> b) -> b se traduit par a -> Cont b a ... le même type de signature que return et, en fait, c'est exactement ce que c'est. A partir de maintenant, tout dépend à peu près des types: Il n'y a pratiquement aucune façon sensée d'implémenter >>= en plus de l'implémentation réelle. Mais qu'est-ce que c'est réellement faire?

À ce stade, nous revenons à ce que j'ai dit initialement: la monade de continuation n'est pas vraiment faire beaucoup de quoi que ce soit. Quelque chose de type Cont r a est trivialement équivalent à quelque chose du type a, simplement en fournissant id comme argument au calcul suspendu. Cela pourrait conduire à se demander si, si Cont r a est une monade mais la conversion est si triviale, ne devrait pas a seule aussi être une monade? Bien sûr, cela ne fonctionne pas tel quel, car il n'y a pas de constructeur de type à définir en tant qu'instance Monad, mais disons que nous ajoutons un wrapper trivial, comme data Id a = Id a. C'est en effet une monade, à savoir la monade d'identité.

Que fait >>= pour la monade d'identité? La signature de type est Id a -> (a -> Id b) -> Id b, ce qui équivaut à a -> (a -> b) -> b, ce qui est encore une simple application de fonction. Ayant établi que Cont r a est trivialement équivalent à Id a, nous pouvons déduire que dans ce cas aussi, (>>=) est juste l'application de la fonction.

Bien sûr, Cont r a est un monde fou inversé où tout le monde a barbiche, donc ce qui se passe en réalité implique des choses brouillant autour de façons confuses afin d'enchaîner deux calculs suspendus ensemble dans un nouveau calcul suspendu, mais en substance, il ISN En fait, il se passe quelque chose d'inhabituel! Appliquer des fonctions aux arguments, ho hum, un autre jour dans la vie d'un programmeur fonctionnel.

Answer 2

EDIT: Article migré vers le lien ci-dessous.

J'ai rédigé un tutoriel traitant directement de ce sujet que j'espère que vous trouverez utile. (Cela a certainement contribué à renforcer ma compréhension!) Il est un peu long de s'adapter confortablement à un sujet de Stack Overflow, donc je l'ai migré vers le Wiki Haskell.

S'il vous plaît voir: MonadCont under the hood

Answer 3

Voici fibonacci:

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

Imaginez que vous avez une machine sans pile d'appel - il ne permet récursion queue. Comment exécuter fib sur cette machine? Vous pouvez facilement réécrire la fonction pour qu'elle fonctionne en linéaire plutôt qu'en temps exponentiel, mais cela nécessite un peu de perspicacité et n'est pas mécanique.

L'obstacle pour rendre la queue récursive est la troisième ligne, où il y a deux appels récursifs. Nous ne pouvons faire qu'un seul appel, qui doit aussi donner le résultat. Voici où les continuations entrent.

Nous allons faire fib (n-1) prendre paramètre supplémentaire, qui sera une fonction spécifiant ce qui doit être fait après avoir calculé son résultat, appelez-le x. Il va ajouter , 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 , après cela, si vous appelez le résultat y, vous renvoyez x+y.

En d'autres termes, vous devez dire:

Comment faire le calcul suivant: « fib' n c = calculer fib n et appliquer c au résultat »?

La réponse est que vous procédez comme suit: « calculer fib (n-1) et appliquer d au résultat », où d x signifie « calculer et appliquer e au résultat », où e y signifie 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) 

Équivalemment, nous pouvons utiliser 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 l'identité réelle de l'utilisation de Fibonacci: fib' n id. Vous pouvez penser que la ligne fib (n-1) $ ... passe son résultat x au suivant.

Les trois dernières lignes odeur comme un bloc do, 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 monade Cont. Notez les différences. Il y a \c -> au début, au lieu de x <- ... il y a ... $ \x -> et c au lieu de return.

Essayez d'écrire factorial n = n * factorial (n-1) dans un style récursif de queue en utilisant CPS. Comment fonctionne >>=?m >>= k est équivalent à

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

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

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

simplifier \t -> c t à c

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

Ajout newtypes vous

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

qui est au-dessus de cette page. C'est complexe, mais si vous savez traduire entre la notation do et l'utilisation directe, vous n'avez pas besoin de connaître la définition exacte de >>=! La monade de continuation est beaucoup plus claire si vous regardez des do-blocks.

Monades et continuations

Si vous regardez cette utilisation de la liste monade ...

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 à la continuation! En fait, (>> =) lorsque vous appliquez un argument a le type (a -> m b) -> m b qui est Cont (m b) a. Voir Mother of all monads de sigfpe pour l'explication. Je considérerais cela comme un bon tutoriel sur la monade de continuation, même si ce n'était pas probablement comme ça. Puisque les continuations et les monades sont si étroitement liées dans les deux sens, je pense que ce qui s'applique aux monades s'applique aux continuations: seul le travail acharné vous les enseignera, et ne pas lire une métaphore ou une analogie de burrito.

Answer 4

Je pense que la façon la plus simple de comprendre la monade Cont est de comprendre comment utiliser son constructeur. Je vais supposer que la définition suivante pour l'instant, bien que les réalités du paquet transformers 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 construire une valeur de type Cont r a, nous besoin de donner une fonction à Cont:

value = Cont $ \k -> ... 

maintenant, k lui-même est de type a -> r, et le corps du lambda doit avoir le type r. Une chose évidente à faire serait d'appliquer k à une valeur de type a, et d'obtenir une valeur de type r. Nous pouvons le faire, oui, mais ce n'est vraiment qu'une des nombreuses choses que nous pouvons faire. Rappelez-vous que value n'a pas besoin d'être polymorphe dans r, il pourrait être de type Cont String Integer ou autre chose de béton. Alors:

• Nous pourrions appliquer k à plusieurs valeurs de type a, et combiner les résultats en quelque sorte.
• Nous pourrions appliquer k à une valeur de type a, observer le résultat, puis décider d'appliquer k à autre chose en fonction de cela.
• Nous pourrions ignorer complètement k et juste produire une valeur de type r nous-mêmes.

Mais qu'est-ce que tout cela signifie? Que devient k? Eh bien, dans un do-bloc, nous pourrions avoir quelque chose qui ressemble à 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 informelle, diviser le do-bloc en deux à l'apparition du Cont constructeur, et penser au reste du calcul entier après comme une valeur en soi. Mais attendez, ce qu'elle est dépend de ce que x est, il est donc vraiment une fonction d'une valeur x de type a à une valeur de résultat:

restOfTheComputation x = do 
    thing3 x 
    thing4 

En fait, ce restOfTheComputation est grosso modo ce k finit par être. En d'autres termes, vous appelez k avec une valeur qui devient le résultat x de votre calcul Cont, le reste du calcul s'exécute, puis le r produit son chemin de retour dans votre lambda à la suite de l'appel à k. Alors:

• Si vous avez appelé k plusieurs fois, le reste du calcul va s'exécuter plusieurs fois, et les résultats peuvent être combinés comme vous le souhaitez.
• Si vous n'avez pas appelé k, le reste du calcul complet sera ignoré et l'appel runCont qui vous renverra vous donnera la valeur r que vous avez réussi à synthétiser. Autrement dit, à moins qu'une autre partie du calcul appelle vous de leurk et tripoter le résultat ...

Si vous êtes toujours avec moi à ce stade, il devrait être facile voir cela pourrait être assez puissant. Pour faire un peu le point, implémentons quelques classes de types standard.

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

On nous donne une valeur Cont avec un résultat de liaison x de type a, et une fonction f :: a -> b, et nous voulons faire une valeur Cont avec un résultat de liaison f x de type b. Eh bien, pour définir le résultat de liaison, il suffit d'appeler k ...

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

Attendez, où pouvons-nous x de? Eh bien, cela va impliquer c, que nous n'avons pas encore utilisé. Rappelez-vous comment fonctionne c: il reçoit une fonction, puis appelle cette fonction avec son résultat de liaison. Nous voulons appeler notre fonction avec f appliquée à ce résultat de liaison. Ainsi:

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

Tada!Ensuite, Applicative:

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

Celui-ci est simple. Nous voulons que le résultat de liaison soit le x obtenu.

pure x = Cont $ \k -> k x 

Maintenant, <*>:

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

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

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

obtenez alors la valeur x de la seconde, et de faire fn x le résultat de liaison:

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

Monad est la même, bien que nécessite runCont ou d'un cas ou laisser déballer le newtype. Cette réponse est déjà assez longue, donc je ne vais pas entrer dans ContT (en bref: c'est exactement la même chose que Cont! La seule différence est dans le type du constructeur de type, les implémentations de tout sont identiques) ou callCC (un combinateur utile qui fournit un moyen pratique d'ignorer k, en implémentant la sortie anticipée d'un sous-bloc).

Pour une application simple et plausible, essayez l'article de blog de Edward Z. Yang implémentant labelled break and continue in for loops.