Elsa Carvalho
Programação em Lógica e Funcional (2000/01)(Actualizado em 2004/05)
1Universidade da Madeira
Departamento de Matemática
Estruturas de Dados em Prolog
Em Prolog não existem estruturas de dados pré-definidas como nas linguagens convencionais. No entanto podemos simular as tradicionais estruturas de dados através de composição de termos Prolog chamados funções. Tipicamente utilizam-se estruturas binárias para este fim como é o caso das listas.
Elsa Carvalho
Programação em Lógica e Funcional (2000/01)(Actualizado em 2004/05)
2Universidade da Madeira
Departamento de Matemática
ListasTradicionalmente uma lista é representada pelo termo •(X, Y) em que X é um elemento e Y o resto da lista. nil denomina a lista vazia.
Em Prolog usa-se uma notação mais conveniente: uma lista é o termo [X|Y] em que X é o primeiro elemento e Y é o resto da lista. Por analogia com as linguagens funcionais podemos dizer que X é a cabeça da lista e Y é a cauda.
A lista vazia representa-se como [ ].
Termos equivalentes
•(a, nil) [a]
•(a, •(b,nil)) [a,b]
•(a, •(b,X)) [a,b|X]
Elsa Carvalho
Programação em Lógica e Funcional (2000/01)(Actualizado em 2004/05)
3Universidade da Madeira
Departamento de Matemática
ListasPodemos definir lista como
list([]).
list([X|Xs]) :- list(Xs).
Ao contrário das linguagens funcionais, em Prolog uma lista é um objecto polimórfico. Isto é, podemos ter listas com objectos de diferentes tipos.
Por exemplo:
[a, 1, ana, 5.32, [b,c], X, 6, [1, [2,3], 4], fim]
Elsa Carvalho
Programação em Lógica e Funcional (2000/01)(Actualizado em 2004/05)
4Universidade da Madeira
Departamento de Matemática
Listas e UnificaçãoUma lista com um só elemento: [X]
A unificação de [X | Xs] = [1, 2, 3, 4]
resulta em X = 1 e Xs = [2, 3, 4]
Lista com 3 elementos: [X, Y, Z]
Uma lista não vazia: [X | _ ] porque [] não unifica com [X | _ ]
A unificação de [X, Y | Ys] = [1, 2, 3, 4, 5, 6]
resulta em X = 1, Y =2 e Ys = [3, 4, 5, 6]
Elsa Carvalho
Programação em Lógica e Funcional (2000/01)(Actualizado em 2004/05)
5Universidade da Madeira
Departamento de Matemática
Predicados para manipular listasDeterminar se um elemento é membro de uma lista (member).
member(X, [X|_ ]).
member(X, [ _|Ys]) :- member(X, Ys).
Diferentes usos de member:
?member(3, [1,2,3,4,5])
ou seja, verificar se um dado elemento é membro de uma lista.
?member(W, [1,2])
ou seja, perguntar quais são os membros de uma lista.
Desenhe as árvores de pesquisa para cada uma das interrogações colocadas, utilizando a definição de member.
Elsa Carvalho
Programação em Lógica e Funcional (2000/01)(Actualizado em 2004/05)
6Universidade da Madeira
Departamento de Matemática
Predicados para manipular listasJuntar uma lista com outra e obter uma terceira (append).
append([ ], Ys, Ys).
append([X | Xs], Ys, [X | Zs]) :- append(Xs, Ys, Zs).
Desenhe a árvore de pesquisa para responder à interrogação
?append([1,2], [4,5,6], W)
Outros usos de append
Encontrar diferenças entre listas. Por exemplo
?append(Xs, [3,4], [1,2,3,4]).
dá como resposta Xs = [1,2]
Elsa Carvalho
Programação em Lógica e Funcional (2000/01)(Actualizado em 2004/05)
7Universidade da Madeira
Departamento de Matemática
Predicados para manipular listasOutros usos de append (cont.)
Partir uma lista em duas sub-listas:
?append(Xs, Ys, [1,2,3,4]).
obtemos várias respostas como por exemplo Xs=[1,2], Ys=[3,4].
Podemos também utilizar append para definir outros predicados:
adjacente, que expressa que dois elementos X e Y são adjacentes numa lista Zs:
adjacente(X, Y, Zs) :- append( _, [X,Y|_ ], Zs).
last, que expressa que um elemento é o último elemento da lista:
last(X, Xs) :- append( _, [X], Xs).
Elsa Carvalho
Programação em Lógica e Funcional (2000/01)(Actualizado em 2004/05)
8Universidade da Madeira
Departamento de Matemática
ExercíciosDefina os seguintes predicados de manipulação de listas:
prefixo(Xs, Ys): que é verdadeiro se Xs é uma sub-lista inicial de Ys. Por exemplo, prefixo([a,b], [a,b,c]) é verdadeiro.
sufixo(Xs, Ys): que é verdadeiro se Xs é uma sub-lista terminal de Ys. Por exemplo, sufixo([b,c], [a,b,c] é verdadeiro.
sublista(Xs, Ys): que é verdadeiro se Xs é uma sub-lista de Ys. De notar que uma sub-lista necessita que os elementos sejam consecutivos, ou seja, [b,c] é uma sub-lista de [a,b,c,d] enquanto que [a,c] não é.
Elsa Carvalho
Programação em Lógica e Funcional (2000/01)(Actualizado em 2004/05)
9Universidade da Madeira
Departamento de Matemática
ExercíciosResolução:
prefixo([ ], Ys).
prefixo([X|Xs], [X|Ys]) :- prefixo(Xs, Ys).
sufixo(Xs, Xs).
sufixo(Xs, [Y|Ys]) :- sufixo(Xs, Ys).
a) Sub-lista como um sufixo de um prefixo
sublista(Xs, Ys) :- prefixo(Ps, Ys), sufixo(Xs, Ps).
b) Sub-lista como um prefixo de um sufixo
sublista(Xs,Ys) :- sufixo(Ss, Ys), prefixo(Xs, Ss).
Elsa Carvalho
Programação em Lógica e Funcional (2000/01)(Actualizado em 2004/05)
10Universidade da Madeira
Departamento de Matemática
ExercíciosResolução:
c) Definição recursiva de sub-lista
sublista(Xs, Ys) :- prefixo(Xs, Ys).
sublista(Xs, [Y|Ys]) :- sublista(Xs, Ys).
d) Sufixo de um prefixo, usando o append
sublista(Xs, AsXsBs) :-
append(As, XsBs, AsXsBs), append(Xs, Bs, XsBs).
d) Prefixo de um sufixo, usando o append
sublista(Xs, AsXsBs) :-
append(AsXs, Bs, AsXsBs), append(As, Xs, AsXs).