Terms are defined inductively:

- an
**atom**is a term. Examples of atoms are:`x`,`test`and`'quotes and space'`. - a
**variable**is a term. Variables start with an uppercase letter or underscore`_`. A single underscore denotes an*anonymous variables*and can be read as "any term". **integers**and**floating point numbers**are terms. Examples: 42 and 42.42.- a
**compound term**is a term, defined inductively as follows:*If*`T`,_{1}`T`, ...,_{2}`T`are terms,_{n}*then**F*(`T`,_{1}`T`, ...,_{2}`T`) is also a term, where_{n}*F*is called the*functor*of the compound term, and`n`is called the*arity*. Examples:`f(a)`,`g(f(X))`and`+(a, f(X))`.

Prolog is

- we
*could*use the atom`zero`to represent 0 - we
*could*use the compound term`s(X)`to represent the successor of`X`.

Prolog terms naturally correspond to trees. There is a standard order on terms.

Lists are defined inductively:

- the atom
`[]`is a list, denoting the*empty list* *if*`Ls`is a list,*then*the term`'.'(L, Ls)`is*also*a list.

- The list
`'.'(a, '.'(b, '.'(c, [])))`can also be written as`[a,b,c]`. - The term
`'.'(L, Ls)`can also be written as`[L|Ls]`.

Lists naturally represent

- Can there be
*arbitrarily many*elements? - Can there be
*zero*elements? - Is the
*order*of elements significant? - Are the elements of the same
*kind*?

In contrast, consider for example the case where each collection comprises exactly three elements. You can use lists of the form

DCG notation is frequently used for describing lists.

Many commonly available predicates also use this syntax to denote pairs. Examples of this are

There is a public domain library called

Here is one way to represent an AVL tree in Prolog:

- the
*empty*tree is represented by the atom`t`. - an
*inner node*is represented as a*compound term*of the form`t(Key, Value, Balance, Left, Right)`where:`Key`and`Value`represent the*association*of`Key`with`Value`.`Balance`is an*atom*that denotes a balance criterion, such as a relation between the number of children of the left and right subtrees. For example, we can use the atoms`<`,`=`and`>`to denote different states between the subtrees.`Left`and`Right`are AVL trees.

AVL trees let us perform many important operations in

For almost any use case that involves some kind of processing, the only sensible thing to do with string data is to turn it into some kind of treeIn Prolog, a convenient representation of strings is available as lists ofearly. Prolog is brilliant with trees.

:- set_prolog_flag(double_quotes, chars).

With this setting, we obtain for example:

?- Cs = "test".Thus, working with strings is reduced to working with lists, which can be easily handled in Prolog.Cs = [t, e, s, t].

First of all, the concept of

That being said, we can access the

Can IIf this holds, your representation is calleddistinguish the kindof each component from itsoutermost functor and arity?

For example, suppose you represent a

**leaves**, which are concrete elements of the tree**nodes**, which have two children that are again full binary trees.

`leaf(L)`represents the*leaf*`L``node(Left, Right)`represents a*node*and its two children.

You can also recognize a clean representation if it lets you describe the general

Sometimes, it will appear to you that there is no clean way out. For instance, you may be faced with a representation that

Here are examples that illustrate their usage:

These predicates cannot be defined by a finite set of clauses, and can therefore be considered higher-order predicates. Do not get carried away with these predicates! Everything that?- functor(f(a,g(X)), Functor, Arity).Functor = f, Arity = 2.?- functor(Term, f, 2).Term = f(_25002, _25004).?- arg(2, f(a,g(X)), Arg).Arg = g(X).?- f(a,g(X)) =.. [Functor|Args].Functor = f, Args = [a, g(X)].?- Term =.. [f,a,g(X)].Term = f(a, g(X)).

Every Prolog term has a

?- write_canonical(a+b=[x,y,z]).The canonical representation shows the structure of the term in such a way that it can also be easily parsed by external programs.=(+(a,b),'.'(x,'.'(y,'.'(z,[]))))