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

Question

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?

Each clause creates what's called a "choice point" in Prolog. If there's a choice point sitting on the stack, Prolog will give you the option of asking for another answer. Since your predicates are logically correct, this choice point is harmless. Removing these is called making your predicates _deterministic_ and can be a good exercise for learning about the cut (`!`) or `once/1`. — Daniel Lyons, Dec 05 '15 at 23:37

score 7 · Accepted Answer · answered Jan 14 '16 at 16:45

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.

Thanks so much, this is really nice. – Archibald Jan 14 '16 at 17:29 — Archibald, Jan 14 '16 at 17:29

score 1 · Answer 2 · edited May 23 '17 at 10:27

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?

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

2 Answers2