Logic Programming in Prolog
• ListRepresentations
– dot operator
– Trees and Vine diagrams
Copyright By PowCoder代写 加微信 powcoder
• MoreListProcessing
– Insertion vs. Deletion – List processing
• Double Recursion
• Accumulators – Examples
List Representations
• Listscanbewrittenwiththebinaryfunctionsymbol . – Instead of using the familiar 𝑒𝑒 , 𝑒𝑒 , … using the
12 binary function the list is (𝑒𝑒1. 𝑒𝑒2. … )
• 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)
Tree Representation of Lists
• Examples: . XY
Fundamental List Properties
• A list is represented by a particular tree with all the leaves of the tree on branches to the left.
– Sometimes the tree is shown in a vine diagram
pie fruit cream
• 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)
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] ;
– As a generator, it can produce different solutions because the element a can be removed from
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]) :-
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
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).
– NeedspartitionListpredicate(nextslide).
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,[],[],[]).
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
?- mirror([1,2,3,4],L).
L= [4,3,2,1].
?- mirror(L,[1,2,3,4]).
L= [4,3,2,1].
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].
Comparing List Inversion
• Firstmirrorpredicateusesdoublerecursion
– first recursion on mirror
– second recursion with append
– Note: replace append/3 with appendList/3 and
• 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
• 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),
applyToList(L,T).
• Example:Sumuptheelementsofalistofnumbers
sumList(L,S) :- sumList(L,0,S). % Helper sumList([],S,S). %Extraargumentforresult sumList([X|L],T,S) :- TT is T+X,
sumList(L,TT,S).
• ListRepresentations
– dot operator
– Trees and Vine diagrams
• MoreListProcessing
– Insertion vs. Deletion – List processing
• Double Recursion
• Accumulators – Examples
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com