Prolog code to split parts of a list into consecutive even and odd parts

Question

I've been given the following question:

Any list of integers can (uniquely) be broken into "parity runs" where each run is a (maximal) sequence of consecutive even or odd numbers within the original list. For example, the list List = [8,0,4,3,7,2,-1,9,9] can be broken into [8, 0, 4], [3, 7], [2] and [-1, 9, 9] Write a predicate paruns(List, RunList) that converts a list of numbers into the corresponding list of parity runs. For example:

?- paruns([8,0,4,3,7,2,-1,9,9], RunList).
RunList = [[8, 0, 4], [3, 7], [2], [-1, 9, 9]]

Here was the code which I tried and it seems to work with the above sample case, thanks to one suggestion, but I've got an issue where when I run paruns([8,0,4], RunList). it prints RunList = [[8,0,4],[]]. Any suggestions would be appreciated :)

paruns([],[]).
paruns([Head | Tail], [E, O | S]) :-
   even([Head | Tail], E, Last),
   odd(Last, O, Last1),
   paruns(Last1, S).

even([Head | Tail], [], [Head | Tail]) :-
   Head mod 2 =:= 1.
even([Head | Tail], [Head | L], Last) :-
   Head mod 2 =:= 0,
   even(Tail, L, Last).
even([],[],[]).

odd([Head | Tail], [], [Head, Tail]) :-
   Head mod 2 =:= 0.
odd([Head | Tail], [Head | L], Last) :-
   Head mod 2 =:= 1,
   odd(Tail, L, Last).
odd([],[],[]).

score 4 · Answer 1 · answered Mar 30 '17 at 13:07

A major attraction of Prolog is its relational nature. This means that we can often use a Prolog predicate in several directions, if only we stick to sufficiently general primitives.

In this concrete case, since you are reasoning over integers, I highly recommend you use your Prolog system's CLP(FD) constraints to benefit from this generality. Please see clpfd for more information about this important declarative feature.

In addition, since you are describing a list, consider using DCG notation (dcg).

Here is a relational solution for your task:

parity_runs([], [])     --> [].
parity_runs([E|Es], Os) --> [E], { E mod 2 #= 0 }, parity_runs(Es, Os).
parity_runs(Es, [O|Os]) --> [O], { O mod 2 #= 1 }, parity_runs(Es, Os).

We can use it for the test case you posted, where the list is specified:

?- phrase(parity_runs(Es, Os), [8,0,4,3,7,2,-1,9,9]).
Es = [8, 0, 4, 2],
Os = [3, 7, -1, 9, 9] ;
false.

Moreover, we can also use it in other directions. For example, suppose that the runs are known, but the list isn't:

?- phrase(parity_runs([2,4], [1,3]), Ls).
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] ;
false.

Moreover, we can also post the most general query, where nothing is known:

?- phrase(parity_runs(Es, Os), Ls).
Es = Os, Os = Ls, Ls = [] ;
Es = Ls, Ls = [_2012],
Os = [],
_2012 mod 2#=0 ;
Es = Ls, Ls = [_256, _258],
Os = [],
_256 mod 2#=0,
_258 mod 2#=0 ;
Es = Ls, Ls = [_826, _832, _838],
Os = [],
_826 mod 2#=0,
_832 mod 2#=0,
_838 mod 2#=0 ;
etc.

To fairly enumerate answers, we can use iterative deepening:

?- length(Ls, _), phrase(parity_runs(Es, Os), Ls).
Ls = Es, Es = Os, Os = [] ;
Ls = Es, Es = [_168],
Os = [],
_168 mod 2#=0 ;
Ls = Os, Os = [_550],
Es = [],
_550 mod 2#=1 ;
Ls = Es, Es = [_770, _776],
Os = [],
_770 mod 2#=0,
_776 mod 2#=0 ;
Ls = [_770, _776],
Es = [_770],
Os = [_776],
_770 mod 2#=0,
_776 mod 2#=1 ;
etc.

thanks for all the advice, i actually went out and learnt about clpfd today and i can see its got a lot of use! i've actually just started prolog and coming from C its quite a difference but your write up was very educative! thanks again! :) — Iza, Mar 31 '17 at 09:15

repeat · Answer 2 · 2017-10-28T20:13:36.507

TL;DR: Find the "right peg" for the "hole" in meta-predicate split_if_adj/3 and you're done!

This answer is based upon:

clpfd (Constraint Logic Programming over Finite Domains),
```
:- use_module(library(clpfd)).
```
reified term equality (=)/3,
```
:- use_module(library(reif)).
```
meta-predicate split_if_adj/3 (defined in a previous answer),

and the reified condition predicate dif_parity_t/3:

dif_parity_t(X, Y, T) :-
   (X+Y) mod 2 #= M,
   =(M,1,T).                  % reified term equality

So, basically, we're delegating the cumbersome and sometimes tricky task of handling lists recursively to a higher-order predicate which we customize appropriately.

Sample query:

?- split_if_adj(dif_parity_t, [8,0,4,3,7,2,-1,9,9], Rss).
Rss = [[8,0,4],[3,7],[2],[-1,9,9]].

Note that above query succeeds deterministically.

CapelliC · Accepted Answer · 2017-03-31T10:02:53.213

I think you have just a typo, in the first odd/3 clause. With the following code

paruns([],[]).
paruns([Head | Tail], [E, O | S]) :-
   even([Head | Tail], E, Last),
   odd(Last, O, Last1),
   paruns(Last1, S).

even([Head | Tail], [], [Head | Tail]) :-
   Head mod 2 =:= 1.
even([Head | Tail], [Head | L], Last) :-
   Head mod 2 =:= 0,
   even(Tail, L, Last).
even([],[],[]).

odd([Head | Tail], [], [Head | Tail]) :-  % corrected
   Head mod 2 =:= 0.
odd([Head | Tail], [Head | L], Last) :-
   Head mod 2 =:= 1,
   odd(Tail, L, Last).
odd([],[],[]).

I get

?- paruns([8,0,4,3,7,2,-1,9,9], RunList).
RunList = [[8, 0, 4], [3, 7], [2], [-1, 9, 9]]

edit

A possibility to discard empty sequences (should occurs only at first or last position, I think... so maybe a better approach would be to sanitize the outcome for these cases):

paruns([],[]).
%paruns([Head | Tail], [E, O | S]) :-
paruns([Head | Tail], R) :-
   even([Head | Tail], E, Last),
   odd(Last, O, Last1),
    (E=[] -> R=[O|S] ; O=[] -> R=[E|S] ; R=[E,O|S]),
   paruns(Last1, S).

Thanks so much I don't know how I didn't see that, only now I have one small other question if you could help. When I run it with the above example it gets perfect output, however with 'paruns([8,0,4], RunList).' it prints RunList = [[8,0,4],[]]. Any suggestions on how to fix this?? Thanks again :) — Iza, Mar 31 '17 at 09:21
Sorry, the easier 'solution' leads to ugly code, anyway, see my edit... — CapelliC, Mar 31 '17 at 10:01

Prolog code to split parts of a list into consecutive even and odd parts

3 Answers3