Understanding splitting in Swi-proog

Question

Understanding splitting in Swi-proog

I have this code for splitting an input list into halves. Everything seems to be in order.

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 decipher it. The beginning is clear:

"Half occupied by a list and two boolean variables":

halve(List,A,B)

(1) Then this part is continuous:

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

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

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

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

Perhaps you could explain this with some examples please?

(3) Ok, hopefully after your explanation of (1) and (2) I get the final part myself ...

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

Thank you very much for helping me.

Okay, our first problem already has a solution. In short, it works like this:

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

If you notice that it splits the list into halves, but if the list has an odd number of items, the second half is larger.

Now what I want to get is that the first one is bigger .

So, I think about this:

I'm going to achieve this:

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

Let's say my input is a list: [1,2,3]. So I'll start by splitting the head and tail of the list: [H|T]

and then I will merge H

with a new empty list - my 1st time ( A

). After that I have A = [1], B = [] and Input = [2,3].

For the merge, I have:

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

And one more thing - I need to check if the 1st half> = the second half, right?

So this is my idea, and only I would like you to help me write it in the prologue. I am a little confused how to put it together.

Thank!

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

+3

list prolog

Nolog lester 08 Apr At 15:09

source to share

3 answers

halve(List,A,B)

copies the first half List

to A

and merges the second half toB

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

This will be true if the length of the list is odd: halve(B,[_],[],B).

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

Here we set that 2 allows them to be called "pointers" at each step, we copy one item from the beginning of our list to A

because we want to get the first half.
Since at each step we remove 2 items from our list, the [_,_|T2]

Predicate will stop when the list has only one left item or empty, then it will concatenate the rest of our list with B

. If you cannot understand the usetrace/0

+1

whd 08 Apr 12 at 15:57

source to share

This version might be helpful ...

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

+1

ProfVersaggi 23 jan. '14 at 1:30

source to share

m09 · Accepted Answer · 2012-04-08T15:47:27+0000

To get started, the Prolog clause looks like this:

Head :- Body

You can read it as " Head

if Body

" or " Body

means Head

".

Please note that sometimes you have

Head

This is because Head is always true

. Instead of calling the a clause Head

, we rather call it a fact in this case.

So, here we have:

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

This means that it is halve(List, A, B)

true if it halve(List, List, A, B)

is true. Specifically, this is just a way to delegate work halve/3

to a halve/4

so-called working predicate.

Why do we need a working predicate? Well, because here we would like to use another variable to calculate our terms A

and B

. But we could not do this with halve/3

because 3 spots argument halve/3

had already taken the input list List

, the first-half results, A

and second-half result B

.

Oh List, List

, it's just a way of saying that we are calling halve/4

with the same first and second arguments as in any programming language.

Then the interesting stuff begins. Prolog will try to prove which is halve/4

true for some given arguments. Let's say to illustrate the execution, which we named halve/3

as follows:

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

Then, if you follow what I talked about earlier, Prolog will now try to prove that halve/3

is true, proving that halve/4

is true with the following arguments: halve([1, 2], [1, 2], A, B).

.

Prolog has 3 options for this. The first choice is the following sentence:

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

Obviously this won't work. Because when Prolog tries to match the caller's second argument "to" the second invoked argument through unification, it will fail. Because it [1, 2]

cannot be combined with []

.

There are only two options left, the following:

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

Same here, Prolog cannot combine [1, 2]

and [_]

because _

is just a variable (see my post on anonymous variable _

if you have problems with it).

So, the only chance that Prolog should find a solution to the problem you presented is the last sentence, that is:

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

Here Prolog finds a way to combine the thing, let's see how:

we must combine [1, 2]

with [H|T]

. This means that H = 1.

andT = [2].
we must combine [1, 2]

with [_,_|T2]

. it means thatT2 = [].
now we start building our results with the following unification, i.e. A = [H|A']

(I downloaded the second A

one because the variables are localized and they don't match). Here we are saying that when we get our result calculated from the body of the sentence, we will add to it H

. Here H

is - 1

, so we already know what the first item A

will be 1

.

OK, unification succeeded, great! We can move on to the body of the position. It just calls halve/4

recursively with those values (calculated above):

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

And here we start all over again. It will be fast this time though, as the first choice of Prolog will fit well:

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

can be unified to

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

with these values: A = []

and B = [2]

.

So, to take a good step, we have now reached the "base case" of recursion. We just need to plot our result from top to bottom. Remember when we recursively called our predicate halve/4

a few steps up? We have already said that the first element A

will be 1

. We now know what the tail is []

, so we can argue that A = [1]

. We didn't talk about anything B

, so it B = [2]

remains untouched as a result.

Now that I've detailed the execution, you might be thinking why this works? Well, if you pay attention, you will notice that the second argument halve/4

passed twice as fast as the first. [H|T]

vs [_, _|T2]

. This means that when we hit the end of the list with our second argument, the first one is still in the middle of our list. In this way, we can divide the thing into two parts.

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

Understanding splitting in Swi-proog

More articles: