Voici les signatures d'un monoïde, d'une version de la monade Writer et d'un foncteur qui construit une telle monade à partir d'un monoïde.

module type WriterMonad  = sig 
    include Monad
    type m
    val tell: m -> unit t
    val writer: 'a * m -> 'a t
    val runWriter: 'a t -> 'a * m
end

type 'c writerT = Writer of 'c

module MakeWriter (M : Monoid) : (WriterMonad with type m = M.m) 
with type 'a t = ('a * M.m) writerT = struct

    type m = M.m
    let ( @ ) = M.(@)

    type 'a t = ('a * m) writerT

    let writer (r, o) = Writer (r, o)
    let tell (x : m) : unit t = Writer ((),x)

    let runWriter m = match m with
        | Writer (a,b) -> (a,b)

    let return x = Writer (x, M.i)

    let ( >>= ) m f = 
        let (old_v, old_w) = runWriter m in
        let (new_v, new_w) = runWriter (f old_v) in 
        writer (new_v, old_w @ new_w)

end

Exercice 0

-Problème 0: Définissez une structure de signature Monoid qui encode le monoïde des entiers avec l'addition comme opération binaire. Vérifier que les lois des monoïdes sont valides pour cette structure.

-Problème 1: En utilisant ce monoïde, construisez la monade correspondante AddWriter en utilisant le foncteur ci-dessus.

-Problème 2: En utilisant cette monade, implémentez une fonction len qui calcule et renvoie une valeur monadique composée de la liste elle-même et de sa longueur. En d'autres termes, cette fonction se comporte comme une identité sur les listes mais elle utilise la monade comme un accumulateur pour calculer la longueur de la liste. Exemple des résultats attendus :

# len [];;
- : 'a list AddWriter.t = Writer ([], 0)
utop # len [0;1;2;3;4;5;6;7;8;9];;
- : int list AddWriter.t =
Writer ([0; 1; 2; 3; 4; 5; 6; 7; 8; 9], 10)

Hint

Vous pouvez utiliser la fonction mapM que nous avons implémentée pour résoudre les les exercices 2 et 3 de la séance 5

-Problème 3: En utilisant à nouveau la monade ci-dessus, implémentez une fonction search qui prend en entrée une liste et une valeur et recherche cette valeur dans la liste, retournant true si elle l'a trouvée et false si elle ne l'a pas trouvée, ainsi que le nombre de comparaisons qu'elle a effectuées, les deux faisant partie d'une seule valeur monadique. Utiliser la valeur retournée pour juger si votre fonction est efficace ou non en termes de nombre de comparaisons effectuées.

Exemples de résultats attendus :

# search [1;2;3;4;5] 3;;
- : bool AddWriter.t = Writer (true, 2)
# search [1;2;3;4;5] 0;;
- : bool AddWriter.t = Writer (false, 5)

Exercice 1

-Problème 0: Donnez une structure avec la signature Monoid qui encode le monoïde des chaînes de caractères avec la concaténation comme opération binaire.

-Problème 1: Créez la monade StringWriter correspondante en utilisant le foncteur présenté ci-dessus.

-Problème 2: Voici une définition d'un type pour les arbres binaires et une valeur encodant l'exemple d'arbre ci-dessus:

type abr = 
    | Leaf of int 
    | Node of int * abr * abr

let example_tree = 
    Node (0, 
        Node (1, 
            Node (2, Leaf 3, Leaf 4), 
            (Leaf 5)), 
        Node (6, Leaf 7, Leaf 8))

Écrivez une fonction search qui prend en entrée un arbre binaire et une valeur et retourne true ou false selon que la valeur existe ou non dans l'arbre, ainsi qu'une chaîne composée des caractères "l" et "r" qui encode le chemin vers la valeur (si elle existe). Exemples de résultats attendus :

# search example_tree 3;;
- : bool StringWriter.t =
Writer (true, "lll")
# search example_tree 5;;
- : bool StringWriter.t = Writer (true, "lr")
# search example_tree 7;;
- : bool StringWriter.t = Writer (true, "rl")
# search example_tree 10;;
- : bool StringWriter.t = Writer (false, "")

-Problème 3: Supposons qu'au lieu de la chaîne de caractères ci-dessus encodant le chemin, nous voulions les sommets (autres que la racine) qui composent ce chemin. Modifiez votre code pour obtenir ce résultat. Exemples de résultats attendus :

# search example_tree 3;;
- : bool ListWriter.t = Writer (true, [1; 2; 3])
# search example_tree 5;;
- : bool ListWriter.t = Writer (true, [1; 5])
# search example_tree 7;;
- : bool ListWriter.t = Writer (true, [6; 7])
# search example_tree 10;;
- : bool ListWriter.t = Writer (false, [])

Hint

Créez un monoïde pour les listes avec concaténation et sa monade correspondant.