Programmation Fonctionnelle, corrigé de l'examen

Version & licenses
Creative Commons License

Programmation Fonctionnelle, corrigé de l'examen

Guyslain Naves

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

  1. Une date représente simultanément 3 informations, on utilise donc un type produit.

    1. type date =
    2. { year : int;
    3. month : int;
    4. day : int
    5. }

  2. Bien sûr, pour l'année il faut 4 chiffres, on adapte donc le motif.

    1. let string_of_date { day; month; year } =
    2. Printf.sprintf "%02d/%02d/%04d" day month year

  3. On donne donc une fonction en dernier argument, utilisant les valeurs lues. On pourrait la donner parenthésée, ou bien la nommer avant, ou comme ici utiliser le @@ avec une fonction anonyme.

    1. let date_of_string text =
    2. Scanf.sscanf text "%d/%d/%d" @@ fun day month year ->
    3. { day; month; year }

  4. On récupère les différents champs avec member et on n'oublie pas des les traduire dans le type adéquat.

    1. let sponsor_of_json json =
    2. let open Yojson.Basic.Util in
    3. { circonscription = json |> member "Circonscription" |> to_string;
    4. civility = json |> member "Civilité" |> to_string;
    5. publication =
    6. json |> member "Date de publication" |> to_string |> date_of_string;
    7. department = json |> member "Département" |> to_string;
    8. mandate = json |> member "Mandat" |> to_string;
    9. last_name = json |> member "Nom" |> to_string;
    10. first_name = json |> member "Prénom" |> to_string
    11. }

  5. Attention à bien utiliser List.map pour convertir les éléments de la liste des parrains.

    1. let sponsorship_of_json json =
    2. let open Yojson.Basic.Util in
    3. { candidate =
    4. json |> member "Candidat-e parrainé-e" |> to_string;
    5. sponsors =
    6. json |> member "Parrainages" |> to_list |> List.map sponsor_of_json;
    7. }

  6. Yojson propose une fonction pour lire un fichier contenant du json. On utilise ensuite les fonctions que nous venons d'écrire.

    1. let load_sponsorships file_name =
    2. Yojson.Basic.from_file file_name
    3. |> to_list
    4. |> List.map sponsorship_of_json

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

  1. On construit des dictionnaires en appliquant le foncteur Map.Make à un type ordonnés des clés.

    1. module StringMap = Map.Make(String)

  2. On récupère la liste des sponsors déjà enregistrés, par défaut la liste vide. Puis on remet cette liste avec le nouveau sponsor en plus.

    1. let add_sponsor departments sponsor =
    2. let previous_sponsors =
    3. StringMap.find_opt sponsor.department sponsor
    4. |> Option.value ~default:[]
    5. in
    6. StringMap.add
    7. sponsor.department
    8. (sponsor :: previous_sponsors)
    9. departments

  3. Il faut ajouter tous les sponsors de la liste dans un même dictionnaire initialement vide. On doit donc consommer tous les éléments d'une liste, donc utiliser List.fold_left.

    1. let convert_sponsors_into_map sponsors =
    2. List.fold_left add_sponsor StringMap.empty sponsors

  4. Pas de problème, on a une fonction StringMap.cardinal.

    1. let has_30_departments departments =
    2. StringMap.cardinal departments >= 30

  5. On veut parcourir tous les éléments de la structure de dictionnaire pour obtenir une valeur agrégée, donc on utilise fold. Pour rester lisible, on utilise ici une fonction nommée.

    1. let find_number_of_sponsors departments =
    2. let add_department_count department sponsors count =
    3. count + min 50 (List.length sponsors)
    4. in
    5. StringMap.fold add_department_count 0 departments

  6. On crée un prédicat qu'on utilise avec List.filter. Le prédicat transforme la liste en dictionnaire et utilise les fonctions des questions précédentes.

    1. let is_valid_sponsorship sponsorship =
    2. let map = convert_sponsors_into_map sponsorship in
    3. has_30_departments map
    4. && find_number_of_sponsors map >= 500

    6. let extract_valid_sponsorships sponsorships =
    7. sponsorships
    8. |> List.filter is_valid_sponsorship

  7. On compte le nombre de fois où chaque signataire a signé. Pour cela, on crée un dictionnaire dont les clés sont les signataires.

    Ensuite on compte tous les parrains de tous les candidats et on garde ceux ayant parrainés deux fois.

    1. module OrderedSponsor =
    2. struct
    3. type t = sponsor
    4. let compare sponsor1 sponsor2 =
    5. let delta = String.compare sponsor1.last_name sponsor2.last_name in
    6. if delta = 0 then
    7. String.compare sponsor1.first_name sponsor2.first_name
    8. else
    9. delta
    10. end

    12. module SponsorMap = Map.Make(Sponsor)

    14. let count_sponsor map sponsor =
    15. let count =
    16. SponsorMap.find_opt sponsor map
    17. |> Option.value ~default:0
    18. in
    19. SponsorMap.add sponsor (count+1) map

    21. let invalid_sponsors sponsorships =
    22. sponsorships
    23. |> List.concat
    24. |> List.fold_left count_sponsor SponsorMap.empty
    25. |> SponsorMap.filter (fun count -> count > 1)

    27. let has_no_duplicate_sponsor sponsorships =
    28. SponsorMap.is_empty (invalid_sponsors sponsorships)

Exercice 3 : Lentilles.

1 . Un coup d'état
  1. let coup state =
  2. { state with
  3. head_of_state =
  4. { state.head_of_state with
  5. id =
  6. { state.head_of_state.id with
  7. genre = Robot
  8. }
  9. }
  10. }
2 . Des lentilles pour simplifier les manipulations.
  1. let id_of_head_lens =
  2. Lens.create
  3. ~setter:(fun head id -> { head with id })
  4. ~getter:(fun head -> head.id)

  6. let name_of_id_lens =
  7. Lens.create
  8. ~setter:(fun id name -> { id with name })
  9. ~getter:(fun id -> id.name)

  11. let genre_of_id_lens =
  12. Lens.create
  13. ~setter:(fun id genre -> { id with genre })
  14. ~getter:(fun id -> id.genre)
3 . Composer des lentilles.
  1. let genre_of_state_lens =
  2. let open Lens in
  3. head_of_state_lens >> id_of_head_lens >> genre_of_id_lens
4 . Utiliser des lentilles.
  1. let change_genre =
  2. Lens.over genre_of_state_lens
  3. ~f:(function
  4. | Male -> Robot
  5. | Robot -> Female
  6. | Female -> Male
  7. )
5 . Élection présidentielle.
  1. let elect =
  2. let open Lens in
  3. set
  4. (head_of_state_lens >> id_of_head_lens >> name_of_id_lens)
  5. france
  6. "Xavier Leroy"
6 . Type d'une lentille.

Une façon simple de faire et de stocker la fonction d'accès et la fonction de modification.

  1. type ('item,'content) lens =
  2. { setter : 'content -> 'item -> 'content;
  3. getter : 'content -> 'item
  4. }

La composition s'écrit alors :

  1. let compose b_in_a c_in_b =
  2. { setter =
  3. fun a new_c ->
  4. let b = b_in_a.getter a in
  5. let new_b = c_in_b.setter b new_c in
  6. b_in_a.setter a new_b;
  7. getter =
  8. fun a ->
  9. a
  10. |> b_in_a.getter
  11. |> c_in_b.getter
  12. }

Il existe cependant des façons plus générales de faire ceci.