Uma lista ou é vazia, representada por [ ], ou então é constituída por um elemento, designado por cabeça da lista, e uma lista (possivelmente vazia) com os restantes elementos. Nesta última situação, a lista é representada por
[X|R]
onde X representa a cabeça da lista e R a lista dos restantes
elementos.
Na posse da definição de lista, vamos implementar o predicado member/2 (que se
encontra disponível na maior parte das implementações de Prolog) e que resulta
verdadeiro se, e sómente se, o objecto no primeiro argumento pertencer à lista no
segundo argumento:
member(X,[X|R]). % a cabeca da lista pertence `a lista member(X,[Y|R]) :- member(X,R). % se nao 'e cabeca, deve pertencer `a % lista dos restantes elementos
Vamos colocar a questão
?- member(a,L).
que significa: ``Quais são as listas L que contêm a constante a?'';
e construir a árvore de procura que ela origina:
Vemos que esta árvore de procura tem um ramo infinito e contém também um número
infinito de respostas calculadas. Reparar que as respostas lógicas à questão não são
todas directamente calculadas. No entanto as respostas calculadas são suficientes para
conhecer todas as respostas lógicas. Por exemplo a resposta lógica é obtida a partir
da resposta calculada (segundo sucesso a partir da esquerda), instanciando E1
com a e R2 com a lista vazia; ou também a partir da resposta calculada
instanciando R1 com [a]. De um modo mais geral, o resultado de
completude enunciado no capítulo anterior pode ser formulado em termos da árvore de
procura: para achar todas as respostas à questão
?- A.
é suficiente construir completamente uma (só) árvore de procura (qualquer uma) originada por A. Basta então construir completamente a árvore de procura standard. Em lugar de partirmos de uma questão com apenas um átomo A, a árvore de procura pode ser originada, de um modo mais geral, por um alvo (ver comentário no final da secção 2.4).