prolog

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:

Explicação Passo-a-Passo

1. Primeira cláusula: membro(X, [X|_]). — X é membro se ele é a cabeça da lista. A variável anônima _ ignora a cauda.
2. Segunda cláusula: membro(X, [_|Y]) :- membro(X, Y). — X é membro se ele está na cauda. Ignoramos a cabeça com _ e chamamos membro recursivamente na cauda Y.

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:

2. Gerar elementos da lista:

3. Verificar se uma lista contém todos os elementos de outra:

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:

Explicação Passo-a-Passo

1. Caso base: anexa([], B, B). — Se a primeira lista é vazia, o resultado é a segunda lista.
2. 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:

2. Dividir uma lista (encontrar prefixos):

3. Encontrar o último elemento (via divisão):

4. Remover um elemento (encontrando o que está antes e depois):

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.

Como funciona: A recursão percorre a lista até chegar ao último elemento, que é retornado.

Exercício 5.2: tam/2

Problema: Calcular o tamanho (comprimento) de uma lista.

Como funciona: A cada chamada recursiva, removemos a cabeça da lista (ignorando-a com _) e adicionamos 1 ao resultado da chamada recursiva.

Exercício 5.3: soma/2

Problema: Calcular a soma dos elementos de uma lista de números.

Como funciona: Percorre a lista recursivamente, somando a cabeça ao resultado da cauda.

4. Recursão e Listas: O Padrão Fundamental

Todos os predicados que vimos seguem o mesmo padrão:

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:

1. 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.
2. minimo/2: Encontre o menor elemento de uma lista de números.
3. remover/3: remover(X, L, R) — R é a lista L sem a primeira ocorrência de X.
   Dica: Use anexa/3 para encontrar X e construir o resultado.
4. remover_todos/3: Remova todas as ocorrências de X da lista L.
5. inverter/2: inverter(L, R) — R é a lista L invertida.
   Dica: Use anexa/3 para construir a lista invertida.
6. 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.

As listas são a estrutura de dados mais importante em Prolog. Elas permitem agrupar uma sequência de itens de forma simples e flexível. Neste artigo, vamos explorar a sintaxe das listas, a notação cabeça-cauda e como usar padrões de casamento para extrair elementos de forma declarativa.

1. O que é uma Lista em Prolog?

Uma lista em Prolog é uma sequência linear de itens delimitada por colchetes ([ ]). Os itens podem ser de qualquer tipo: números, átomos, variáveis ou até mesmo outras listas.

2. A Lista Vazia: []

A lista vazia é representada por []. Ela é o caso base para quase todos os predicados recursivos que manipulam listas. Em Prolog, [] é um átomo especial que representa “nenhum elemento”.

3. Notação Cabeça-Cauda: [X|Y]

A notação [X|Y] é a forma mais importante de manipular listas em Prolog. Ela separa a lista em dois componentes:

• X — a cabeça: o primeiro elemento da lista.
• Y — a cauda: o resto da lista (que é sempre uma lista).

Essa notação é usada tanto para construir quanto para decompor listas através de unificação.

Exemplo 1: Decompondo uma Lista

A cabeça X recebe o primeiro elemento (terra) e a cauda Y recebe o restante da lista ([sol, lua]).

Exemplo 2: Lista com Apenas um Elemento

Quando a lista tem apenas um elemento, a cauda é a lista vazia.

Exemplo 3: Lista Vazia

A notação [X|Y] não casa com a lista vazia, pois exige pelo menos um elemento (a cabeça).

4. Tabela de Padrões de Listas

A seguir, os principais padrões de listas e o que eles representam:

Padrão	Significado	Exemplo de Casamento
[]	Lista vazia (0 elementos)	[] = [] ✅
[X]	Lista com exatamente 1 elemento	[X] = [sol] → X = sol
[X|Y]	Lista com pelo menos 1 elemento	[X|Y] = [a,b,c] → X = a, Y = [b,c]
[X,Y|Z]	Lista com pelo menos 2 elementos	[X,Y|Z] = [a,b,c,d] → X = a, Y = b, Z = [c,d]
[X,Y]	Lista com exatamente 2 elementos	[X,Y] = [a,b] → X = a, Y = b
[X,Y,Z]	Lista com exatamente 3 elementos	[X,Y,Z] = [a,b,c] → X = a, Y = b, Z = c

5. Selecionando Elementos Específicos

Usando padrões, podemos extrair qualquer elemento de uma lista. Para selecionar o terceiro elemento, usamos a variável anônima _ para ignorar os primeiros:

Explicação:

• _ (primeiro) → ignora a
• _ (segundo) → ignora b
• X → recebe c (terceiro elemento)
• _ (cauda) → ignora o resto [d, e]

Exemplo: Quarto Elemento

6. Padrões para Números Exatos de Elementos

Para listas com um número exato de elementos, podemos usar padrões fixos:

7. Exercícios Propostos

Pratique a extração de elementos usando padrões:

1. Segundo elemento: Escreva um padrão que extraia o segundo elemento da lista [10, 20, 30, 40].
   Resposta: ?- [_,X|_] = [10, 20, 30, 40]. → X = 20.
2. Quarto elemento: Extraia o quarto elemento da lista [a, b, c, d, e, f].
   Resposta: ?- [_,_,_,X|_] = [a, b, c, d, e, f]. → X = d.
3. Último elemento: Como extrair o último elemento de uma lista com qualquer tamanho?
   Dica: Use append/3 ou recursão.
4. Lista com 2 elementos: Verifique se [a, b, c] casa com [X, Y].
   Resposta: false (tamanhos diferentes).

8. A Importância da Notação Cabeça-Cauda

A notação [X|Y] é a base de praticamente todos os predicados recursivos que manipulam listas em Prolog. Ela permite:

• Percorrer listas elemento por elemento.
• Construir novas listas adicionando elementos à frente.
• Dividir uma lista em partes menores.
• Combinar listas através de recursão.

Veja um exemplo clássico: o predicado membro/2 que verifica se um elemento está em uma lista:

Esse predicado usa a notação cabeça-cauda para:

1. Verificar se X é o primeiro elemento ([X|_]).
2. Se não for, ignorar a cabeça e verificar recursivamente na cauda ([_|T]).

Dominar a notação [X|Y] é o primeiro passo para se tornar proficiente em Prolog. Pratique com diferentes padrões e explore como eles se comportam em unificações e recursões.