Prolog/Listas
Listas e Strings
[editar | editar código-fonte]Listas
[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):
- o átomo [] é uma lista vazia;
- 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
[editar | editar código-fonte]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.
Member
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]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.