Clever Geek Handbook

Prologue code for dividing parts of a list into consecutive even and odd parts

I was asked the following question:

Any list of integers can (unambiguously) be broken up into "parity runs", where each run is a (maximum) sequence of consecutive even or odd numbers in the original list. For example, the list List = [8,0,4,3,7,2,-1,9,9]

can be broken up into [8, 0, 4]

, [3, 7]

, [2]

and [-1, 9, 9]

write the predicate paruns(List, RunList)

, which converts the list of numbers in the appropriate list runs parity. For example:

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

Here is the code I tried and it seems to work with the above example, thanks to one suggestion, but I have a problem where paruns([8,0,4], RunList).

it prints when I run it 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([],[],[]).
+3


source to share


3 answers


I think you only have a typo, in the first odd / 3 section. 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]]


change

Ability to discard empty sequences (should only happen in the first or last position, I guess ... so perhaps a better approach would be to sanitize the results 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).
+2


source


The main attraction of Prolog is its relational nature . This means that we can often use the Prolog predicate in multiple ways, as long as we stick to reasonably general primitives.

In this particular case, since you are reasoning over integers , I highly recommend that you use your Prolog system CLP (FD) constraints in order to benefit from this generality.clpfdfor more information on this important declarative. function

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

Here is a relational solution for your problem:

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 ways. For example, suppose the runs are known but the list is not specified:

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

In addition, we can also send the most general request 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 calculate the answers correctly, 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.
+3


source


TL; DR: Find the "right anchor" for the "hole" inmeta-predicate split_if_adj/3

and you're done!

This answer is based on:

So basically, we delegate the cumbersome and sometimes complex task of recursively processing lists for a higher-order predicate, which we tweak accordingly.

Example request:

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

Please note that this request was successfully deterministic.

+3


source






More articles:


All Articles