Programming in Prolog – Aggregates
Programming in Prolog
Aggregates
Romain Barnoud
Thanks to:
Dr Fariba Sadri
Claudia Schulz
From lists to individuals
Program
city(asia, [tokyo, seoul, beijing]).
city(europe, [berlin, amsterdam, paris, london]).
city(america, [new_york, vancouver]).
Queries
?- city(america, _List), member(City, _List).
City = new_york ;
City = vancouver ;
no
?- city(_Continent, _List), member(City, _List).
City = tokyo ;
City = seoul ;
…
City = vancouver ;
no
All cities in America
All cities in the world
From lists to individuals
Program
city(asia, [tokyo, seoul, beijing]).
city(europe, [berlin, amsterdam, paris, london]).
city(america, [new_york, vancouver]).
Queries
?- city(america, _List), member(City, _List).
City = new_york ;
City = vancouver ;
no
?- city(_Continent, _List), member(City, _List).
City = tokyo ;
City = seoul ;
…
City = vancouver ;
no
All cities in America
All cities in the world
From individuals to lists
Program
city(asia, tokyo).
city(asia, seoul).
city(asia, beijing).
city(europe, berlin).
city(europe, amsterdam).
city(europe, paris).
city(europe, london).
city(america, new_york).
city(america, vancouver).
How to get a list of the cities in
Europe? Or in the entire world?
Prolog has three built-in predicates
for this kind of purpose:
findall/3
bagof/3
setof/3
From individuals to lists
Program
city(asia, tokyo).
city(asia, seoul).
city(asia, beijing).
city(europe, berlin).
city(europe, amsterdam).
city(europe, paris).
city(europe, london).
city(america, new_york).
city(america, vancouver).
How to get a list of the cities in
Europe? Or in the entire world?
Prolog has three built-in predicates
for this kind of purpose:
findall/3
bagof/3
setof/3
findall/3
De�nition
findall(+T, +Goal, -List):
List is the list of all instances of T for which Goal succeeds.
findall/3
De�nition
findall(+T, +Goal, -List):
List is the list of all instances of T for which Goal succeeds.
Examples I
?- findall(City, city(europe, City), L).
L = [berlin, amsterdam, paris, london] ;
no
?- findall(City, city(Cont, City), L).
L = [tokyo, seoul, beijing, berlin, amsterdam, paris, london,
new_york, vancouver] ;
no
findall/3
De�nition
findall(+T, +Goal, -List):
List is the list of all instances of T for which Goal succeeds.
Examples II
?- findall(Cont, city(Cont, City), L).
L = [asia, asia, asia, europe, europe, europe, europe, america,
america] ;
no
?- findall(City, city(antarctica, City), L).
L = [] ;
no
findall/3
De�nition
findall(+T, +Goal, -List):
List is the list of all instances of T for which Goal succeeds.
Examples III
?- findall(Cont-City, city(Cont, City), L).
L = [asia-tokyo, asia-seoul, asia-beijing, europe-berlin,
europe-amsterdam, europe-paris, europe-london,
america-new_york, america-vancouver] ;
no
?- findall(hello, city(asia, City), L).
L = [hello, hello, hello] ;
no
findall/3
De�nition
findall(+T, +Goal, -List):
List is the list of all instances of T for which Goal succeeds.
Things to be aware of:
If Goal cannot be proven, List will be uni�ed with the empty list.
An instance Tθ may appear several several times in List if there are
di�erent successful paths to prove Goalθ.
Free variables in Goal are existentially quanti�ed (hence, there are not
part of the answer) � more on that later.
bagof/3
De�nition
bagof(+T, +Goal, -List):
For a given substitution σ of free variables in Goal
(all possible substitutions are generated through backtracking),
List is the list of all instances of T such that Goalσ succeeds.
bagof/3
De�nition
bagof(+T, +Goal, -List):
For a given substitution σ of free variables in Goal
(all possible substitutions are generated through backtracking),
List is the list of all instances of T such that Goalσ succeeds.
Examples I
?- bagof(City, city(europe, City), L).
L = [berlin, amsterdam, paris, london] ;
no
?- bagof(City, city(Cont, City), L).
Cont = america, L = [new_york, vancouver] ;
Cont = asia, L = [tokyo, seoul, beijing] ;
Cont = europe, L = [berlin, amsterdam, paris, london] ;
no
bagof/3
De�nition
bagof(+T, +Goal, -List):
For a given substitution σ of free variables in Goal
(all possible substitutions are generated through backtracking),
List is the list of all instances of T such that Goalσ succeeds.
Examples II
?- bagof(Cont, city(Cont, City), L).
City = amsterdam, L = [europe] ;
City = beijing, L = [asia] ;
City = berlin, L = [europe] ;
…
City = tokyo, L = [asia] ;
City = vancouver, L = [america] ;
no
?- bagof(City, city(antarctica, City), L).
no
bagof/3
De�nition
bagof(+T, +Goal, -List):
For a given substitution σ of free variables in Goal
(all possible substitutions are generated through backtracking),
List is the list of all instances of T such that Goalσ succeeds.
Examples III
?- bagof(Cont-City, city(Cont, City), L).
L = [asia-tokyo, asia-seoul, asia-beijing, europe-berlin,
europe-amsterdam, europe-paris, europe-london,
america-new_york, america-vancouver] ;
no
?- bagof(hello, city(asia, City), L).
City = beijing, L = [hello] ;
City = seoul, L = [hello] ;
City = tokyo, L = [hello] ;
no
bagof/3
De�nition
bagof(+T, +Goal, -List):
For a given substitution σ of free variables in Goal
(all possible substitutions are generated through backtracking),
List is the list of all instances of T such that Goalσ succeeds.
Things to be aware of:
If Goal cannot be proven, bagof/3 will fail.
For a given instantiation σ of the free variables in Goal, an instance Tθ
may appear several several times in List if there are di�erent successful
paths to prove Goalσθ.
Free variables in Goal are part of the answer.
setof/3
De�nition
setof(+T, +Goal, -List):
For a given substitution σ of free variables in Goal
(all possible substitutions are generated through backtracking),
List is the sorted set of all instances of T such that Goalσ succeeds.
setof/3
De�nition
setof(+T, +Goal, -List):
For a given substitution σ of free variables in Goal
(all possible substitutions are generated through backtracking),
List is the sorted set of all instances of T such that Goalσ succeeds.
Examples I
?- setof(City, city(europe, City), L).
L = [amsterdam, berlin, london, paris] ;
no
?- setof(City, city(Cont, City), L).
Cont = america, L = [new_york, vancouver] ;
Cont = asia, L = [beijing, seoul, tokyo] ;
Cont = europe, L = [amsterdam, berlin, london, paris] ;
no
setof/3
De�nition
setof(+T, +Goal, -List):
For a given substitution σ of free variables in Goal
(all possible substitutions are generated through backtracking),
List is the sorted set of all instances of T such that Goalσ succeeds.
Examples II
?- setof(Cont, city(Cont, City), L).
City = amsterdam, L = [europe] ;
City = beijing, L = [asia] ;
City = berlin, L = [europe] ;
…
City = tokyo, L = [asia] ;
City = vancouver, L = [america] ;
no
?- setof(City, city(antarctica, City), L).
no
setof/3
De�nition
setof(+T, +Goal, -List):
For a given substitution σ of free variables in Goal
(all possible substitutions are generated through backtracking),
List is the sorted set of all instances of T such that Goalσ succeeds.
Examples III
?- setof(Cont-City, city(Cont, City), L).
L = [america-new_york, america-vancouver, asia-beijing,
asia-seoul, asia-tokyo, europe-amsterdam,
europe-berlin, europe-london, europe-paris] ;
no
?- setof(hello, city(asia, City), L).
City = beijing, L = [hello] ;
City = seoul, L = [hello] ;
City = tokyo, L = [hello] ;
no
setof/3
De�nition
setof(+T, +Goal, -List):
For a given substitution σ of free variables in Goal
(all possible substitutions are generated through backtracking),
List is the sorted set of all instances of T such that Goalσ succeeds.
Things to be aware of:
If Goal cannot be proven, setof/3 will fail.
For any given instantiation σ of the free variables in Goal, the elements
in List are sorted in ascending order and duplicates are removed.
Free variables in Goal are part of the answer.
Prolog Ordering
Standard Order of Terms
1 Variables < Floats < Integers < Atoms < Compound Terms
2 Variables are sorted according to their order of appearance.
3 Numbers are compared according the natural order (but a �oat is
always smaller than an integer[∗]).
4 Atoms are compared alphabetically
5 Compound terms are compared: by their arity, then by their functor
name (alphabetically), then recursively by their arguments from left to
right.
To compare terms, use the built-in predicates '==', '\==', '@<', '@=<',
'@>‘, ‘@>=’ or ‘compare’.
[∗]SWI Prolog uses a di�erent ordering for numbers.
See http://www.swi-prolog.org/pldoc/man?section=compare
http://www.swi-prolog.org/pldoc/man?section=compare
bagof/3 vs. setof/3
Program
foo(2,a). foo(2,a). foo(2,a).
foo(1,b). foo(1,d). foo(1,d).
foo(3,c). foo(1,c). foo(1,a).
bagof/3
?- bagof(A, foo(N,A), L).
N = 1, L = [b, d, c, d, a] ;
N = 2, L = [a, a, a] ;
N = 3, L = [c] ;
no
setof/3
?- setof(A, foo(N,A), L).
N = 1, L = [a, b, c, d] ;
N = 2, L = [a] ;
N = 3, L = [c] ;
no
Existential quanti�ers
bagof(T, VˆGoal, L): variable V is existentially quanti�ed, it will not
be bound in goal (thus reproducing the behaviour of findall/3).
Program
bar(a,b,c). bar(b,c,e). bar(c,c,g).
bar(a,b,d). bar(b,c,f).
Queries
?- bagof(Z, bar(X,Y,Z), L).
X = a, Y = b, L = [c, d] ;
X = b, Y = c, L = [e, f] ;
X = c, Y = c, L = [g] ;
no
?- bagof(Z, X^bar(X,Y,Z), L).
Y = b, L = [c, d] ;
Y = c, L = [e, f, g] ;
no
?- bagof(Z, X^Y^bar(X,Y,Z), L).
L = [c, d, e, f, g] ;
no
Cautions
Aggregates are powerful, but computationally very expensive as well.
So do not use them if not necessary!.
setof/3 less e�cient than bagof/3 less e�cient than findall/3.
To avoid
findall(X, member(X, L), List)
(use L directly).
findall(X, Goal, List), member(Elt, List)
(call Goal directly and use X in place of Elt).
What have we learned today?
How to collect solutions in a list,
using findall/3, bagof/3 or setof/3
What are the di�erences between these three aggregates