Segregating Lists in Prolog

Question

I am having a really hard time understanding how to get my code to show my segregated lists consisting of even and odd numbers. I am not even sure what my understanding is lacking. I am new to this language obviously and must use it for school. My imperative and functional mind won't let me know what the hell is going on with this lol.

Now, no I am not asking you to do my homework! I am simply asking you to help me see what my lack of understanding is. I have also looked up similar answers but I cannot convert them to the way I am supposed to write this function.

Please, once more, do not bash me for this like I have previously usually been bashed. Please just help me see what my understanding is lacking. Do not just give me answers and code snippets without explaining it please.

Here it is:

is_even(H) :-
   0 is mod(H, 2).

segregate(List, Even, Odd) :- segregator(List, Even, Odd).

segregator([], [], []).
segregator([H|T], E, O) :-
    is_even(H),
    % I feel here is where I am supposed to build the list, 
    % but I have no clue how since Even or Odd has not been unified.
    segregator(T, E, O),
    write('Even is '), write(E), nl.
segregator([H|T], E, O) :-
    % Same here as above.
    segregator(T, E, O),
    write('Odd is '), write(O), nl.

Your `is_even` predicate looks fine. Your `segregate(List, Even, Odd) :- segregator(List, Even, Odd).` doesn't hurt anything, but it serves no purpose. `segregator([], [], [])` is a correct base case. What you need now would be to fix your other two `segregator` rules which right now don't provide any direction on what `E` and `O` consist of. Think recursively. If `H` is even, what should `E` and `O` look like in `segregator([H|T], E, O)`? What happens to `H`? And what happens to `H` if it is not even (`\+ is_even(H)` succeeds - which you'll probably want in your 3rd `segregator` clause). — lurker, Apr 04 '15 at 22:02
So to be clear, your second `segregator/3` clause is describing the relation between the lists when the head of the first list is even. So it would say, `segregator([H|T], [H|E], O) :- is_even(H), ...`. In your 3rd clause, you'll want the odd case. So check `\+ is_even(H)`. — lurker, Apr 04 '15 at 22:50
Thank you very much guys! I knew I was going in the right direction with my logic, but unifying the lists has been my problem this entire time. I couldn't quite wrap my head around why I couldn't unify them. — James Combs, Apr 05 '15 at 22:51

score 4 · Accepted Answer · edited May 23 '17 at 12:15

A logically pure implementation is very straight-forward, thanks to clpfd:

:- use_module(library(clpfd)).

list_evens_odds([],[],[]).
list_evens_odds([X|Xs],[X|Es],Os) :-
   X mod 2 #= 0,
   list_evens_odds(Xs,Es,Os).
list_evens_odds([X|Xs],Es,[X|Os]) :-
   X mod 2 #= 1,
   list_evens_odds(Xs,Es,Os).

Some sample queries we expect to succeed (with a finite sequence of answers):

?- Xs = [1,2,3,4,5,6,7], list_evens_odds(Xs,Es,Os).
Xs = [1,2,3,4,5,6,7],
Es = [  2,  4,  6  ],
Os = [1,  3,  5,  7] ;
false.

?- list_evens_odds(Ls,[2,4],[1,3]).
Ls = [2,4,1,3] ? ;
Ls = [2,1,4,3] ? ;
Ls = [2,1,3,4] ? ;
Ls = [1,2,4,3] ? ;
Ls = [1,2,3,4] ? ;
Ls = [1,3,2,4] ? ;
no

What about queries we expect to fail?

?- list_evens_odds(Ls,[2,4,5],[1,3]).
no
?- list_evens_odds(Ls,[2,4],[1,3,6]).
no
?- list_evens_odds([_,_,_],[2,4],[1,3]).
no

At last, the most general query:

?- assert(clpfd:full_answer).
yes

?- list_evens_odds(Ls,Es,Os).
Ls = [],   Es = [],   Os = []                              ? ;
Ls = [_A], Es = [_A], Os = [], _A mod 2#=0, _A in inf..sup ? ...

Edit 2015-05-06

Here's another way to do it with logical-purity!

Use the meta-predicate tpartition/4 together with zeven_t/2 or zodd_t/2.

bool01_t(1,true).
bool01_t(0,false).

zeven_t(Z,Truth) :- Z mod 2 #= 0 #<==> B, bool01_t(B,Truth).

%zodd_t(Z,Truth) :- Z mod 2 #= 1 #<==> B, bool01_t(B,Truth).
zodd_t(Z,Truth)  :- Z mod 2 #=         B, bool01_t(B,Truth). % tweaked

zeven_t/2 reifies the evenness of an integer, zodd_t/2 the oddness.

With everything in place, let's run some queries!

?- tpartition(zeven_t,[1,2,3,4,5,6,7],Es,Os).
Es = [2,4,6], Os = [1,3,5,7].
?- tpartition(zodd_t ,[1,2,3,4,5,6,7],Os,Es). % argument order differs
Es = [2,4,6], Os = [1,3,5,7].

Both succeed deterministically. The equivalent query using list_evens_odds/3 does not.

Segregating Lists in Prolog

1 Answers1

Edit 2015-05-06

Linked