Chapter 7 - Working with lists in Prolog

Question 1

Lists

Answer 1

symbolic structures; sequence of objects that are called elements

Question 2

Lists can help to..

Answer 2

write clauses for predicates that are very similar except for the number of arguments they take

Question 3

Valid lists examples in Prolog

Answer 3

[anna,karenina]
[john,paul,george,ringo,zeppo]
[1,2,3,3,2,1]
[]

Question 4

Can lists contain other lists aswell?

Answer 4

Yes:
[[john,23],[mary,14],[hello]]
[8,john,[’199y’,john]]
[[]]

Question 5

Is a one element list different from the element itself?

Answer 5

Yes:

[anna] is different from anna ;
[[]]is different from[].

Question 6

Head

Answer 6

First element of a non-empty list. Can be anything.

Question 7

Tail

Answer 7

list that is formed by removing the first element from a list
[a,b,c,d] has head a and tail[b,c,d];
[[a],b,[c]] has head [a] and tail [b,[c]];
[a,[b,c]] has head a and tail [[b,c]];

A tail MUST be a list

Question 8

Prolog term

Answer 8

Constant, variable, number and LIST

Question 9

Two ways for Prolog to write lists:

Answer 9

1. A left square parenthesis, followed by a sequence of terms separated by commas and terminated by a right square parenthesis.
2. A left square parenthesis, followed by a nonempty sequence of terms separated by commas, followed by a vertical bar, followed by a term denoting a list, and terminated by a right square parenthesis.

Question 10

List –> [X|Y, Z]

Answer 10

list who head is X and whose tail is the list with head Y and tail Z.

Question 11

Are [1 , X , 3 | [ ] ] and [1,X,3] the same list?

Answer 11

Yes

Question 12

Unification with lists

Answer 12

1. Two lists without variables are considered to unify when they are identical, element for element.
2. Two lists with distinct variables are considered to unify when the variables can be given values that make the two lists identical, element for element.

Question 13

Not-unification with lists

Answer 13

Lists will not unify if they have different numbers of elements or if at least one corresponding element does not unify.

Question 14

Unification with lists take-away

Answer 14

X matches anything, including any list.
[X] matches any list with exactly one element.
[X|Y] matches any list with at least one element.
[X,Y] matches any list with exactly two elements.

Question 15

What will the following query output?

member(X,[a,b,c]).

Answer 15

X=a ;
X=b ;
X=c ;
No

Question 16

What will the following query output?

member(3,L), 1=2.

Answer 16

ERROR: Out of global stack

each time the subquery 1=2, fails, the program backtracks to try to find a new value for L. Since there will always be another value to consider (that is, a bigger list), the process runs until L gets so large that it causes an error.

Question 17

Can variables that are not instantiated be used in lists in Prolog?

Answer 17

Yes, unlike numbers

Question 18

Examples of queries that can be solved with the “append” predicate

Answer 18

1. What pairs of lists when joined give [a,b,c]?
   append(X,Y,[a,b,c]).
2. [a,b] joined to what list L gives [a,b,c,d,e,f]?
   append([a,b],L,[a,b,c,d,e,f]).
3. Solve for the variables X, Y, and L.
   append([X,b],[d|L],[a,_,Y,e,f]).

Question 19

front(L1,L2).

Answer 19

holds if the listL1is the start of listL2:

front(L1,L2) :- append(L1,_,L2).

Question 20

last(E,L).

Answer 20

holds if E is the last element of list L :

last(E,L) :- append(_,[E],L).

Question 21

another version of the member predicate using the append predicate

Answer 21

elem2(E,L) :- append(,[E|],L).

Explanation: is an element of L if L is a list that has some number of elements, then E, then some number of other elements.

Question 22

Will this version of the before predicate run?

before(X,Y,L) :- append(,[X|],Z), append(Z,[Y|_],L).

Answer 22

No, because there are infinitely many lists Z that contain X, and it may turn out that none of them satisfy the second query.

Question 23

Will this version of the before predicate run?

before(X,Y,L) :- append(Z,[Y|],L), append(,[X|_],Z).

Answer 23

Yes, follow this logic:

1. join Z to a list whose head is Y, results in a list L;
2. there is a list Z such that X appears somewhere in Z
   Since 1. specifies that Z comes AFTER Y, then automatically whatever is inside Z (X in this case), also comes after Y.