CODEWITHSUNDEEP
prolog
asdf
asdf

Reputation: 667

Prolog - tracing a rule

Considering the following rules:

example(A, [A|As], As).
example(A, [B|Bs], [B|Cs]) :- what(A, Bs, Cs).

and the query:

example(c, [a, b, c, a], X).

results:

X = [ a, b, a ]

Can anyone help me trace how it does this? I am unsure what example it goes into first and I'm sure I can figure it out from there.

Upvotes: 0

Views: 50

Answers (1)

Grzegorz Adam Kowalski
Grzegorz Adam Kowalski

Reputation: 5565

First, I suppose, that what is an alias of example and your rules really look like that:

example(A, [A|As], As).
example(A, [B|Bs], [B|Cs]) :- example(A, Bs, Cs).

Then, things are going like that:

?- example(c, [a, b, c, a], X).

Now we look for a matching clause:

example(c, [a, b, c, a], X) = example(A, [A|As], As).

This one is false. So we try next one:

example(c, [a, b, c, a], X) = example(A, [B|Bs], [B|Cs]).

This one works and we get results: 

X = [a|Cs],
A = c,
B = a,
Bs = [b, c, a].

So we get:

example(c, [a, b, c, a], [a|Cs]) = example(c, [a|[b, c, a]], [a|Cs]).

From the second rule of example/3 we know that:

example(c, [a|[b, c, a]], [a|Cs]) :- example(c, [b, c, a], Cs).

So we do the process again and we get:

example(c, [b, c, a], Cs) = example(A, [B|Bs], [B|Cs]).

Which results in:

Cs = [b|Cs],
A = c,
B = b,
Bs = [c, a]

Which means that:

example(c, [b, c, a], [b|Cs]) = example(c, [b|[c, a]], [b|Cs]).

And again from the second rule:

example(c, [b|[c, a]], [b|Cs]) :- example(c, [c, a], Cs).

So we search for another match - this time first rule:

example(c, [c, a], Cs) = example(A, [A|As], As).

Now we have:

Cs = As,
As = [a],
A = c.

And now we can go back and transfer values of Cs. This is what we have now:

Cs = As = [a],

We move this to the previous results:

OldCs = [b|Cs] = [b,a]

And to the previous results:

X = [a|OldCs] = [a,b,a].

Upvotes: 1

Related Questions