Arquivo de prolog - Página 2 de 13

Estruturas (Functors)

16/07/202615/07/2026 Por antonino

Em Prolog, estruturas (também chamadas de functors) são a forma de criar objetos de dados complexos que agrupam múltiplos componentes sob um mesmo nome. Elas são equivalentes a registros em outras linguagens, permitindo modelar dados estruturados de forma natural e declarativa.

1. O que é uma Estrutura?

Uma estrutura em Prolog é um objeto composto que agrupa vários componentes (argumentos) sob um functor (um nome que identifica o tipo da estrutura). A sintaxe é:

functor(componente1, componente2, componente3, ...)

1	functor(componente1, componente2, componente3, ...)

Os componentes podem ser de qualquer tipo: átomos, números, variáveis ou até mesmo outras estruturas.

Exemplos de Estruturas

% Uma data: dia, mês, ano
data(6, agosto, 2003)

% Um ponto no plano cartesiano
ponto(3, 5)

% Uma pessoa com nome, idade e cidade
pessoa(joao, 30, 'São Paulo')

% Uma linha com dois pontos
linha(ponto(7,9), ponto(13,2))

% Uma data: dia, mês, ano

data(6, agosto, 2003)

% Um ponto no plano cartesiano

ponto(3, 5)

% Uma pessoa com nome, idade e cidade

pessoa(joao, 30, 'São Paulo')

% Uma linha com dois pontos

linha(ponto(7,9), ponto(13,2))

2. Estruturas como Dados vs. Fatos como Relacionamentos

É importante entender a diferença entre estruturas e fatos:

Estrutura: Um objeto de dados. Ex: ponto(3,5) é um dado que representa um ponto no plano.
Fato: Um relacionamento entre objetos. Ex: distancia(ponto(0,0), ponto(3,4), 5). é um fato que relaciona dois pontos e sua distância.

Estruturas podem aparecer como argumentos dentro de fatos e regras.

3. Programa 5.6: Acontecimentos Históricos

Vamos criar uma base de dados de acontecimentos históricos usando estruturas para representar datas:

% hist(Data, Acontecimento)
% Data é uma estrutura: data(Dia, Mes, Ano)

hist(data(7, setembro, 1822), 'Independência do Brasil').
hist(data(13, maio, 1888), 'Abolição da Escravatura').
hist(data(15, novembro, 1889), 'Proclamação da República').
hist(data(25, dezembro, 1991), 'Fim da União Soviética').
hist(data(11, setembro, 2001), 'Atentados de 11 de setembro').

% hist(Data, Acontecimento)

% Data é uma estrutura: data(Dia, Mes, Ano)

hist(data(7, setembro, 1822), 'Independência do Brasil').

hist(data(13, maio, 1888), 'Abolição da Escravatura').

hist(data(15, novembro, 1889), 'Proclamação da República').

hist(data(25, dezembro, 1991), 'Fim da União Soviética').

hist(data(11, setembro, 2001), 'Atentados de 11 de setembro').

Consultando Acontecimentos Históricos

1. Qual é o acontecimento de uma data específica?

?- hist(data(7, setembro, 1822), F).
F = 'Independência do Brasil'.

1 2	?- hist(data(7, setembro, 1822), F). F = 'Independência do Brasil'.

2. Em que data ocorreu a Proclamação da República?

?- hist(D, 'Proclamação da República').
D = data(15, novembro, 1889).

1 2	?- hist(D, 'Proclamação da República'). D = data(15, novembro, 1889).

3. Quais acontecimentos ocorreram no mês de setembro?

?- hist(data(_, setembro, _), F).
F = 'Independência do Brasil' ;
F = 'Atentados de 11 de setembro' ;
false.

?- hist(data(_, setembro, _), F).

F = 'Independência do Brasil' ;

F = 'Atentados de 11 de setembro' ;

false.

4. Quais acontecimentos ocorreram no século XIX (anos 1800-1899)?

?- hist(data(_, _, Ano), F), Ano >= 1800, Ano < 1900.
Ano = 1822, F = 'Independência do Brasil' ;
Ano = 1888, F = 'Abolição da Escravatura' ;
Ano = 1889, F = 'Proclamação da República' ;
false.

?- hist(data(_, _, Ano), F), Ano >= 1800, Ano < 1900.

Ano = 1822, F = 'Independência do Brasil' ;

Ano = 1888, F = 'Abolição da Escravatura' ;

