Prolog - Prolog Recursion

Author

Prolog Recursion

George

2006-07-26, 7:01 pm

Dear All,

I work with lists of a specific format (e.g.
[a,b,[c:d]:[d,e,f,[g,h]:[i,k]]]) and I would like to write a predicate
that returns the last element of the list with the form A:B (in the
previous case [g,h]:[i,k]. I wrote the following code for that:

last_game(R,T):-
last(R,T),
T = A:X,
\+ last_game(X,_).

My logic is look at the end of the list (because of the nature of the
programme such lists would only occur there), check if the last element is
of the form A:B and then check if the list in B has any more lists of that
case. In the previous example, in the first run we should have got
[c,d]:[d,e,f,[g,h]:[i,k] and so on. I then pass that argument to the
predicate again so it will check if there are any further lists of that
kind until it does not find any more. I would expect to get the last list
for which no sublists exist, but this does not happen.

Could somebody please offer some explanation as I keep looking at the
predicate for the past three hours without any luck?

Thanks,
George

Bill Spight

2006-07-26, 7:01 pm

Dear George,

>
> I work with lists of a specific format (e.g.
> [a,b,[c:d]:[d,e,f,[g,h]:[i,k]]]) and I would like to write a predicate
> that returns the last element of the list with the form A:B (in the
> previous case [g,h]:[i,k]. I wrote the following code for that:
>
>
> last_game(R,T):-
> last(R,T),
> T = A:X,
> \+ last_game(X,_).

BTW, are you working with combinatorial games?

>
> My logic is look at the end of the list (because of the nature of the
> programme such lists would only occur there), check if the last element is
> of the form A:B and then check if the list in B has any more lists of that
> case.

You might consider building the lists so that the games occur at the
front. That would save you some trouble at this point.

> In the previous example, in the first run we should have got
> [c,d]:[d,e,f,[g,h]:[i,k] and so on. I then pass that argument to the
> predicate again so it will check if there are any further lists of that
> kind until it does not find any more. I would expect to get the last
> list for which no sublists exist, but this does not happen.
>
> Could somebody please offer some explanation as I keep looking at the
> predicate for the past three hours without any luck?
>

last_game(R,T):-

R is the list, T is the last game, right?

last(R,T),

T is the last element of R, right?

T = A:X,

T is a game with right side X.

\+ last_game(X,_).

last_game/2 fails for X. X is not a list, or is empty, or its last element
is not a game, or its last element is a game, U, and last_game succeeds
for it.

So if R = [a:[b:c]], then T = a:[b:c], right? But if R = [d:[a:[b:c]]],
last_game fails, because X = [a:[b:c]], for which last_game/2 succeeds.

I take it that this is not what you want to happen.

(If you are working with combinatorial games, you might try games of the
form A:B where A and B are lists. Then []:[] = 0.)

How's this?

last_game(R,A:X):-
last(R,A:X),
\+ last(X,Y:Z).

Cheers,

Bill

Bill Spight

2006-07-26, 7:01 pm

Correction:

George wrote:

I wrote:
[color=darkred]
> So if R = [a:[b:c]], then T = a:[b:c], right? But if R = [d:[a:[b:c]]],
> last_game fails, because X = [a:[b:c]], for which last_game/2 succeeds.
>

I think I got that wrong. Let's try again.

Let R = [b:c]

Then T = b:c

Then X = c

and \+ last_game(c,_) fails, because c is not a list.

So last_game([b:c],T) succeeds.

Now let R = [a:[b:c]]

Then T = a:[b:c]

Then X = [b:c]

But last_game([b:c],_) succeeds, so last_game([a:[b:c]],T) fails.

George

2006-07-26, 7:01 pm

Hi Bill,

On Wed, 26 Jul 2006 Lekeas GK wrote...

|From: Bill Spight <bspight@pacXbell.net>
|Date: Wed, 26 Jul 2006 20:03:59 GMT
|Subject: Re: Prolog Recursion
|
|Dear George,
|
|>
|> I work with lists of a specific format (e.g.
|> [a,b,[c:d]:[d,e,f,[g,h]:[i,k]]]) and I would like to write a predicate
|> that returns the last element of the list with the form A:B (in the
|> previous case [g,h]:[i,k]. I wrote the following code for that:
|>
|>
|> last_game(R,T):-
|> last(R,T),
|> T = A:X,
|> \+ last_game(X,_).
|
|BTW, are you working with combinatorial games?

In a way, I am. I am using games and situation calculus to simulate
protocols and I want to represent subgames as sublists within greater
lists, representing the main game. In this context, as the last move will
be made in a subgame - if one is active - or in the main game if noone is,
I want to check the last move in the last subgame. Because there is a
limitation that you can not exit a subgame unless you finish it, if the
last move is not a 'finishing' move, this is the active subgame.

|>
|> My logic is look at the end of the list (because of the nature of the
|> programme such lists would only occur there), check if the last element is
|> of the form A:B and then check if the list in B has any more lists of that
|> case.
|
|You might consider building the lists so that the games occur at the
|front. That would save you some trouble at this point.
|
|> In the previous example, in the first run we should have got
|> [c,d]:[d,e,f,[g,h]:[i,k] and so on. I then pass that argument to the
|> predicate again so it will check if there are any further lists of that
|> kind until it does not find any more. I would expect to get the last
|> list for which no sublists exist, but this does not happen.
|>
|> Could somebody please offer some explanation as I keep looking at the
|> predicate for the past three hours without any luck?
|>
|
| last_game(R,T):-
|
|R is the list, T is the last game, right?
|
| last(R,T),
|
|T is the last element of R, right?
|
| T = A:X,
|
|T is a game with right side X.
|
| \+ last_game(X,_).
|
|last_game/2 fails for X. X is not a list, or is empty, or its last element
|is not a game, or its last element is a game, U, and last_game succeeds
|for it.
|
|So if R = [a:[b:c]], then T = a:[b:c], right? But if R = [d:[a:[b:c]]],
|last_game fails, because X = [a:[b:c]], for which last_game/2 succeeds.
|
|I take it that this is not what you want to happen.
|
|(If you are working with combinatorial games, you might try games of the
|form A:B where A and B are lists. Then []:[] = 0.)
|
|How's this?
|
| last_game(R,A:X):-
| last(R,A:X),
| \+ last(X,Y:Z).

Thank you very much for your suggestion. Will try it tomorrow at the
office, since I do not have Prolog at home.|
|Cheers,
|
|Bill
|
|

Bill Spight

2006-07-27, 4:00 am

Dear George,

Back to your original problem.

> I work with lists of a specific format (e.g.
> [a,b,[c:d]:[d,e,f,[g,h]:[i,k]]]) and I would like to write a predicate
> that returns the last element of the list with the form A:B (in the
> previous case [g,h]:[i,k]. I wrote the following code for that:
>
>
> last_game(R,T):-
> last(R,T),
> T = A:X,
> \+ last_game(X,_).
>
> My logic is look at the end of the list (because of the nature of the
> programme such lists would only occur there), check if the last element is
> of the form A:B and then check if the list in B has any more lists of that
> case.

I think this does the job.

last_game(R,T) :-
last(R,A:X),
last_game1(A:X,T).

The last element of R is a game. Now to use an auxiliary predicate to find
the last game.

last_game1(A:X,T) :-
( %% If
last(X,B:Y)
-> %% Then
last_game1(B:Y,T)
; %% Else
T = A:X
).

Cheers,

Bill

Sponsored Links