Programmation Fonctionnelle, TD10

Figure
Version & licenses
Creative Commons License

Programmation Fonctionnelle, TD10 : Révisions.

Guyslain Naves

Écriture de fonctions élémentaires (examen 2016).

Expressions régulières, nombre d'étoiles.

On se donne le type suivant pour représenter des expresssions régulières.

  1. type regular_expression =
  2. | Empty (* langage vide *)
  3. | Epsilon (* mot vide *)
  4. | Letter of char (* exemple : a *)
  5. | Concat of regular_expression * regular_expression (* exemple : ab *)
  6. | Union of regular_expression * regular_expression (* exemple : (a|b) *)
  7. | Star of regular_expression (* exemple : a* *)

Voici quelques exemples d'expressions régulières, avec leur notation standard en commentaires, qui seront utilisés dans les tests :

  1. let (^) regexp1 regexp2 = Concat (regexp1, regexp2)
  2. let (||) regexp1 regexp2 = Union (regexp1, regexp2)

  3. let some_regexps =
  4. [ (Letter 'a' || Epsilon) ^ Letter 'b'; (* (a|epsilon)b *)
  5. Star (Letter 'a') ^ Star (Letter 'b'); (* a*b* *)
  6. Star (Letter 'b' ^ Star(Letter 'a') ^ Letter 'b'); (* (ba*b)* *)
  7. Star Epsilon ^ Letter 'a' ^ Letter 'b'; (* epsilon*ab *)
  8. ]

Écrire une fonction comptant le nombre d'étoiles d'une expression régulière.

  1. val count_kleene_stars : regular_expression -> int = <fun>

  2. let tests_count_kleene_stars () =
  3. assert (List.map count_kleene_stars some_regexps = [ 0; 2; 2; 1 ])

Expressions régulières, longueur maximum d'un mot.

On se propose de calculer la longueur maximum d'un mot du langage associé à une expression régulière. Puisque cette longueur peut être indéfinie, on utilise le type suivant :

  1. type length =
  2. | Finite of int
  3. | Infinite

Donner le code de trois fonctions, calculant respectivement la somme de deux longueurs, le maximum de deux longueurs, et la longueur maximum d'un mot du langage associé à une expression régulière.

  1. val max_length : length -> length -> length = <fun>
  2. val add_length : length -> length -> length = <fun>
  3. val length_of_longuest_word : regular_expression -> length = <fun>

  4. let tests_length_longuest_word () =
  5. assert (
  6. List.map length_of_longuest_word some_regexps
  7. = [ Finite 2; Infinite; Infinite; Finite 2 ]
  8. )

Somme d'entiers pairs.

Écrire une fonction prenant une liste d'entiers en paramêtre et retournant la somme des entiers pairs de cette liste.

  1. val sum_of_even_elements : int list -> int = <fun>

  2. let test_sum_of_even_elements () =
  3. assert (
  4. List.map sum_of_even_elements
  5. [ [1;2;3;4;5;6;7;8];
  6. [];
  7. [2;4;6;8];
  8. [7;5;3;1]
  9. ]
  10. = [ 20; 0; 20; 0]
  11. )

Prénoms féminins.

Nous définissons les types suivants pour représenter les prénoms :

  1. type gender =
  2. | FemaleOnly
  3. | MaleOnly
  4. | Any

  5. type first_name =
  6. { name : string;
  7. gender : gender
  8. }

Écrire une fonction qui prend en paramêtre une liste de prénoms, et retourne les chaînes de caractères pouvant faire office de prénoms féminins.

  1. val extract_first_names_suitable_for_female :
  2. first_name list -> string list = <fun>

  3. let test_extract_first_names_suitable_for_female =
  4. assert (
  5. extract_first_names_suitable_for_female
  6. [ { name = "Camille"; gender = Any };
  7. { name = "Alphonse"; gender = MaleOnly };
  8. { name = "Diane"; gender = FemaleOnly };
  9. { name = "Gérard"; gender = MaleOnly };
  10. { name = "Sophie"; gender = FemaleOnly }
  11. ]
  12. = ["Camille"; "Diane"; "Sophie"]
  13. )

Map de deux listes.

List.map applique une fonction à tous les éléments d'une liste. Soit $f$ une fonction à deux arguments. Écrire une fonction qui applique $f$ (donnée en paramêtre) à toutes les paires d'éléments apparaissant en même position dans deux listes (voir les exemples).

  1. val map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list = <fun>

  2. let tests_map2 =
  3. assert (map2 (+) [1;2;3] [40;50;20;30] = [41; 52; 23]);
  4. assert (map2 (^) ["ba";"be";"bi"] ["dou";"di"] = ["badou"; "bedi"])

