findall, bagof et setof

pcaboche

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)

- Titre : findall, bagof et setof

- Auteur : pcaboche

- Parution : 11 avril 2006

- Mise à jour : 16 août 2006

- Licence : Copyright ® 2006 pcaboche. 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.

Sommaire

- 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 :

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