Understanding the splitting in Swi-prolog

Question

I have this code for splitting input list into its halves. It seems to be OK.

halve(List,A,B) :- halve(List,List,A,B), !.
halve(B,[],[],B).
halve(B,[_],[],B).
halve([H|T],[_,_|T2],[H|A],B) :-halve(T,T2,A,B). 

Ok, so I tried to decode it. The beginning is clear:

"Halve took list and 2 logic variables" is this:

halve(List,A,B) 

(1) Then continuous this part:

:- halve(List,List,A,B).

And this means, that I am creating new two lists (List, List) from the first one or what? What exacly represents ":-"? I guess the new lists = halves will be the A, and B, right?

(2) Second, please, I don't quite get these two lines:

halve(B,[],[],B).
halve(B,[_],[],B).

Maybe you could explain it on some examples, please?

(3) Well, I hope after your explanation of (1) and (2), I'll get the final part by myself...

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B). 

Thank you very, very much for helping me.

---

Ok, our first problem already has its solution. Long story short, it works like this:

halve([1,2,3,4,5],[1,2],[3,4,5]). 
->true

If you notice it splits the list into its halves but if the list has an odd number of the elements, the second half is the bigger one.

Now what I want to obtain is to have the first one bigger.

So I'm thinking about this:

I'm going to reach this:

Halves_div([1,2,3],A,B).
A=[1,2],
B=[3].

Let's say my input is list: [1,2,3]. So I'll start with splitting list's head and tail: [H|T] and then I will merge the H with new empty list - my 1st Half (A). After that I have A=[1], B=[] and Input=[2,3].

For merging I have:

merge([],List,List).
merge([H|T],List,[H|New]) :- merge(T,List,New).

And one more thing - I need to check whether the 1st half is already >= 2nd half, right?

So this is my idea and only thing I'd love you to help me is to write it in prolog. I'm kinda confused how to put it together.

Thanks!

---

It seems my idea of solution is too complicated and I found something better!

Answer 1

To start, a Prolog clause looks like that:

Head :- Body

You can read that as "Head if Body", or "Body implies Head".

Note that sometimes you just have

Head

That's because Head is always true. Instead of calling Head a clause, we rather call it a fact in this case.

So here, we have:

halve(List,A,B) :- halve(List,List,A,B).

That means that halve(List, A, B) is true if halve(List, List, A, B) is true. Concretely it's just a way to delegate the work of halve/3 to halve/4, a so called worker predicate.

Why do we need a worker predicate? Well, because here we'd like to use another variable to calculate our A and B terms. But we couldn't do that with halve/3 because the 3 argument spots of halve/3 were already taken by the input list, List, the first half of the result, A and the second half of the result, B.

About the List, List thing, it's just a way to say that we call halve/4 with the same first and second argument, like you would in any programming language.

Then the interesting stuff starts. Prolog will try to prove that halve/4 is true for some given arguments. Let's say to illustrate the execution that we called halve/3 this way:

?- halve([1, 2], A, B).

Then, if you followed what I talked about previously, Prolog will now try to prove that halve/3 is true by proving that halve/4 is true with the following arguments: halve([1, 2], [1, 2], A, B)..

To do that, Prolog has 3 choices. The first choice is the following clause:

halve(B,[],[],B).

Obviously, that won't work. Because when Prolog will try to fit the second argument of the caller "in" the second argument of the callee through unification, it will fail. Because [1, 2] can't be unified with [].

Only two choices left, the next is:

halve(B,[_],[],B).

Same thing here, Prolog cannot unify [1, 2] and [_] because _ is just a variable (see my post about the anonymous variable _ if you've troubles with it).

So the only chance Prolog has to find a solution to the problem you presented it is the last clause, that is:

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B).

Here, Prolog will find a way to unify thing, let's see which way:

• we have to unify [1, 2] with [H|T]. That means that H = 1. and T = [2].
• we have to unify [1, 2] with [_,_|T2]. that means that T2 = [].
• now we start to build our results with the next unification, ie A = [H|A'] (I primed the second A because variables are scoped locally and they are not the same). Here we tell that when we'll have our result calculated from the body of the clause, we'll add H to it. Here H is 1 so we already know that the first element of A will be 1.

Ok ok, unification succeeded, great! We can proceed to the body of the clause. It just calls halve/4 in a recursive manner with those values (calculated above):

halve([2], [], A, B).

And here we start all over again. Though this time things will be fast since the first choice Prolog has will be a good fit:

halve(B,[],[],B).

can be unified to

halve([2], [], A, B).

with those values: A = [] and B = [2].

So that's a good step, we now reached the "base case" of the recursion. We just have to build our result from bottom to top now. Remember when we called recursively our predicate halve/4 a few steps above? We had already said that the first element of A would be 1. Now we know that the tail is [] so we can state that A = [1]. We hadn't stated anything particular about B so B = [2] is left untouched as the result.

Now that I detailed the execution, you might wonder, why does this work? Well, if you pay attention, you'll note that the second argument of halve/4 is gone through twice as fast as the first one. [H|T] vs [_, _|T2]. That means that when we hit the end of the list with our second argument, the first one is still at the middle of our list. This way we can divide the thing in two parts.

I hope I helped you catch some of the subtle things at work here.

Answer 2

halve(List,A,B) copies first half of List to A and unifies second half with B

That will be true when length of our list will be even: halve(B,[],[],B).

That will be true when length of out list will be odd: halve(B,[_],[],B).

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B).

Here we are setting 2 lets call them 'pointers' in each step we copy one element from beginning of our list to A because we want get first half.
Because in each step we are removing 2 elements from our list [_,_|T2] Predicate will stop when list will have only one left element or empty, then it will unify rest of our list with B. If you cant understand use trace/0

Answer 3

This version might prove useful ...

split_in_half(Xs, Ys, Zs) :-  length(Xs, Len),
Half is Len // 2,    % // denotes integer division, rounding down
split_at(Xs, Half, Ys, Zs).

split_at(Xs, N, Ys, Zs) :- length(Ys, N), append(Ys, Zs, Xs).