IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Les listes en Prolog

Cet article présente les listes en Prolog : principes de base et prédicats prédéfinis permettant la manipulation de listes. ♪

Article lu   fois.

L'auteur

Profil ProSite personnel

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

Introduction

Le but de cet article est de fournir une ressource concernant l'utilisation des listes en Prolog. Cette ressource vient compléter les documentations existantes sur le sujet.

Nous commencerons par présenter les notions de base concernant les listes en Prolog. Ensuite, nous présenterons les prédicats existants concernant le traitement des listes en Prolog. Enfin, nous conclurons sur une discussion plus générale sur l'utilisation des listes en Prolog.

Une grande importance a été accordée aux prédicats servant à la manipulation des listes en Prolog, et ce pour plusieurs raisons :

  1. Il est inutile de réinventer la roue. De nombreux prédicats ont été implémentés en standard afin de faciliter le travail du programmeur ;
  2. Les prédicats implémentés en standard sont très bien testés, bien optimisés, et offrent souvent plus de fonctionnalités que les prédicats implémentés par le programmeur ;
  3. Les prédicats sur les listes sont parfois implémentés à bas niveau, directement en C, ce qui leur confère d'excellentes performances. C'est le cas par exemple des prédicats permettant le tri.

Il existe de nombreuses implémentations de Prolog différentes. C'est swi-prolog qui a été choisie pour écrire cet article. Pourquoi ? Parce que swi-prolog est entièrement gratuite et propose de nombreuses fonctionnalités (en témoignent les nombreux prédicats servant au traitement des listes). Les prédicats décrits dans cet article sont ceux qu'on trouve dans swi-prolog.

Si vous utilisez une autre implémentation de Prolog, il est fort probable qu'elle dispose de sa propre implémentation des prédicats décrits dans cet article (si ce n'est pas le cas, permettez-moi d'émettre de sérieux doutes quant à la qualité de cette implémentation étant donné qu'un produit gratuit comme swi-prolog les fournit en standard). Sinon, swi-prolog étant diffusé sous licence LGPL, vous pouvez récupérer et utiliser les fichiers implémentant les différents prédicats décrits dans cet article (fichier « lists.pl » du répertoire « library »).

Comme il a été dit plus haut, les différents prédicats portant sur les listes sont implémentés en standard afin de faciliter le travail du programmeur. Ces prédicats étant nombreux, la difficulté est alors de trouver celui dont on a besoin, ou plus simplement de savoir s'il existe avant de chercher à l'implémenter soi-même. Pour faciliter cette tâche, j'ai effectué plusieurs classements :

  • par ordre alphabétique ;
  • par catégorie ;
  • sous forme de « How-to » : on accède au prédicat qui convient à partir d'une liste de questions fréquemment posées, du genre : « Comment trier une liste en fonction d'un ou plusieurs critères ? »

Voici donc le plan pour cet article :

  • Section 1 : Généralités sur les listes en Prolog
    Présente les concepts de base sur les listes

  • Section 2, 3, 4 : Prédicats sur les listes en swi-prolog
    Les prédicats servant au traitement de listes en Prolog

  • Section 5 : Exemple de prédicat sur les listes
    Un exemple servant à montrer comment utiliser les prédicats sur les listes

  • Section 6 : Listes et programmation en Prolog
    Discussion sur l'usage des listes en Prolog

I. Généralités

En Prolog, on ne connait que deux choses d'une liste :

  • son premier élément (la tête, ou head) ;
  • le reste de la liste (la queue, ou tail).

Le parcours d'une liste se fait de manière récursive sur la queue.

La liste vide se note : [].

Une liste constituée d'au moins un élément se note [T|Q].
Ici, T représente la tête et Q représente la queue. C'est aussi grâce à [T|Q] que l'on ajoute un élément en début de liste (par unification).

Les différents éléments d'une liste sont séparés par des virgules. Exemple: [1, 2, 3, 4, 5, 6, 7].

Ainsi: [1, 2, 3 | Q] représente une liste dont les premiers éléments sont 1, 2, 3 et le reste de la liste est unifié avec la variable Q.

Voilà , c'est à peu près tout ce qu'il est nécessaire de savoir pour parcourir des listes en Prolog. Contrairement à d'autres langages, on n'a pas besoin d'avoir recours à des itérateurs pour parcourir une liste (comme c'est le cas en C++ ou en Java, et je ne parle même pas du C !). En Prolog, tout est déjà prévu pour cela dans le langage.

