Prolog Cheat Sheet

Prolog Fundamentals

Facts

Facts are basic assertions about the world. Always end with a period.

% Facts about people
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).

% Facts about food
likes(john, pizza).
likes(mary, sushi).
likes(bob, pizza).

Rules

Rules define relationships based on other facts and rules.

% X is a grandparent of Z if X is parent of Y and Y is parent of Z
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

% X is a sibling of Y if they share a parent
sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.

% X is an ancestor of Y if X is parent of Y (base case)
% OR if X is parent of Z and Z is ancestor of Y (recursive)
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

Queries

Ask questions at the ?- prompt.

?- parent(tom, bob).
true.

?- parent(bob, ann).
true.

?- parent(tom, ann).
false.

% Find all children of bob (X is a variable)
?- parent(bob, X).
X = ann ;
X = pat.

% Find all grandchildren of tom
?- grandparent(tom, X).
X = ann ;
X = pat.

% Find who likes pizza
?- likes(X, pizza).
X = john ;
X = bob.

Unification & Variables

% Find if tom is parent of anyone (don't care who)
?- parent(tom, _).
true.

% Match patterns
?- parent(tom, Child).
Child = bob ;
Child = liz.

% Unification operator =
?- X = 5.
X = 5.

?- [1,2,3] = [H|T].
H = 1,
T = [2, 3].

% Checking inequality
?- 5 \= 10.
true.

?- X = 5, X \= 10.
X = 5.

Lists

List Operations

% Check if X is in list
member(X, [X|_]).
member(X, [_|T]) :- member(X, T).

?- member(2, [1,2,3]).
true.

% Find length of list
len([], 0).
len([_|T], N) :- 
    len(T, N1), 
    N is N1 + 1.

?- len([1,2,3], N).
N = 3.

% Append two lists
append([], L, L).
append([H|T1], L2, [H|T3]) :- 
    append(T1, L2, T3).

?- append([1,2], [3,4], X).
X = [1, 2, 3, 4].

% Reverse a list
reverse([], []).
reverse([H|T], R) :- 
    reverse(T, RT), 
    append(RT, [H], R).

?- reverse([1,2,3], X).
X = [3, 2, 1].

More List Examples

% Sum of list elements
sum([], 0).
sum([H|T], Sum) :- sum(T, RestSum), Sum is H + RestSum.

% Find maximum in list
max([X], X).
max([H|T], Max) :- max(T, TMax), (H > TMax -> Max = H ; Max = TMax).

% Get last element
last([X], X).
last([_|T], X) :- last(T, X).

% Get nth element (0-indexed)
nth(0, [H|_], H).
nth(N, [_|T], E) :- N > 0, N1 is N - 1, nth(N1, T, E).

Arithmetic & Comparison

Arithmetic Operators

Comparison Operators

% Factorial
factorial(0, 1).
factorial(N, F) :- 
    N > 0,
    N1 is N - 1,
    factorial(N1, F1),
    F is N * F1.

% Fibonacci
fib(0, 0).
fib(1, 1).
fib(N, F) :-
    N > 1,
    N1 is N - 1,
    N2 is N - 2,
    fib(N1, F1),
    fib(N2, F2),
    F is F1 + F2.

Backtracking & Cut

% Prolog will try each clause in order
color(red).
color(green).
color(blue).

?- color(X).
X = red ;      % First answer, user types ;
X = green ;    % Second answer, user types ;
X = blue.      % Third answer

% Backtracking example
likes(mary, food).
likes(mary, wine).
likes(john, wine).
likes(john, mary).

?- likes(mary, X), likes(john, X).
X = wine.      % Only wine satisfies both conditions

The Cut Operator (!)

% Without cut - tries all solutions
max_no_cut(X, Y, X) :- X >= Y.
max_no_cut(X, Y, Y) :- X < Y.

% With cut - stops after first match
max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).

% Cut prevents unnecessary backtracking
member_check(X, [X|_]) :- !.
member_check(X, [_|T]) :- member_check(X, T).

% Negation using cut and fail
not_member(_, []).
not_member(X, [H|T]) :- X \= H, not_member(X, T).

Control Structures

Conjunction (AND)

% Both conditions must be true (comma means AND)
?- parent(tom, bob), parent(bob, ann).
true.

happy(Person) :- healthy(Person), wealthy(Person).

Disjunction (OR)

% Either condition can be true (semicolon means OR)
?- parent(tom, bob); parent(tom, liz).
true.

eligible(Person) :- student(Person); veteran(Person).

Negation

% \+ means NOT
?- \+ parent(tom, ann).
true.

different(X, Y) :- \+ X = Y.

% Not a member
not_in(_, []).
not_in(X, [H|T]) :- X \= H, not_in(X, T).

If-Then-Else

% Syntax: (Condition -> ThenPart ; ElsePart)

max(X, Y, Max) :- (X >= Y -> Max = X ; Max = Y).

absolute(X, Abs) :- (X >= 0 -> Abs = X ; Abs is -X).