Ano = 1889, F = 'Proclamação da República' ;

false.

5. Extrair partes da data:

?- hist(data(Dia, Mes, Ano), 'Independência do Brasil').
Dia = 7, Mes = setembro, Ano = 1822.

1 2	?- hist(data(Dia, Mes, Ano), 'Independência do Brasil'). Dia = 7, Mes = setembro, Ano = 1822.

4. O Conceito de Functor

O functor é a “tag” ou “rótulo” que identifica o tipo da estrutura. Ele consiste no nome do functor e na sua aridade (número de argumentos).

data/3   % Functor "data" com 3 argumentos
ponto/2  % Functor "ponto" com 2 argumentos
pessoa/3 % Functor "pessoa" com 3 argumentos
linha/2  % Functor "linha" com 2 argumentos

data/3 % Functor "data" com 3 argumentos

ponto/2 % Functor "ponto" com 2 argumentos

pessoa/3 % Functor "pessoa" com 3 argumentos

linha/2 % Functor "linha" com 2 argumentos

Dois functors com o mesmo nome mas aridades diferentes são considerados diferentes. Por exemplo, data/3 (dia, mês, ano) e data/2 (mês, ano) são functors distintos.

5. Estruturas Aninhadas

Uma das grandes vantagens das estruturas é que elas podem ser aninhadas, permitindo modelar dados complexos de forma hierárquica.

% Linha definida por dois pontos
linha(ponto(7,9), ponto(13,2)).

% Endereço com rua, número, cidade e estado
endereco('Rua das Flores', 100, 'São Paulo', 'SP').

% Pessoa com nome, idade, endereço e telefone
pessoa(joao, 30, endereco('Rua A', 10, 'RJ', 'RJ'), telefone(11, 987654321)).

% Linha definida por dois pontos

linha(ponto(7,9), ponto(13,2)).

% Endereço com rua, número, cidade e estado

endereco('Rua das Flores', 100, 'São Paulo', 'SP').

% Pessoa com nome, idade, endereço e telefone

pessoa(joao, 30, endereco('Rua A', 10, 'RJ', 'RJ'), telefone(11, 987654321)).

Consultas com Estruturas Aninhadas

% Extrair coordenadas de uma linha
?- linha(ponto(X1,Y1), ponto(X2,Y2)).
X1 = 7, Y1 = 9, X2 = 13, Y2 = 2.

% Encontrar pessoas de um determinado estado
?- pessoa(Nome, _, endereco(_, _, _, Estado), _).
Nome = joao, Estado = 'SP'.

% Extrair o telefone de uma pessoa
?- pessoa(joao, _, _, telefone(DDD, Numero)).
DDD = 11, Numero = 987654321.

% Extrair coordenadas de uma linha

?- linha(ponto(X1,Y1), ponto(X2,Y2)).

X1 = 7, Y1 = 9, X2 = 13, Y2 = 2.

% Encontrar pessoas de um determinado estado

?- pessoa(Nome, _, endereco(_, _, _, Estado), _).

Nome = joao, Estado = 'SP'.

% Extrair o telefone de uma pessoa

?- pessoa(joao, _, _, telefone(DDD, Numero)).

DDD = 11, Numero = 987654321.

6. Exercícios Propostos

Pratique a criação e uso de estruturas com estes desafios:

Livro: Crie uma estrutura livro/4 com título, autor, ano e ISBN. Adicione alguns fatos livro(...) e faça consultas para:
- Encontrar todos os livros de um autor específico.
- Encontrar livros publicados antes de 1950.
- Extrair o ISBN de um livro pelo título.
Funcionário: Crie uma estrutura funcionario/4 com nome, cargo, salário e departamento. Adicione fatos e consulte:
- Funcionários com salário acima de 5000.
- Funcionários de um determinado departamento.
- Encontrar o salário de um funcionário pelo nome.
Endereço aninhado: Crie uma estrutura pessoa/3 com nome, idade e endereco/4 (rua, número, cidade, estado). Adicione fatos e consulte:
- Pessoas que moram em um determinado estado.
- Pessoas que moram em uma determinada cidade.
- Pessoas com idade acima de 18 anos.
Pedido: Crie estruturas para representar um sistema de pedidos:
- produto(Nome, Preco)
- item(Produto, Quantidade)
- pedido(Numero, Cliente, ListaDeItens, Total)
Desafio: Calcule o total do pedido somando preco * quantidade.

7. Conclusão

