Arquivo de prolog - Página 4 de 13

Estruturas de Dados em Prolog

16/07/202615/07/2026 Por antonino

Listas, Functors e a arte de organizar informações

1. Listas: A Estrutura Fundamental

Em Prolog, listas são a estrutura de dados mais utilizada. Diferente de arrays em linguagens imperativas, as listas em Prolog são recursivas por natureza: uma lista é composta por uma cabeça (primeiro elemento) e uma cauda (o resto da lista). Essa estrutura é representada como [H|T], onde H é o primeiro elemento e T é uma lista com os demais.

A sintaxe é simples: [1, 2, 3] é uma lista de três elementos. A lista vazia é representada por []. O poder das listas em Prolog vem do casamento de padrões com [H|T], que permite extrair e processar elementos de forma elegante.

Manipulação de Listas com Padrões

O casamento de padrões com listas é uma das características mais poderosas do Prolog. Por exemplo, a consulta [X|Y] = [1, 2, 3] unifica X = 1 e Y = [2, 3]. Isso permite escrever predicados recursivos de forma natural:

% membro(X, L) - X é elemento da lista L
membro(X, [X|_]).
membro(X, [_|T]) :- membro(X, T).

% membro(X, L) - X é elemento da lista L

membro(X, [X|_]).

membro(X, [_|T]) :- membro(X, T).

Essa estrutura recursiva é a base para praticamente todas as operações com listas em Prolog.

Predicados Clássicos para Listas

O Prolog oferece diversos predicados embutidos para manipulação de listas, e muitos outros podem ser facilmente definidos:

append/3: append(L1, L2, L3) — L3 é a concatenação de L1 e L2.
member/2: member(X, L) — X é elemento de L.
length/2: length(L, N) — N é o comprimento de L.
reverse/2: reverse(L, R) — R é L invertida.
sort/2: sort(L, S) — S é a lista ordenada de L (sem duplicatas).
maplist/2: aplica um predicado a todos os elementos de uma lista.

Algoritmos Recursivos em Listas: Merge Sort

O Merge Sort é um exemplo clássico de algoritmo recursivo em listas. A implementação em Prolog é elegante e declarativa:

% merge_sort(L, S) - S é a lista L ordenada
merge_sort([], []).
merge_sort([X], [X]).
merge_sort(L, S) :-
    length(L, N),
    M is N // 2,
    split(L, M, L1, L2),
    merge_sort(L1, S1),
    merge_sort(L2, S2),
    merge(S1, S2, S).

% split(L, N, L1, L2) - L1 e L2 são as duas metades de L
split(L, 0, [], L) :- !.
split([H|T], N, [H|L1], L2) :-
    N > 0,
    N1 is N - 1,
    split(T, N1, L1, L2).

% merge(L1, L2, L3) - L3 é a fusão ordenada de L1 e L2
merge([], L, L).
merge(L, [], L).
merge([H1|T1], [H2|T2], [H1|T]) :-
    H1 =< H2,
    merge(T1, [H2|T2], T).
merge([H1|T1], [H2|T2], [H2|T]) :-
    H1 > H2,
    merge([H1|T1], T2, T).

% merge_sort(L, S) - S é a lista L ordenada

merge_sort([], []).

merge_sort([X], [X]).

merge_sort(L, S) :-

length(L, N),

M is N // 2,

split(L, M, L1, L2),

merge_sort(L1, S1),

merge_sort(L2, S2),

merge(S1, S2, S).

% split(L, N, L1, L2) - L1 e L2 são as duas metades de L

split(L, 0, [], L) :- !.

split([H|T], N, [H|L1], L2) :-

N > 0,

N1 is N - 1,

split(T, N1, L1, L2).

% merge(L1, L2, L3) - L3 é a fusão ordenada de L1 e L2

merge([], L, L).

merge(L, [], L).

merge([H1|T1], [H2|T2], [H1|T]) :-

H1 =< H2,

merge(T1, [H2|T2], T).

merge([H1|T1], [H2|T2], [H2|T]) :-

H1 > H2,

merge([H1|T1], T2, T).

Esse algoritmo demonstra como a recursão, o casamento de padrões e a divisão de listas se combinam para criar soluções poderosas com poucas linhas de código.

2. Estruturas (Functors): Objetos em Prolog

Além das listas, o Prolog permite criar estruturas compostas usando functors. Um functor é um nome que agrupa outros termos, funcionando como um “objeto” ou “registro”. Por exemplo:

% Estrutura: pessoa(Nome, Idade, Cidade)
pessoa(joao, 30, 'SP').
pessoa(maria, 25, 'RJ').
pessoa(pedro, 40, 'SP').

