CODEWITHSUNDEEP
prolog
Archibald
Archibald

Reputation: 456

How to tell if list length is odd or even in Prolog

I'm attempting to determine whether a Prolog list has an odd or even number of elements. I realize there are likely better solutions using length/2 and I would be willing to mark a better solution than this one the right answer, I would just like to know what I am doing wrong in this example.

I have code detailed as:

oddSize([]) :-
    false.
oddSize([_]).
oddSize([_,_|T]) :-
    oddSize(T).

The output I receive when I attempt to test this code is:

1 ?- oddSize([]).
false.

2 ?- oddSize([1]).
true ;
false.

3 ?- oddSize([1,2]).
false.

4 ?- oddSize([1,2,3]).
true ;
false.

It seems to be detecting which of the lists have an odd number of elements, but why do I get the extra result of false?

Upvotes: 2

Views: 5119

Answers (2)

Paulo Moura
Paulo Moura

Reputation: 18663

Note that you can define an odd_size/1 predicate that succeeds at most once, i.e. without leaving any choice-point (*):

odd_size([_| Tail]) :-
    even_size(Tail).

even_size([]).
even_size([_| Tail]) :-
    odd_size(Tail).

(*) Assuming that your Prolog systems uses first-argument indexing (true for modern systems), which avoids creating a choice-point when calling the even_size/1 predicate with an instantiated argument.

Some sample queries:

?- odd_size([1,2,3]).
true.

?- odd_size([1]).
true.

?- odd_size([1,2]).
false.

Upvotes: 7

K. Shea
K. Shea

Reputation: 107

It looks to me like your code is correct, I think you are just misunderstanding Prolog's output. I've found a more comprehensive response from someone else on stackoverflow and linked it below. Sorry, I'm new to stackoverflow so I don't know how best to link it.

"This answer is correct. In Prolog, the order in which your facts are rules are written determines the order they will be found by a query. More specifically, the 'backtrack' option ";" essentially tells forces the query engine to discard the returned result and answer the question "are there any other answers?". So, it is not that f(a,b) is both true and false; but rather that it is true and if you choose to ignore that result the engine will tell you there are no other f(a,b) fact entries. To prove this, watch what happens if you add a second f(a,b) fact." – Assaf Jul 24 '10 at 2:17

Source: Why is this prolog query both true and false?

Upvotes: 1

Related Questions