Split one list into three using Prolog

Question

I am trying to create a function that splits a variable-length list into three lists of even length in order. The following divides it into three, but processes insert them into each list one at a time.

An example of what I want:

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

Another example might be:

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

The following code breaks them, inserting one at a time into each list:

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

This code outputs:

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

How can I fix this problem?

Answer 1

@Boris answer does not end when the length of the list of the first argument is unknown. To see this, there is no need to look beyond the first step with failure-slice :

  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 pretty 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 completion, you only need one argument (either A , or B or C or D ) to be a specific list that is finite and ground (which is what b(..) means). This is a very strong termination condition. It is unfortunate that the arguments do not fit! Why not generalize your program? The only problem is that it restricts the list items. Therefore, I replaced all the variable names of the list items with _ s:

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

the same completion properties for this program.

Alas, now this is too much. Boris’s decision can now be repackaged:

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

My preferred way of expressing the same is:

 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 .

Answer 2

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

Do you see how this separates the three lists? Now you don’t say how much time you expect from lists L1 , L2 and L3 . You can use length/2 to get the length L and specify the length of the three results if you do not want the predicate to be as general as it is now.

Since you say "relatively even length", which is relative, and I need to interpret it somehow, let's say 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 know how to calculate 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).