Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations TouchToneTommy on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

couples 1

Status
Not open for further replies.

xristiana

Programmer
Oct 23, 2010
48
GR
Hi, I want to apologize to all and especially Mr. Kahleen for my continuous asking for help, but I have boggled.
Here's what I have to do next, I have a list A and a list B with the couples of the elements of list A, for example: list A=[4,5,6,7,8,9] and list B=[[4,5],[6,7],[8,9]].
I have made a programm, but the only thing it does when I insert a example, is true. Here it is:

couples([], _).
couples([H, H1|A], B) :- append([H], [H1], L), pair_list(A, [L|B]).

But it's wrong. The question is, what is the right one?
 
What is pair_list?

The way to solve almost any problem about list is this:

solve([H | T], Solution) :-
solve(T, PartialSolution),
compute_final_solution(H, PartialSolution, Solution).

So you need to solve the problem for T which is [H | T] without the first element H, and you will get the solution for T. Then the solution for the entire list [H | T] should be simple to compute once you have PartialSolution, which is the solution for T.

Example in your case:

Suppose your list is [4,5,6,7,8,9]

You need to put it as [H, H1 | A] like you did, then H = 4, H1 = 5 and A = [6, 7, 8, 9].

Then you should call 'couples' on A and it will result in B = [[6, 7], [8, 9]]. This is your PartialSolution.

Now with H = 4, H1 = 5 and B = [[6, 7], [8, 9]] you should obtain the full solution [[4, 5], [6, 7], [8, 9]].

It's a step forward to append [H] with [H1] and get L which would be [4, 5], like you already did. Now you have L = [4, 5] and B = [[6, 7], [8, 9]]. From L and B it's easy to obtain the whole solution
 
Sorry, pair_list is another name for couples.. So, my programm is that:
couples([], _).
couples([H, H1|A], B) :- append([H], [H1], L), couples(A, [L|B]).
Sorry, I don't understand your explanation, what I thought my programm does is:
First, seperates H and H1 from the body. It uses append to join the two lists of H, and H1, and then it uses couples to do the same for the rest elements of B, which are saved in L|B, and finally to B. But I don't know why that doesn't work!
 
Ok, first of all your first rule is wrong.

Code:
couples([], []).

As I already told you in another topic, you should think very carefully what you want to express in each Prolog clause and you should take care that similar predicates have similar meanings everywhere they are used. If you call 'couples' on an empty list, what would be the desired outcome?

'_' means 'anything', so couples on an empty list should not return 'anything', but also an empty list.

Now, to your second rule ... What does 'couples' mean?

couples(A, B) means 'B is the list of couples extracted from A'

What you say in your last rule is this (read it backwards):

If [[H, H1] | B] is the list of couples extracted from a list A, then B is the list of couples extracted from [H, H1 | A].

See, the correct version would be this:

If B is the list of couples extracted from a list A, then [[H, H1] | B] would be the list of couples extracted from [H, H1 | A].

In code:

Code:
couples([H, H1 | A], [L | B]) :-
    L = [H, H1], %this is equivalent to your append
    couples(A, B).
 
I didn't understand what I had done wrong, but I understood the explanation of the correct programm. :) About the first rule, I translated that when we finish rule 2, what shall we have for rule 1? So, my translation was wrong if you get it. Thank you so much for everything! Be well!
 
But when I insert couples([4,5,6,7,8,9],S).
it says false. :S
 
But I have a general question, which for example in this programm, is that since we separate the H and H1 in the head of the rule, how can the body be the first action? Do you get what I mean? That we say first the body, but the first action is on the head of the rule. I don't understand how this is.
 
Prolog only goes by matching the question you type at the Prolog prompt with the knowledge he has in the knowledge base.

Given the program:

Code:
couples([], []).
couples([H, H1 | A], [L | B]) :-
    L = [H, H1],
    couples(A, B).

... when you type at the Prolog prompt:

?- couples([4, 5], S).

... Prolog will take your question and will try to find out a match. The first rule won't match because [4, 5] doesn't match with []. But the second rule will match, so H = 4, H1 = 5 and A = []. Then Prolog concludes that S (your desired result) must match [L | B] because that's what the matching rule has as second argument.

Now Prolog will look in the body of the rule to determine what L and B are. So he sees "ah, L is the list [H, H1], or [4, 5] in our case". And he sees that B should result from calling 'couples(A, B)'. But A is [] so the first 'couples' rule tells Prolog that B should also be []. Then Prolog puts everything together and the result to the whole question would be [L | B] with L = [4, 5] and B = [].

So the result he tells you is [[4, 5]] which is the result of coupling the list [4, 5]. I didn't understand your question very well but I think this is what you asked
 
Thank you, but I asked the opposite. What's the translation, the meaning of the second rule if we use if. Since the meaning starts from the second clause with if, then how the first action (the separation of H and H1) happens first. Now you got it?
 
Since the meaning starts from the second clause with if ..."

I assume you are referring to the body of the rule, the portion that starts after the 'if'. Every Prolog rule is of the form: Head :- Body.

