As listas são a estrutura de dados mais importante em Prolog. Para manipulá-las, utilizamos predicados recursivos
que exploram a natureza recursiva das listas. Neste artigo, vamos estudar os predicados mais fundamentais:
membro/2, anexa/3, e alguns outros como ultimo/2, tam/2 e soma/2.
1. O Predicado membro/2 (Programa 5.2)
O predicado membro/2 verifica se um elemento pertence a uma lista.
Ele tem duas cláusulas:
|
1 2 3 4 5 6 7 8 9 10 |
% membro(X, L) - X é elemento da lista L % Caso base: X é a cabeça da lista membro(X, [X|_]). % Passo recursivo: X está na cauda da lista membro(X, [_|Y]) :- membro(X, Y). |
Explicação Passo-a-Passo
- Primeira cláusula:
membro(X, [X|_]).— X é membro se ele é a cabeça da lista. A variável anônima_ignora a cauda. - Segunda cláusula:
membro(X, [_|Y]) :- membro(X, Y).— X é membro se ele está na cauda. Ignoramos a cabeça com_e chamamosmembrorecursivamente na caudaY.
A recursão percorre a lista elemento por elemento até encontrar X ou chegar ao fim da lista.
Usos de membro/2
1. Testar pertinência:
|
1 2 3 4 5 |
?- membro(3, [1, 2, 3, 4]). true. ?- membro(5, [1, 2, 3, 4]). false. |
2. Gerar elementos da lista:
|
1 2 3 4 5 |
?- membro(X, [a, b, c]). X = a ; X = b ; X = c ; false. |
3. Verificar se uma lista contém todos os elementos de outra:
|
1 2 3 4 |
?- membro(X, [1, 2, 3]), membro(X, [2, 3, 4]). X = 2 ; X = 3 ; false. |
2. O Predicado anexa/3 (Programa 5.3)
O predicado anexa/3 (também conhecido como append/3)
concatena duas listas. Ele tem dois casos:
|
1 2 3 4 5 6 7 8 9 10 |
% anexa(A, B, C) - C é a concatenação de A e B % Caso base: concatenar a lista vazia com B resulta em B anexa([], B, B). % Passo recursivo: [X|A] concatenado com B é [X|C], onde C é A concatenado com B anexa([X|A], B, [X|C]) :- anexa(A, B, C). |
Explicação Passo-a-Passo
- Caso base:
anexa([], B, B).— Se a primeira lista é vazia, o resultado é a segunda lista. - Passo recursivo:
anexa([X|A], B, [X|C]) :- anexa(A, B, C).— Remove a cabeça X da primeira lista, concatena A com B recursivamente (resultando em C), e depois coloca X de volta na frente.
Usos de anexa/3
1. Concatenar duas listas:
|
1 2 |
?- anexa([1, 2], [3, 4], R). R = [1, 2, 3, 4]. |
2. Dividir uma lista (encontrar prefixos):
|
1 2 3 4 5 6 |
?- anexa(A, B, [a, b, c]). A = [], B = [a, b, c] ; A = [a], B = [b, c] ; A = [a, b], B = [c] ; A = [a, b, c], B = [] ; false. |
3. Encontrar o último elemento (via divisão):
|
1 2 |
?- anexa(_, [X], [a, b, c, d]). X = d. |
4. Remover um elemento (encontrando o que está antes e depois):
|
1 2 |
?- anexa(A, [b|B], [a, b, c]). A = [a], B = [c]. |
3. Exercícios do PDF (5.1, 5.2, 5.3)
Exercício 5.1: último/2
Problema: Encontrar o último elemento de uma lista.
|
1 2 3 4 5 6 7 8 9 10 |
% ultimo(L, X) - X é o último elemento da lista L % Caso base: lista com um único elemento ultimo([X], X). % Passo recursivo: ignorar a cabeça e continuar na cauda ultimo([_|T], X) :- ultimo(T, X). |
Como funciona: A recursão percorre a lista até chegar ao último elemento, que é retornado.
|
1 2 3 4 5 6 7 8 |
?- ultimo([1, 2, 3, 4], X). X = 4. ?- ultimo([a, b, c], X). X = c. ?- ultimo([], X). false. |
Exercício 5.2: tam/2
Problema: Calcular o tamanho (comprimento) de uma lista.
|
1 2 3 4 5 6 7 8 9 10 11 |
% tam(L, N) - N é o número de elementos da lista L % Caso base: lista vazia tem tamanho 0 tam([], 0). % Passo recursivo: tamanho = 1 + tamanho da cauda tam([_|T], N) :- tam(T, N1), N is N1 + 1. |
Como funciona: A cada chamada recursiva, removemos a cabeça da lista (ignorando-a com _)
e adicionamos 1 ao resultado da chamada recursiva.
|
1 2 3 4 5 6 7 8 |
?- tam([1, 2, 3, 4], N). N = 4. ?- tam([a, b, c, d, e], N). N = 5. ?- tam([], N). N = 0. |
Exercício 5.3: soma/2
Problema: Calcular a soma dos elementos de uma lista de números.
|
1 2 3 4 5 6 7 8 9 10 11 |
% soma(L, S) - S é a soma dos elementos da lista L % Caso base: soma da lista vazia é 0 soma([], 0). % Passo recursivo: soma = cabeça + soma da cauda soma([H|T], S) :- soma(T, S1), S is H + S1. |
Como funciona: Percorre a lista recursivamente, somando a cabeça ao resultado da cauda.
|
1 2 3 4 5 6 7 8 |
?- soma([1, 2, 3, 4], S). S = 10. ?- soma([5, 10, 15], S). S = 30. ?- soma([], S). S = 0. |
4. Recursão e Listas: O Padrão Fundamental
Todos os predicados que vimos seguem o mesmo padrão:
|
1 2 3 4 5 |
% Padrão geral para predicados de listas pred([], ...). % Caso base: lista vazia pred([H|T], ...) :- % Passo recursivo: processa a cabeça H e chama pred na cauda T pred(T, ...). % A cauda T é uma lista menor |
Esse padrão é universal em Prolog para manipulação de listas. A recursão percorre a lista até o fim, processando cada elemento (ou acumulando resultados) e depois retorna o resultado combinado.
5. Exercícios Adicionais
Pratique com estes desafios:
-
maximo/2: Encontre o maior elemento de uma lista de números.
Dica: Caso base: lista com um elemento. Passo: compare a cabeça com o máximo da cauda. - minimo/2: Encontre o menor elemento de uma lista de números.
-
remover/3:
remover(X, L, R)— R é a lista L sem a primeira ocorrência de X.
Dica: Useanexa/3para encontrar X e construir o resultado. - remover_todos/3: Remova todas as ocorrências de X da lista L.
-
inverter/2:
inverter(L, R)— R é a lista L invertida.
Dica: Useanexa/3para construir a lista invertida. -
pertence_todos/2:
pertence_todos(Xs, Ys)— todos os elementos de Xs estão em Ys.
6. Conclusão
As listas são a estrutura de dados fundamental em Prolog. Através da notação cabeça-cauda
[X|Y] e da recursão, podemos implementar uma vasta gama de operações:
- Busca:
membro/2 - Combinação:
anexa/3 - Medidas:
tam/2,soma/2,ultimo/2 - Transformações:
inverter/2,remover/3
Dominar esses predicados fundamentais é o primeiro passo para se tornar um programador Prolog proficiente. Pratique com os exercícios e explore como a recursão pode ser aplicada a problemas cada vez mais complexos.