« Paradigmes et langages non classiques 2013

Ce TD permet de manipuler et d’approfondir les différents concepts abordés lors du second et troisième cours d’Haskell.

Monad probabilistique

On souhaite construire un modèle de calcul probabilistique en utilisant les monads de Haskell. Un monad décrit un modèle d’application de fonction, et paraît donc adapté à cette tâche.

Type

On construira un type Prob (avec un constructeur du même nom) qui contient une liste de possibilités, chacune associée à une fraction représentant la probabilité de son occurrence. On pourra avantageusement utiliser le type Rational se trouvant dans le module standard Data.Ratio qui permet de représenter un nombre rationnel sous la forme d’une fraction à l’aide de l’opérateur % :

Prelude> import Data.Ratio
Prelude Data.Ratio> :t 3 % 4
3 % 4 :: Integral a => Ratio a
Prelude Data.Ratio> 3%4
3 % 4
Prelude Data.Ratio> 6%8
3 % 4
Prelude Data.Ratio>

La somme des probabilités devra toujours être égale à 1.

On crééra également une fonction sameProbability qui permet de transformer une liste de possibilités en un objet Prob représentant ces possibilités de manière équiprobable. La signature sera :

sameProbability :: [a] -> Prob a

Instances

Le type Prob sera une instance de Functor : en effet, on peut appliquer une fonction sur toutes les alternatives sans en changer les probabilités respectives. Il faudra donc définir sa fonction fmap.

De même, le type Prob sera une instance de Monad, dont on définira les fonctions return et (>>=) : return crééra une unique possibilité de probabilité 1, tandis que (>>=) appliquera la fonction sur l’ensemble des probabilités et combinera les probabilités initiales et les probabilités finales. On ne s’occupera pas de normaliser les résultats, c’est à dire que certaines possibilités pourront apparaître plusieurs fois dans la liste.

On pourra définir fail comme renvoyant Prob []. Cette liste ne représente pas une somme de probabilités égale à 1 donc elle est défectueuse. Lorsqu’on utilisera fail, il faudra donc renormaliser la distribution de probabilité résultante comme on le verra plus tard.

Simplification et extraction

Dans le cas où le type paramètre de Prob appartient à la classe Eq, on pourra écrire une fonction canonize qui garantit que chaque possibilité n’apparaît qu’une seule fois, avec comme probabilité la somme des probabilités initiales. On pourra utiliser la fonction partition de Data.List.

De même, une fonction probability devra extraire d’un objet de classe Prob dont le type paramètre appartient à la classe Eq la probabilité associée à cette alternative. Cette fonction devra appeler canonize car la liste des probabilités n’aura pas forcément été transformée auparavant. On pourra utiliser la fonction lookup de Data.List ainsi que la fonction fromMaybe de Data.Maybe qui permet d’extraire une valeur d’un Maybe en spécifiant la valeur par défaut dans le cas où on ait Nothing.

Les signatures de ces fonctions seront donc :

canonize :: Eq a => Prob a -> Prob a
probability :: Eq a => a -> Prob a -> Rational

Test

Si dice renvoie les entiers de 1 à 6 de manière équiprobable, vérifier que la possibilité d’obtenir un double en jetant deux dés vous donne la probabilité attendue avec probability True double :

double :: Prob Bool
double = do
  x <- dice
  y <- dice
  return $ x == y

De même, on pourra vérifier la répartition de la somme de deux dés avec canonize pair :

pair :: Prob Int
pair = do
  x <- dice
  y <- dice
  return $ x + y

Probabilités conditionnelles

On souhaite vérifier la validité d’un nouveau test fiable à 99,9% (dans un cas sur 1000, le résultat du test sera donc faux) permettant de détecter une maladie rare qui touche 1 individu sur 100000. Nous sommes intéressés par savoir quelle est la probabilité, lorsque le test renvoie un résultat positif, que la personne soit vraiment malade, car le seul remède connu aujourd’hui tuerait une personne saine.

On définira une fonction sick qui renverra la distribution de probabilités correspondant aux personnes atteintes ou non par la maladie. Une fonction positive qui renverra le résultat du test en fonction de l’état du malade.

sick :: Prob Bool
positive :: Bool -> Prob Bool

results renverra, pour le seul cas où le test est positif, une distribution de probabilité avec True si le patient est effectivement malade ou False s’il ne l’est pas. Si le test est faux, on utilisera fail pour ne pas considérer ce cas. Il faudra donc renormaliser la distribution de probabilité avant de la renvoyer en utilisant la fonction renormalize :

results :: Prob Bool
renormalize :: Prob a -> Prob a

Finalement, vaut-il mieux soigner une personne dont le test est positif, ou bien est-ce risqué au vu de la dangerosité du remède pour une personne saine ?

Interlude (préparation à Factor)

Écrire, de la manière la plus compacte possible, les deux fonctions suivantes : cleave prend une valeur et une liste de fonctions et renvoie, dans le même ordre, la liste des résultats de chaque fonction appliquée à la valeur. spread applique à une liste de valeurs une liste de fonctions une à une (la première fonction s’applique à la première valeur, la seconde fonction à la seconde valeur, etc.).

cleave :: a -> [a -> b] -> [b]
spread :: [a -> b] -> [a] -> [b]

Monads avec état

En cours, nous avons vu comment écrire les monads Writer, Reader et State. Les réécrire, sans utiliser le cours bien entendu, avec leurs procédures d’accompagnement permettant de les manipuler dont on rappelle ici les signatures :

-- Ajout à l'environnement d'un Writer
tell :: w -> Writer w ()
compute :: Writer w x -> x
describe :: Writer w x -> w
display :: Writer [String] x -> IO ()

-- Récupération de l'environnement d'un Reader avec ou sans transformation
asks :: (e -> a) -> Reader e a
ask :: Reader e e

-- Manipulation de l'état d'un State monad
put :: s -> State s ()
get :: State s s
modify :: (s -> s) -> State s ()