Ceux qui connaissent Caml ou tout autre langage fonctionnel seront avantagés, car le parcours d'une liste est très similaire en Prolog. Pour les autres, ils trouveront un exemple de prédicat utilisant les listes un peu plus loin dans ce tutoriel.

Les prochaines sections de ce tutoriel portent sur les prédicats servant à la manipulation de listes en Prolog (et plus particulièrement en swi-prolog).

II. Prédicats sur les listes (par ordre alphabétique)

append/3
bagof/3
findall/3
flatten/2
intersection/3
is_list/1 *
is_set/1
keysort/2 *
last/2
length/2 *
list_to_set/2
maplist/2
maplist/3
maplist/4
member/2
memberchk/2 *
merge/3 *
merge_set/3 *
msort/2 *
nextto/3
nth0/3
nth1/3
numlist/3
permutation/2
predsort/3 *
reverse/2
select/3
setof/3
sort/2 *
sublist/3
subset/2
subtract/3
sumlist/2
union/3

III. How-to

Comment :

Accéder au i-ème élément d'une liste ?







Énumérer tous les éléments d'une liste ?







Supprimer tous les doublons d'une liste ?

Trier une liste ?





IV. Prédicats sur les listes (par catégorie)

IV-A. Propriétés de liste

 

is_list/1 *

(implémenté à bas niveau, optimisé pour la vitesse)


 
Sélectionnez
is_list(+Terme).

Réussit si Terme est une liste.

is_set/1

 
Sélectionnez
is_set(+Terme).

Réussit si Terme est un set, c'est-à-dire une liste ne comportant pas de doublons.

length/2 *

(implémenté à bas niveau, optimisé pour la vitesse)


 
Sélectionnez
length(+Liste, +Int).

Unifie Int avec la longueur de la liste.

Exemple
Sélectionnez
| ?- length([1,2,3,4,5], Long).
 
Long = 5 
 
Yes

Peut également servir à créer une liste de longueur Int ne contenant que des variables libres.

Exemple
Sélectionnez
| ?- length(L, 3).
 
L = [_G316, _G319, _G322] 
 
Yes

IV-B. Accès aux éléments

 

nth0/3

 
Sélectionnez
nth0(?Ind, ?List, ?Elem).

Réussit si l'élément d'indice Ind de la liste List s'unifie avec Elem. Les indices commencent à 0.

nth0/3 sert généralement à récupérer l'élément d'indice Ind dans la liste List.

nth0/3 peut servir à :

  • récupérer l'élément d'indice Ind :
Exemple
Sélectionnez
| ?-  nth0(2, [3,1,8,6,9], E).
 
E = 8
  • vérifier si l'élément d'indice Ind est Elem :
Exemple
Sélectionnez
| ?-  nth0(2, [3,1,8,6,9], 8).
 
Yes
  • énumérer les éléments d'une liste avec leurs indices :
Exemple
Sélectionnez
| ?- nth0(I, [3,15,8], E).
 
I = 0
E = 3 ;
 
I = 1
E = 15 ;
 
I = 2
E = 8 ;
 
No
  • insérer l'élément Elem à l'indice Ind dans la liste List si l'élément à l'indice Ind est une variable libre :
Exemple
Sélectionnez
| ?- length(L,5), nth0(1, L, 8888).
 
L = [_G444, 8888, _G450, _G453, _G456] 
 
Yes

nth1/3

 
Sélectionnez
nth1(?Ind, ?List, ?Elem).

Pareil que nth0, mais avec les indices commençant à 1.

last/2

 
Sélectionnez
last(?List, ?Elem).

Unifie Elem avec le dernier élément de la liste List.

IV-C. Manipulations sur les listes

 

numlist/3

 
Sélectionnez
numlist(+Min, +Max, -List).

Unifie List avec la liste des entiers compris.

Préconditions :

  • Min <= Max (sinon échec) ;
  • Min et Max sont des entiers (sinon échec).

Ce prédicat est très utile pour créer des intervalles de valeurs entières, pour symboliser le domaine d'une variable, par exemple.

Exemple
Sélectionnez
| ?- numlist(2,8, Domaine).
 
Domaine = [2, 3, 4, 5, 6, 7, 8]

Si l'usage d'une liste n'est pas justifié, préférer l'usage de between/3.

