Exercice 0

Le but de ce premier exercice est de vous familiariser avec l'implémentation (basée sur le type option) de la monade Maybe présentée pendant le cours :

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

module Maybe : Monad with type 'a t = 'a option = struct 
    type 'a t = 'a option 

    let return x = Some x 

    let ( >>= ) m f = match m with 
        | None -> None 
        | Some x -> f x
end

-Problème 0 : En utilisant la monade Maybe, implémentez le premier exemple que nous avons vu pendant le cours : une fonction nth_to_str : int -> int list -> string option qui prend en entrée une liste l et une valeur entière n et retourne soit :

Une valeur Some s où s est la représentation en chaîne du n-ème élément de la liste (s'il existe).
Ou None si ce n'est pas le cas.

La fonction nth_to_str doit utiliser les deux fonctions suivantes vues pendant le cours :

let nth_t l n = 
    if n < 0 then None else
    let rec nth_aux l n =
        match l with
            | [] -> None 
            | a::l -> if n = 0 then Some a else nth_aux l (n-1)
    in nth_aux l n

let str_of_int_m x = string_of_int x |> return

Exemples de résultats attendus :

# nth_to_str [1;2;3;4;5] 3;;
- : string option = Some "4"
# nth_to_str [1;2;3;4;5] 5;;
- : string option = None
# nth_to_str [1;2;3;4;5] (-1);;
- : string option = None

-Problème 1 : Implémentez une fonction nth_to_pretty_string : int -> int list -> string option qui retourne soit :

Si l'index fourni est valide : une valeur Some s où s est de la forme The element at index *n* is *e* avec *n* et *e* la chaîne de représentant l'indice et de la valeur correspondante, respectivement.

Si ce n'est pas le cas : None. Exemples de résultats attendus :

# nth_to_pretty_str [1;2;3] 0;;
- : string option = Some "The element at index 0 is: 1"
# nth_to_pretty_str [1;2;3] 1;;
- : string option = Some "The element at index 1 is: 2"
# nth_to_pretty_str [1;2;3] 2;;
- : string option = Some "The element at index 2 is: 3"
# nth_to_pretty_str [1;2;3] 3;;
- : string option = None
# nth_to_pretty_str [1;2;3] (-1);;
- : string option = None

Exercice 1

-Problème 0 : Implémentez une fonction comb_opt : 'a list -> 'b list -> ('a * 'b) list option qui, lorsqu'on lui donne deux listes l, k, retourne :

Si les deux listes d'entrée sont de même taille, Some r où r est une liste dont le n-ième élément est un tuple constitué des n-ième éléments de l et k respectivement.
Si ce n'est pas le cas, None.

Exemples de résultats attendus :

# comb_opt [1;2;3] [4;5;6];;
- : (int * int) list option = Some [(1, 4); (2, 5); (3, 6)]
# comb_opt [1;2;3;4] [5;6;7];;
- : (int * int) list option = None

-Problème 1 : Implémentez une fonction print_combined : int list -> int list -> unit list option qui prend comme arguments deux listes l, k d'entiers et fait ce qui suit :

Si les deux listes sont de la même taille, disons \(\ell\), elle imprime \(\ell\) lignes, dont chacune est du format a <-> b où a et b sont définis en fonction du numéro de ligne : pour la \(n\)-ième ligne (\(1 \leq n \leq \ell\)), a est le \(n\)-ième élément de la liste l et b est le \(n\)-ième élément de la liste k.
Si ce n'est pas le cas, il retourne None.

Exemples de résultats attendus :

# print_combined [1;2;3] [4;5;6];;
1<->4
2<->5
3<->6
- : unit list option = Some [(); (); ()]
# print_combined [1;2;3] [4;5;6;7];;
- : unit list option = None

Exercice 2 : Utilisation de la monade Maybe avec des listes

Considérons les deux fonctions suivantes qui renvoient la "tête" et la "queue" d'une liste lorsqu'elle existe :

let car l = match l with
    | [] -> None 
    | h :: _ -> Some h

let cdr l = match l with 
    | [] -> None 
    | _ :: t -> Some t

Problème 0 : Définissez une fonction cadr : 'a list -> 'a option qui renvoie le deuxième élément (s'il existe) d'une liste en utilisant les fonctions car et cdr définies ci-dessus.

Essayez de le faire d'au moins deux façons :

Une façon en faisant explicitement du pattern matching avec des valeurs de type option.
Une autre façon en utilisant internally_dec_tree_height_4la structure monadique du type option (la monade Maybe).

Exemples de comportements attendus :

# cadr [1;2;3];;
- : int option = Some 2
# cadr [1];;
- : int option = None
# cadr [];;
- : 'a option = None

-Problème 1 : Faire la même chose pour une fonction caddr : 'a list -> 'a option qui renvoie le troisième élément d'une liste (s'il existe).

Exemples de comportements attendus :

# caddr [1;2;3];;
- : int option = Some 3
# caddr [1;2];;
- : int option = None
# caddr [1];;
- : int option = None
utop # caddr [];;
- : 'a option = None

-Problème 2 : En utilisant les fonctions susmentionnées, implémentez une fonction plus_car_cadr_caddr : int list -> int option qui ajoute le premier, le deuxième et le troisième élément d'une liste d'entiers (si possible).

Exemples de comportements attendus :

# plus_car_cadr_caddr [1;2;3;4];;
- : int option = Some 6
# plus_car_cadr_caddr [1;2];;
- : int option = None
# plus_car_cadr_caddr [];;
- : int option = None

-Problème 3 : En utilisant les fonctions susmentionnées, définissez une fonction check_dups : 'a list -> bool option qui retourne quelque chose de vrai si une liste contient deux éléments identiques contigus et quelque chose de faux si ce n'est pas le cas.

Exemples de comportements attendus :

# check_dups [1;2;3];;
- : bool option = Some false
# check_dups [1;3;3];;
- : bool option = Some true
# check_dups [1];;
- : bool option = Some false
# check_dups [];;
- : bool option = Some false

-Problème 4 : Considérez la version monadique suivante de la fonction intégrée mod, qui au lieu de produire une exception Division_by_zero lorsque son second argument est zéro, retourne None :

let mod_t x y = match y with
    | 0 -> None 
    | _ -> Some (x mod y)

Implémentez une fonction maybe_mod_list : int list -> int -> int list option qui, lorsqu'on lui donne une liste l et un entier m, produit une nouvelle liste dont les éléments sont ceux de l modulo m (si possible). Exemples de comportements attendus :

# maybe_mod_list [1;2;3;4;5;6] 3;;
- : int list option = Some [1; 2; 0; 1; 2; 0]
# maybe_mod_list [1;2;3;4;5;6] 2;;
- : int list option = Some [1; 0; 1; 0; 1; 0]
# maybe_mod_list [1;2;3;4;5;6] 0;;
- : int list option = None

Fun-fact

Les structures n telles que n = a list qui permettent de faire correspondre des fonctions monadiques f : 'a -> 'b m sur elles pour produire une valeur de type 'b n m sont appelées "traversables". Les arbres que nous verrons dans le prochain exercice sont également traversables !

Exercice 3 : Utilisation de la monade Maybe avec les arbres

Considérons la définition suivante d'un type d'arbres binaires, quelques fonctions qui récupèrent respectivement l'enfant gauche, l'enfant droit, et la valeur d'un noeud (s'il n'est pas une feuille) et un exemple de valeur de ce type :

type 'a tree = 
    | Leaf 
    | Node of 'a * 'a tree * 'a tree 

let left_child t = match t with
    | Leaf -> None 
    | Node (_,l,_) -> Some l 

let right_child t = match t with
    | Leaf -> None 
    | Node (_,_,r) -> Some r

let get_val t = match t with 
    | Leaf -> None 
    | Node (v,_,_) -> Some v 

let example_tree = 
    Node (1,
        Node (2, Leaf, Leaf),
        Node (3, 
            Node (4, Leaf, Leaf),
            Node (5, Leaf, Leaf)))

Problème 0 : Implémentez une fonction follow_path : 'a tree -> string list -> 'a list option qui retourne les valeurs rencontrées si l'on suit le chemin décrit par une liste (dont les éléments sont soit l qui signifie un virage à gauche, soit r qui signifie un virage à droite) dans l'arbre, en commençant par la racine.

Exemples de comportements attendus :

# follow_path example_tree ["l";"l"];;
- : int list option = Some [1; 2]
# follow_path example_tree ["l";"l";"r"];;
- : int list option = None
# follow_path example_tree ["r";"l";"l"];;
- : int list option = Some [1; 3; 4]
# follow_path example_tree ["r";"r";"l"];;
- : int list option = Some [1; 3; 5]
# follow_path example_tree ["r";"l";"l";"l"];;
- : int list option = None

Problème 1 : implémentez une fonction maybe_mod_tree : int tree -> int -> int tree option qui, lorsqu'on lui donne un arbre avec des valeurs entières stockées à ses noeuds, renvoie un nouvel arbre dont les noeuds stockent les valeurs de l'original modulo le second argument de la fonction (s'il n'est pas zéro).

Exemple de comportements attendus :

# maybe_mod_tree example_tree 2;;
- : int tree option =
Some
 (Node (1, Node (0, Leaf, Leaf),
   Node (1, Node (0, Leaf, Leaf), Node (1, Leaf, Leaf))))
# maybe_mod_tree example_tree 3;;
- : int tree option =
Some
 (Node (1, Node (2, Leaf, Leaf),
   Node (0, Node (1, Leaf, Leaf), Node (2, Leaf, Leaf))))
# maybe_mod_tree example_tree 0;;
- : int tree option = None

Devoir à rendre avant le 24 novembre 2024, 23h59, heure de Paris:

Cet exercice concerne la monade Error, qui est étroitement liée à la monade Maybe. Pour implémenter cette monade, nous allons utiliser la fonctionnalité fournie par le module Result de la bibliothèque standard d'OCaml (voir https://v2.ocaml.org/api/Result.html).

Le type ('a, 'e) result :

type ('a, 'e) t = ('a, 'e) result = 
    | Ok of 'a
    | Error of 'e

fournie par Result est paramétrée par deux paramètres:

Le paramètre de type 'a qui représente les valeurs des calculs réussis.
Le paramètre de type 'e qui représente les valeurs retournées en cas d'erreur.

Dans notre cas, nous prendrons 'e = string car en cas d'erreur, nous voulons retourner une chaîne de caractères décrivant l'erreur. Quant aux valeurs des calculs réussis, nous autorisons n'importe quelle valeur, donc nous gardons 'a comme variable de type et ne la fixons pas.

Cela donne la monade suivante :

module Error : Monad with type 'a t = ('a, string) result = struct
    type 'a t = ('a, string) result 

    let return x = Ok x

    let ( >>= ) m f = match m with 
        | Error s -> Error s
        | Ok v -> f v

