Even and Odd lists

Question

I am trying to implement a Prolog program that will split a list in two lists. The first one will contain the numbers in even positions and the second one the numbers is odd positions.

E.g.: even_odd([1,2,4,7,5],Even,Odd). will result in Even=[2,7]. and Odd=[1,4,5].

I have found more elegant solutions than mine googling the problem, however I would like to find where the problem lies with in my code (probably operator misuse) because I really think I have a very bad understanding of Prolog operators (especially in arithmetic comparison). Also googling it only makes it worse, every website has a completely different explanation.

My code:

even_odd([], [], []).
even_odd([H|T], Even, Odd) :-
    length([H|T], X),
    X mod 2 is 0,
    append(Even1, H, Even),
    even_odd(T, Even1, Odd).
even_odd([H|T], Even, Odd) :-
    length([H|T], X),
    X mod 2 is 1,
    append(Odd1, H, Odd),
    even_odd(T,Even,Odd1).

I have tried tracing and I know the problem lies in the X mod 2 is 1 or 0, none of them is ever true. If I have a list of three elements and change condition to X is 3 it is completely fine, but the division seems to mess it up, so any ideas?

Answer 1

You can use this

even_odd([], [], []).
even_odd([H|T], [H|Odd1], Even) :-
  1 is H mod 2,
  even_odd(T, Odd1, Even).
even_odd([H|T], Odd, [H|Even1]) :-
  0 is H mod 2,
  even_odd(T, Odd, Even1).

Answer 2

There are a few issues.

First is the one @CapelliC pointed out, which is that the is/2 predicate instantiates a single variable on the left with the value of an expression on the right. The original code has the expression on the left and the value on the right and will always fails. Therefore this:

X mod 2 is 1

Should be changed to:

1 is X mod 2

Or, as @CapelliC says, X mod 2 =:= 1.

Second, your append attempts to append a single element to a list. append only operates on lists. So this:

append(Odd1, H, Odd)

Should be

append(Odd1, [H], Odd)

Third, the ordering of append and the recursive even_odd call will cause an issue:

append(Odd1, [H], Odd),
even_odd(T,Even,Odd1).

Odd1 is uninstantiated when append is called, as is Odd. This generates an infinite number of solutions for the append before an acceptable answer can be bound by the base case, resulting in a stack overflow. The simple solution to this is to swap them:

even_odd(T, Even, Odd1),
append(Odd1, [H], Odd).

This will function now, but yields results in the opposite order:

| ?- even_odd([1,2,3,4,5,6], E, O).

E = [5,3,1]
O = [6,4,2] ? ;

The easiest thing to fix that is to prepend rather than append. Replace

append(Odd1, [H], Odd)

With

Odd = [H|Odd1]

Or simply include that in the head of the clause. The final clauses, with all the fixes, then look like:

even_odd([], [], []).
even_odd([H|T], [H|Even1], Odd) :-
    length([H|T], X),
    0 is X mod 2,
    even_odd(T, Even1, Odd).
    %%Even = [H|Even1].   % equivalent to append([H], Even1, Even)
even_odd([H|T], Even, [H|Odd1]) :-
    length([H|T], X),
    1 is X mod 2,
    even_odd(T, Even, Odd1).
    %%Odd = [H|Odd1].   % equivalent to append([H], Odd1, Odd)

Yielding

| ?- even_odd([1,2,3,4,5,6], E, O).

E = [1,3,5]
O = [2,4,6] ? ;

no

Finally, there's another issue: the parity of the lists is being determined from the end of the list rather than the beginning. This is due to the logic of using length on the current list fragment as a means of determining parity.

To resolve this, within the given code structure (again, side-stepping the more natural solution that @ATS presented), you'd really need to count/index from the beginning. Looking at it verbosely, that would lead us to a solution like this:

even_odd(L, Even, Odd) :-
    even_odd(L, 1, Even, Odd).
even_odd([], _, [], []).
even_odd([H|T], C, [H|Even1], Odd) :-
    0 is C mod 2,
    C1 is C + 1,
    even_odd(T, C1, Even1, Odd).
even_odd([H|T], C, Even, [H|Odd1]) :-
    1 is C mod 2,
    C1 is C + 1,
    even_odd(T, C1, Even, Odd1).

Which gives:

| ?- even_odd([1,2,3,4,5,6], E, O).

E = [2,4,6]
O = [1,3,5] ? a

no

It's a working solution, but not at all optimal since it doesn't take advantage of the "knowledge" of the list position in the code (redundantly introduces a count or index to know where we're at in the list).

Answer 3

While CapelliC has the right idea about why your code fails, he misunderstood your question about wanting the even/odd positions.

The problem is, you're calculating those from the end of the list, so even_odd([1,2,4,7],Even,Odd). will result in Even=[1,4]. and Odd=[2,7]. which is not what you want.
A solution would be reversing the list before processing and reversing the results afterwards, or taking a different approach.

Here, we start by adding the first element to the odd list, and then alternating between adding to the even and to the odd list, until we've reached the final element.

even_odd(List, Even, Odd) :- 
    % First position is odd
    even_odd_odd(List, Even, Odd).

% We handle the odd position, the next is even
even_odd_odd([H|T], Even, [H|Odd]) :- 
    even_odd_even(T, Even, Odd).
even_odd_odd([], [], []).

% We handle the even position; the next is odd
even_odd_even([H|T], [H|Even], Odd) :- 
    even_odd_odd(T, Even, Odd).
even_odd_even([], [], []).

Answer 4

Arithmetic evaluation operator (is)/2 performs arithmetic on the right expression, and unify it with its left argument, and you apply the test to the wrong variable. Should be

even_odd([H|T],Even,Odd):- 0 is H mod 2,...

Alternatively, there is (=:=)/2 that performs arithmetic on both sides. Then could be

H mod 2 =:= 0

Moreover, the way you process lists doesn't make much sense. You must put an even value in Even list. Then something like

even_odd([H|T],[H|Even],Odd):- 0 is H mod 2,...

would make more sense.