The meaning does not start from the body of the rule. Like I explained in the previous post, when you type anything at the Prolog prompt, your query is matched with all the heads and when a match is found, then the body is evaluated.

So if you have a head like this:

Code:
couples([H, H1 | A], S) :- ...

... and you type at the Prolog prompt:

?- couples([1, 2, 3, 4, 5, 6], Result).

... then there is a match and Prolog will work its way in the matching rule using the variable assignments that are derived from your query.

[H, H1 | A] = [1, 2, 3, 4, 5, 6]

this means H = 1, H2 = 2 and A = [3, 4, 5, 6] so all this variables suddenly are bound to values and the body is then evaluated using these values for those variables.

I only read the rule backwards because it is easier to understand it if you put it in the form: Body -> Head (Body implies Head). But Prolog uses it the other way around: Head :- Body (Head if Body)
 
Yes, but again you explained me about what Swi-prolog does, I am talking about the meaning here. How can we say if for sth, if it happens first in the Swi-prolog and the meaning? That's what I'm saying. And also, I would like you to tell me if you can, what is saved in the B list when we insert for example couples([4,5,6,7,8,9], S).
 
I don't understand this: "How can we say if for sth, if it happens first in the Swi-prolog and the meaning", it doesn't have any sense, please do a better job clarifying your question.

As for the other question ...

Code:
couples([], []).
couples([H, H1 | A], [L | B]) :-
    L = [H, H1],
    couples(A, B).

If you type: ?- couples([4, 5, 6, 7, 8, 9], S).

To understand this call, you should read 4 posts ago when I've explained what happens when you call couples([4, 5], S).

The result will be S = [[4, 5]]. Now if you can solve the problem with 2-element lists, you can go one step further and solve it with 4-element lists.

?- couples([4, 5, 6, 7], S).

This call will match the second rule again, so:

H = 4, H1 = 5, A = [6, 7] and S = [[4, 5] | B]

with B being the result of couples([6, 7], B).

So using the previous reasoning since [6, 7] is a 2-element list, B = [[6, 7]] ... and now we return and use B in the expression of S

S = [[4, 5] | [[6, 7]]] which is the same as [[4, 5], [6, 7]]

Then you can go further for 6-element lists, which will rely on solving the problem for 4-element lists, which will rely on solving the problem for 2-element lists, which will rely on solving the problem for 0-element lists, and for these lists the first Prolog rule provides a straight solution saying that couples([], []). This is the point where all the previous problems will start to get solved, because each of them relied on the next one until [] is reached.
 
Sorry, it's difficult for me to explain textually better than I already did. You need to have a basic understanding of recursivity and things should be quite clear, if you don't understand how recursivity works then learning Prolog would be quite difficult since it relies massively on recursivity
 
Sorry, I am not English and I can't explain it further. I' m talking about the meaning here and in the meaning we use firstly the if clause. That's what I 'm saying. In the Swi- prolog, it is obvious that it happens secondly, not firstly I was wrong.
I didn't understand how B is [[6,7]].
 
Ok, I'll try one more time.

Question: couples([6, 7], S).

Second Rule: couples([H, H1 | A], [[H, H1] | B]) :- couples(A, B).

H = 6, H1 = 7, A = [] and the result = [[6, 7] | B]

Now we need to determine B, and for that we need to solve couples(A, B).

But A = [], so it's couples([], B).

This call will also be matched with one of the two 'couples' rules, and only the first one will match

First Rule: couples([], []).
And we have: couples([], B).

So B = [].

Then we return, our complete result is [[6, 7] | B] and we determined B to be []. So the final result is [[6, 7]].
 
Ok, I understand with two elements. The problem is with four elements, but you don't have to explain it if you don't want to.
 
With 4 elements, the problem reduces itself to the problem for 2 elements.

You said you understood how couples([4, 5], S) makes S = [[4, 5]].

Then couples([4, 5, 6, 7], S) will use the second rule:

couples([H, H1 | A], [[H, H1] | B]) :- couples(A, B).

The result is [[4, 5] | B] and B is the result of couples([6, 7], B).

We know that couples([6, 7], B) computes B = [[6, 7]] because [6, 7] is a 2-element list.

So the full result is [[4, 5] | [[6, 7]]]

But this is equivalent with [[4, 5], [6, 7]]

Type this at the Prolog prompt to verify:

?- [[4, 5] | [[6, 7]]] = [[4, 5], [6, 7]].

I supppose this equivalence is what you don't understand, but it's really simple.

[1, 2, 3, 4, 5] = [1 | [2, 3, 4, 5]] = [1 | X] where X = [2, 3, 4, 5]
 
No, I understand this equivalence, what I don't understand is this:
"We know that couples([6, 7], B) computes B = [[6, 7]] because [6, 7] is a 2-element list.
 
You just said 2 posts before that you understand with 2 elements but you don't understand with 4.

couples([6, 7], B) is an example of calling couples with a list of 2 elements
 
Status
Not open for further replies.

Part and Inventory Search

Sponsor

Back
Top