% Estrutura: pessoa(Nome, Idade, Cidade)

pessoa(joao, 30, 'SP').

pessoa(maria, 25, 'RJ').

pessoa(pedro, 40, 'SP').

Functors podem ser aninhados, criando estruturas mais complexas:

% Endereço: endereco(Rua, Numero, Cidade, Estado)
% Pessoa com endereço aninhado
pessoa(joao, 30, endereco('Rua A', 100, 'SP', 'SP')).

% Endereço: endereco(Rua, Numero, Cidade, Estado)

% Pessoa com endereço aninhado

pessoa(joao, 30, endereco('Rua A', 100, 'SP', 'SP')).

As estruturas em Prolog são imutáveis e funcionam como registros em outras linguagens. Elas são particularmente úteis para representar dados estruturados e podem ser usadas com unificação e casamento de padrões.

Aplicação Prática com Estruturas

Considere um sistema de biblioteca com livros e empréstimos:

% livro(Titulo, Autor, Ano, ISBN)
livro('O Senhor dos Anéis', 'Tolkien', 1954, '978-0-618-00222-8').
livro('1984', 'Orwell', 1949, '978-0-452-28423-4').

% emprestimo(Usuario, Livro, Data, Status)
emprestimo('ana', '1984', data(15, 6, 2024), 'ativo').
emprestimo('joao', 'O Senhor dos Anéis', data(10, 6, 2024), 'devolvido').

% livro(Titulo, Autor, Ano, ISBN)

livro('O Senhor dos Anéis', 'Tolkien', 1954, '978-0-618-00222-8').

livro('1984', 'Orwell', 1949, '978-0-452-28423-4').

% emprestimo(Usuario, Livro, Data, Status)

emprestimo('ana', '1984', data(15, 6, 2024), 'ativo').

emprestimo('joao', 'O Senhor dos Anéis', data(10, 6, 2024), 'devolvido').

Com essas estruturas, podemos criar consultas poderosas:

% Livros emprestados para um usuário
emprestimos_usuario(Usuario, Livros) :-
    findall(L, emprestimo(Usuario, L, _, 'ativo'), Livros).

% Livros publicados antes de 1950
livros_antigos(Antigos) :-
    findall(T, livro(T, _, A, _), A < 1950, Antigos).

% Empréstimos ativos em uma data específica
emprestimos_ativos(Data, Lista) :-
    findall(Usuario-Livro, emprestimo(Usuario, Livro, Data, 'ativo'), Lista).

% Livros emprestados para um usuário

emprestimos_usuario(Usuario, Livros) :-

findall(L, emprestimo(Usuario, L, _, 'ativo'), Livros).

% Livros publicados antes de 1950

livros_antigos(Antigos) :-

findall(T, livro(T, _, A, _), A < 1950, Antigos).

% Empréstimos ativos em uma data específica

emprestimos_ativos(Data, Lista) :-

findall(Usuario-Livro, emprestimo(Usuario, Livro, Data, 'ativo'), Lista).

A combinação de functors e listas permite modelar domínios complexos de forma natural e consultá-los de maneira declarativa, sem a necessidade de estruturas de controle complexas.

3. Conclusão

As listas e estruturas (functors) são as bases da modelagem de dados em Prolog. As listas oferecem uma maneira flexível e recursiva de agrupar elementos, enquanto os functors permitem criar objetos estruturados com campos nomeados.

A verdadeira força de Prolog vem da integração dessas estruturas com o mecanismo de busca e unificação: você pode definir dados, criar relações entre eles e consultar essas relações de forma natural e declarativa. Combine isso com recursão e você terá um toolkit poderoso para resolver problemas complexos.

Para aprofundar, pratique com:

Predicados para manipulação de listas (map, filter, fold, etc.)
Estruturas para representar dados do mundo real (pedidos, clientes, produtos)
Consultas complexas usando findall, setof e bagof
Algoritmos recursivos avançados em listas

Exercícios de Recursividade em Prolog

16/07/202615/07/2026 Por antonino

A melhor forma de aprender recursividade em Prolog é praticando! Neste artigo, vamos resolver três exercícios clássicos que cobrem diferentes aspectos da recursão: operações aritméticas, conversão de bases e caminhamento em grafos. Cada exercício inclui dicas, solução completa, testes e desafios extras.

Exercício 4.1: Produto de Números Naturais

Problema: Defina um predicado recursivo prod(X, Y, P) que calcule o produto de dois números naturais X e Y usando apenas soma e subtração.

