Prolog: obtain a list with two sublists, containing the odd position elements and the even position elements. How to Improve this code

1
votes

I would like to ask, if anyone knows how to improve (if it's not optimal) this code.

The idea, is that you have a list of elements, and I want to return a list, with two sublists inside it, the first sublist should contain the elements that are contained in the odd positions of the list, and the second sublist should contain, the elements that are contained in the even positions of the list.

Some examples:

?-evenAndOdd([1,2,3,4,5],[[1,3,5],[2,4]])
True.

?-evenAndOdd([a,b,c,d,e],[[a,c,e],[b,d]]).
True.

The code I have implemented is the next one:

evenAndOdd([],[]).

evenAndOdd([H|R],NL):-
    evenAndOddRec([H|R], [[],[]],1,NL).


evenAndOddRec([], [LOdd,LEven],_,[LOdd,LEven]).

evenAndOddRec([H|R],[LOdd,LEven],Pos,NL):-
    \+ even(Pos),
    !,
    NPos is Pos +1,
    append(LOdd,[H],NLOdd),
    evenAndOddRec(R,[NLOdd,LEven],NPos,NL).

evenAndOddRec([H|R],[LOdd,LEven],Pos,NL):-
    NPos is Pos + 1,
    append(LEven, [H], NLEven),
    evenAndOddRec(R,[LOdd, NLEven],NPos,NL).



even(N):-
    N mod 2 =:=0.
2
prolog
This looks like a duplicate, but I could not find it, but that does not mean it is not a duplicate. While you are using [LOdd,LEven], consider instead [LOdd,LEven|Rest]. In other words, throw out your code and start with the concept of [LOdd,LEven|Rest] and build your predicates up on that. - Guy Coder

2 Answers

4
votes

You can implicitly determine even and odd values upon recursion, by taking two elements at a time (and taking into account when the has an odd number of elements):

evenAndOdd(L, [LOdd, LEven]):-
  evenAndOdd(L, LOdd, LEven).

evenAndOdd([], [], []).
evenAndOdd([Odd], [Odd], []).
evenAndOdd([Odd,Even|Tail], [Odd|LOdd], [Even|LEven]):-
  evenAndOdd(Tail, LOdd, LEven).
3
votes

One symptom that the code is not optimal is that it will run off into the woods if you ask for an additional solution in the -,+,+ instantiation pattern:

?- evenAndOdd(X, [[1,3,5], [2,4,6]]).
X = [1, 2, 3, 4, 5, 6] ;
<time passes>

This kind of thing is a frequent occurrence when manually trying to match up lists with indexes in Prolog.

Stylistically, I would rather not give back a list containing exactly two lists when I could just have three arguments instead of two; this is, after all, a relationship between three lists, the combined list and the even and odd items.

Additionally, just eyeballing it, I'm not sure why any arithmetic or any cuts are needed here. This is how I would implement it:

evenAndOdd([], [], []).
evenAndOdd([O], [O], []).
evenAndOdd([O,E|Rest], [O|ORest], [E|ERest]) :- evenAndOdd(Rest, ORest, ERest).

This works with many instantiations:

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

?- evenAndOdd([1,2,3,4,5], O, E).
O = [1, 3, 5],
E = [2, 4] ;
false.

?- evenAndOdd(X, [1,3,5], [2,4]).
X = [1, 2, 3, 4, 5] ;
false.

?- evenAndOdd(X, [1,3,5], [2,4,6]).
X = [1, 2, 3, 4, 5, 6].

?- evenAndOdd(X, [1,3,5], [2,4,6,8]).
false.

?- evenAndOdd([1,2,3,4,5,6], X, [2,4,6,8]).
false.

?- evenAndOdd([1,2,3,4,5,6], X, [2,4,6]).
X = [1, 3, 5].