reverse/2

 
Sélectionnez
reverse(+List1, -List2).

Inverse l'ordre des éléments de List1 et unifie le résultat dans List2.

Exemple
Sélectionnez
| ?- reverse([1,2,3,4,5], L2).
 
L2 = [5, 4, 3, 2, 1]

append/3

 
Sélectionnez
append(?List1, ?List2, ?List3).

Réussit si List3 est la concaténation de List1 et List2.

append/3 sert principalement pour ajouter le contenu de List2 à la suite de List1 et unifier le résultat dans List3.

Exemple 1
Sélectionnez
| ?- append([1,2,3], [4,5,6], L3).
 
L3 = [1, 2, 3, 4, 5, 6]

Cependant, append/3 ne se limite pas à cet usage et peut unifier indifféremment les variables List1, List2 et List3 :

Exemple 2
Sélectionnez
| ?- append(L1, L2, [1,2,3]).
 
L1 = []
L2 = [1, 2, 3] ;
 
L1 = [1]
L2 = [2, 3] ;
 
L1 = [1, 2]
L2 = [3] ;
 
L1 = [1, 2, 3]
L2 = [] ;
 
No

flatten/2

 
Sélectionnez
flatten(+List1, -List2).

Aplanit List1 et unifie le résultat dans List2. List1 peut contenir de nombreuses listes imbriquées récursivement. flatten/2 extrait tous les éléments contenus dans List1 et stocke le résultat dans une liste « plane » (à une seule dimension).

Exemple
Sélectionnez
| ?- flatten([[1,[2],3], [[4,5],[6,7]]], Flat).
 
Flat = [1, 2, 3, 4, 5, 6, 7]

permutation/2

 
Sélectionnez
permutation(?List1, ?List2).

Permet de vérifier si List1 est une permutation de List2 ou inversement.

Exemple
Sélectionnez
| ?- permutation([1,2,3,4,5], [5,3,1,4,2]).
 
Yes

Permet également d'énumérer toutes les permutations possibles de List1 ou List2.

Exemple
Sélectionnez
| ?- permutation([1,2,3], Perm).
 
Perm = [1, 2, 3] ;
 
Perm = [2, 1, 3] ;
 
Perm = [2, 3, 1] ;
 
Perm = [1, 3, 2] ;
 
Perm = [3, 1, 2] ;
 
Perm = [3, 2, 1] ;
 
No

IV-D. Test d'appartenance

memberchk/2 *

(implémenté à bas niveau, optimisé pour la vitesse)


 
Sélectionnez
memberchk(?Elem, ?List)

Permet de vérifier si Elem appartient à List. memberchk/2 parcours List et s'arrête au premier élément qui s'unifie avec Elem.

memberchk/2 se comporte comme, mais sans point de choix :

Exemple
Sélectionnez
memberchk(Elem, List) :-
  member(Elem, List), !.

memberchk/2 retournera au maximum 1 solution (la première), alors que memberchk/2 retournera autant de solutions qu'il y a d'éléments qui s'unifient avec Elem.

nextto/3

 
Sélectionnez
nextto(?X, ?Y, ?List)

Réussit si X et Y se suivent dans List.

Permet :

  • de vérifier si X et Y sont côte à côte dans List ;
  • de déterminer quel élément suit X (ou précède Y) ;
  • d'énumérer les éléments X et Y qui se suivent dans List.
Exemple
Sélectionnez
| ?- nextto(3, 4, [1,2,3,4,5]).
 
Yes
 
| ?- nextto(X, Y, [1,2,3]).
 
X = 1
Y = 2 ;
 
X = 2
Y = 3 ;
 
No
 
| ?- nextto(a, Y, [1,a,2,3,a,5,a,9,10]).
 
 Y = 2 ;
 
 Y = 5 ;
 
 Y = 9 ;
 
No

IV-E. Énumération d'éléments

 

member/2

 
Sélectionnez
member(?Elem, ?List).

Réussit si Elem avec un élément de la liste List.

Utilisé principalement pour énumérer les membres de la liste.

Exemple
Sélectionnez
| ?- member(X, [1,2,3,5,8]).
 
X = 1 ;
 
X = 2 ;
 
X = 3 ;
 
X = 5 ;
 
X = 8 ;
 
No