Raciocínio

Sabemos que X * Y = X + X + X + … (Y vezes). Usando recursão:

Caso base: X * 0 = 0
Passo recursivo: X * Y = X + X * (Y-1)

Diagrama do Processo

prod(3, 4, P)
│
├─ Y = 4 > 0, Y1 = 3
│  chama prod(3, 3, P1)
│  │
│  ├─ Y = 3 > 0, Y1 = 2
│  │  chama prod(3, 2, P2)
│  │  │
│  │  ├─ Y = 2 > 0, Y1 = 1
│  │  │  chama prod(3, 1, P3)
│  │  │  │
│  │  │  ├─ Y = 1 > 0, Y1 = 0
│  │  │  │  chama prod(3, 0, P4)
│  │  │  │  │
│  │  │  │  ├─ [BASE] prod(3, 0, 0)  ✅
│  │  │  │  │
│  │  │  │  └─ P4 = 0
│  │  │  │
│  │  │  └─ P3 = 3 + 0 = 3
│  │  │
│  │  └─ P2 = 3 + 3 = 6
│  │
│  └─ P1 = 3 + 6 = 9
│
└─ P = 3 + 9 = 12  ✅

prod(3, 4, P)

│

├─ Y = 4 > 0, Y1 = 3

│ chama prod(3, 3, P1)

│ │

│ ├─ Y = 3 > 0, Y1 = 2

│ │ chama prod(3, 2, P2)

│ │ │

│ │ ├─ Y = 2 > 0, Y1 = 1

│ │ │ chama prod(3, 1, P3)

│ │ │ │

│ │ │ ├─ Y = 1 > 0, Y1 = 0

│ │ │ │ chama prod(3, 0, P4)

│ │ │ │ │

│ │ │ │ ├─ [BASE] prod(3, 0, 0) ✅

│ │ │ │ │

│ │ │ │ └─ P4 = 0

│ │ │ │

│ │ │ └─ P3 = 3 + 0 = 3

│ │ │

│ │ └─ P2 = 3 + 3 = 6

│ │

│ └─ P1 = 3 + 6 = 9

│

└─ P = 3 + 9 = 12 ✅

Solução em Prolog

% prod(X, Y, P) - P é o produto de X e Y
% Caso base: qualquer número multiplicado por 0 é 0
prod(_, 0, 0).

% Passo recursivo: X * Y = X + X * (Y-1)
prod(X, Y, P) :-
    Y > 0,                % Garante que Y é positivo
    Y1 is Y - 1,          % Decrementa Y
    prod(X, Y1, P1),      % Chama recursivamente com Y-1
    P is P1 + X.          % Soma X ao resultado parcial

% prod(X, Y, P) - P é o produto de X e Y

% Caso base: qualquer número multiplicado por 0 é 0

prod(_, 0, 0).

% Passo recursivo: X * Y = X + X * (Y-1)

prod(X, Y, P) :-

Y > 0, % Garante que Y é positivo

Y1 is Y - 1, % Decrementa Y

prod(X, Y1, P1), % Chama recursivamente com Y-1

P is P1 + X. % Soma X ao resultado parcial

Consultas de Teste

?- prod(3, 4, P).
P = 12.

?- prod(5, 0, P).
P = 0.

?- prod(7, 3, P).
P = 21.

?- prod(0, 5, P).
P = 0.

?- prod(3, 4, P).

P = 12.

?- prod(5, 0, P).

P = 0.

?- prod(7, 3, P).

P = 21.

?- prod(0, 5, P).

P = 0.

Desafios Adicionais

Modifique o predicado para funcionar com números negativos.
Implemente potencia(Base, Expoente, Resultado) usando o mesmo padrão recursivo.
Implemente divisao(Dividendo, Divisor, Quociente, Resto) usando apenas subtração.

Exercício 4.2: Número Natural em Binário

Problema: Defina um predicado recursivo binario(N, B) que converta um número natural N para sua representação binária B (como lista de bits).

Raciocínio

Para converter um número para binário:

Caso base: N = 0 → [0]; N = 1 → [1]
Passo recursivo: O bit menos significativo é N mod 2; o resto é a representação binária de N // 2.

Exemplo: 13 em binário é 1101.

13 / 2 = 6, resto 1  → bit menos significativo = 1
 6 / 2 = 3, resto 0  → próximo bit = 0
 3 / 2 = 1, resto 1  → próximo bit = 1
 1 / 2 = 0, resto 1  → próximo bit = 1

Resultado: [1, 1, 0, 1] (lido de cima para baixo)

