Splitting a list into two lists equal in length in

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

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.