CSI2120 Programming Paradigms Jochen Lang
jlang@uottawa.ca
Faculté de génie | Faculty of Engineering
Jochen Lang, EECS jlang@uOttawa.ca
Logic Programming in Prolog
• ListRepresentations
– dot operator
– Trees and Vine diagrams
• MoreListProcessing
– Insertion vs. Deletion – List processing
• Double Recursion
• Accumulators – Examples
Jochen Lang, EECS jlang@uOttawa.ca
List Representations
• Lists can be written with the binary function symbol . – Instead of using the familiar , , … using the
binary function the list is . . …
• Theemptylistisalsonotedasnilandistheendmarker
of the list • Examples:
– The list {pie, fruit, cream} is written (pie.(fruit.(cream.nil)))
– The variables X followed by Y can be written as (X.Y)
Jochen Lang, EECS jlang@uOttawa.ca
Tree Representation of Lists
• Examples: . XY
.
Jochen Lang, EECS jlang@uOttawa.ca
pie fruit
.
.
cream
nil
Fundamental List Properties
• Alistisrepresentedbyaparticulartreewithalltheleaves of the tree on branches to the left.
– Sometimes the tree is shown in a vine diagram
Jochen Lang, EECS jlang@uOttawa.ca
… pie fruit cream
nil
• Example:
– Solve the equation X.Y = pie.fruit.cream.nil – Solution:
• {X = pie; Y = fruit.cream.nil}
Fundamental List Properties (cont’d)
• ThenotationX.YrepresentstheheadXandthetailYof the list.
• TheheadisthefirstelementandYisthetailofthelist.
– The notion of head and tail of a list is the basis of list processing in Prolog.
– But the term pie.fruit is not a list just a pair – Need brackets for a list, i.e., pie.(fruit.nil)
Jochen Lang, EECS jlang@uOttawa.ca
List insertion and deletion
• Considerthelistinsertionpredicatefrombefore
listInsert(A,L,[A|L]).
listInsert(A,[X|L], [X|LL]) :-
listInsert(A,L,LL).
– Query with the list after insertion and get the list before.
?- listInsert(a,L,[b,a,d,a,f]).
L = [b, d, a, f] ;
L = [b, a, d, f] ;
false.
– As a generator, it can produce different solutions because the element a can be removed from
Jochen Lang, EECS jlang@uOttawa.ca
different positions
Delete Elements from a List
• Deletionofthefirstoccurrenceofanelement
deleteFront(R,[R|L],L). % Element found deleteFront(R,[X|LL],[X|L]) :-
deleteFront(R,LL,L). % Use Accumulator
• Deletealloccurrencesofanelement
deleteAll(_,[],[]).
deleteAll(X,[X|T],Result) :-
deleteAll(X,T,Result),!. % Delete once deleteAll(X,[H|T],[H|Result]) :-
Jochen Lang, EECS jlang@uOttawa.ca
deleteAll(X,T,Result). % Other element
Intersection of two lists (set operations)
Lists can represent sets in Prolog
• Simplifiedintersectionassumingtheinputlistscontain no duplicate elements, i.e., they are sets themselves
intersectList( [], _, [] ).
intersectList( [ X | Xs ], Ys, Zs ) :-
\+member( X, Ys), % built-in
intersectList( Xs, Ys, Zs ).
intersectList( [ X | Xs ], Ys, [ X | Zs ] ) :-
member( X, Ys ),
intersectList( Xs, Ys, Zs ). • Notethereisalsoalibrarypredicateintersection/3
Jochen Lang, EECS jlang@uOttawa.ca
Quick Sorting a List
• Recursivesorting
• Quicksortwithsimplyselectingthefirstelementasthe pivot, better to randomize
sortList([],[]).
sortList([P|Q],T) :- partitionList(P,Q,G,D)
sortList(G,GG),
sortList(D,DD),
append(GG,[P|DD],T).
– Making use of the library predicate append (could use our own definition appendList from before).
– Needs partitionList predicate (next slide).
Jochen Lang, EECS jlang@uOttawa.ca
Partitioning a List
• Splittingalistinto2listswithapivot
– One list greater than the pivot
– One list smaller than the pivot
– Use alphanumeric comparison operator
• Instead could use an additional rule
lessThan(X,P)
partitionList(P,[X|L],[X|PG],PD) :- X @< P,
partitionList(P,L,PG,PD).
partitionList(P,[X|L],PG,[X|PD]) :- X @>= P,
partitionList(P,L,PG,PD).
partitionList(P,[],[],[]).
Jochen Lang, EECS jlang@uOttawa.ca
Invert the Order of a List
mirror([],[]). % empty list is mirrored itself
mirror([X|L1], L2) :- % Take X off the front
mirror(L1,L3), % Mirror the rest L1
append(L3, [X], L2). % Put X at the back
– Note we use built-in append which behaves as appendList
– Queries
?- mirror([1,2,3,4],L).
L= [4,3,2,1].
?- mirror(L,[1,2,3,4]).
L= [4,3,2,1].
Jochen Lang, EECS jlang@uOttawa.ca
Improved List Inversion
reverseList([],L,L) :- !.
reverseList([H|T],L,R) :-
reverseList(T,[H|L],R).
mirrorAcc(L,R) :- reverseList(L,[],R).
• NotetheuseoftheCutintheboundarycase • Example
?- mirrorAcc(L,[1,2,3,4]).
L = [4,3,2,1].
Jochen Lang, EECS jlang@uOttawa.ca
Comparing List Inversion
• Firstmirrorpredicateusesdoublerecursion
– first recursion on mirror
– second recursion with append
– Note: replace append/3 with appendList/3 and trace
• Second mirrorAcc predicate uses an accumulator
– Not instantiated variable is passed as an argument to the base case
– Once reached it is unified all the way up the call stack
– Improved efficiency compared with double recursion
Jochen Lang, EECS jlang@uOttawa.ca
• Only one recursion. Call stack has a depth equals the length of the list.
Operators on a List
• Example:Applyanoperatortoeachelementofalist
applyToList([],[]). % boundary case
applyToList([X|L],[Y|T]) :- applyOp(X,Y),
• Example:Sumuptheelementsofalistofnumbers
sumList(L,S) :- sumList(L,0,S). % Helper
sumList([],S,S). % Extra argument for result
sumList([X|L],T,S) :- TT is T+X,
Jochen Lang, EECS jlang@uOttawa.ca
applyToList(L,T).
sumList(L,TT,S).
Summary
• ListRepresentations
– dot operator
– Trees and Vine diagrams
• MoreListProcessing
– Insertion vs. Deletion – List processing
• Double Recursion
• Accumulators – Examples
Jochen Lang, EECS jlang@uOttawa.ca