Programmation Avancée

TP9: monades (2)

On continuera dans ce TP d'utiliser la signature suivante:

module type MONAD = sig
  type +'a t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end

Monades de non-déterminisme et de probabilité

Question 1

Proposer une monade pour le calcul non-déterministe, qui peut renvoyer un nombre arbitraire de valeurs, potentiellement nul ou infini. Votre monade devra implémenter MONAD ainsi que l'opération de choix non-déterministe plus : 'a t -> 'a t -> 'a t. La sémantique de plus m n est que ce calcul peut s'exécuter, de façon non-déterministe, soit comme m soit comme n. Ses résultats possibles sont donc l'union des résultats possibles de m et de n.

On se donnera aussi fail : 'a t, qui correspond à un calcul non-déterministe sans aucun résultat possible: c'est l'unité de plus.

On dotera enfin cette monade d'une opération run : 'a t -> ('a -> unit) -> unit tel que run c f exécute f v sur chaque résultat possible v du calcul c dans la monade.

Tester votre monade en implémentant l'algo de tirage non-déterministe d'un élément dans une liste.

Question 2

Adapter votre monade de non-déterminisme en une monade de calcul probabiliste, qui associe une probabilité à chaque valeur retournée, de sorte que la somme des probabilités des valeurs retournées possibles soit (inférieure ou égale à) 1.

Cette monade devra être équipée de l'opération choice : float -> 'a t -> 'a t -> 'a t, où le calcul choice p m n s'exécute comme m (resp. n) avec probabilité p (resp. 1-p). On définira aussi fail : 'a t, le calcul qui ne renvoie rien.

Implémenter l'algorithme de tirage aléatoire d'un élement dans une liste. Tester, vérifier que le tirage est uniforme.

Bonus: implémenter un algorithme de tirage uniforme qui, étant donnés k et n, renvoie une liste de n booléens dont exactement k valent true.

Application: la chèvre (monades, probabilités)

On considère le jeu suivant, dont l'enjeu mirobolant est de gagner une chèvre. Le joueur est placé devant trois portes, et il sait que derrière une seule d'entre elles se trouve une chèvre. Il choisit une première porte. On lui ouvre alors une autre porte qui ne cachait pas de chèvre. Le joueur peut alors de nouveau choisir une porte parmi les trois, et s'il découvre la chèvre il l'emporte.

Le jeu se formalise comme la fonction play ci-dessous, qui prend en argument une stratégie de type first représentant un comportement du joueur, c'est à dire un calcul probabiliste renvoyant un entier (la première porte choisie) ainsi qu'une fonction de type second représentant la stratégie au deuxième tour (son argument est la porte révélée entre les deux tours). Je suppose ici que A.pick est la fonction de choix uniforme dans une liste.

let doors = [1;2;3]

type second = int -> int P.t
type first = (int*second) P.t

let (>>=) = P.bind
let play (strategy:first) =
  A.pick doors >>= fun chevre ->
  strategy >>= fun (first,strategy) ->
  let empty_doors =
    List.filter
      (fun d -> d <> first && d <> chevre)
      doors
  in
  A.pick empty_doors >>= fun empty ->
  strategy empty >>= fun second ->
  P.return (second = chevre)

Votre mission est de trouver la meilleure stratégie, de l'implémenter et d'évaluer ainsi sa probabilité de succès.

Par exemple, voici la stratégie qui choisit une porte au hasard et ne change pas son choix au deuxième tour:

let () =
  let second first =
    fun _ -> M.return first
  in
  let first : first =
    P.bind
      (A.pick doors)
      (fun p -> P.return (p, second p))
  in
    Printf.printf "P[win] = %.3f\n" (play first (dirac true))