member/2 peut être utilisé avec forall/2 pour appliquer des prédicats sur chacun des éléments de la liste (exemple 1) ou pour vérifier que tous les éléments d'une liste vérifient certaines propriétés (exemple 2) :

Exemple 1
Sélectionnez
  …
  forall( 
    member(Var, Liste), 
    (
      write(Var), nl
    )
  ),
  …
Exemple 2
Sélectionnez
  …
  forall( 
    member(Var, Liste),
    (
      5 < Var , Var < 10 
    )  
  ),    
  …

À ce sujet, voir aussi le prédicat.

Les prédicats et permettent en plus de connaitre l'indice où se trouve l'élément de la liste.
Le prédicat, quant à lui, retourne la liste privée de l'élément.

select/3

 
Sélectionnez
select(?Elem, ?List, ?Rest).

Se comporte comme , sauf qu'en plus il unifie Rest avec la liste List privée de l'élément Elem.

Exemple
Sélectionnez
?- select(E, [1,2,3,4], R).
 
E = 1
R = [2, 3, 4] ;
 
E = 2
R = [1, 3, 4] ;
 
E = 3
R = [1, 2, 4] ;
 
E = 4
R = [1, 2, 3] ;
 
No

Il permet en outre d'énumérer les insertions possibles dans une liste :

Exemple
Sélectionnez
| ?-  select(99, L, [1,2,3,4]).
 
L = [99, 1, 2, 3, 4] ;
 
L = [1, 99, 2, 3, 4] ;
 
L = [1, 2, 99, 3, 4] ;
 
L = [1, 2, 3, 99, 4] ;
 
L = [1, 2, 3, 4, 99] ;
 
No

IV-F. Tri

 

msort/2 *

(implémenté à bas niveau, optimisé pour la vitesse)


 
Sélectionnez
msort(+List, -Triee).

Trie la liste List et unifie le résultat dans Triee.

Le tri est très rapide, car implémenté en interne en C. L'algorithme utilisé est le tri fusion naturel (rapide et stable). Pour ordonner les éléments, msort/2 se base sur l'ordre standard des termes défini dans Prolog.

sort/2 *

(implémenté à bas niveau, optimisé pour la vitesse)


 
Sélectionnez
sort(+List, -Triee).

Se comporte comme msort/2, mais supprime les doublons.

keysort/2 *

(implémenté à bas niveau, optimisé pour la vitesse)


 
Sélectionnez
keysort(+List, -Triee).

Le prédicat keysort/2 permet de trier sur un ou plusieurs critères. Les éléments de List sont de la forme Clef-Valeur. Le tri s'effectue sur les clefs et non sur les valeurs.

Il est possible d'utiliser plusieurs critères pour le tri, pour ce faire il suffit d'ajouter des clefs
(ex. : Clef1-Clef2-Clef3-…-ClefN-Valeur).

Caractéristiques de keysort/2 :

  • keysort/2 conserve l'ordre des éléments de même clef (on dit que le tri est « stable ») ;
  • keysort/2 ne supprime pas les doublons ;
  • keysort/2 est rapide, car implémenté en interne.

En effet, keysort/2 est basé sur un tri fusion naturel (rapide et stable) implémenté en C.

Exemple
Sélectionnez
| ?- keysort( [5-3-d, 3-4-c, 5-3-b, 5-1-a], L).
 
L = [3-4-c, 5-1-a, 5-3-d, 5-3-b]

predsort/3 *

(implémenté à bas niveau, optimisé pour la vitesse)


 
Sélectionnez
predsort(+Pred, +List, -Triee).

Se comporte comme , mais utilise le prédicat Pred pour déterminer l'ordre.

Le prédicat Pred est de la forme Pred(-Delta, +E1, +E2), où E1 et E2 sont les éléments à comparer et Delta peut être l'un des trois symboles suivants : <, > ou =.

Si utilisé avec le prédicat compare/3, predsort/2 se comporte comme :

predsort/3 supprime les doublons.

IV-G. Maplist

Les prédicats maplist appliquent un prédicat sur tous les membres d'une liste ou jusqu'à ce que le prédicat échoue.

Pour ce faire, des arguments sont ajoutés au prédicat Pred grâce au prédicat call/[2..]. Ainsi, pour les prédicats d'arité supérieure à l'arité requise par maplist, les premiers arguments devront être unifiés.

Exemple
Sélectionnez
| ?- maplist(plus(8), [0, 1, 2], L).
 
