Saltar para o conteúdo

Prolog/Listas

Origem: Wikilivros, livros abertos por um mundo aberto.

Listas e Strings

[editar | editar código-fonte]

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 (do inglês "head"), que é seguida pelo conteúdo do restante da lista, T (do inglês "tail"), 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 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

[editar | editar código-fonte]

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.

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.

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(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).

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.