As estruturas (functors) são uma ferramenta essencial em Prolog para:

Modelar dados complexos: Agrupe informações relacionadas em um único objeto.
Criar hierarquias: Aninhe estruturas para representar dados com múltiplos níveis.
Facilitar consultas: Use padrões de unificação para extrair componentes específicos.
Organizar o código: Dê nomes significativos aos seus dados usando functors.

Diferente de listas (que são sequências), estruturas têm componentes fixos e nomeados (pelo functor), o que as torna ideais para representar entidades do mundo real com atributos conhecidos.

Pratique com os exercícios e explore como estruturas podem tornar seus programas Prolog mais legíveis, organizados e expressivos!

Algoritmos Recursivos em Listas (Merge Sort)

16/07/202615/07/2026 Por antonino

O Merge Sort é um algoritmo clássico de ordenação baseado no paradigma “dividir para conquistar”. Em Prolog, sua implementação é particularmente elegante devido à natureza recursiva das listas e ao poder da unificação. Vamos construir o algoritmo passo a passo.

1. O Paradigma “Dividir para Conquistar”

O Merge Sort segue três passos fundamentais:

Distribuir (Dividir): A lista original é dividida em duas sublistas aproximadamente iguais.
Ordenar recursivamente (Conquistar): Cada sublista é ordenada recursivamente usando o mesmo algoritmo.
Intercalar (Combinar): As duas sublistas ordenadas são mescladas em uma única lista ordenada.

2. Passo 1: Distribuir — `distribui/3` (Programa 5.4)

O predicado distribui/3 divide uma lista em duas, alternando os elementos entre elas.

% distribui(L, A, B) - A e B são as duas metades de L (alternadas)
% Caso base: lista vazia → duas listas vazias
distribui([], [], []).

% Caso base: lista com um elemento → A recebe o elemento, B fica vazio
distribui([X], [X], []).

% Passo recursivo: [X,Y|Z] → X vai para A, Y vai para B, continua com Z
distribui([X,Y|Z], [X|A], [Y|B]) :-
    distribui(Z, A, B).

% distribui(L, A, B) - A e B são as duas metades de L (alternadas)

% Caso base: lista vazia → duas listas vazias

distribui([], [], []).

% Caso base: lista com um elemento → A recebe o elemento, B fica vazio

distribui([X], [X], []).

% Passo recursivo: [X,Y|Z] → X vai para A, Y vai para B, continua com Z

distribui([X,Y|Z], [X|A], [Y|B]) :-

distribui(Z, A, B).

Explicação Passo-a-Passo

distribui([], [], []): Se a lista está vazia, ambas as sublistas estão vazias.
distribui([X], [X], []): Se a lista tem um elemento, ele vai para a primeira lista.
distribui([X,Y|Z], [X|A], [Y|B]): O primeiro elemento X vai para A, o segundo Y vai para B, e a recursão distribui o restante Z.

Exemplo de Distribuição

?- distribui([1,2,3,4,5,6], A, B).
A = [1,3,5],
B = [2,4,6].

?- distribui([a,b,c,d,e], A, B).
A = [a,c,e],
B = [b,d].

?- distribui([1,2,3,4,5,6], A, B).

A = [1,3,5],

B = [2,4,6].

?- distribui([a,b,c,d,e], A, B).

A = [a,c,e],

B = [b,d].

3. Passo 2: Intercalar — `intercala/3`

O predicado intercala/3 mescla duas listas ordenadas em uma única lista ordenada.

% intercala(A, B, C) - C é a fusão ordenada de A e B
% Caso base: A vazia → resultado é B
intercala([], B, B).

% Caso base: B vazia → resultado é A
intercala(A, [], A).

% Passo recursivo: compara as cabeças, coloca a menor primeiro
intercala([X|A], [Y|B], [X|C]) :-
    X =< Y,
    intercala(A, [Y|B], C).

intercala([X|A], [Y|B], [Y|C]) :-
    X > Y,
    intercala([X|A], B, C).

% intercala(A, B, C) - C é a fusão ordenada de A e B

% Caso base: A vazia → resultado é B

intercala([], B, B).

% Caso base: B vazia → resultado é A

intercala(A, [], A).

% Passo recursivo: compara as cabeças, coloca a menor primeiro

intercala([X|A], [Y|B], [X|C]) :-

X =< Y,

intercala(A, [Y|B], C).

intercala([X|A], [Y|B], [Y|C]) :-

X > Y,

intercala([X|A], B, C).

