Conceitos e Predicados de Listas em Prolog

Listas em Prolog

Exemplos de representação de listas:

• Lista1 = [a, b, c]
• Lista2 = [a, b, c]

Estruturas aninhadas:

• Hobbies1 = [tênis, música]
• Hobbies2 = [esqui, comida]
• L = [ana, [tênis, música], pedro, [esqui, comida]]

Estrutura de Listas: Cabeça e Cauda

Em geral, é comum tratar a cauda como um objeto simples.

• Por exemplo, L = [a, b, c] pode ser escrito como:
  • Cauda = [b, c]
  • L = .(a, Cauda)
• Para expressar isso, Prolog fornece a notação de barra vertical (|), que separa a cabeça da cauda:
  • L = [a | Cauda]
• A notação é geral, permitindo que qualquer número de elementos seja seguido por ‘|’ e o restante da lista:
  • [a, b, c] = [a | [b, c]] = [a, b | [c]] = [a, b, c | [ ]]

Predicado de Pertinência (pertence/2)

Define-se o predicado pertence(X, Y) para verificar se um elemento pertence a uma lista.

1. A primeira condição especifica que um elemento X pertence à lista se ele está na cabeça dela:pertence(X, [X|Z]).
2. A segunda condição especifica que um elemento X pertence à lista se ele pertencer à sua cauda:pertence(X, [W|Z]) :- pertence(X, Z).

Condições Limites e Caso Recursivo

Ao definir um procedimento recursivo, procuram-se as condições limites (parada) e o caso recursivo:

pertence(Cabeca, [Cabeca|Cauda]).
pertence(Cabeca, [OutraCabeca|Cauda]) :- 
    pertence(Cabeca, Cauda).

Exemplos de interrogação:

• ?- pertence(a, [a, b, c]). yes
• ?- pertence(d, [a, b, c]). no
• ?- pertence(X, [a, b, c]). X = a ; X = b ; X = c ; no

Observação: Interrogações como ?- pertence(a, X). ou ?- pertence(X, Y). podem ter infinitas respostas, pois existem infinitas listas que validam o procedimento.

Documentação de Modos de Ativação

Utiliza-se notação para documentar instanciações de variáveis:

• +: argumento de entrada (deve estar instanciado)
• -: argumento de saída (não deve estar instanciado)
• ?: argumento de entrada e saída (pode ou não estar instanciado)

O procedimento pertence/2 documentado para atingir a condição de parada:

% pertence(?Elemento, +Lista)
pertence(E, [E|_]).
pertence(E, [_|Cauda]) :- 
    pertence(E, Cauda).

Último Elemento de uma Lista

Procedimento para encontrar o último elemento:

• O último elemento de uma lista com um só elemento é o próprio elemento: ultimo(Elemento, [Elemento]).
• O último elemento de uma lista com mais de um elemento é o último elemento da cauda: ultimo(Elemento, [Cabeca|Cauda]) :- ultimo(Elemento, Cauda).

Procedimento completo:

% ultimo(?Elemento, +Lista)
ultimo(Elemento, [Elemento]).
ultimo(Elemento, [Cabeca|Cauda]) :- ultimo(Elemento, Cauda).

Inserção na Primeira Posição

Predicado insere/3:

insere(X, L, [X|L]).

Exemplo:

?- insere(a, [b, c, d], Y).
Y=[a, b, c, d];
no

Conversão para Valores Absolutos

Converte valores de uma lista em seus valores absolutos.

Exemplo: ?- converte([5, -3, 1, -4], L). resulta em L= [5, 3, 1, 4]

converte([ ], [ ]).
converte([X|L], [Y|L2]):-
    abs(X, Y),
    converte(L, L2).

Concatenar Duas Listas

Procedimento concatenar/3:

• Se o primeiro argumento é a lista vazia, o segundo e terceiro argumentos devem ser iguais: concatenar([ ], L, L).
• Se o primeiro argumento é não-vazio ([X|L1]), a concatenação com L2 resulta em [X|L3], onde L3 é a concatenação de L1 e L2: concatenar([X|L1], L2, [X|L3]) :- concatenar(L1, L2, L3).

Procedimento completo:

% concatenar(?/+L1,?/?L2,+/?L)
concatenar([ ], L, L).
concatenar([X|L1], L2, [X|L3]) :- concatenar(L1, L2, L3).

Exemplo de interrogação:

?- concatenar(X, Y, [1, 2, 3, 4]).
X = [ ] Y = [1, 2, 3, 4];
X = [1] Y = [2, 3, 4];
X = [1, 2] Y = [3, 4];
X = [1, 2, 3] Y = [4];
X = [1, 2, 3, 4] Y = [ ];
no