CPS721:ArtificialIntelligence (CS/RU)
CPS721: Artificial Intelligence
Acknowledgement:
based on the slides prepared by
Copyright By PowCoder代写 加微信 powcoder
September 29, 2021
September29,2021 1/18
Intro to lists
To write efficient recursive programs we need a recursive data structure. Linked lists were invented in AI in 1958 to write a program that can automatically prove theorems. Recall a linked list is a structure that keeps an element itself and a pointer to the next element. In PROLOG, pointers remain implicit.
Much of AI computing requires the ability to work on a collection of symbolic objects as a unit. Prolog provides such a collection; it’s called a list.
A list is a sequence of objects which are called the elements of the list. Examples:
[anna, karanina]
A two element list, with first element anna and second element karanina.
[intro,to,programming,in,prolog]
A five element list.
[1, 2, 3, 3, 2, 1] Lists may have repeated elements
[ ] The list with no elements. The empty list.
[[john, 24], [mary, 19], [[hello]], c, b, c, 10]
A 7 element list some of whose elements are also lists with 2 or 1 elements
[1, john, [CPS721, john]]
Note: a one element list is different from the element: [anna] is different from anna and [[anna]]
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021 2/18
Heads and Tails
The first element of a list is called its head. The rest of the list is called its tail.
[a,b,c,d] has head a and tail [b,c,d]. [a] has head a and tail [].
[] has neither head nor tail.
Prolog provides two ways of writing lists:
as a sequence of elements separated by “,”
using a “|” to separate some initial elements from a list formed of the remaining ones
For example, [a, b, c, d] can be equivalently rewritten as:
[a | [b, c, d]]
(meaning a is its head and [b, c, d] is its tail) [a, b | [c, d]]
(meaning a and b are the first two elements and the list [c,d] makes up the rest) [a, b, c | [d]]
[a, b, c, d | [ ]]
Note the lists above are just different notations of [a,b,c,d]. We do not change this list, when we write it using “|”. Why notation “|” can be convenient ?
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021 3/18
Matching goals to rules
When Prolog has a goal expression it is working on, it must find a clause in the program to match.
For example, if we have the goal expression p(a,U) we need to find a clause like p(a,b).
or p(X,Y) :- … or p(W,b) :- …
A clause in the program like p(b,X). or
p(X,Y,Z) :- …
does not apply.
Implicit in this is the idea of matching the arguments in the goal (a and U) with the
arguments in the clause (W and b).
When successful, this can generate values for the variables (W=a and U=b).
We now consider how this matching should work for lists.
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021 4/18
Matching lists
When do two lists match in Prolog?
• When they are identical, element for element.
• If one or more of the lists have variables, when the variables can be given values that make the two lists identical, element for element.
2 [a,b,c] and [a,b,c]
3 [X] and [a] with X=a
4 [X] and [Y] with X=X and Y=X
5 [a,b,c] and [a,X,Y] with X= , Y=
6 [a,b,a] and [X,b,X] with X=
7 [a|[b,c]] and [a,b,c] /* Why ? */
8 [a|[b|[c]]] and [a,b|[c]] /* Why ? */
9 [X|Y] and [a] with X= , Y=
10 [a,b | [c]] and [a|X] with X=
11 [a|[b,c]] and [a,X,Y] with X= , Y=
12 [a,b,c] and [X|Y] with X= , Y=
13 [X,Y|Y] and [a,[b,c],b,c] with X= , Y=
14 [a,b] and [a,X|Y] with X= , Y=
15 [[a,b],[c,d,e]] and [[X|Y],[Z,d|W]] with
X= , Y= , Z= , W=
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021 5/18
Computing with lists
We can now use this matching to write some simple predicates on lists.
First: consider the predicate head(X,Y) which should hold iff Y is a non-empty list
and X is its first element.
In other words, we want the following query behaviour:
?- head(a,[a,b,c]). yes
head(a,[H,b]).
Because we want the first argument to match the head of the second argument, we should use X.
So the required program clause is: head(X,[X|Y]). Similarly, the program for a tail predicate is: tail(Y,[X|Y]).
?- head(W,[ ]).
?- head(a,[b,c,a]).
Because the second argument must be a list with at least one element, use [X|Y].
CPS721:ArtificialIntelligence (CS/RU) Lists
September29,2021 7/18
Non-matching lists
Lists do not match if they have different numbers of elements, or if at least one corresponding element does not match.
Some non-matching pairs (explain why they do not match?): [a] and [ ]
[a, b, c] and [a, a, c] [ ] and [[ ]]
[X,Y] and [U,V,W] [a,b,c] and [X,b,X] [X|Y] and [ ]
[a,b] and [b,a] Observe:
X matches anything, including any list.
[X ] only matches a list with one element (that can be a list itself). [X | Y ] matches a list with one or more elements.
[X , Y ] only matches a list with two elements.
We will be using these matching properties when lists appear in the heads of rules in Prolog programs. We will see that “|” notation faciliates writing recursive programs.
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021 6/18
Recursion: approach and tips
Unce upon a time, a TA taught his class the following:
“To understand recursion you have to understand recursion”.
Is it a good lesson ? Yes/No and Why ? Explain your opinion.
The main idea of recursion is delegating a bit reduced work that remains to be done to someone else, i.e., to the same predicate, your friend, or anyone else. The key is that whoever takes remaining work, there is less work to do than it was at the start.
Each step of reduction bring closer to a base case, or base cases. They solve the problem directly, since for small parameter values there is little work to do.
The program design technique: divide the problem top-down into several mutually exclusive cases, and do case-analysis. Make sure that all possible cases are considered.
For each of the cases, write a rule that handles this specific case only. Combine the rules from different cases into a program that covers all of them.
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021 8/18
The predicate member(X,List)
The predicate member(X,List) is true if the element X occurs somewhere in a List.
|X|||||||||||X|||||||||||X| /*ImagineagivenList asatape*/
Do case analysis. Case 1: If a given List is empty, then this predicate is false for any
element X. There is no rule to write.
Case 2: Suppose that List is not empty, i.e., it has at least one element. Then, this list
can be represented as
List = [Head|Tail]. We consider two sub-cases for a non-empty List: a) the 1st element, Head, of List is actually X,
b) the 1st element, Head, of List is different from X.
Obviously, in the sub-case (a), X is a member of List:
member(X, [Head | Tail]) :- Head=X. (*)
In the sub-case (b), if X is different from Head, then X is a member of the list [Head|Tail], if X is a member of Tail:
member(X, [Head | Tail]) :- not Head=X, member(X,Tail). (**) How to simplify this program, i.e., the rules (*) and (**) ?
CPS721:ArtificialIntelligence (CS/RU) Lists
September29,2021 9/18
The predicate append(List1,List2,Result)
The predicate append(List1,List2,Result) is true, if the list Result is obatined by
joining lists List1 and List2 together:
Examples. All of the following queries succeed.
?- append([a,b], [c,d,e], [a,b,c,d,e]). ?- append([ ], [a,b], [a,b]).
?- append([a,b], [ ], [a,b]).
?- append([ ], [ ], [ ]).
List1 | List2
If appending List2 to Tail1 results in the list BigList, then joining lists [Head1|Tail1] and List2 yields the list [Head1|BigList]. BigList
[Head 1|BigList ]
Do case analysis. Case 1: List1 is empty. Then, appending List2 to the empty list,
Head1| Tail1 List2
yields List2 itself: append([ ],List2,List2). (*)
Case 2: List1 is not empty. Then, it has at least one element. So, it can be written as List1=[Head1|Tail1]. In this case, according to the diagram
append([Head1 | Tail1],List2,[Head1 | BigList]) :- append(Tail1,List2,BigList). (**)
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021 11/18
Simplified program for member(X,List) member(X, [X | Tail]).
member(X, [Head | Tail]) :- member(X,Tail).
(New∗) (New∗∗)
Possible queries:
?- member(b, [a,b,c,d]). ?- member(k, [a,b,c,d]). ?- member(X, [a,b,c,d]).
/* answer is yes */ /* answer is no */ /* returns a,b,c,d consecutively */
Exercise 1. Explain why the above recursive program terminates for an arbitrary list? Exercise 2. What is the complexity of the above algorithm for computing membership ?
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021
Quries to append(List1,List2,Result)
Thus, we have 2 rules that define the predicate completely:
append([ ],List,List).
append([X | List1],List2,[X | Result]) :-
append(List1,List2,Result). (**) Exercise 3: Will this recusive program terminate ? Yes/No and When ?
Exercise 4: What is the running time of this program depending on the length of List1? Exercise 5: Can we do recursion over the 2nd argument, instead of the 1st argument ?
This simple and elegant program can be used to run many different computations:
?- append([a,b,c],[d,e,f],Result).
?- append([a,b,c],Final,[a,b,c,d,e,f]). ?- append(Init,[d,e,f],[a,b,c,d,e,f]). ?- append(Init,Final,[a,b,c,d,e,f]).
/* find Result=[a,b,c,d,e,f] */ /* find Final=[d,e,f] */ /* find Init=[a,b,c] */ /* split the given list */
Note this last query will consecutively find all decompositions of the given list into different initial and final sub-lists.
What will be the first answer returned ? Init= Final=
What will be the last answer returned ? Init= Final=
?- append(Before, [may | After], [jan,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,dec]). Before= After= /* convenient for pattern matching */
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021 12/18
Defining new predicates with append
The predicate last(X,List) means that the element X is the last element of List.
How can we write a program for last(X,List) using append ? last(X,List) :- append(InitList, [X], List).
The predicate front(L1,L2) is true if the list L1 is an initial sub-list of the list L2. How can we write a program for front (L1, L2) using append ?
front(L1,L2) :- append(L1, SomeList, L2).
What is remarkable, we can use append to redefine membership of element X in a given List. How this can be done ?
memberNew(X,List) :- append(InitPart, [X | FinalPart], List).
Exercise 6:
Comparethesetwodifferentimplementationsofmember. Whichimplementationis more computationally efficient ? Assume List is long. You can try answering different queries using both programs before arriving at your conclusion.
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021 13/18
Examples of replaceFirst (X , Y , L1, L2)
replaceFirst(X, Y, [ ], [ ]).
replaceFirst(X, Y, [X | L], [Y | L]).
replaceFirst(X,Y, [Z | L1], [Z | L2]) :-
not X = Z, replaceFirst(X,Y, L1, L2).
Examples: A. Transform “house” into “mouse”
?- replaceFirst(h, m, [h,o,u,s,e], L).
L = [m,o,u,s,e]
Yes (0.00s cpu, solution 1, maybe more) ; No (0.02s cpu)
B. Transform [s,a,n,d] into [g,o,l,d]. Exercise.
Hint: call replaceFirst consecutively several times: s-> g, a -> o, n -> l.
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021 15/18
The predicate replaceFirst (X , Y , L1, L2)
“The list L2 results from replacing the very first occurrence of X in the list L1 by Y ” Encode this English sentence with the predicate replaceFirst (+X , +Y , +L1, −L2). Do case analysis: there are 3 cases when the sentence is true. What are the cases ?
Case1: The input list L1 is empty, but then output L2 is also empty. Encode in Prolog? replaceFirst(X, Y, [ ], [ ]).
Case 2: The list L1 begins with X, i.e., L1 = [X|Tail]. Then our sentence is true if L2 begins with Y and its tail is identical to Tail, i.e., L2 = [Y|Tail]. Prolog code ?
replaceFirst(X, Y, [X | Tail], [Y | Tail]).
Case 3: L1 is not empty, but it begins with Z which is different from X , i.e., L1 = [Z|Tail1] and not(X = Z). What program must do in this case?
Skip Z and keep searching recursively for X in Tail1, i.e., make sure that the sentence is true with respect to the elements in the tails of L1 and L2. Prolog code ?
replaceFirst(X,Y, [Z | Tail1], [Z | Tail2]) :-
not X = Z, replaceFirst(X,Y, Tail1, Tail2).
Why starting this rule with not(X=Z) is ok in this case ?
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021 14/18
The predicate replaceAll (X , Y , L1, L2)
“The list L2 results from replacing all occurrences of X in the list L1 by Y ” Encode this English sentence by the predicate replaceAll (X , Y , L1, L2)
Develop code for replaceAll from our Prolog code for replaceFirst. How? replaceFirst(X, Y, [ ], [ ]). /* how to change this line?*/
replaceAll(X, Y, [ ], [ ]).
replaceFirst(X, Y, [X | Tail], [Y | Tail]). /* what to chamge here?*/ replaceAll(X, Y, [X | Tail1], [Y | Tail2]) :-
replaceAll(X, Y, Tail1, Tail2).
replaceFirst(X,Y, [Z | L1], [Z | L2]) :-
not X = Z, replaceFirst(X,Y, L1, L2).
How to revise this last rule?
replaceAll(X, Y, [Z | L1], [Z | L2]) :-
not X = Z, replaceAll(X, Y, L1, L2).
Example. What list is the result of replacing p by m everywhere in the list [p, a, p, a] ? ?- replaceAll(p, m, [p,a,p,a], L).
L = [m,a,m,a].
Transform [s,p,e,e,d] into [p,i,z,z,a]. Exercise.
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021 16/18
The predicate sum(L, S)
The predicate sum(List,S) is true if S is the sum of the numbers in List.
Do case analysis, but explore a few simple cases before arriving at correct recursion. If the input is the empty list, then the sum of its elements is 0.
sum([ ], 0). (*) If the input list has only 1 element X 1, then the sum is simply X 1.
sum([X1], X1).
If the input list has only 2 elements X1 and X2, then the sum is X1 + X2. sum([X1,X2], S) :- S is X1+X2.
If the input list has only 3 elements [X 1, X 2, X 3], then to compute sum, add X 3 to the sum of X1 and X2.
sum([X1,X2,X3], S) :- sum([X1,X2],M), S is X3+M.
For an arbitrary list, compute recursively sum of the tail, and then add the number in the head of input to the intermediate sum.
sum([Head | Tail], S) :- sum(Tail,M), S is Head + M. (**)
Order of computation in this rule is important ! We cannot do addition before the recursive call.
Can remove analysis, and keep only (*) and (**).
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021
The predicate length(List,N)
The predicate length(List,N) is true if N is the number of elements in List.
Do case analysis, but explore a few simple cases before arriving at correct recursion. If the input is the empty list, then its length is 0.
length([ ], 0). (*) If the input list has only one element X 1, then its length is simply 1.
length([X1], 1).
If the input list has only 2 elements X 1 and X 2, then the length is 2. length([X1,X2], L) :- L is 2.
If the input list has only 3 elements [X 1, X 2, X 3], then to compute its length, add 1 to the length of [X 1, X 2].
length([X1,X2,X3], L) :- length([X1,X2],M), L is M+1.
For an arbitrary non-empty list, compute recursively the length of its tail, then add 1.
length([Head | Tail], L) :- length(Tail,M), L is M+1. (**)
Order of computation in this rule is important ! We cannot do addition before the recursive call.
Can remove analysis, and keep only (*) and (**).
CPS721:ArtificialIntelligence (CS/RU) Lists September29,2021 18/18
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com