Programmation Fonctionnelle, Examen

Version & licenses
Creative Commons License

Programmation Fonctionnelle, Examen

Guyslain Naves

Les deux premiers exercices portent sur les règles de validation des listes de signatures pour les candidats à la présidence de la République Française.

Exercice 1 : Élection présidentielle, Json (partie 1).

On dispose d'un fichier sponsors.json au format json dans le répertoire courant. Ce fichier contient la liste des signatures déposées au conseil constitutionnel, classées par candidat supporté. On l'a récupéré sur le site du conseil constitutionnel :

https://presidentielle2017.conseil-constitutionnel.fr/les-parrainages/tous-les-parrainages/

Chaque signataire est décrit dans une table d'association json par ses nom, prénom, circonscription électorale (ville, département,...), mandat ( "Maire" , "Député-e" ,...), civilité ( "M" , "Mme" , ...), département, et la date de publication de sa signature par le conseil constitutionnel, au format "jj/mm/aaaa" . Tous ces champs sont des chaînes de caractères et sont toujours définis. Le premier signataire du fichier est par exemple représenté par le fragment json :

  1. { "Circonscription":"",
  2. "Civilité":"Mme",
  3. "Date de publication":"01/03/2017",
  4. "Département":"Manche",
  5. "Mandat":"Conseiller/ère départemental-e",
  6. "Nom":"LARSONNEUR-MOREL",
  7. "Prénom":"Dominique"
  8. }

Le fichier json complet est une liste json de candidats, chaque candidat est une table d'association avec deux champs :

  • "Candidat-e parrainé-e" contient une chaîne de caractère, le nom du candidat.
  • "Parrainages" contient une liste json de signataires (au format vu ci-dessus).

On se propose de lire le fichier et de l'organiser sous une forme exploitable en OCaml. On ne se préoccupera pas de gérer les erreurs si le fichier est mal-formé.

  1. Proposer un type pour les dates.
  2. On veut écrire une fonction de conversion d'une chaîne de caractères en date. Dans un premier temps, donner une fonction convertissant une date en chaîne de caractères en utilisant Print.sprintf. Pour écrire un entier en 2 chiffres, on utilise le motif "%02d" .
  3. Écrire la fonction date_of_string. Pour écrire avec printf il faut donner le format et les valeurs à attribuer à chaque motif du format. Pour lire avec Scanf.sscanf, il faut donner :
    • la chaîne de caractères à lire
    • le format avec ses motifs

    • une fonction prenant la valeur de chaque motif en argument, dans l'ordre. Par exemple :

      1. let int_pair_of_string string =
      2. Scanf.sscanf string "(%d,%d)" @@ fun left right ->
      3. (left,right)

  4. Utiliser le module Json = Yojson.Basic.Util pour convertir un fragment json correspondant à un signataire en sponsor:

    1. type sponsor =
    2. { circonscription : string;
    3. civility : string;
    4. publication_date : date;
    5. department : string;
    6. mandate : string;
    7. last_name : string;
    8. first_name : string
    9. }

  5. On représente chaque liste de parrainages avec le type :

    1. type sponsorship =
    2. { candidate : string; (* name of the candidate *)
    3. sponsors : sponsor list (* list of sponsors for this candidate *)
    4. }

    Écrire une fonction convertissant un fragment json correspondant à un candidat en une valeur du type sponsorship.

  6. Enfin, écrire une fonction chargeant un fichier dont le nom est donné en argument :

    1. val load_sponsorships : string -> sponsorship list

Exercice 2 : Élection présidentielle, validation (partie 2).

Cet exercice réutilise les types sponsor et sponsorship de l'exercice 1 . Il n'est cependant pas nécessaire d'avoir répondu aux questions de l'exercice 1 pour répondre à celui-ci.

