Les listes en Prolog


précédentsommairesuivant

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

3. How-to

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

4.1. 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




4.2. 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
  • Enumé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.


4.3. 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).

Applanit 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 stoque 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
 




4.4. 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 cote-à -cote 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




4.5. Enumé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 
    )  
  ),    
  …

A ce sujet, voir aussi le prédicat .


Les prédicats et permettent en plus de connaïtre 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

4.6. 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 élements à 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.




4.7. 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édicat 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 suppé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.




4.8. 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 appellé, c'est <(5,Y) avec Y appartenant à List1 (donc List2 est bien unifiée avec les nombres supérieurs à 5 contenus dans List1).



4.9. 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





4.10. 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.




4.11. 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 .





précédentsommairesuivant

  

Copyright © 2006 Pierre Caboche. Aucune reproduction, même partielle, ne peut être faite de ce site et 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.