TP4

Devinez le type

Additions

Filtres pour listes

Différents filtres

Factorisation avec l'ordre supérieur

Notez que vos trois fonctions définies plus haut se ressemblent beaucoup : toutes les trois renvoient une liste contenant les éléments de la liste donnée en argument qui remplissent une condition.

Notez donc que, dans le code de ces fonctions, la seule différence est la condition pour laquelle les éléments de la liste en argument sont conservés ou non dans la liste résultat.

Liste d'association

Dans cet exercice, on va manipuler des listes d'association, c'est-à-dire des listes de couples (clé, valeur).

Tri de listes

Question 0 : Avant toute chose, comme ce TP va se concentrer sur les listes, nous vous proposons d'écrire une fonction générique d'affichage de liste. Cette fonction va prendre en paramètre la chaine de format à utiliser pour afficher un élément de la liste ainsi qu'une chaine de caractère servant de séparateur.
Ainsi print_list "%d" ", " [1 ; 2 ; 3] affichera 1, 2, 3 et print_list "%s" " " ["J'aime" ; "le" ; "poulet"] affichera J'aime le poulet.
Vous ferez attention à gérer le cas de la liste vide et à ne pas afficher le séparateur après le dernier élément de la liste ! Le type de la fonction est un peu compliqué à cause de la chaine de format mais elle s'écrira print_list fmt sep l avec fmt la chaine de format et sep la chaine de caractère à utiliser comme séparateur. N'essayez pas de manipuler fmt directement, mais utilisez Printf.printf qui interprète correctement ce type d'objets.

L'objectif de cet exercice est de coder une fonction de tri générique pour les listes. L'algorithme considéré est le tri fusion (dont la définition est rappelée en question 3).

Ensembles à base de listes

Nous voulons encoder des ensembles à base de listes de manière naïve. L'encodage est très simple : on dit qu'un élément x appartient à l'ensemble encodée par la liste l s'il est dans la liste l. L'ordre des éléments de la liste n'a pas d'importance. Nous n'imposons pas de contrainte sur l'unicité des éléments dans la liste. Si un élément apparaît plusieurs fois dans la liste, cela ne change pas l'ensemble associé. Cependant, les fonctions que nous écrirons respecteront le fait que si l'entrée n'a pas de doublons, la sortie non plus. Si en revanche l'entrée contient des doublons, la sortie est aussi autorisée à contenir des doublons.