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: [].

 
Sélectionnez
habite(jean, belfort).
habite(lucie, paris).
habite(christian, toulouse).
habite(adeline, paris).
habite(nicolas, paris).
Execution
Sélectionnez
| ?- 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 :

 
Sélectionnez
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 :

  1. les variables A et B sont unifiées. On a 3 solutions: une pour chaque couple (A,B) disctinct.
  2. seule le variable B est unifiée, la variable A restant libre. On a 2 solutions: une par valeur de B différente.
  3. les variables A et B ne sont pas unifiées. On n'a alors plus qu'une solution.
  4. é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).