CODEWITHSUNDEEP
listprolog
Sia Nravoha
Sia Nravoha

Reputation: 35

What does this code mean and do?

I am completely new to Prolog and I can't understand this piece of code. How would you read these 4 clauses? What do they do? 

a([]). 
a([_|L]):-b(L).

b([_]).
b([_|L]):-a(L).

Thank you.

Upvotes: 1

Views: 103

Answers (2)

lurker
lurker

Reputation: 58324

As @repeat suggested in his comment, run a general query, and here's what you get:

| ?- a(Xs).

Xs = [] ? ;

Xs = [_,_] ? ;

Xs = [_,_] ? ;

Xs = [_,_,_,_] ? ;

Xs = [_,_,_,_] ? ;

Xs = [_,_,_,_,_,_] ? ;

Xs = [_,_,_,_,_,_] ? ;
...

And:

| ?- b(Xs).

Xs = [_] ? ;

Xs = [_] ? ;

Xs = [_,_,_] ? ;

Xs = [_,_,_] ? ;

Xs = [_,_,_,_,_] ? ;

Xs = [_,_,_,_,_] ? ;

Xs = [_,_,_,_,_,_,_] ? ;

Xs = [_,_,_,_,_,_,_] ? ;
...

So a(Xs) succeeds if Xs is a list containing an even number of elements, and b(Xs) succeeds if Xs is a list containing an odd number of arguments. As you can see, a/1 and b/1 succeed twice in each case except a([]). which succeeds only once. So it is not an efficient predicate for determining list length parity.

Let's rewrite these with more descriptive names:

even([]).
even([_|L]) :- odd(L).
odd([_]).
odd([_|L]) :- even(L).

Now let's "read" what they say:

  1. [] is an even list
  2. [_|L] is an even list if L is an odd list
  3. [_] is an odd list
  4. [_|L] is an odd list if L is an even list

These sound logical, but why do even/1 and odd/1 succeed twice with the exception of even([])? If you look at the definition of odd/1, there are two ways for [_] to succeed. One is via the odd([_]). clause. The second is by the second odd/1, since you would have:

odd([_|[]]) :- even([]).  % [_] == [_|[]]

Since both even/1 and odd/1 calls (with the exception of even([]).) eventually recurse down to a call to odd([_]), you'll get two solutions.

One way to eliminate the ambiguity in the logic is to refactor them a little. Consider the following recursive rules:

  • A list of at least 2 elements has an even number of elements if the tail of the list, after the first 2, is also even.
  • A list of at least 2 elements has an odd number of elements if the tail of the list, after the first 2, is also odd.

Translating these rules to Prolog, including the base cases as before:

even([]).
even([_,_|L]) :- even(L).
odd([_]).
odd([_,_|L]) :- odd(L).

Now the results will be:

| ?- even(Xs).

Xs = [] ? ;

Xs = [_,_] ? ;

Xs = [_,_,_,_] ? ;

Xs = [_,_,_,_,_,_] ? ;
...

And

| ?- odd(Xs).

Xs = [_] ? ;

Xs = [_,_,_] ? ;

Xs = [_,_,_,_,_] ? ;
...

Following CapelliC's suggestion of using a DCG, similar rules can be written:

even --> [] | [_,_], even.
odd --> [_] | [_,_], odd.

With results:

| ?- phrase(even, L).

L = [] ? ;

L = [_,_] ? ;

L = [_,_,_,_] ? ;
...

And

| ?- phrase(odd, L).

L = [_] ? ;

L = [_,_,_] ? ;

L = [_,_,_,_,_] ? ;
...

Following @false's suggestion, an even more direct "fix" to the original code would be to eliminate the redundant base case for odd([_]). since it's already covered by the base case for even([]). This is also a little simpler than the above solution since it takes advantage of the interdependency between the even/1 and odd/1 predicates (in the above solution, even/1 and odd/1 stand on their own).

even([]).
even([_|L]) :- odd(L).
odd([_|L]) :- even(L).

Or, in DCG:

even --> [] | [_], odd.
odd --> [_], even.

Upvotes: 1

CapelliC
CapelliC

Reputation: 60034

the argument schema is important:

a) the list is clearly a counter, since we never consider the content.

b) just a suggestion: read logic as productions, or as DCG

a-->[];[_],b.
b-->[_];[_],a.

to be called - for instance

?- phrase(a, [w,h,a,t]).

Upvotes: 1

Related Questions