Prolog/Listas

Listas e Strings

Listas

Uma lista não é um tipo de dados à parte, mas sim definida por uma construção recursiva (usando o termo '.'/2):

1. o átomo [] é uma lista vazia;
2. se T é uma lista e H é um elemento, então o termo '.'(H, T) é uma lista.

O primeiro elemento, chamado cabeça, é H, que é seguida pelo conteúdo do restante da lista, T, também chamado de cauda. A lista [1, 2, 3] seria representada internamente como '.'(1, '.'(2, '.'(3, []))). Um atalho sintático é [H | T], que é mais usado para construir regras. Uma lista pode ser processada como um todo processando o primeiro elemento, e em seguida o restante da lista, de forma recursiva.

Para conveniência do programador, as listas podem ser construídas e destruídas de várias formas.

• Enumerando os elementos: [abc, 1, f(X), Y, g(A,rst)]
• Precedendo-a com um elemento: [abc | L1]
• Precedendo-a com múltiplos elementos: [abc, 1, f(X) | L2]
• Expandindo o termo: '.'(abc, '.'(1, '.'(f(X), '.'(Y, '.'(g(A,rst), [])))))
• O predicado append

Strings

Strings são normalmente escritas como uma seqüência de caracteres entre aspas. É comum serem representadas internamente como listas de códigos de caracteres, em geral utilizando a codificação local ou Unicode, se o sistema dá suporte a Unicode. O ISO Prolog também permite que strings sejam representadas por uma lista de átomos com um único caractere.

Funções da biblioteca padrão que manipulam listas

Existem, na biblioteca padrão, várias funções que manipulam listas. A maioria destas funções são facilmente implementadas em prolog, usando-se recursão.

Member

Unifica um elemento a uma lista, quando o elemento pertence à lista.

Por exemplo,

 member(1, [1,2,3]).

retorna Yes. Por outro lado, podemos chamar:

 member(X, [1,2,3]).

o que faz X assumir, sucessivamente, os valores 1, 2 e 3.

Também pode-se fazer:

 member(2, [1,X,Y]).

que faz X = 2 e, sem seguida, Y = 2.

Até mesmo

 member(1, X).

é possível, unificando X com uma lista de cabeça 1 e corpo indefinido (como [1 | L1]), em seguida a uma lista do tipo [Y1, 1 | L2], em seguida a [Y1, Y2, 1 | L3] - esta é uma recursão que não termina.

Append

O comando

 append(L1, L2, L3).

unifica a lista L3 com a concatenação de L1 e L2. Esta função pode ser chamada passando-se L3, ou passando-se L1 e L2, ou qualquer outra combinação.

Por exemplo:

 append(X, Y, [1]).

retorna duas soluções, a primeira com X = [] e Y = [1], e a segunda com X = [1] e Y = [].

Um exemplo mais complicado:

 append(X, [a, b, Y], [Z, b, c| W]).

irá unificar X = [], Y = c, Z = a, W = [], em seguida X = [Z, b, c], W = [a, b, Y], em seguida X = [Z, b, c, U], W = [U, a, b, Y], e em seguida todas as listas no formato acima, em que U vai sendo substituído por listas de 2, 3, etc elementos.

Reverse

 reverse(X, Y).

Unifica a lista X com a reversa da lista Y. Novamente, existe liberdade em escolher quem será input e quem será output:

 reverse(X, [1, 2, 3]).
 reverse([a, b, c], Y).

Length

O número de elementos de uma lista.

 length(X, 0).

Unifica X = [].

length([a | X], 2).

Unifica X com uma lista de um elemento.