findall, bagof et setofDate de publication : 11 Avril 2006 , Date de mise à jour : 16 Août 2006
Par
pcaboche (autres articles)
Cet article présente les prédicats findall/3, bagof/3 et setof/3 du Prolog
(explications plus détaillées que dans la documentation officielle)
1. Documentation
Explication de base
L'opérateur ^
Tableau récapitulatif
2. Utilisation
1. Documentation
Explication de base
findall(+Motif, +But, -Liste)
findall/3 créé une liste des instanciations de
Motif par retours arrières sur But et unifie
le résultat dans Liste. Si le But n'a pas
de solution, findall retournera la liste vide: [].
|
habite(jean, belfort).
habite(lucie, paris).
habite(christian, toulouse).
habite(adeline, paris).
habite(nicolas, paris). |
| Execution | | ?- findall(X, habite(X,paris), R).
R = [lucie,adeline,nicolas] ? |
bagof(+Motif, +But, -Liste)
Se comporte comme findall/3, à la différence que:
- bagof/3 échoue si But n'a pas de solution
- a un comportement différent concernant les variables
libres de Motif (voir plus loin)
|
setof(+Motif, +But, -Liste)
Se comporte comme bagof/3, à la différence que:
- il y a suppression des doublons
- les résultats sont triés en utilisant le prédicat sort/2
|
L'opérateur ^
 |
L'opérateur ^ permet de spécifier dans bagof/3 (et setof/3)
les variables qui doivent rester libres (ne pas être unifiées).
|
bagof(+Motif, +But, -Liste)
Si But a des variables libres qui n'apparaissent
pas dans Motif, bagof/3 unifiera ces variables
libres avec les différentes valeurs possibles dans
But (retournant ainsi plusieurs solutions).
L'opérateur Var^But permet de spécifier à bagof que
la variable Var ne doit pas être unifiée avec les
différentes valeurs retournée par But.
bagof/3 et setof/3 ont le même comportement
concernant l'unification des variables libres.
|
findall(+Motif, +But, -Liste)
A exactement le même comportement que bagof/3, avec toutes les
variables libres de But utilisées avec l'opérateur ^ .
|
Pour bien comprendre ce principe d'unification ainsi que les
différences entre bagof/3 et findall/3, nous allons partir de ce programme :
foo(a, b, c).
foo(a, b, d).
foo(b, c, e).
foo(b, c, f).
foo(c, c, g). |
Exécutions :
| Cas 1 |
Cas 2 |
Cas 3 |
Cas 4 |
|?- bagof(C, foo(A,B,C), L).
C = _G328
A = a
B = b
L = [c, d] ;
C = _G328
A = b
B = c
L = [e, f] ;
C = _G328
A = c
B = c
L = [g] ;
No
|
|?- bagof(C, A^foo(A,B,C), L).
C = _G340
A = _G338
B = b
L = [c, d] ;
C = _G340
A = _G338
B = c
L = [e, f, g] ;
No
|
|?- bagof(C, A^B^foo(A,B,C), L).
C = _G352
A = _G350
B = _G351
L = [c, d, e, f, g] ;
No
|
|?- findall(C, foo(A,B,C), L).
C = _G352
A = _G350
B = _G351
L = [c, d, e, f, g] ;
No
|
Voilà ce qui se passe dans chaque cas :
- les variables A et B sont unifiées. On a 3 solutions:
une pour chaque couple (A,B) disctinct.
- seule le variable B est unifiée, la variable A restant libre.
On a 2 solutions: une par valeur de B différente.
- les variables A et B ne sont pas unifiées. On n'a alors
plus qu'une solution.
- équivalent au cas précédent
|
Plus on utilise l'opérateur ^, moins bagof/3 (ou setof/3)
retournera de solutions.
|
Tableau récapitulatif
| |
findall |
bagof |
setof |
| Si pas de solution |
Retourne [] |
Echoue |
Echoue |
| Unification des variables libres
dans But |
Jamais |
Avec l'opérateur ^ |
Avec l'opérateur ^ |
| Suppression des doublons |
Non |
Non |
Oui |
| Liste ordonnée |
Non |
Non |
Oui |
2. Utilisation
Pour une illustration concrète du prédicat findall/3 (et par extension
des prédicats bagof/3 et setof/3), se reporter à l'article suivant:
Pattern 4: Génération de listes
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 keysort/2, 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).
 
|