Pour être validée par le conseil constitutionnel, une candidature doit être supportée par au moins 500 signatures, telles que :

  • pas plus de 10 % viennent du même département (ou de la même collectivité d'Outre-Mer),
  • au moins 30 départements (ou collectivités d'Outre-Mer) sont représentées.

Le but de l'exercice est de trouver les candidatures valides parmi la liste de toutes les candidatures :

  1. val extract_valid_sponsorship : sponsorship list -> sponsorship list
  1. Comment définir un module StringMap proposant des dictionnaires dont les clés sont des chaînes de caractères ?

  2. Il nous faut, pour chaque candidature, classer les signatures par département. Pour cela, nous allons transformer la liste des signatures en un dictionnaire StringMap.t, associant à chaque département les signataires pour ce département. Commencer par écrire une fonction permettant d'ajouter une signature dans le dictionnaire :

    1. val add_sponsor : sponsor list StringMap.t -> sponsor -> sponsor list StringMap.t

  3. Ajouter une fonction transformant une liste de signature en dictionnaire :

    1. val convert_sponsors_into_map : sponsor list -> sponsor list map

  4. Écrire un prédicat pour tester si les signatures proviennent d'au moins 30 départements différents.

    1. val has_30_departments : sponsor list StringMap.t -> bool

  5. Écrire une fonction pour compter le nombre de signatures d'un candidat, en n'en comptant pas plus de 50 par département (pour respecter la contrainte d'au plus 10 % par département) :

    1. val find_number_of_sponsors : sponsor list StringMap.t -> int
  6. Écrire la fonction extract_valid_sponsorship.
  7. (bonus) Écrire une fonction vérifiant qu'aucun signataire n'a signé deux fois.

Exercice 3 : Lentilles.

On représente les États et leurs chefs d'État à l'aide des types suivants :

  1. type genre = Male | Female | Robot
  2. type id =
  3. { name : string;
  4. genre : genre
  5. }

  7. type residence = string
  8. type head_of_state =
  9. { id : id;
  10. residence : residence;
  11. }

  13. type country_name = string
  14. type state =
  15. { country : country_name;
  16. head_of_state : head_of_state;
  17. }

Par exemple :

  1. let france =
  2. let f_hollande = { name = "François Hollande"; genre = Male } in
  3. let french_president = { id = f_hollande; residence = "Palais de l'Élysée" } in
  4. { country = "France";
  5. head_of_state = french_president
  6. }

  8. let usa =
  9. let d_trump = { name = "Donald John Trump"; genre = Male } in
  10. let us_president = { id = d_trump; residence = "The White House" } in
  11. { country = "United States of America";
  12. head_of_state = us_president
  13. }
1 . Un coup d'état

Le complexe militaro-industriel américain décide de remplacer les chefs d'État par des robots indistingables des originaux. Écrire une fonction qui à un État associe un autre État similaire mais tel que le genre de son chef d'État soit Robot.

  1. val coup : state -> state = <fun>

  3. # let usa_after_coup = coup usa;; (* an example *)
  4. val usa_after_coup : state =
  5. { country = "United States of America";
  6. head_of_state =
  7. { id = {name = "Donald John Trump"; genre = Robot};
  8. residence = "The White House"
  9. }
  10. }
2 . Des lentilles pour simplifier les manipulations.

La fonction coup est très verbeuse. Les lentilles sont une technique pour manipuler et modifier des champs profondément imbriqués dans une structure de données. Voici un petit module proposant des lentilles :

  1. module Lens :
  2. sig
  3. (** A lens, allowing access to a ['content] contained in an ['item] *)
  4. type ('item, 'content) lens

  6. (** Creates a lens from a setter and a getter *)
  7. val create :
  8. setter:('item -> 'content -> 'item) ->
  9. getter:('item -> 'content) ->
  10. ('item, 'content) lens

  12. (** composing two lenses: access to the content of a subitem of an item *)
  13. val compose :
  14. ('subitem, 'content) lens ->
  15. ('item, 'subitem) lens -> ('item, 'content) lens

  17. (** composing two lenses (infix notation, arguments flipped) *)
  18. val ( >> ) :
  19. ('item, 'subitem) lens ->
  20. ('subitem, 'content) lens -> ('item, 'content) lens

  22. (** convert a lens into a getter *)
  23. val view : ('item, 'content) lens -> 'item -> 'content

  25. (** convert a lens into a setter *)
  26. val set : ('item, 'content) lens -> 'item -> 'content -> 'item

  28. (** convert a lens into an update function *)
  29. val over :
  30. ('item, 'content) lens -> 'item -> f:('content -> 'content) -> 'item
  31. end

Par exemple, voici une lentille pour pour accéder au chef d'État dans un État :

  1. let head_of_state_lens =
  2. Lens.create
  3. ~setter:(fun state new_head -> { state with head_of_state = new_head })
  4. ~getter:(fun state -> state.head_of_state)

Écrire de la même façon :

  • une lentille pour accéder à l'identité à partir d'un chef d'État,
  • une autre pour accéder au nom à partir d'une identité,
  • une autre pour accéder au genre à partir d'une identité.
3 . Composer des lentilles.

Utiliser une fonction de composition de Lens pour créer une lentille permettant d'accéder au genre d'un chef d'État à partir de l'État.

  1. val genre_from_state_lens : (state,genre) lens
4 . Utiliser des lentilles.

On peut convertir une lentille en accesseur ou mutateur avec les fonctions view, set et over de Lens.

Écrire une fonction permettant, étant donné un État, de modifier le genre de son chef, transformant les hommes en robots, les robots en femme et les femmes en hommes.

5 . Élection présidentielle.

Proposer une expression utilisant les lentilles pour remplacer le chef d'État de la France par la personnalité de votre choix.

6 . Type d'une lentille.

À votre avis, comment est représentée une lentille ? Quelle peut être la définition du type lens ? Comment écrire la fonction compose ?

Éléments de langage

Fonctions utiles du module List :

  1. val length : 'elt list -> int
  2. val rev : 'elt list -> 'elt list
  3. val concat : 'elt list list -> 'elt list
  4. val map : ('elt -> 'im) -> 'elt list -> 'im list
  5. val fold_left : ('state -> 'elt -> 'state) -> 'state -> 'elt list -> 'state
  6. val for_all : ('elt -> bool) -> 'elt list -> bool
  7. val exists : ('elt -> bool) -> 'elt list -> bool
  8. val mem : 'elt -> 'elt list -> bool
  9. val filter : ('elt -> bool) -> 'elt list -> 'elt list
  10. val fast_sort : ('elt -> 'elt -> int) -> 'elt list -> 'elt list

Fonctions utiles de Map.S :

  1. type key
  2. type 'assoc t
  3. val empty : 'assoc t
  4. val add : key -> 'assoc -> 'assoc t -> 'assoc t
  5. val mem : key -> 'assoc t -> bool
  6. val find : key -> 'assoc t -> 'assoc (* may fail if key is not present *)
  7. val map : ('assoc -> 'im) -> 'assoc t -> 'im t
  8. val fold : ('key -> 'assoc -> 'state -> 'state) -> 'assoc t -> 'state -> state
  9. val cardinal : 'assoc t -> int

Fonctions utiles de Json = Yojson.Basic :

  1. val from_file : string -> json

  3. module Util : sig
  4. (** [member fieldname json] returns the content of a field [fieldname]
  5. in a json association table [json] *)
  6. val member : string -> json -> json
  7. (** [to_list json] returns the list of elements in a json list [json] *)
  8. val to_list : json -> json list
  9. (** [to_string json] returns the string corresponding
  10. to a json string [json] *)
  11. val to_string : json -> string
  12. end

Exemples de syntaxe :

  1. type ratio = int * int

  3. let rec euclid a b =
  4. if b = 0 then a
  5. else euclid b (a mod b)

  7. let pgcd a b = euclid (abs a) (abs b)

  9. let ratio p q =
  10. let d = pgcd p q in
  11. if q < 0 then (-p / d, q / d)
  12. else (p/d, q/d)

  14. let (+/) (a,b) (c,d) = ratio (a*d + b*c) (b*d)

  16. let (++) (a,b) (c,d) = ratio (a+c) (b+d)

  18. module Queue =
  19. struct

  21. type 'elt t =
  22. Queue of ('elt list) * ('elt list)

  24. exception Empty

  26. let empty = Queue ([],[])

  28. let is_empty = function
  29. | Queue ([],[]) -> true
  30. | _ -> false

  32. let queue = function
  33. | Queue ([],l) -> Queue(List.rev l,[])
  34. | x -> x

  36. let snoc (Queue (l1,l2)) ele =
  37. queue (Queue (l1,ele::l2))

  39. let head = function
  40. | Queue ([],_) -> raise Empty
  41. | Queue (l,_) -> List.hd l

  43. let tail = function
  44. | Queue ([],_) -> raise Empty
  45. | Queue (l1,l2) -> queue (Queue (List.tl l1,l2))

  47. end