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?

Solution 1

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.

Solution 2

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([], [], []).

Solution 3

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).

Solution 4

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).

View more solutions

Comments

[SQB]

TO wants numbers in even/odd positions, not with even/odd values.

[CapelliC]

yeah, thanks, maybe I had blind spot while reading the question

[lurker]

This is a nice solution, although not what the OP was asking for: 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...

[SQB]

@mbratch I agree, but there was a flaw in their solution that couldn't easily be rectified, except by adding more kludges like reversing before and after. That's why I added this example: it seems to me as if they are trying to write procedural code in Prolog. I think it's vitally important to teach the proper way of thinking in Prolog.

[SQB]

And, as discussed, we're computing oddity/evenness from the end of the list, which may very well be the requirement, but doesn't sound like it would be.

[SQB]

I just thought of an interesting challenge. Do this for any number of lists, instead of two. So for instance divvy([1,5,4,8,6,4,4,2,0,4], 3, X) ? X = [[1,8,4,4], [5,6,2], [4,4,0]].

[Angelos Chalaris]

Well, I know my solution does not make a lot of sense after trying out for a while, but the problem was mainly why the evaluation failed. So this answers my question why the check was false. It seems to work out now! :)

[Angelos Chalaris]

Thanks for the effort. Although my problem was mainly why the comparison failed, this is a nice solution. However I have found a more elegant one anyway! I was just curious why my solution couldn't get past a certaint point!;)

[mat]

Totally +1. Everything that can be expressed via pattern matching should be expressed via pattern matching. The case of relating a list to its odd/even positions can clearly be expressed via pattern matching, so this solution is very advisable. Notice that you can use this version in all directions, for example: ?- even_odd(List, [a,b,c], [d,e,f])., which is either not possible at all or leads to termination problems with moster other versions and does not work even after applying the suggested corrections.