Dans ce TP nous allons nous intéresser aux listes en Prolog. Cette fois il n'y a ni roi ni prisonnier, ni princesse, et heureusement pas de tigre. Je vous laisse avec la froideur des objets formels, mais l'informaticien qui sommeille en vous ne sera pas déçu.
Les listes peuvent être défines de plusieurs façons différentes. La plus simple consiste à émumérer les éléments de la liste un par un. Par exemple :
[a, 42,f(3,a), [3, a]]
Comme vous pouvez le voir, une liste peut contenir des éléments de types différents, et elle peut contenir de tout : constantes, nombres, prédicats, listes, etc.
La deuxième notation est plus structurelle et permet de réaliser des inductions :
[X | L]
où
X
est la tête de la liste (premier élément) et
L
la queue de la liste (liste contenant tous les éléments sauf le premier).
Opérations de base sur les listes
Nous allons commencer par écrire des fonctions usuelles sur les listes. Mettez à profit la structure inductive des listes, démontez les et remontez les comme il faut pour obtenir le résultat souhaité. Je vous conseille fortement de sortir un stylo (peu importe la couleur) une feuille de papier (peu importe s'il y a des carreaux) et de faire des schémas.
Définissez le prédicat
longueur/2
qui calcule la longueur d'une liste.
Exemple
?- longueur([1, 2, 3], A).
A = 3.
Définissez le prédicat
somme/2
qui calcule la somme des éléments d'une liste.
Exemple
?- somme([1,2,3,4], X).
X = 10.
Définissez le prédicat
membre/2
qui retourne
true
si un élément appartient à une liste une liste.
Exemple
?- membre(2, [1, 2, 3, 4]).
true.
?- membre(5, [1, 2, 3, 4]).
false.
Définissez le prédicat
ajoute_en_tete/3
qui ajoute un élément en tête de liste .
Exemple
?- ajoute_en_tete(1, [2, 3, 4], L).
L = [1, 2, 3, 4].
Définissez le prédicat
ajoute_en_queue/3
qui ajoute un élément en queue de liste .
Exemple
?- ajoute_en_queue(4, [1, 2, 3], L).
L = [1, 2, 3, 4].
Pour la question suivante, nous allons utiliser la propriété de réversibilité de Prolog.
Utilisez
ajoute_en_tete
pour définir le prédicat
extraire_tete/3
qui retourne la tête et la queue d'une liste.
Exemple
?- extraire_tete([1, 2, 3, 4], X, L).
X = 1,
L = [2, 3, 4].
Définissez le prédicat
concatene/3
qui concatène deux listes.
Exemple
?- concatene([1, 2, 3], [4, 5, 6], L).
L = [1, 2, 3, 4, 5, 6].
Définissez le prédicat
retourne/3
qui retourne les éléments d'une liste. Utilisez un accumulateur sous la forme d'un paramètre que vous initialiserez à
[]
.
Exemple
?- retourne([1, 2, 3], [], A).
A = [3, 2, 1].
Tris de listes
Comme on vous l'a déjà expliqué assez souvent, les tris de listes sont des opérations courantes. En plus ça fait des TP très intéressants. On va donc implémenter quelques tris.
Tri par insertion
Commençons par le commencement : le tri par insertion. Ce tri utilise une fonction qui insère un élément à la bonne place dans une liste triée. L'algorithme principal se contente donc juste d'insérer les éléments un par un à l'aide de la fonction précédente.
Définissez le prédicat
insert_trie/3
qui insère un élément dans une liste à la bonne place.
Exemple
?- insert_trie(3, [1, 2, 4, 5], L).
L = [1, 2, 3, 4, 5].
Définissez le prédicat
tri_insert/2
qui trie une liste en utilisant le prédicat de la question précédente.
Exemple
?- tri_insert([5,2,4,3,1], L).
L = [1, 2, 3, 4, 5].
Essayons maintenant d'implémenter le tri fusion. Pour rappel, ce tri utilise la stratégie « diviser pour régner » : la liste est divisée en deux parties égales, les deux parties sont triées récursivement, puis fusionnées en conservant l'ordre des éléments.
Définissez le prédicat
divise/3
qui divise une liste en deux parties égales (à un élément près). L'exemple suivant donne une idée de stratégie. Si vous songez à compter les éléments de la liste, ce n'est pas sérieux.
Exemple
?- divise([1,2,3,4,5], L, L2).
L = [1, 3, 5],
L2 = [2, 4].
Définissez le prédicat
fusion/3
qui fusionne deux listes, en conservant l'ordre des éléments.
Exemple
?- fusion([1,3,4], [2,5], L).
L = [1, 2, 3, 4, 5].
Définissez le prédicat
tri_fusion/2
qui trie une liste avec l'algorithme de tri fusion. Bien entendu, réutilisez le résultat des questions prcédentes.
Exemple
?- tri_fusion([5,2,4,3,1], L).
L = [1, 2, 3, 4, 5].
Je vous sens impatients d'essayer le tri rapide. Votre vœu est exaucé. Je vous rappelle cependant le principe du tri rapide. On choisit un pivot dans la liste (par exemple le premier élément). Nous créons ensuite à partir de ce pivot et du reste de la liste deux nouvelle listes. La première contient les éléments plus petits que le pivot et la seconde les éléments plus grands que le pivot. Il suffit ensuite de trier ces deux listes récursivement, et de concaténer le tout (sous-listes triées et pivot) pour obtenir la liste triée.
Définissez le prédicat
balance/4
qui étant donné un élément et une liste produit deux listes, l'une contenant les élément plus grands et l'autre contenant les éléments plus petits.
Exemple
?- balance(3, [1, 2, 3, 4, 5], L1, L2).
L1 = [1, 2],
L2 = [3, 4, 5].
Utilisez le prédicat précédent pour définir le prédicat
tri_rapide/2
qui trie une liste à l'aide de l'algorithme de tri rapide. Vous pouvez utiliser le prédicat
concatene/2
défini précédemment.
Exemple
?- tri_rapide([5,2,4,3,1], L).
L = [1, 2, 3, 4, 5].
Opérations de base sur les ensembles
Nous allons maintenant utiliser des listes pour coder des ensembles. Je vous rappelle que dans un ensemble, un élément ne peut appartenir au plus qu'une seule fois.
Définissez le prédicat
est_vide/1
qui retourne vrai si et seulement si l'ensemble passé en argument est vide.
Exemple
?- est_vide([]).
true.
?- est_vide([1]).
false.
Définissez le prédicat
ajoute_ensemble/3
qui ajoute un élément à un ensemble. L'élément n'est ajouté que s'il n'est pas déjà dans l'ensemble.
Exemple
?- ajoute_ensemble(2, [1, 2, 3], L).
L = [1, 2, 3].
?- ajoute_ensemble(4, [1, 2, 3], L).
L = [1, 2, 3, 4].
Définissez le prédicat
sous_ensemble/2
qui retourne vrai si et seulement si le premier ensemble est un sous-ensemble du second.
Exemple
?- sous_ensemble([4,2], [1,2,3,4]).
true.
?- sous_ensemble([4,2,5], [1,2,3,4]).
false.
Définissez le prédicat
union/3
qui retourne l'union de deux ensembles.
Exemple
?- union([1,3,2], [2,3,4], L).
L = [1, 2, 3, 4].
Définissez le prédicat
intersect/3
qui retourne l'intersection de deux ensembles.
Exemple
?- intersect([1,3,2], [2,3,4], L).
L = [3, 2].
?- intersect([1,5], [2,3,4], L).
L = [].
Définissez le prédicat
diff/3
qui retourne la différence de deux ensembles.
Exemple
?- diff([1,3,2,5], [2,3,4], L).
L = [1, 5].