Explicação Passo-a-Passo

intercala([], B, B): Se A está vazia, o resultado é B.
intercala(A, [], A): Se B está vazia, o resultado é A.
intercala([X|A], [Y|B], [X|C]): Se X ≤ Y, X é colocado na frente e a intercalação continua com A e [Y|B].
intercala([X|A], [Y|B], [Y|C]): Se X > Y, Y é colocado na frente e a intercalação continua com [X|A] e B.

Exemplo de Intercalação

?- intercala([1,3,5], [2,4,6], C).
C = [1,2,3,4,5,6].

?- intercala([a,c,e], [b,d], C).
C = [a,b,c,d,e].

?- intercala([1,3,5], [2,4,6], C).

C = [1,2,3,4,5,6].

?- intercala([a,c,e], [b,d], C).

C = [a,b,c,d,e].

4. Passo 3: Ordenar — `ordena/2`

O predicado ordena/2 combina distribuição, ordenação recursiva e intercalação.

% ordena(L, S) - S é a lista L ordenada
% Caso base: lista vazia
ordena([], []).

% Caso base: lista com um elemento
ordena([X], [X]).

% Passo recursivo: divide, ordena cada parte, intercala
ordena([X,Y|Z], S) :-
    distribui([X,Y|Z], A, B),   % Divide a lista
    ordena(A, As),              % Ordena a primeira metade
    ordena(B, Bs),              % Ordena a segunda metade
    intercala(As, Bs, S).       % Intercala as duas metades ordenadas

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

% Caso base: lista vazia

ordena([], []).

% Caso base: lista com um elemento

ordena([X], [X]).

% Passo recursivo: divide, ordena cada parte, intercala

ordena([X,Y|Z], S) :-

distribui([X,Y|Z], A, B), % Divide a lista

ordena(A, As), % Ordena a primeira metade

ordena(B, Bs), % Ordena a segunda metade

intercala(As, Bs, S). % Intercala as duas metades ordenadas

5. Fluxo de Execução: ordena([3,5,0,4,1,2], S)

Vamos acompanhar a execução passo a passo:

1. distribui([3,5,0,4,1,2], A, B)
   A = [3,0,1], B = [5,4,2]

2. ordena([3,0,1], As)
   a. distribui([3,0,1], A1, B1) → A1 = [3,1], B1 = [0]
   b. ordena([3,1], As1)
      - distribui([3,1], A2, B2) → A2 = [3], B2 = [1]
      - ordena([3], [3])
      - ordena([1], [1])
      - intercala([3], [1], S1) → S1 = [1,3]
   c. ordena([0], [0])
   d. intercala([1,3], [0], As) → As = [0,1,3]

3. ordena([5,4,2], Bs)
   a. distribui([5,4,2], A3, B3) → A3 = [5,2], B3 = [4]
   b. ordena([5,2], Bs1)
      - distribui([5,2], A4, B4) → A4 = [5], B4 = [2]
      - ordena([5], [5])
      - ordena([2], [2])
      - intercala([5], [2], S2) → S2 = [2,5]
   c. ordena([4], [4])
   d. intercala([2,5], [4], Bs) → Bs = [2,4,5]

4. intercala([0,1,3], [2,4,5], S)
   S = [0,1,2,3,4,5]

1. distribui([3,5,0,4,1,2], A, B)

A = [3,0,1], B = [5,4,2]

2. ordena([3,0,1], As)

a. distribui([3,0,1], A1, B1) → A1 = [3,1], B1 = [0]

b. ordena([3,1], As1)

- distribui([3,1], A2, B2) → A2 = [3], B2 = [1]

- ordena([3], [3])

- ordena([1], [1])

- intercala([3], [1], S1) → S1 = [1,3]

c. ordena([0], [0])

d. intercala([1,3], [0], As) → As = [0,1,3]

3. ordena([5,4,2], Bs)

a. distribui([5,4,2], A3, B3) → A3 = [5,2], B3 = [4]

b. ordena([5,2], Bs1)

- distribui([5,2], A4, B4) → A4 = [5], B4 = [2]

- ordena([5], [5])

- ordena([2], [2])

- intercala([5], [2], S2) → S2 = [2,5]

c. ordena([4], [4])

d. intercala([2,5], [4], Bs) → Bs = [2,4,5]

4. intercala([0,1,3], [2,4,5], S)

S = [0,1,2,3,4,5]

Consulta Completa