grade(Score, Grade) :-
    (   Score >= 90 -> Grade = a
    ;   Score >= 80 -> Grade = b
    ;   Score >= 70 -> Grade = c
    ;   Score >= 60 -> Grade = d
    ;   Grade = f
    ).

Common Built-in Predicates

atom(X)      % X is atom
number(X)    % X is number
integer(X)   % X is integer
is_list(X)   % X is list
var(X)       % X is unbound
nonvar(X)    % X is bound

length(L, N)      % length
append(L1, L2, L3) % concatenate
member(X, L)      % membership
reverse(L, R)     % reverse
sort(L, S)        % sort
nth0(I, L, E)     % get nth

findall(X, Goal, L)
% Find all X satisfying Goal

bagof(X, Goal, L)
% Like findall, groups

setof(X, Goal, L)
% Sorted unique results

write(Term)
writeln(Term)
read(X)
nl              % newline
tab(N)          % N spaces

Finding All Solutions

% Given these facts:
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).

% Get all children of tom
?- findall(Child, parent(tom, Child), Children).
Children = [bob, liz].

% Get all parents and their children as pairs
?- findall([Parent, Child], parent(Parent, Child), Pairs).
Pairs = [[tom, bob], [tom, liz], [bob, ann], [bob, pat]].

% Count how many children bob has
?- findall(Child, parent(bob, Child), Children), length(Children, N).
Children = [ann, pat],
N = 2.

Common Recursion Patterns

Processing Lists

% Base case: empty list
% Recursive case: process head, recurse on tail

% Count elements
count([], 0).
count([_|T], N) :- count(T, N1), N is N1 + 1.

% Double each element
double([], []).
double([H|T], [H2|T2]) :- H2 is H * 2, double(T, T2).

% Filter even numbers
evens([], []).
evens([H|T], [H|T2]) :- 0 is H mod 2, !, evens(T, T2).
evens([_|T], T2) :- evens(T, T2).

Accumulator Pattern

% More efficient with accumulator

% Sum with accumulator
sum(List, Sum) :- sum_acc(List, 0, Sum).

sum_acc([], Acc, Acc).
sum_acc([H|T], Acc, Sum) :- 
    NewAcc is Acc + H,
    sum_acc(T, NewAcc, Sum).

% Reverse with accumulator (tail recursive)
reverse(List, Rev) :- reverse_acc(List, [], Rev).

reverse_acc([], Acc, Acc).
reverse_acc([H|T], Acc, Rev) :- 
    reverse_acc(T, [H|Acc], Rev).

Tree Traversal

% Binary tree: node(Value, Left, Right) or nil

% Count nodes
count_nodes(nil, 0).
count_nodes(node(_, L, R), Count) :-
    count_nodes(L, CL),
    count_nodes(R, CR),
    Count is CL + CR + 1.

% Tree height
height(nil, 0).
height(node(_, L, R), H) :-
    height(L, HL),
    height(R, HR),
    H is max(HL, HR) + 1.

% Search tree
search(Val, node(Val, _, _)).
search(Val, node(_, L, _)) :- search(Val, L).
search(Val, node(_, _, R)) :- search(Val, R).

Practical Examples

Family Tree

% Facts
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).

male(tom).
male(bob).
male(jim).
female(liz).
female(ann).
female(pat).

% Rules
father(X, Y) :- parent(X, Y), male(X).
mother(X, Y) :- parent(X, Y), female(X).

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
grandmother(X, Z) :- grandparent(X, Z), female(X).
grandfather(X, Z) :- grandparent(X, Z), male(X).

sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.
brother(X, Y) :- sibling(X, Y), male(X).
sister(X, Y) :- sibling(X, Y), female(X).

uncle(X, Y) :- brother(X, P), parent(P, Y).
aunt(X, Y) :- sister(X, P), parent(P, Y).

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

Graph Traversal

% Graph edges
edge(a, b).
edge(b, c).
edge(b, d).
edge(c, d).
edge(d, e).
edge(a, e).

% Path exists between two nodes
path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

% Path with visited nodes (avoid cycles)
path(X, Y, Visited, [X,Y]) :- 
    edge(X, Y), 
    \+ member(Y, Visited).
path(X, Y, Visited, [X|Path]) :- 
    edge(X, Z), 
    \+ member(Z, Visited),
    path(Z, Y, [X|Visited], Path).

Quicksort

% Quicksort implementation
quicksort([], []).
quicksort([Pivot|T], Sorted) :-
    partition(Pivot, T, Less, Greater),
    quicksort(Less, SortedLess),
    quicksort(Greater, SortedGreater),
    append(SortedLess, [Pivot|SortedGreater], Sorted).

% Partition list around pivot
partition(_, [], [], []).
partition(Pivot, [H|T], [H|Less], Greater) :-
    H =< Pivot, !,
    partition(Pivot, T, Less, Greater).
partition(Pivot, [H|T], Less, [H|Greater]) :-
    partition(Pivot, T, Less, Greater).

Important Tips