Splitting a list into two lists equal in length in Prolog

3
votes

I am writing a predicate in Prolog to divide a list into two equal in length lists. For example : 

div([1,2,3,4] , X , Y).
X = [1,2].
Y = [3,4].

That's my code but it's not working :

div(L , L1 , L):- length(L) == length(L1).
div([ H | T ] , [ H | T1] , L2):- div(T , T1 , L2).
6
prolog
Once you fix the problem with length/2 as @larsmans pointed out, your solution still appears to try and construct the first half list, but it doesn't have any code to deal with the second half. You might need an auxiliary predicate to deal with a length counter. Alternatively, you can consider using append/3. For div(L, X, Y) look at append(X, Y, L) and constrain the length of X or Y. – lurker

6 Answers

7
votes

Could be just:

div(L, A, B) :-
    append(A, B, L),
    length(A, N),
    length(B, N).

Read as "appending list A and list B results in original list L, length of A is some value N and also length of B is the same value N".

5
votes

Funny is this split which doesn't use length :

div(L, A, B) :-
    split(L, L, A, B).

split(B, [], [], B).

split([H|T], [_, _|T1], [H | T2], B) :-
    split(T, T1, T2, B).

For a list of 100 000 elements, it uses 50 001 inferences but 0,016 CPU, for the same list, lurker's code uses 50 015 inferences and 0,000 CPU.

2
votes
length(L) == length(L1)

is not how you compare lengths of lists in Prolog. It compares the ''terms'' length(L) and length(L1) without interpreting them, i.e. without calling any predicates. To compare lengths, do

length(L, N), length(L1, N)

If you fix that, your program should be closer to working.

2
votes

I like Sergey's solution for its elegance and simplicity (+1). Here's another approach which is less elegant in favor of some further efficiency as it prunes the cases where append is queried. If either A or B are ground, then we let their length drive the process. Otherwise, we let the length of L drive it:

div(L, A, B) :-
    (   \+ground(A),
        \+ground(B)
    ->  length(L, N),
        HalfN is N div 2
    ;   true
    ),
    length(A, HalfN),
    length(B, HalfN),
    append(A, B, L).

And this will yield, for example:

| ?-  div2(L, A, B).

A = []
B = []
L = [] ? ;

A = [C]
B = [D]
L = [C,D] ? ;

A = [C,D]
B = [E,F]
L = [C,D,E,F] ?
...

| ?- div([1,2,3|T], A, B).

A = [1,2]
B = [3,C]
T = [C] ? ;

A = [1,2,3]
B = [C,D,E]
T = [C,D,E] ? ;
...

| ?- div(L, [1,2], B).

B = [A,C]
L = [1,2,A,C]

yes
| ?- div([1,2|T], [1,2], [3,4]).

T = [3,4]

yes
| ?-

Etc.

0
votes

It would just be,

div(L,L1,L2) :- length(L,Len), N is Len/2, split(L,L1,L2,N).
split([H|T],[H|L1],L2,N):- N1 is N-1, split(T,L1,L2,N1).
split(T,[],T,0).
0
votes
div(L, A, B) :-
append(A, B, L),
length(A, O),
length(B, N),
((O-1)=:=N;(O+1)=:=N;O=:=N),
!.

It's just this, works with odd lenght :)