?- ordena([3,5,0,4,1,2], S).
S = [0,1,2,3,4,5].

?- ordena([5,2,8,1,9,3], S).
S = [1,2,3,5,8,9].

?- ordena([], S).
S = [].

?- ordena([7], S).
S = [7].

?- ordena([3,5,0,4,1,2], S).

S = [0,1,2,3,4,5].

?- ordena([5,2,8,1,9,3], S).

S = [1,2,3,5,8,9].

?- ordena([], S).

S = [].

?- ordena([7], S).

S = [7].

6. Árvore de Recursão do Merge Sort

Visualize a árvore de recursão para ordena([3,5,0,4,1,2], S):

                    [3,5,0,4,1,2]
                    /           \
              [3,0,1]           [5,4,2]
              /     \           /     \
           [3,1]   [0]       [5,2]   [4]
           /   \             /   \
        [3]   [1]         [5]   [2]
         |     |           |     |
        [3]   [1]         [5]   [2]
           \   /             \   /
          [1,3]             [2,5]
              \             /
            [0,1,3]     [2,4,5]
                 \     /
              [0,1,2,3,4,5]

[3,5,0,4,1,2]

/ \

[3,0,1] [5,4,2]

/ \ / \

[3,1] [0] [5,2] [4]

/ \ / \

[3] [1] [5] [2]

| | | |

[3] [1] [5] [2]

\ / \ /

[1,3] [2,5]

\ /

[0,1,3] [2,4,5]

\ /

[0,1,2,3,4,5]

7. Análise de Complexidade

O Merge Sort tem complexidade:

Tempo: O(n log n) no pior caso, médio e melhor caso.
Espaço: O(n) para armazenar as sublistas durante a intercalação.

Em Prolog, a implementação é particularmente elegante porque:

A recursão natural do Prolog se alinha perfeitamente com a estrutura do algoritmo.
A unificação simplifica a distribuição e intercalação.
O código é declarativo e fácil de ler.

8. Exercícios Propostos

Insertion Sort: Implemente o algoritmo Insertion Sort em Prolog.
Dica: Use insere/3 para inserir um elemento em uma lista ordenada.
Quick Sort: Implemente o Quick Sort em Prolog.
Dica: Use um pivô (ex: o primeiro elemento) e divida a lista em menores e maiores.
Bubble Sort: Implemente o Bubble Sort em Prolog.
Dica: Use troca_uma_vez/2 e repita até a lista ficar ordenada.
Selection Sort: Implemente o Selection Sort.
Dica: Encontre o menor elemento, remova-o e ordene o resto.
Comparação: Teste os diferentes algoritmos com listas de diferentes tamanhos e compare a eficiência em termos de tempo (use time/1).

9. Conclusão

O Merge Sort é um exemplo perfeito de como o Prolog pode expressar algoritmos complexos de forma elegante e declarativa. Com poucas linhas de código, implementamos um algoritmo eficiente de ordenação que é:

Correto: A recursão garante que todas as partes sejam ordenadas.
Eficiente: O(log n) para divisão e O(n) para intercalação.
Legível: Cada passo do algoritmo é claramente expresso em Prolog.

Dominar o Merge Sort em Prolog é um excelente exercício para entender como a recursão, a unificação e a divisão de listas se combinam para criar soluções poderosas.

1. O que é uma Estrutura?

Exemplos de Estruturas

2. Estruturas como Dados vs. Fatos como Relacionamentos

3. Programa 5.6: Acontecimentos Históricos

Consultando Acontecimentos Históricos

4. O Conceito de Functor

5. Estruturas Aninhadas

Consultas com Estruturas Aninhadas

6. Exercícios Propostos

7. Conclusão

1. O Paradigma “Dividir para Conquistar”

2. Passo 1: Distribuir — distribui/3 (Programa 5.4)

Explicação Passo-a-Passo

Exemplo de Distribuição

3. Passo 2: Intercalar — intercala/3

Explicação Passo-a-Passo

Exemplo de Intercalação

4. Passo 3: Ordenar — ordena/2

5. Fluxo de Execução: ordena([3,5,0,4,1,2], S)

Consulta Completa

6. Árvore de Recursão do Merge Sort

7. Análise de Complexidade

8. Exercícios Propostos

9. Conclusão

2. Passo 1: Distribuir — `distribui/3` (Programa 5.4)

3. Passo 2: Intercalar — `intercala/3`

4. Passo 3: Ordenar — `ordena/2`