Lists may have repeated elements
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. Here are some examples:
Copyright By PowCoder代写 加微信 powcoder
• [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]
The list with no elements. The empty list.
• [[john, 23], [mary, 14], [hello]]
A three element list whose elements are also lists
• [1, john, [199Y, john]]
Note: a one element list is different from the element: [anna] is different from anna and [[anna]] .
cps721 Artificial Intelligence © Lists 1
Artificial Intelligence © Lists 2
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 elements at the front from a list formed of the remaining ones
For example, [a, b, c, d] can be 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 | [ ]]
Matching goals to rules
When Prolog has a goal it is working on, it must find a clause in the program to use.
For example, if we have the goal
we need to find a clause like
or p(X,Y) :- … or p(W,b) :- …
A clause in the program like
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=aandU=b).
We now consider how this matching should work for lists.
cps721 Artificial Intelligence © Lists 3
with X=a, Y=[b], Z=c, W=[e].
Artificial Intelligence © Lists 4
[ ] and [ ].
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.
Some matching pairs:
[a, b, c] and [a, b, c].
[X] and [a] with X = a.
[X] and [Y] with X=_978, Y=_978.
[a,b,c] and [a,X,Y] with X=b, Y=c.
[a,b,a] and [X,b,X] with X=a.
[a|[b,c]] and [a,b,c].
[a|[b|[c]]] and [a|[b,c]].
[X|Y] and [a] with X=a, Y=[ ].
[a|[b,c]] and [a|X] with X=[b, c].
[a|[b,c]] and [a,X,Y] with X=b, Y=c.
[a,b,c] and [X|Y] with X=a, Y=[b,c].
[X,Y|Y] and [a,[b,c],b,c] with X=a, Y=[b,c].
[a,b] and [a,X|Y] with X=b, Y=[]. [[a,b],[c,d,e]] and [[X|Y],[Z,d|W]]
Non-matching lists
Lists do not match if they have different numbers of elements, of if at least one corresponding element soes not match.
Some non-matching pairs: [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 [].
X matches anything, including any list.
[X] only matches a list with one element.
[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 clauses of Prolog programs
cps721 Artificial Intelligence © Lists 5
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]). head(W,[ ]).
head(a,[H,b]). head(a,[b,c,a]). H = a . no
Because the second argument must be a list with at least one element, we can use [X|Y].
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]).
cps721 Artificial Intelligence © Lists 6
Another predicate
Now consider a predicate that holds iff its single argument is a list with at least three elements:
at_least_three_elements([a,_,c,d]).
at_least_three_elements([_,_]).
at_least_three_elements([X,e,Z]). X = _568 Z = _659 .
A definition that works is:
at_least_three_elements([A,B,C|_]).
or just as good:
at_least_three_elements([_,_,_|_]).
Now we turn our attention to more complex predicates on lists, whose definition requires more than 1 clause and with a non-empty body.
cps721 Artificial Intelligence © Lists 7
Artificial Intelligence © Lists 8
List membership
The predicate member(E,L) holds when E is an element of list L. It is defined by two clauses:
/* E is a member of any list whose first
element is E */
member(E, [E|_]).
/* If E is a member of list L, then it is
a member of any list whose tail is L */
member(E, [_|L]) :- member(E, L).
member(a, [b, c, a, d]).
member(a, [c, a, d]).
member(a, [a, d]).
Artificial Intelligence ©
success X =a
member(X,[b, c]).
More on member member(X, [a, b, c]).
success X =b
member(X,[c]).
member(X,[a,b,c]). X=a ;
success X= c
Appending two lists
The predicate append(L1,L2,L) holds when L is the result of joining lists L1 and L2 together.
For example, these goals should all succeed:
append([a,b],[c,d,e],[a,b,c,d,e])
append([ ],[a,b],[a,b])
append([a,b],[ ],[a,b])
append([ ],[ ],[ ])
The program has two clauses:
/* Appending a list L to the empty list
produces the list L itself */
append([ ], L, L).
/* If appending L2 to L1 gives the list L,
then appending L2 to the list [H|L1]
gives the list [H|L]. */
append([H|L1], L2, [H|L]) :-
append(L1, L2, L).
These two clauses are sufficient since they describe the predicate for all possible arguments by considering the two cases for the first argument: an empty list and a list with at least one element.
cps721 Artificial Intelligence © Lists 10
Solve for the query variable L: L = [a | L3]
L = [a,b,c,d,e]
SoLis which is
[a | [b | [c,d,e]]] [a,b,c,d,e].
L3 = [b | L4]
L4 = [c, d, e]
cps721 Artificial Intelligence ©
Using append
append([a,b], [c,d,e], L).
append([b], [c,d,e], L3). L3 = [b | L4]
append([ ], [c,d,e], L4). L4 = [c,d,e]
L = [a | L3]
Fun with append
What list, when [d,e,f] is appended to it, gives the list [a,b,d,e,f]?
append(L, [d,e,f], [a,b,d,e,f]). L = [a,b].
What list, when appended to [a,b], gives the list [a,b,d,e,f]?
append([a,b], L, [a,b,d,e,f]). L = [d,e,f].
Solve the equation append(X,Y,[a,b,c]): append(X,Y,[a,b,c]).
X = [a,b,c] Y = [ ] ; no
Y = [a,b,c] ; Y = [b,c] ;
No other programming language can do this kind of thing!
cps721 Artificial Intelligence © Lists 12
Defining intersection using
It is sometimes convenient to treat lists with no duplicate elements as sets and then perform set operations on them.
The predicate intersection(L1,L2,L) holds when L is the list of all elements common to lists L1 and L2. It can be defined by:
intersection([],L,[]).
intersection([E|L1],L2,[E|L]) :-
member(E,L2),
intersection(L1,L2,L).
intersection([E|L1],L2,L) :-
not member(E,L2),
intersection(L1,L2,L).
This definition is correct. But as we will see when we look at an example, that it does some needless work.
A more efficient definition in Prolog is possible, but we will not consider it here.
cps721 Artificial Intelligence © Lists 13
member(a, [c,d,b]) eventually fails.
member(a, [c,d,b]) eventually fails.
Artificial Intelligence ©
An example intersection
member(a, [c,d,b]), intersection([b,c], [c,d,b], L).
not member(a, [c,d,b]), intersection([b,c], [c,d,b], List).
intersection([a,b,c], [c,d,b], List). List = [a | L]
intersection([b,c], [c,d,b], List). List = [b | List1]
member(b, [c,d,b]), intersection([c], [c,d,b] ,List1).
Note: whenever member fails, it ends up being considered twice on the same arguments
intersection([c], [c,d,b], List1). List1 = [c | List2]
member(c, [c,d,b]), intersection([ ], [c,d,b], List2).
intersection([ ], [c,d,b], List2). List2 = [ ]
success List = [b,c]
Defining new predicates using
E is the last element of list L:
The member predicate:
/* E is the last element of L if L is the
result of appending [E] to some list */
last(E,L) :- append(_,[E],L).
The list L1 is at the front of list L2:
front(L1,L2) :- append(L1,_,L2).
member(E,L) :- append(_,[E|_],L).
The list L can be broken into three lists, Front, Middle, and End:
break(L,Front,Middle,End) :-
append(Front,Middle,Temp),
append(Temp,End,L).
An element X appears before Y in a list L:
before(X,Y,L) :-
break(L,_,[X|_],[Y|_]).
cps721 Artificial Intelligence © Lists 15
Artificial Intelligence © Lists 16
append(L1, [c|_], [c,d]). L1 = [ ]
An example of before
before(a, c, [a,b,c,d]).
break([a,b,c,d] ,_, [a|_], [c|_]).
append(_, [a|_], Temp), append(Temp, [c|_], [a,b,c,d]). Temp = [a | _]
append([a|_], [c|_], [a,b,c,d]).
append(_, [c|_], [b,c,d]).
Blocks world using lists
Represent each pile of blocks with a top-to-bottom list, and the scene itself by a left-to-right list of piles.
scene([[b1,b2],[b3,b4,b5,b6],[b7]]). We can then define the predicates on, above, left
and others using list predicates:
on_table(X) :- scene(Piles),
member(Pile,Piles),
last(X,Pile).
above(X,Y) :- scene(Piles),
member(Pile,Piles),
before(X,Y,Pile).
on(X,Y) :- scene(Piles),
member(Pile,Piles),
append(_,[X,Y|_],Pile).
left(X,Y) :- scene(Piles),
before(Pile1,Pile2,Piles),
member(X,Pile1),
member(Y,Pile2).
cps721 Artificial Intelligence © Lists 17
A blocks world example
Skipping many steps …
member(b7,[b3,b4,b5,b6])
member(b7,[b7])
Notice how backtracking is
used here: we generate a Pile1 and
a later Pile2, then test b1 and b7 for membership.
If they do not contain b1 and b7, we backtrack and choose new piles.
This is often called nondeterministic programming.
left(b1,b7)
scene(Piles), before(…), member(b1,Pile1), member(b7,Pile2) Piles = [[b1,b2],[b3,b4,b5,b6],[b7]]
before(Pile1,Pile2,…), member(b1,Pile1), member(b7,Pile2) Pile1 = [b1,b2]
Pile2 = [b3,b4,b5,b6]
Pile1 = [b1,b2] Pile2 = [b7]
member(b1,[b1,b2]), member(b7,[b3,b4,b5,b6])
member(b1,[b1,b2]), member(b7,[b7])
cps721 Artificial Intelligence © Lists 18
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com