13 / 2 = 6, resto 1 → bit menos significativo = 1

6 / 2 = 3, resto 0 → próximo bit = 0

3 / 2 = 1, resto 1 → próximo bit = 1

1 / 2 = 0, resto 1 → próximo bit = 1

Resultado: [1, 1, 0, 1] (lido de cima para baixo)

Solução em Prolog

% binario(N, B) - B é a lista de bits da representação binária de N
% Caso base: números 0 e 1
binario(0, [0]).
binario(1, [1]).

% Passo recursivo: divide N por 2, converte o quociente e adiciona o resto
binario(N, B) :-
    N > 1,                % Apenas para números maiores que 1
    Q is N // 2,          % Quociente da divisão por 2
    R is N mod 2,         % Resto (bit menos significativo)
    binario(Q, B1),       % Converte o quociente recursivamente
    append(B1, [R], B).   % Adiciona o bit ao final da lista

% binario(N, B) - B é a lista de bits da representação binária de N

% Caso base: números 0 e 1

binario(0, [0]).

binario(1, [1]).

% Passo recursivo: divide N por 2, converte o quociente e adiciona o resto

binario(N, B) :-

N > 1, % Apenas para números maiores que 1

Q is N // 2, % Quociente da divisão por 2

R is N mod 2, % Resto (bit menos significativo)

binario(Q, B1), % Converte o quociente recursivamente

append(B1, [R], B). % Adiciona o bit ao final da lista

Consultas de Teste

?- binario(13, B).
B = [1, 1, 0, 1].

?- binario(0, B).
B = [0].

?- binario(5, B).
B = [1, 0, 1].

?- binario(255, B).
B = [1, 1, 1, 1, 1, 1, 1, 1].

?- binario(13, B).

B = [1, 1, 0, 1].

?- binario(0, B).

B = [0].

?- binario(5, B).

B = [1, 0, 1].

?- binario(255, B).

B = [1, 1, 1, 1, 1, 1, 1, 1].

Desafios Adicionais

Implemente binario_str(N, S) que retorna uma string binária em vez de lista.
Implemente decimal(B, N) que converte uma lista de bits de volta para decimal.
Implemente binario_completo(N, Bits, Tamanho) que retorna a representação com um número fixo de bits (ex: 8 bits).

Exercício 4.3: Mapa de Estradas

Problema: Dado um mapa de estradas com distâncias, defina um predicado dist(A, B, D) que calcule a distância total entre duas cidades A e B, considerando caminhos diretos e indiretos.

Raciocínio

Temos fatos estrada(Origem, Destino, Km). Queremos encontrar a distância total entre duas cidades:

Caso base: Existe uma estrada direta entre A e B.
Passo recursivo: Existe uma estrada de A para C, e um caminho de C para B.

Diagrama do Mapa

     10
A -------- B
|          |
| 15       | 20
|          |
C -------- D
     25

Estradas:
- estrada(a, b, 10)
- estrada(a, c, 15)
- estrada(b, d, 20)
- estrada(c, d, 25)

Rotas possíveis:
- a → b → d = 10 + 20 = 30
- a → c → d = 15 + 25 = 40
- a → b → d → c → a = 10 + 20 + 25 + 15 = 70 (ciclo)

A -------- B

| |

| 15 | 20

| |

C -------- D

Estradas:

- estrada(a, b, 10)

- estrada(a, c, 15)

- estrada(b, d, 20)

- estrada(c, d, 25)

Rotas possíveis:

- a → b → d = 10 + 20 = 30

- a → c → d = 15 + 25 = 40

- a → b → d → c → a = 10 + 20 + 25 + 15 = 70 (ciclo)

Solução em Prolog

% Fatos: estrada(Origem, Destino, Km)
estrada(a, b, 10).
estrada(a, c, 15).
estrada(b, d, 20).
estrada(c, d, 25).

% Para rotas bidirecionais (opcional)
estrada(X, Y, D) :- estrada(Y, X, D).

% dist(A, B, D) - D é a distância total entre A e B
% Caso base: estrada direta
dist(A, B, D) :-
    estrada(A, B, D).

% Passo recursivo: A → C → B
dist(A, B, D) :-
    estrada(A, C, D1),    % Vai de A para C
    dist(C, B, D2),       % Caminho de C para B
    D is D1 + D2.         % Soma as distâncias

% Fatos: estrada(Origem, Destino, Km)

estrada(a, b, 10).

estrada(a, c, 15).

estrada(b, d, 20).

estrada(c, d, 25).

% Para rotas bidirecionais (opcional)

estrada(X, Y, D) :- estrada(Y, X, D).

