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:
|
1 2 3 4 |
% 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
% 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:
|
1 2 3 4 5 |
% 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:
|
1 2 3 4 5 |
% 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:
|
1 2 3 4 5 6 7 8 9 |
% 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
% 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