CODEWITHSUNDEEP
prolog
Krab
Krab

Reputation: 6756

Prolog - how to understand lists

I don't know much, how to understand that fact p([H|T], H, T). I know C/C++/Java etc.. but this looks diferrent. So when i pass first argument to "function" p, it separates it into H and T and makes it accessible through this vars? I don't know how to logically understand this.

http://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/lists.html

p([H|T], H, T).


Lets see what happens when we ask some simple queries.

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

X=a


Y=[b,c]


yes

Upvotes: 0

Views: 96

Answers (2)

Will Ness
Will Ness

Reputation: 71065

The page you refer to says, "Consider the following fact.

p([H|T], H, T)."

So we must treat this as a fact. That means, it's like having a predicate

p([H|T], H, T):- true.         % or,  p(L,H,T) :- L=[H|T].

Now, when you query p([a,b,c], X, Y)., one is put besides the other:

p([a,b,c], X, Y).              % a query
p([H|T],   H, T) :- true.      % a rule's clause: _head_ :- _body_.

the equivalences are noted: [a,b,c] = [H|T], X = H, Y = T and treated as unification equations. The first gets further translated into

a = H                          % list's head element
[b,c] = T                      % list's tail

because [A|B] stands for a list with A the head element of the list, and B the list's tail, i.e. all the rest of its elements, besides the head. H and T are common mnemonic names for these logical variables.

So on the whole, we get X = H = a, Y = T = [b,c].

This process is what's known as unification of a query and a rule's head (the two things starting with a p "functor", and both having the 3 "arguments").

Since the query and the head of a rule's "clause" matched (had same functor and same number of arguments), and their arguments were all successfully unified, pairwise, using the above substitution, we only need to prove the body of that rule's clause (that was thus selected).

Since it is true, we immediately succeed, with the successful substitution as our result.

That's how Prolog works.

TL;DR: yes, when you call p(L,H,T) with a given list L, it will be destructured into its head H and tail T. But you may call it with a given list T, a value H, and a variable L, and then a new list will be constructed from the head and the tail. And if L is given as well, it will be checked whether its head is H, and its tail is T.

This is because Prolog's unification is bi-directional: A = B is the same as B = A. Unification with a variable is like setting that variable, and unification with a value is like checking the (structural) equality with that value.

Calling p(L,H,T) is really equivalent to the unification L = [H|T].

Upvotes: 1

CapelliC
CapelliC

Reputation: 60014

In Prolog we have relations, in a way similar to relationals DBs.

Then p/3 it's a relation among a list (first argument), its head H and its tail T.

Appropriately the tutorial' author used descriptive and synthetic symbols as Variables.

Syntactically, variables are symbols starting Uppercase and can get any value, but only one time (that is, cannot be 'reassigned').

Upvotes: 1

Related Questions