A few quick and dirty Prolog notes for getting up and running.
Data types
1, -1, 1.11 % constants
a 'a b c' % atoms
X The_end % variables start with capitals
a(1,2) functionname(x,y) % compound terms
a 'a b c' % atoms
X The_end % variables start with capitals
a(1,2) functionname(x,y) % compound terms
Interacting with prolog
- Start prolog: pl
- Quit prolog: halt.
- Start entering facts: [user].
- Stop entering facts: Control+D
- Find another solution: ; (or enter to just accept current answer)
- See full result: w
To create your own predicates: save them in a file as
whatever.pl. To load them in Prolog, type [whatever].
Solving problems
- See as Prolog sees: write_canonical([1,2,3]).
- Print: print('hello world').
- Debugging: trace,program(A,B,C). or guitracer,program(A,B,C).
- Help files: help.
Example code
% Write a predicate replace(OldCharacter, NewCharacter, InputList, OutputList)
% that replaces all the occurrences of OldCharacter in InputList with
% NewCharacter.
replace(_,_,[],[]).
replace(Old,New,[Old|TOld],[New|TNew]) :-
replace(Old,New,TOld,TNew).
replace(Old,New,[Different|TOld],[Different|TNew]) :-
not(Old = Different),
replace(Old,New,TOld,TNew).
% that replaces all the occurrences of OldCharacter in InputList with
% NewCharacter.
replace(_,_,[],[]).
replace(Old,New,[Old|TOld],[New|TNew]) :-
replace(Old,New,TOld,TNew).
replace(Old,New,[Different|TOld],[Different|TNew]) :-
not(Old = Different),
replace(Old,New,TOld,TNew).
% Write a predicate textify(ListToReplace, NewCharacter, InputList, OutputList)
% that replaces all the occurrences of ListToReplace in InputList with the
% character NewCharacter. Assume that ListToReplace always has exactly three
% characters.
% textify([a,t,e],8,[s, e, e,' ',y,o,u,' ',l,a,t,e,r,' ',k,a,t,e],Answer).
textify(_,_,[],[]).
textify(_,_,[_],[]).
textify(_,_,[_,_],[]).
textify([Old1,Old2,Old3],New,[Old1,Old2,Old3|TOld],[New|TNew]) :-
textify([Old1,Old2,Old3],New,TOld,TNew).
textify([Old1,Old2,Old3],New,[Different|TOld],[Different|TNew]) :-
not(Old1=Different),
textify([Old1,Old2,Old3],New,TOld,TNew).
% Describe how you would modify textify to deal with lists of any length.
% replace first rule with:
textify(ListToReplace, _, InputList, InputList) :-
length(ListToReplace,L), length(InputList,I), I < L.
% replace second rule with:
textify([Old|OldT],New,[Old|TOld],[New|TNew]) :-
TOld = [OldT|TOld2],
textify([Old|OldT],New,TOld2,TNew).
% that replaces all the occurrences of ListToReplace in InputList with the
% character NewCharacter. Assume that ListToReplace always has exactly three
% characters.
% textify([a,t,e],8,[s, e, e,' ',y,o,u,' ',l,a,t,e,r,' ',k,a,t,e],Answer).
textify(_,_,[],[]).
textify(_,_,[_],[]).
textify(_,_,[_,_],[]).
textify([Old1,Old2,Old3],New,[Old1,Old2,Old3|TOld],[New|TNew]) :-
textify([Old1,Old2,Old3],New,TOld,TNew).
textify([Old1,Old2,Old3],New,[Different|TOld],[Different|TNew]) :-
not(Old1=Different),
textify([Old1,Old2,Old3],New,TOld,TNew).
% Describe how you would modify textify to deal with lists of any length.
% replace first rule with:
textify(ListToReplace, _, InputList, InputList) :-
length(ListToReplace,L), length(InputList,I), I < L.
% replace second rule with:
textify([Old|OldT],New,[Old|TOld],[New|TNew]) :-
TOld = [OldT|TOld2],
textify([Old|OldT],New,TOld2,TNew).
% Given an input tree T, write a Prolog program that constructs a tree of the
% same shape as T, but in which the value of each node has been set to the value
% of the maximum value node in T.
% readable solution:
max(X,X,X) :- !.
max(X,Y,X) :- X > Y.
max(X,Y,Y) :- X < Y.
setMaxTree(n(V,[],[]), V, Max, n(Max,[],[])).
setMaxTree(n(V,L,[]), CurrMax, Max, n(Max,LNew,[])) :-
setMaxTree(L, V2, Max, LNew),
max(V, V2, CurrMax).
setMaxTree(n(V,[],R), CurrMax, Max, n(Max,[],RNew)) :-
setMaxTree(R, V2, Max, RNew),
max(V, V2, CurrMax).
setMaxTree(n(V,L,R), CurrMax, Max, n(Max,LNew,RNew)) :-
setMaxTree(L,V2,Max,LNew),
setMaxTree(R,V3,Max,RNew),
max(V,V2,VMax1),
max(VMax1,V3,CurrMax).
applyMax(T,TNew) :- setMaxTree(T,Max,Max,TNew).
% condensed to four clauses:
setMaxTree(n(V,[],[]), V, Max, n(Max,[],[])).
setMaxTree(n(V,L,[]), CurrMax, Max, n(Max,LNew,[])) :-
setMaxTree(L, V2, Max, LNew),
(V>=V2 -> CurrMax=V; CurrMax=V2).
setMaxTree(n(V,[],R), CurrMax, Max, n(Max,[],RNew)) :-
setMaxTree(R, V2, Max, RNew),
(V>=V2 -> CurrMax=V; CurrMax=V2).
setMaxTree(n(V,L,R), CurrMax, Max, n(Max,LNew,RNew)) :-
setMaxTree(L,V2,Max,LNew),
setMaxTree(R,V3,Max,RNew),
(V>=V2 -> VMax1=V; VMax1=V2),
(VMax1>=V3 -> CurrMax=VMax1; CurrMax=V3).
% 'simply' call with setMaxTree(Tree,M,M,X).
% to produce X as the new tree with all the nodes set to max
% same shape as T, but in which the value of each node has been set to the value
% of the maximum value node in T.
% readable solution:
max(X,X,X) :- !.
max(X,Y,X) :- X > Y.
max(X,Y,Y) :- X < Y.
setMaxTree(n(V,[],[]), V, Max, n(Max,[],[])).
setMaxTree(n(V,L,[]), CurrMax, Max, n(Max,LNew,[])) :-
setMaxTree(L, V2, Max, LNew),
max(V, V2, CurrMax).
setMaxTree(n(V,[],R), CurrMax, Max, n(Max,[],RNew)) :-
setMaxTree(R, V2, Max, RNew),
max(V, V2, CurrMax).
setMaxTree(n(V,L,R), CurrMax, Max, n(Max,LNew,RNew)) :-
setMaxTree(L,V2,Max,LNew),
setMaxTree(R,V3,Max,RNew),
max(V,V2,VMax1),
max(VMax1,V3,CurrMax).
applyMax(T,TNew) :- setMaxTree(T,Max,Max,TNew).
% condensed to four clauses:
setMaxTree(n(V,[],[]), V, Max, n(Max,[],[])).
setMaxTree(n(V,L,[]), CurrMax, Max, n(Max,LNew,[])) :-
setMaxTree(L, V2, Max, LNew),
(V>=V2 -> CurrMax=V; CurrMax=V2).
setMaxTree(n(V,[],R), CurrMax, Max, n(Max,[],RNew)) :-
setMaxTree(R, V2, Max, RNew),
(V>=V2 -> CurrMax=V; CurrMax=V2).
setMaxTree(n(V,L,R), CurrMax, Max, n(Max,LNew,RNew)) :-
setMaxTree(L,V2,Max,LNew),
setMaxTree(R,V3,Max,RNew),
(V>=V2 -> VMax1=V; VMax1=V2),
(VMax1>=V3 -> CurrMax=VMax1; CurrMax=V3).
% 'simply' call with setMaxTree(Tree,M,M,X).
% to produce X as the new tree with all the nodes set to max
% Write a Prolog program to return a list of all the 0’s and a list of all the
% 1’s in a given tree. For example, the goal enum(n(n(0, 1, 0), 1, 0), X, Y)
% should instantiate X to [0, 0, 0] and Y to [1, 1]. The program should use
% difference lists.
% without difference lists:
flatten(0,[0]).
flatten(1,[1]).
flatten(n(X,Y,Z),List) :-
flatten(X,XL),flatten(Y,YL),flatten(Z,ZL),
append(XL,YL,List1),
append(List1,ZL,List).
enum(T,X,Y) :- flatten(T,FlatT),getN(0,FlatT,X),getN(1,FlatT,Y).
getN(X,[X|TIn],[X|TOut]) :- getN(X,TIn,TOut).
getN(X,[Y|TIn],TOut) :- not(X=Y),getN(X,TIn,TOut).
getN(_,[],[]).
% with difference lists:
flatten(0,[0|T]-T).
flatten(1,[1|T]-T).
flatten(n(X,Y,Z),List) :-
flatten(X,XL),flatten(Y,YL),flatten(Z,ZL),
dapp(XL,YL,List1),
dapp(List1,ZL,List).
dapp(A-B,B-C,A-C).
getN(_,A-B,A-B) :- unify_with_occurs_check(A,B), !.
getN(X,[X|TIn]-T1,[X|TOut]-T2) :- getN(X,TIn-T1,TOut-T2).
getN(X,[Y|TIn]-T1,TOut-T2) :- not(X=Y),getN(X,TIn-T1,TOut-T2).
enum(T,X,Y) :- flatten(T,FlatT),getN(0,FlatT,X),getN(1,FlatT,Y).
% 1’s in a given tree. For example, the goal enum(n(n(0, 1, 0), 1, 0), X, Y)
% should instantiate X to [0, 0, 0] and Y to [1, 1]. The program should use
% difference lists.
% without difference lists:
flatten(0,[0]).
flatten(1,[1]).
flatten(n(X,Y,Z),List) :-
flatten(X,XL),flatten(Y,YL),flatten(Z,ZL),
append(XL,YL,List1),
append(List1,ZL,List).
enum(T,X,Y) :- flatten(T,FlatT),getN(0,FlatT,X),getN(1,FlatT,Y).
getN(X,[X|TIn],[X|TOut]) :- getN(X,TIn,TOut).
getN(X,[Y|TIn],TOut) :- not(X=Y),getN(X,TIn,TOut).
getN(_,[],[]).
% with difference lists:
flatten(0,[0|T]-T).
flatten(1,[1|T]-T).
flatten(n(X,Y,Z),List) :-
flatten(X,XL),flatten(Y,YL),flatten(Z,ZL),
dapp(XL,YL,List1),
dapp(List1,ZL,List).
dapp(A-B,B-C,A-C).
getN(_,A-B,A-B) :- unify_with_occurs_check(A,B), !.
getN(X,[X|TIn]-T1,[X|TOut]-T2) :- getN(X,TIn-T1,TOut-T2).
getN(X,[Y|TIn]-T1,TOut-T2) :- not(X=Y),getN(X,TIn-T1,TOut-T2).
enum(T,X,Y) :- flatten(T,FlatT),getN(0,FlatT,X),getN(1,FlatT,Y).
% A terminal node of the trinary tree is said to be of odd parity if the number
% of its 1 components is an odd number. For example, n(1, 1, 1) is of odd
% parity, and n(1, 0, 1) is not of odd parity. Write a Prolog program to count
% the number of terminal nodes in a tree that have odd parity. For example,
% the goal odd(n(n(0, 1, 0), 1, 0), X) should instantiate X to 1.
isodd(n(0,0,1)).
isodd(n(0,1,0)).
isodd(n(1,0,0)).
isodd(n(1,1,1)).
odd(1,0).
odd(0,0).
odd(n(X,Y,Z),1) :- isodd(n(X,Y,Z)),!.
odd(n(X,Y,Z),Count) :- odd(X,C1),odd(Y,C2),odd(Z,C3), Count is C1+C2+C3.
% note to self: would be better to use the 99 prolog challenges rather than old supervision work, so have removed questions that do not show anything new
% of its 1 components is an odd number. For example, n(1, 1, 1) is of odd
% parity, and n(1, 0, 1) is not of odd parity. Write a Prolog program to count
% the number of terminal nodes in a tree that have odd parity. For example,
% the goal odd(n(n(0, 1, 0), 1, 0), X) should instantiate X to 1.
isodd(n(0,0,1)).
isodd(n(0,1,0)).
isodd(n(1,0,0)).
isodd(n(1,1,1)).
odd(1,0).
odd(0,0).
odd(n(X,Y,Z),1) :- isodd(n(X,Y,Z)),!.
odd(n(X,Y,Z),Count) :- odd(X,C1),odd(Y,C2),odd(Z,C3), Count is C1+C2+C3.
% note to self: would be better to use the 99 prolog challenges rather than old supervision work, so have removed questions that do not show anything new