Thursday, April 14, 2016

Prolog: Splitting Single List into Three in Order

By Hường Hana 7:30 AM Leave a Comment

I am trying to make a function that splits a list of variable length into 3 lists of even length in order. The following splits it into 3 but processes inserts them into each list one at a time.

An example of what I want is:

[1, 2, 3, 4, 5] -> [1, 2], [3, 4], [5]

Another example would be:

[8, 7, 6, 5, 4, 3, 2, 1] -> [8, 7, 6], [5, 4, 3], [2, 1].

The following code splits them by inserting into each list one at a time:

div([], [], [], []). div([X], [X], [], []). div([X,Y], [X], [Y], []). div([X,Y,Z|End], [X|XEnd], [Y|YEnd], [Z|ZEnd]):-   div(End, XEnd, YEnd, ZEnd).

What this code outputs is:

[1, 2, 3, 4, 5] -> [1, 4], [2, 5], [3]

I would appreciate any pointers that could help me with this.

2 Answers

Answers 1

The answer by @Boris does not terminate when the length of the list of the first argument is not known. To see this, there is no need to look any further than the first goal with a :

 div(L, L1, L2, L3) :-     length(L, Len), false,     % here you compute for example Len1 and Len2     length(L1, Len1),     length(L2, Len2),     append(L1, L1_suffix, L),     append(L2, L3, L1_suffix).

On the other hand, your original program had quite nice termination properties. cTI gave the following optimal termination property:

div(A,B,C,D) terminates_if b(A);b(B);b(C);b(D).

In other words, to ensure termination, you only need a single argument (either A or B or C or D) to be a concrete list that is finite and ground (that's what b(..) means). That is a very strong termination condition. It's really a pity that the arguments do not fit! Why not generalize your program? The only problem it has it that it restricts the list elements. So I will replace all variable names of list elements by _s:

gdiv([], [], [], []). gdiv([_], [_], [], []). gdiv([_,_], [_], [_], []). gdiv([_,_,_|End], [_|XEnd], [_|YEnd], [_|ZEnd]):-   gdiv(End, XEnd, YEnd, ZEnd).

The very same termination properties hold for this program.

Alas, it is now a bit too general. Boris's solution can now be repurposed:

divnew(Zs, As, Bs, Cs) :-    gdiv(Zs, As, Bs, Cs),    append(As, BsCs, Zs),    append(Bs, Cs, BsCs).

My preferred way to express the same would rather be:

divnew(Zs, As, Bs, Cs) :-    gdiv(Zs, As, Bs, Cs),    phrase( ( seq(As), seq(Bs), seq(Cs) ), Zs).

See other answers for a definition of seq//1.

Answers 2

div(L, L1, L2, L3) :-     append(L1, L1_suffix, L),     append(L2, L3, L1_suffix).

Do you see how this splits the three lists? Now you don't say how long you expect the lists L1, L2, and L3 to be. You can use length/2 to get the length of L and set the length of the three results if you don't want the predicate to be as general as it is at the moment.

Since you say "relatively even length", which is relative and I need to interpret it somehow, lets assume you mean that, for a positive integer len and n, len = 3n, you get len1 = len2 = len3 = n, for k = 3n+1 you get len1 = n+1, len2 = len3 = n, and for k = 3n+2 you get len1 = len2 = n+1, len3 = n. I let you figure out how to compute the lengths.

div(L, L1, L2, L3) :-     length(L, Len),     % here you compute for example Len1 and Len2     length(L1, Len1),     length(L2, Len2),     append(L1, L1_suffix, L),     append(L2, L3, L1_suffix).
If You Enjoyed This, Take 5 Seconds To Share It

0 comments:

Post a Comment