5

I am trying to make a function that splits a list of variable length into three lists of even length in order. The following splits it into three, 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).

This code outputs:

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

How can I fix this problem?

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
Mocking
  • 1,764
  • 2
  • 20
  • 36

2 Answers2

6

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

false
  • 10,264
  • 13
  • 101
  • 209
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).
  • I'm not 100% sure but I think you misunderstood my problem. I'm trying to split the first list into 3 lists. – Mocking Nov 21 '14 at 09:36
  • @Mocking Did you actually try out what this predicate does? Also, still unclear if there is any constraint on the lengths of the resulting lists. –  Nov 21 '14 at 09:38
  • Sorry, I tried to make my problem more clear. I am trying to split a list of variable length into 3 even (or relatively even) lists. Would this actually help for that case? – Mocking Nov 21 '14 at 09:46
  • It took me a while but I got it based on your help. Thanks a bunch! – Mocking Nov 21 '14 at 20:12