end

Remarquez la grande similarité entre Error et Maybe : en fait, Error n'est différent que par le fait qu'au lieu de None il a

Error
s

(qui porte avec lui une chaîne décrivant l'erreur) et qu'au lieu de

Some
x

il a Ok x.

Nous utiliserons cette monade pour mettre en œuvre une structure de base de données très simple.

Notre base de données enregistre les étudiants et est composée de trois listes contenant des chaînes de caractères : 1. La première liste enregistre les noms des étudiants.

La deuxième liste enregistre les noms de famille des étudiants.
La troisième liste enregistre les numéros des étudiants.

Le \(k\)-ième élément de chaque liste est respectivement le nom, le prénom et le numéro d'étudiant d'un étudiant. Un exemple d'une telle base de données est

let example_db = (["Alice" ; "Bob"],["Smith" ; "Joe"],["001" ; "002"])

qui contient deux étudiants : "Alice Smith" avec le numéro "001" et "Bob Joe" avec le numéro "002". Voici un exemple de base de données non valide :

let example_db_invalid = (["Alice" ; "Bob"],["Smith" ; "Joe"],["001"])

car il manque le numéro d'étudiant de "Bob Joe".

Une base de données est valide si les trois listes ont la même taille (c'est-à-dire si chaque étudiant a un nom, un prénom et un numéro bien définis).

Voici la signature complète de la base de données :

module type Database = sig 
    type database = string list * string list * string list

    val empty : database

    val is_valid : database -> bool 

    val print_db : database -> unit list t 

    val find_and_print : database -> (string * string * string -> bool) -> unit list t 

    val insert_into_database : string -> string -> string -> database -> database t 

end

(NB. le type monadique 'a t ici est ('a, string) result).

Le but de cet exercice est de fournir une implémentation de cette base de données sous la forme d'un module appelé MyDatabase.

-Problème 0 : Implémentez la fonction is_valid qui vérifie si une base de données est valide (en vérifiant que les trois listes sont de la même taille).

# MyDatabase.is_valid example_db;;
- : bool = true
# MyDatabase.is_valid example_db_invalid;;
- : bool = false

-Problème 1 : Implémentez la fonction print_db qui imprime le contenu de la base de données, en une ligne par entrée, au format :

Nom : *n* Nom de famille : *s* Numéro : *i*

où n,s,i sont le nom, le prénom et le numéro d'étudiant d'un étudiant. Par exemple, en appliquant cette fonction à l'exemple défini précédemment, nous obtenons :

# MyDatabase.print_db example_db;;
Name: Alice Surname: Smith Student Number: 001
Name: Bob Surname: Joe Student Number: 002
- : unit list Error.t = Ok [(); ()]

Hint

Vous pouvez créer des tuples de la forme (n,s,i) à partir des trois listes d'une base de données en modifiant légèrement la fonction comb_opt que nous avons implémentée en classe. En utilisant ces tuples, il est facile d'imprimer la ligne souhaitée. Bien sûr, une telle fonction échoue si on lui fournit trois listes de longueurs inégales, donc la fonction doit renvoyer Error "Can't combine lists of different sizes".

-Problème 2 : Implémentez la fonction insert_into_database qui prend trois chaînes de caractères et une base de données comme arguments et (si la base de données est valide) ajoute une nouvelle entrée à la base de données en utilisant la première chaîne comme nom, la deuxième comme nom de famille et la troisième comme numéro d'étudiant.

Si la base de données n'est pas valide, le programme renvoie Error "Cannot insert into invalid database".

Voici des exemples:

# MyDatabase.insert_into_database "Carlos" "Jones" "123" example_db;;
- : MyDatabase.database Error.t =
Ok
 (["Carlos"; "Alice"; "Bob"], ["Jones"; "Smith"; "Joe"], ["123"; "001"; "002"])
# MyDatabase.insert_into_database "Carlos" "Jones" "123" example_db_invalid;;
- : MyDatabase.database Error.t =
Error "Cannot insert into invalid database!"

-Problème 3 (Bonus): Implémentez la fonction find_and_print qui prend comme arguments une base de données b et un prédicat f : string * string * string -> bool et affiche toutes les entrées de la base de données b pour lesquelles f donne true. Par exemple :

# let find_name n = function (x,_,_) -> (x = n);;
# MyDatabase.find_and_print example_db (find_name "Alice");;
Name: Alice Surname: Smith Student Number: 001
- : unit list Error.t = Ok [()]
# MyDatabase.find_and_print example_db (find_name "Bob");;
Name: Bob Surname: Joe Student Number: 002
- : unit list Error.t = Ok [()]
# MyDatabase.find_and_print example_db (find_name "Neo");;
- : unit list Error.t = Ok []