Generate List then Split into Two in Prolog-CodePudding

I am a complete amateur on Prolog so my question might be very basic. I want to automatically generate a list from 1 to N, then split it into even and odd, from just one integer input (so I don't input the list manually). Let's say I input 5, then the result should be like this: X = [1,3,5] Y = [2,4] Doesn't matter which one is X, which one is Y.

How should I tackle this problem?

I know the built-in function to generate list is numlist(1,5,L). I also found an answer on how to split the list here

I tried to combine those two like this separate_even_odd(N) :- numlist(1,N,L), separate_even_odd(L, X, Y). Then call the function separate_even_odd(5).

All i got is True.

Ultimately I want to append the odd list to the even list but let's put that on another story. For now, I just want it splitted.

CodePudding user response：

SWI-Prolog has a library predicate partition/4 that seems it's done to fulfill your needs:

separate_even_odd(Integers, Even, Odd) :-
  partition(integer_is_even, Integers, Even, Odd).
integer_is_even(I) :- I mod 2 =:= 0.

Instead of providing the service predicate integer_is_even/1, we could as well use the lambda library(yall):

separate_even_odd(Integers, Even, Odd) :-
  partition([I] >> (I mod 2 =:= 0), Integers, Even, Odd).

and we get

?- numlist(1,5,L), separate_even_odd(L, Even, Odd).
L = [1, 2, 3, 4, 5],
Even = [2, 4],
Odd = [1, 3,

Just to illustrate some of the unusual constructs of Prolog (unification and if/then/else), take a look at a simple implementation, in procedural style, without library predicates:

list_with_separate_even_odd(IntegerLow, IntegerHigh, Even, Odd) :-
    (   IntegerLow > IntegerHigh
    ->  Even = [], Odd = []
    ;   (   IntegerLow mod 2 =:= 0
        ->  Even = [IntegerLow|RestEven], Odd = RestOdd
        ;   Even = RestEven, Odd = [IntegerLow|RestOdd]
        ),
        LowSucc is IntegerLow   1,
        list_with_separate_even_odd(LowSucc, IntegerHigh, RestEven, RestOdd)
    ).

Note in particular how =/2 performs unification, not assigment.

CodePudding user response：

Alternative method, with an introduction to difference lists due to "Ultimately I want to append the odd list to the even list":

between_evens_odds(Upper, Evens, EvensTail, Odds) :-
    integer(Upper),
    Upper @>= 1,
    between_evens_odds_(1, Upper, Evens, EvensTail, Odds).

between_evens_odds_(Upto, Upper, Evens, EvensTail, Odds) :-
    compare(Comp, Upper, Upto),
    between_evens_odds_comp_(Comp, Upto, Upper, Evens, EvensTail, Odds).

between_evens_odds_comp_(<, _Upto, _Upper, EvensTail, EvensTail, []).
% Started with 1, so final number will also be odd
between_evens_odds_comp_(=, Upto, _Upper, EvensTail, EvensTail, [Upto]).
between_evens_odds_comp_(>, Upto, Upper, [Upto1|Evens], EvensTail, [Upto|Odds]) :-
    Upto1 is Upto   1,
    Upto2 is Upto   2,
    between_evens_odds_(Upto2, Upper, Evens, EvensTail, Odds).

Results in swi-prolog:

% Using 0 as an example - it of course fails
?- between(0, 6, Upper), between_evens_odds(Upper, Ev, EvT, Od).
Upper = 1,
Ev = EvT,
Od = [1] ;
Upper = 2,
Ev = [2|EvT],
Od = [1] ;
Upper = 3,
Ev = [2|EvT],
Od = [1, 3] ;
Upper = 4,
Ev = [2, 4|EvT],
Od = [1, 3] ;
Upper = 5,
Ev = [2, 4|EvT],
Od = [1, 3, 5] ;
Upper = 6,
Ev = [2, 4, 6|EvT],
Od = [1, 3, 5].

Here's the magic of difference lists - since we've already iterated through the list of Evens to the end, we can grab the tail of Evens, rather than iterate through all of Evens yet again using append, for performance:

?- between_evens_odds(5, Ev, EvT, Od), EvT = Od.
Ev = [2, 4, 1, 3, 5],
EvT = Od, Od = [1, 3, 5].