CODEWITHSUNDEEP
listprologswi-prolog
Choirul R
Choirul R

Reputation: 13

Generate List then Split into Two in Prolog

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.

Upvotes: 1

Views: 76

Answers (3)

slago
slago

Reputation: 5519

A simple and efficient implementation:

separate_odd_even(N, Odd, Even) :-
    odd_even_loop(1, N, Odd, Even).

odd_even_loop(M, N, Odd, Even) :-
    Bool is sign(abs(N-M)),              % reify equality between M and N to avoid non-determinism
    odd_even_case(Bool, M, N, Odd, Even).

odd_even_case(0, M, _, [M], []).         % M and N are equal
odd_even_case(1, M, N, [M|Odd], Even) :- % M and N are different
    M1 is M + 1,
    odd_even_loop(M1, N, Even, Odd).

Examples:

?- separate_odd_even(8, O, E).
O = [1, 3, 5, 7],
E = [2, 4, 6, 8].

?- separate_odd_even(9, O, E).
O = [1, 3, 5, 7, 9],
E = [2, 4, 6, 8].

?- separate_odd_even(3, [1,3], E).
E = [2].

?- separate_odd_even(3, O, [2]).
O = [1, 3].

?- separate_odd_even(3, [1,3], [2]).
true.

?- separate_odd_even(3, [1,2], [3]).
false.

?- time(separate_odd_even(1000000, O, E)).
% 3,000,001 inferences, 0.313 CPU in 0.312 seconds (100% CPU, 9600003 Lips)
O = [1, 3, 5, 7, 9, 11, 13, 15, 17|...],
E = [2, 4, 6, 8, 10, 12, 14, 16, 18|...].

Upvotes: 0

brebs
brebs

Reputation: 4438

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

Upvotes: 0

CapelliC
CapelliC

Reputation: 60014

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.

Upvotes: 1

Related Questions