X = [8, 9, 10]
 

maplist/2

 
Sélectionnez
maplist(+Pred, +List).

Applique le prédicat Pred à tous les membres d'une liste ou jusqu'à ce que Pred échoue, auquel cas le prédicat maplist/2 échoue.

Ce prédicat permet de vérifier que tous les éléments d'une liste vérifient certaines propriétés (grâce au prédicat Pred).

Voici par exemple comment vérifier qu'une liste est composée uniquement d'entiers (grâce au prédicat integer/1) :

Exemple
Sélectionnez
| ?- maplist( integer, [15,8,5,6,9,4] ).
 
Yes

Et voici comment vérifier qu'une liste est composée uniquement de nombres supérieurs à 3 (grâce au prédicat </2) :

Exemple
Sélectionnez
| ?- maplist( <(3), [15,8,5,6,9,4] ).
 
Yes

maplist/3

 
Sélectionnez
maplist(+Pred, ?List1, ?List2).

Appelle le prédicat Pred (d'arité 2 au minimum) avec comme arguments les membres de List1 et List2.

Ce prédicat sert à appliquer le prédicat Pred sur les membres d'une liste et à mettre le résultat dans l'autre.

Exemple :

Exemple
Sélectionnez
| ?- maplist(plus(8), [0, 1, 2], L).
 
X = [8, 9, 10]

Ce prédicat est comparable à la fonction map du Caml.

maplist/4

 
Sélectionnez
maplist(+Pred, ?List1, ?List2, ?List3).

Appelle le prédicat Pred (d'arité 3 au minimum) avec comme arguments les membres de List1, List2 et List2.

Ce prédicat sert à appliquer le prédicat Pred sur les membres de 2 listes et à mettre le résultat dans une troisième.

Exemple :

Exemple
Sélectionnez
| ?- maplist(plus, [0, 1, 2], [4, 8, 16], L).
 
X = [4, 9, 18]

Ce prédicat est comparable à la fonction map2 du Caml.

IV-H. Extraction de données

sublist/3

 
Sélectionnez
sublist(+Pred, +List1, ?List2).

Extrait tous les éléments de List1 pour lesquels Pred réussit, unifie le résultat dans List2.

Exemple: voici comment extraire d'une liste tous les éléments supérieurs à 5 :

Exemple
Sélectionnez
| ?- sublist( <(5), [15,2,8,5,6,9,4], L ).
 
L = [15, 8, 6, 9]

Explications sur le fonctionnement :

Dans l'exemple précédent, on utilise le prédicat </2.

Exemple:

Exemple
Sélectionnez
| ?- <(1,5).
 
Yes

<(X,Y) est équivalent à X<Y.

On fixe le premier argument de </2 à 5 et c'est sublist qui ajoute le deuxième argument grâce au prédicat call/[2..]. Donc en fait, ce qui est appelé, c'est <(5,Y) avec Y appartenant à List1 (donc List2 est bien unifiée avec les nombres supérieurs à 5 contenus dans List1).

IV-I. Liste les solutions d'un prédicat

 

findall/3

Les prédicats findall/3, bagof/3 et setof/3 permettent de faire la liste des solutions d'un prédicat.

Ces prédicats peuvent être utiles pour dresser une liste de solutions possibles afin de trier ces solutions en fonction de certains critères (grâce au prédicat , par exemple).

Ces prédicats peuvent également être utiles pour effectuer des tests unitaires en Prolog (on dresse la liste des solutions d'un prédicat grâce au prédicat findall/2, puis on compare cette liste avec la liste des solutions attendues).

Les prédicats findall/3, bagof/3 et setof/3 ont fait l'objet d'un autre article qui met en avant les différences entre ces prédicats et explique leur fonctionnement : findall, bagof et setof

bagof/3

setof/3

IV-J. Opérations sur les sets

Un set est une liste ne contenant aucun doublon.

is_set/1

 
Sélectionnez
is_set(+Terme).

Réussit si Terme est un set, c'est-à-dire une liste ne comportant pas de doublons.

list_to_set/2

 
Sélectionnez
list_to_set(+List, -Set).

Transforme une liste en set. En d'autres termes, supprime tous les doublons de List et unifie le résultat dans Set.

list_to_set/2 conserve l'ordre des éléments (si la liste contient des doublons, seul le premier est gardé).

subset/2

 
Sélectionnez
subset(+Subset, +Set).

Réussit si tous les éléments de Subset appartiennent à Set.

Note: subset/2 ne vérifie pas que Subset et Set ne contiennent pas de doublons, et ce pour de nombreuses raisons (y compris de performance).

union/3

 
Sélectionnez
union(+Set1, +Set2, -Set3).

Unifie Set3 avec l'union de Set1 et Set2. Les listes n'ont pas besoin d'être ordonnées.

Note: pour des raisons de performance, aucune vérification n'est faite pour garantir que Set1 et Set2 ne contiennent pas de doublons. Si Set1 et Set2 ne contiennent pas de doublons, Set3 ne contiendra pas de doublon. Si Set1 et Set2 contiennent des doublons, Set3 est susceptible de contenir des doublons. Utilisez pour supprimer les doublons.

intersection/3

 
Sélectionnez
intersection(+Set1, +Set2, -Set3).

Unifie Set3 avec l'intersection de Set1 et Set2. Les listes n'ont pas besoin d'être ordonnées.

Note: pour des raisons de performance, aucune vérification n'est faite pour garantir que Set1 et Set2 ne contiennent pas de doublons. Si Set1 et Set2 ne contiennent pas de doublons, Set3 ne contiendra pas de doublon. Si Set1 et Set2 contiennent des doublons, Set3 est susceptible de contenir des doublons. Utilisez pour supprimer les doublons.

subtract/3

 
Sélectionnez
subtract(+Set, +Delete, -Rest).

Supprime de Set tous les éléments contenus dans Delete et unifie le résultat dans Rest.

Note: pour des raisons de performance, aucune vérification n'est faite pour garantir que Set et Set2 ne contient pas de doublons.

IV-K. Divers

 

sumlist/2

 
Sélectionnez
sumlist(+List, -Sum).

Unifie Sum avec la somme de tous les éléments de List.

Précondition :

  • List est une liste de nombres (sinon, échoue)
Exemple
Sélectionnez
| ?- sumlist([2,4,6,8,10], Sum).
 
Sum = 30

merge/3 *

(implémenté à bas niveau, optimisé pour la vitesse)


 
Sélectionnez
merge(+List1, +List2, -List3).

List1 et List2 sont des listes triées. merge/3 fusionne List1 et List2 pour en faire en une liste triée et unifie le résultat dans List3. merge/3 ne supprime pas les doublons.

Précondition :

  • List1 et List2 sont triées (sinon, comportement aléatoire)

Le prédicat merge/3 est utilisé par le prédicat.

merge_set/3 *

(implémenté à bas niveau, optimisé pour la vitesse)


 
Sélectionnez
merge_set(+Set1, +Set2, -Set3).

Set1 et Set2 sont des listes triées, supposées sans doublons. merge_set/3 fusionne Set1 et Set2 pour en faire en une liste triée sans doublons et unifie le résultat dans Set3.

Préconditions :

  • Set1 et Set2 sont triés (sinon, comportement aléatoire) ;
  • Set1 et Set2 ne contiennent pas de doublons.

Comportement :

  • Si Set1 et Set2 ne contiennent pas de doublons, alors Set3 ne contiendra pas de doublons ;
  • Si Set1 ou Set2 contiennent des doublons, alors Set3 contiendra des doublons.

Le prédicat merge_set/3 est utilisé par le prédicat.

V. Exemple

Parmi les prédicats portant sur les listes il en manquait un permettant de mélanger une liste. Qu'à cela ne tienne ! Cela nous permettra de voir comment écrire un prédicat sur les listes en Prolog.

shuffle/2

Voici donc le prototype du prédicat shuffle/2 (que nous allons implémenter), et sa description :

 
Sélectionnez
shuffle(+List, -Shuffled).

Change l'ordre des éléments de List et unifie le résultat dans Shuffled (le mélange se fait aléatoirement).

Voici maintenant le code du prédicat shuffle/2 :

Code du prédicat shuffle/2
Sélectionnez
shuffle(List, Shuffled) :-
  length(List, Len),
  shuffle(Len, List, Shuffled).
 
 
shuffle(0, [], []) :- !.
 
shuffle(Len, List, [Elem|Tail]) :-
  RandInd is random(Len),
  nth0(RandInd, List, Elem),
  select(Elem, List, Rest),
  !,
  NewLen is Len - 1,
  shuffle(NewLen, Rest, Tail).

Fonctionnement
Dans shuffle/2, on invoque length/2 et on appelle shuffle/3.
Dans shuffle/3, on génère un indice RandInd entre 0 et la taille de la liste grâce à random/1. Avec nth0/3, on récupère la valeur située à l'indice RandInd, puis grâce à select/3 on extrait cette valeur ainsi que la liste privée de cette valeur (Rest).
On invoque ensuite shuffle/3 sur Rest (de longueur Len-1) jusqu'à obtenir une liste vide (dans ce cas, on s'arrête).
C'est en extrayant les éléments de cette façon que l'on obtient la liste mélangée.

Le prédicat shuffle/3 a été introduit dans un but d'effectuer une optimisation. En effet, on ne calcule la longueur de la liste qu'une seule fois (au début, dans shuffle/2), ce qui évite de la parcourir à chaque itération.

Maintenant, la partie ci-dessous pourrait être optimisée afin de ne parcourir la liste qu'une seule fois et pas deux :

 
Sélectionnez
  …
  nth0(RandInd, List, Elem),
  select(Elem, List, Rest),
  …

Cependant, cela nous obligerait à écrire un nouveau prédicat et nous prive de l'opportunité de vous montrer l'utilisation des prédicats nth0/3 et select/3 dans un exemple concret. Aussi, je vous laisse cette optimisation à titre d'exercice.

VI. Les listes et la programmation en Prolog (Conclusion)

Comme je l'ai dit dans les principes de base sur les listes (section 1), en Prolog, on ne connait que les premiers éléments d'une liste (la tête) et c'est de manière récursive qu'on accède au reste de la liste (la queue). On n'a pas d'accès direct aux éléments d'une liste et pour accéder au ième élément, on utilise les prédicats nth0/3 ou nth1/3 (programmés récursivement).

Tout cela est extrêmement long et couteux.

Aussi, autant que faire se peut, il faut garder à l'esprit qu'une liste est censée être parcourue séquentiellement et optimiser ses programmes en conséquence, afin d'éviter les allers-retours inutiles.

Maintenant, je souhaiterais attirer votre attention sur un deuxième point: la manipulation de listes requiert beaucoup de mémoire. En effet, en Prolog les manipulations de listes nécessitent souvent la création de nouvelles listes, ce qui peut rapidement engendrer un coût énorme en termes de mémoire, qui peut se traduire par l'arrêt du programme par manque de mémoire.

Dans certains cas, l'utilisation de listes est extrêmement utile, par exemple pour effectuer des tris. Cependant, dans d'autres cas, il est tout à fait possible d'exploiter certaines spécificités du langage Prolog pour se passer de listes. Par exemple, nous avons vu qu'il était possible d'effectuer des opérations sur les sets (union/3, intersection/3, subtract/3, etc.) or ces opérations sont également réalisables au moyen de prédicats, comme indiqué dans l'article Prolog et algèbre relationnelle.

Une question fondamentale en Prolog est: « Comment représenter le problème à résoudre? » De la réponse à cette question dépendra l'implémentation et donc les performances du programme.

Les programmeurs habitués à des langages comme C, Java ou autres ont tendance à se réfugier derrière les listes, car elles leur rappellent certaines structures de données existantes dans d'autres langages (les tableaux). Cependant, il existe d'énormes différences entre manipuler des tableaux en C et manipuler des listes en Prolog (pas d'accès direct, grande consommation de mémoire…). À l'inverse, Prolog offre des mécanismes qui n'ont aucun équivalent dans d'autres langages (bases de connaissance et de règles, retour sur trace, etc.) et qu'il faut apprendre à exploiter. Bref, pour faire du Prolog, il faut mettre de côté certaines habitudes issues d'autres langages.

En résumé, il est nécessaire de se rappeler que :

  1. Les listes ne sont pas le seul moyen pour stocker de l'information en Prolog ;
  2. Quand on a besoin d'utiliser des listes, il faut penser à exploiter les spécificités des listes (accès aux éléments par la tête de liste) ainsi que les prédicats mis à notre disposition pour nous faciliter le travail ;
  3. La quantité de mémoire nécessaire pour manipuler les listes ne doit pas être négligée.

Remerciements

Je tiens à remercier Trap D et Katyucha pour la relecture de cet article.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

Copyright © 2006 Pierre Caboche. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.