% dist(A, B, D) - D é a distância total entre A e B

% Caso base: estrada direta

dist(A, B, D) :-

estrada(A, B, D).

% Passo recursivo: A → C → B

dist(A, B, D) :-

estrada(A, C, D1), % Vai de A para C

dist(C, B, D2), % Caminho de C para B

D is D1 + D2. % Soma as distâncias

Problema: Loops Infinitos!

O predicado acima pode entrar em loops infinitos devido a ciclos no grafo. Para resolver isso, mantemos uma lista de visitados:

% dist_seguro(A, B, D) - com prevenção de loops
dist_seguro(A, B, D) :-
    dist_seguro(A, B, [A], D).

% Caso base: estrada direta
dist_seguro(A, B, _, D) :-
    estrada(A, B, D).

% Passo recursivo com lista de visitados
dist_seguro(A, B, Visitados, D) :-
    estrada(A, C, D1),
    \+ member(C, Visitados),      % C não foi visitado ainda
    dist_seguro(C, B, [C|Visitados], D2),
    D is D1 + D2.

% dist_seguro(A, B, D) - com prevenção de loops

dist_seguro(A, B, D) :-

dist_seguro(A, B, [A], D).

% Caso base: estrada direta

dist_seguro(A, B, _, D) :-

estrada(A, B, D).

% Passo recursivo com lista de visitados

dist_seguro(A, B, Visitados, D) :-

estrada(A, C, D1),

\+ member(C, Visitados), % C não foi visitado ainda

dist_seguro(C, B, [C|Visitados], D2),

D is D1 + D2.

Consultas de Teste

?- dist(a, d, D).
D = 30 ;    % Via b
D = 40 ;    % Via c
false.

?- dist_seguro(a, d, D).
D = 30 ;    % Via b
D = 40 ;    % Via c
false.

?- dist(a, a, D).
D = 0 ;     % (se houver estrada direta de a para a)
... loop infinito (com dist)
... false (com dist_seguro, após explorar ciclos)

?- dist_seguro(a, b, D).
D = 10 ;    % Direto
D = 40 ;    % Via c → d → b (15 + 25 + 20)
D = 70 ;    % Via c → d → b → a → ... (ciclo) - com dist_seguro, evita

?- dist(a, d, D).

D = 30 ; % Via b

D = 40 ; % Via c

false.

?- dist_seguro(a, d, D).

D = 30 ; % Via b

D = 40 ; % Via c

false.

?- dist(a, a, D).

D = 0 ; % (se houver estrada direta de a para a)

... loop infinito (com dist)

... false (com dist_seguro, após explorar ciclos)

?- dist_seguro(a, b, D).

D = 10 ; % Direto

D = 40 ; % Via c → d → b (15 + 25 + 20)

D = 70 ; % Via c → d → b → a → ... (ciclo) - com dist_seguro, evita

Desafios Adicionais

Caminho mais curto: Implemente menor_dist(A, B, D) que encontra a menor distância entre A e B (use findall/3 e min_list/2).
Lista de cidades: Modifique o predicado para retornar a lista de cidades no caminho, além da distância.
Grafo com pesos negativos: Como você lidaria com estradas de “mão única” ou pesos negativos?
Todas as rotas: Implemente todas_rotas(A, B, R) que retorna todas as rotas possíveis entre A e B (sem loops).

Conclusão: A Importância da Recursão em Prolog

Os exercícios acima demonstram três áreas onde a recursão em Prolog é essencial:

Operações aritméticas: A recursão permite definir operações matemáticas a partir de conceitos mais simples, como soma e subtração.
Conversão e processamento de dados: A recursão é natural para processar estruturas hierárquicas, como a representação binária de números.
Exploração de grafos: A recursão é a ferramenta ideal para navegar em estruturas interconectadas, encontrando caminhos e calculando distâncias.

A beleza da recursão em Prolog está na sua simplicidade declarativa: você descreve o caso base e a regra de redução, e o Prolog cuida da execução, backtracking e busca de soluções. Isso permite que problemas complexos sejam expressos em poucas linhas de código.

Para dominar a recursão em Prolog, pratique com diferentes tipos de problemas:

Estruturas de lista: soma, inversão, busca, ordenação
Árvores: percurso, altura, busca
Grafos: caminhos, ciclos, conectividade
Matemática: sequências, séries, relações

Lembre-se sempre: todo predicado recursivo precisa de um caso base e de uma garantia de progresso (a chamada recursiva deve operar sobre uma instância menor do problema). Com isso, você estará pronto para explorar todo o poder da programação lógica!