Si l'une des listes est plus longue que l'autre, les éléments excédentaires sont ignorés.

Paires d'éléments consécutifs d'une liste.

Utiliser la fonctionnelle map2 vue à la question précédente pour écrire une fonction retournant la liste des paires d'éléments consécutifs d'une liste, sans utiliser de récursion ni d'autre fonctionnelle.

  1. val pair_adjacent_items : 'a list -> ('a * 'a) list = <fun>

  2. let test_pair_adjacent_items () =
  3. assert (
  4. pair_adjacent_items [1;3;4;6;2;5]
  5. = [(1, 3); (3, 4); (4, 6); (6, 2); (2, 5)]
  6. )

Exercice 2 : 2048 (examen 2014)

2048 est le nom d'un jeu ayant récemment fait le buzz sur Internet. Il se présente sous la forme d'un damier de dimension 4x4. Chaque case est vide, ou bien contient une seule tuile sur laquelle figure un entier. Le joueur choisit à chaque tour une des quatre directions (haut, bas, gauche, droite), et cela pousse au maximum toutes les tuiles dans cette direction. Les tuiles ne peuvent pas se superposer, mais lorsque deux tuiles de même valeur sont poussées l'une vers l'autre, elles fusionnent en une seule tuile de valeur double.

Il n'est pas utile de connaître le jeu pour résoudre les questions suivantes.

Nous représentons une position du jeu grâce aux types suivants :

  1. type tile = int option
  2. type line = tile list
  3. type table = line list

L'exemple suivant nous servira à plusieurs reprises.

  1. let t : table =
  2. [ [ None; Some 2; None; None ];
  3. [ None; Some 4; Some 8; None ];
  4. [ None; Some 2; Some 4; Some 4 ];
  5. [ None; Some 2; Some 4; Some 2 ]
  6. ]

La première liste représente donc la ligne du haut, de gauche à droite, et ainsi de suite.

Faire tomber une ligne

Voici le code de la fonction faisant tomber les tuiles d'une ligne vers la gauche :

  1. let fall_line : line -> line = fun line ->
  2. let rec loop none_tiles = function
  3. | Some i :: Some j :: tail when i = j -> Some (i+j) :: loop (None :: none_tiles) tail
  4. | Some i :: None :: tail -> loop (None :: none_tiles) (Some i :: tail)
  5. | Some i :: tail -> Some i :: loop none_tiles tail
  6. | None :: tail -> loop (None :: none_tiles) tail
  7. | [] -> none_tiles
  8. in loop [] line

Calculer le résultat de fall_line [ Some 4; None; Some 4; Some 8; None; Some 2 ], en procédant par substitutions successives.

Faire tomber les tuiles à gauche

Pour faire tomber tout le damier, il suffit de faire tomber chaque ligne indépendamment. En déduire la fonction qui prend un tableau et fait tomber les tuiles de chaque ligne vers la gauche.

  1. val fall_leftward : table -> table
  2. let t' = fall_leftward t
  3. val t' : table =
  4. [ [ Some 2; None; None; None];
  5. [ Some 4; Some 8; None; None];
  6. [ Some 2; Some 8; None; None];
  7. [ Some 2; Some 4; Some 2; None] ]

Faire tourner le tableau

Pour faire tomber les tuiles dans les autres directions, il suffit de savoir faire tourner le tableau de 90 degrés, pour se ramener à fall_leftward. Écrire une fonction effectuant une telle rotation (dans le sens horaire) du tableau.

Remarquez que la $k^\textrm{e}$ ligne après la rotation correspond à la $k^\textrm{e}$ colonne avant la rotation, en sens inverse.

Pour cette question, vous avez exceptionnellement le droit d'utiliser List.hd pour récupérer le premier élément d'une liste, et List.tl pour récupérer la queue d'une liste.

  1. val clockwise_rotation : table -> table
  2. let t'' = clockwise_rotation t;;
  3. val t'' : table =
  4. [ [ None; None; None; None ];
  5. [ Some 2; Some 2; Some 4; Some 2 ];
  6. [ Some 4; Some 4; Some 8; None ];
  7. [ Some 2; Some 4; None; None ] ]

Faire tomber les tuiles dans les autres directions

En déduire les fonctions pour faire tomber les tuiles dans les autres directions.

  1. val fall_downward : table -> table
  2. val fall_rightward : table -> table
  3. val fall_upward : table -> table

Question bonus : Rajouter une tuile

Seulement si vous avez fini toutes les autres questions !

Après chaque tour du joueur, une tuile est ajoutée dans une position vide choisie aléatoirement. La nouvelle tuile aura la valeur $2$ avec probabilité $0.9$, et $4$ avec probabilité $0.1$. Coder une fonction permettant l'ajout d'une tuile selon ce procédé.