Listas em Prolog

De Augusto Baffa Wiki
Ir para navegação Ir para pesquisar

Listas

Prolog usa colchetes [...] como um construtor de uma lista. A notação [X|Y] se refere a uma lista cujo primeiro elemento é X e cuja cauda é Y. Uma lista finita pode ser explicitamente enumerada, como [1,2,3,4]. As três definições a seguir devem fazer sentido para um programador Lisp, onde 'car' se refere ao primeiro elemento de uma lista, 'cdr' se refere ao final ou resto da lista e 'cons' é o construtor da lista. 

car([X|Y],X).
cdr([X|Y],Y).
cons(X,R,[X|R]).

significando ...

  • A cabeça (car) de [X|Y] é X.
  • A cauda (cdr) de [X|Y] é Y.
  • Colocando X na cabeça e Y como cauda construímos (cons) a lista [X|R].

No entanto, veremos que essas definições explícitas são desnecessárias. Uma lista cuja cabeça é X e cuja cauda é Y pode apenas ser referida usando o termo Prolog [X|Y]. Inversamente, se a lista pode ser unificada com o termo Prolog '[X|Y]', então o primeiro elemento da lista é vinculado a (unificado com) X e a cauda da lista é vinculada a Y.

Muitos dos predicados discutidos nesta seção são "nativos" para muitos intérpretes Prolog.

Considere a seguinte definição do predicado 'member/2'. 

member(X,[X|R]).
member(X,[Y|R]) :- member(X,R).

Pode-se ler as cláusulas da seguinte maneira, respectivamente:

  • X é membro de uma lista cujo primeiro elemento é X.
  • X é um membro de uma lista cuja cauda é R se X é um membro de R.

Este programa pode ser usado de várias maneiras. Pode-se testar se um item é mebro da lista: 

?- member(2,[1,2,3]).
Yes

Pode-se consultar membros de uma lista: 

?- member(X,[1,2,3]).
X = 1 ;
X = 2 ;
X = 3 ;
No

Segue a árvore de derivação mostrando como este último objetivo gerou todas as respostas.

Fig. 2.7

Cada ramificação esquerda corresponde a uma correspondência (unificação) com a primeira cláusula para 'member' e cada ramificação direita corresponde a uma correspondência com a segunda cláusula. O subobjetivo 'member(X,[])' no ramo direito inferior não corresponderá ao cabeçalho de qualquer cláusula 'member'. Em particular, '[]' não se unificará com um padrão da forma '[X|R]' porque o último representa uma lista com pelo menos um elemento.

Encontraremos muitos outros usos para 'member'. Este exemplo de consulta ... 

?- member([3,Y], [[1,a],[2,m],[3,z],[4,v],[3,p]]).
Y = z ;
Y = p ;
No

... sugere um uso onde se pretende pesquisar para encontrar elementos emparelhados com um elemento especificado. Aqui está outro, encontrando elementos de uma lista que satisfaçam alguma restrição: 

?- member(X,[23,45,67,12,222,19,9,6]), Y is X*X, Y < 100.
X = 9   Y = 81 ;
X = 6   Y = 36 ;
No

A definição de 'member' é geralmente escrita 

member(X,[X|_]).
member(X,[_|R]) :- member(X,R).

onde '_' (underscore) designa uma variável "irrelevante", geralmente chamada de variável anônima. Em geral, essas variáveis têm nomes cujo primeiro caractere é o sublinhado. Na verdade, eles correspondem a qualquer termo do Prolog, mas nenhuma ligação variável resulta da correspondência livre. Observe que isso é consistente com as intenções originais da definição de 'member'. Não ter que vincular valores a variáveis anônimas economiza um pouco de espaço e tempo de execução.

Relacionado a 'memebr' está a seguinte definição para 'takeout'. 

takeout(X,[X|R],R).
takeout(X,[F|R],[F|S]) :- takeout(X,R,S).

These clauses can be paraphrased in English as follows:

  • When X is taken out of [X|R], R results.
  • When X is taken out of the tail of [X|R], [X|S] results, where S is the result of taking X out of R.

Essas cláusulas podem ser parafraseadas em português da seguinte forma:

  • Quando X é retirado de [X|R], resulta em R.
  • Quando X é retirado da cauda de [X|R], resulta em [X|S], onde S é o resultado de tirar X de R.

Por exemplo, 

?- takeout(X,[1,2,3],L).
X=1  L=[2,3] ;
X=2  L=[1,3] ;
X=3  L=[1,2] ;
No

Observe que não seria apropriado usar nenhuma variável anônima na definição de 'takeout'. Aqui está uma árvore de cláusulas do programa mostrando que 'takeout(3,[1,2,3],[1,2])' é uma consequência da definição. Preste atenção especial em como exatamente as cláusulas são usadas para construir a árvore. 

takeout(3,[1,2,3],[1,2])
        |
        |
takeout(3,[2,3],[2])
        |
        |
takeout(3,[3],[])
        |
        |
      true

O objetivo a seguir, 

?- takeout(3,W,[a,b,c]).
W = [3,a,b,c] ;
W = [a,3,b,c] ;
W = [a,b,3,c] ;
W = [a,b,c,3] ;
No

mostra que 'takeout(X,Z,W)' também pode ser interpretado como "inserir X em W para produzir Z". Ou seja, 'takeout' tem o nome de apenas um de seus usos. Claro, pode-se definir

putin(X,L,R) :- takeout(X,R,L).

Segue uma definição para anexar ou concatenar duas listas Prolog. 

append([X|Y],Z,[X|W]) :- append(Y,Z,W).
append([],X,X).

Vários tipos de objetivos são possíveis: 

?- append([1,2,3],[4,5],[1,2,3,4,5]).
Yes

?- append([1,2,3],[4,5],A).
A = [1,2,3,4,5]

?- append([1,2,3],W,[1,2,3,4,5]).
W = [4,5]

... e assim por diante.


Exercício 2.7.1 Considere a seguinte definição alternativa para membro: 

member(X,[_|R) :- member(X,R).
member(X,[X|_]).

(a) Mostre que este programa teria exatamente as mesmas consequências da versão original. (b) Explique, entretanto, como e por que essa versão pode produzir comportamentos diferentes do objetivo do Prolog.


Exercício 2.7.2 Desenhe uma árvore de derivação Prolog para o objetivo '?- append([1,2],[a,b,c],A)'. Explique como é que o primeiro valor '[1,2]' é copiado para calcular o resultado A.

Reverter uma lista pode ser feito com 

reverse([X|Y],Z,W) :- reverse(Y,[X|Z],W).
reverse([],X,X).

Este programa ilustra a abordagem de Prolog para uma estratégia importante -= usando um parâmetro de acumulação (a variável do meio) -- para acumular uma resposta de lista até que o cálculo seja concluído. Por exemplo, considere a seguinte árvore de derivação (parcial) 

?- reverse([1,2,3],[],A)
        |
        |
   reverse([2,3],[1],A)
        |
        |
   reverse([3],[2,1],A)
        |
        |
   reverse([],[3,2,1],A)
        |
        |
       true   
      A = [3,2,1]

onde a primeira cláusula 'reverse' é usada três vezes e a segunda cláusula 'reverse' é usada para "capturar" a resposta combinando o segundo e o terceiro argumentos. Pode-se usar a seguinte definição para "ocultar" o parâmetro de acumulação.

reverse(A,R) :- reverse(A,[],R).


Exercício 2.7.3 Escreva uma versão de dois parâmetros de 'reverse' que não use a ideia de parâmetro de acumulação. Use 'append', por exemplo, onde uma regra seria parafraseada assim ...

reverta a lista [X|R] invertendo R para obter T, então anexar T a [X]

E sobre a eficiência desta versão? Compare-o com o 'reverse' fornecido acima. Aqui está uma definição interessante projetada para produzir todas as permutações possíveis de uma lista. 

perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W).   
perm([],[]).

Pense em 'takeout(X,Z,W)' como sendo usado no sentido de "X colocado em W produz Z" aqui. Então, as definições podem ser parafraseadas da seguinte forma:

  • Z é uma permutação de [X|Y] desde que W seja uma permutação de Y e então X é colocado em W para produzir Z.
  • [] é a (única) permutação de [].

Aqui está um exemplo de objetivo para 'perm': 

?- perm([1,2,3],P).
P = [1,2,3] ;
P = [2,1,3] ;
P = [2,3,1] ;
P = [1,3,2] ;
P = [3,1,2] ;
P = [3,2,1] ;
No

O usuário deve tentar o objetivo '?- perm(P,[1,2,3]).'


Exercício 2.7.4 Construa uma árvore de cláusulas de programa com todas as folhas verdadeiras para 'perm([a,b,c],[c,b,a])'.

É comum representar conjuntos como listas Prolog. Essa representação tem algumas falhas, como o fato de que as listas Prolog são ordenadas inerentemente (conjuntos não são), e uma lista pode ter várias ocorrências de um elemento particular (conjuntos não). No entanto, a representação da lista é muito conveniente. A associação ao conjunto pode ser calculada usando a relação de 'member' para listas discutidas anteriormente. Os subconjuntos podem ser testados usando 

subset([X|R],S) :- member(X,S), subset(R,S).
subset([],_).

Objetivos tais como... 

?- subset([4,3],[2,3,5,4]).
Yes

funcionam bem. Por que '?- subset([1,2],W)' e '?- subset(A,[1,2,3])' não seriam objetivos razoáveis? União e interseção podem ser aproximadas usando as seguintes versões da lista Prolog: 

union([X|Y],Z,W) :- member(X,Z),  union(Y,Z,W).
union([X|Y],Z,[X|W]) :- \+ member(X,Z), union(Y,Z,W).
union([],Z,Z).
 
intersection([X|Y],M,[X|Z]) :- member(X,M), intersection(Y,M,Z).
intersection([X|Y],M,Z) :- \+ member(X,M), intersection(Y,M,Z).
intersection([],M,[]).

Eles devem ser usados para objetivos em que as duas primeiras variáveis já têm um valor de lista. Às vezes, essa intenção é indicada escrevendo algo como 'union(+,+,-)' para indicar o perfil de variável pretendido. Por exemplo, 

?- union([1,2,3,4],[1,a,b,4],A).
A = [2,3,1,a,b,4]
 
?- intersection([1,2,3,4],[1,a,b,4],B).
B = [1,4]

Por que objetivos como '?- union(X,[2,3],[1,3,a,2])' causariam dificuldades? Alguma ineficiência de tempo de execução resulta de ter que combinar novamente os cabeçalhos de cláusulas para ambas as definições. Aqui está uma versão alternativa de união, usando! em vez de: 

union([X|Y],Z,W) :- 
  member(X,Z), 
  !,        /* do not  use next clauses */
  union(Y,Z,W). 
union([X|Y],Z,[X|W]) :- union(Y,Z,W).
union([],Z,Z).


Exercício 2.7.5 Projete e teste 'delete(X,L,R)', que se destina a excluir todas as ocorrências de X da lista L para produzir o resultado R.


Exercício 2.7.6 Projete e teste 'prune(A,B)', que se destina a remover várias ocorrências de elementos de A para produzir o resultado B. Por exemplo, 

?- prune([a,1,b,2,a,3,a,4,b],B).
B = [a,1,b,2,3,4]

Tente fazer com que B tenha elementos restantes na ordem em que ocorreram em A.

Exercício 2.7.7 Projete e teste o 'prefix(A,B)' que testa para ver se A é um prefixo de lista de B e que pode gerar prefixos de uma determinada lista. Por exemplo, 

?- prefix([1,2,3],[1,2,3,4,5]).
yes

?- prefix([1,2],[1,a,2,3]).
No 

?- prefix(W,[1,2,3]).
W = [] ;
W = [1] ;
W = [1,2] ;
W = [1,2,3] ;
No

Desenhe uma árvore de cláusulas do programa mostrando que 'prefix([1,2],[1,2,3])' é uma consequência do seu programa.


Exercício 2.7.8 Projete um de predicado Prolog chamado 'segment', que testa se seu primeiro argumento de lista é um segmento contíguo contido em qualquer lugar dentro do segundo argumento de lista. Por exemplo, 

?- segment([a,b,c],[1,c,a,b,c,3]).
Yes
 
?- segment([a,b],[c,a,c,b]).
No

Desenhe uma árvore de cláusulas mostrando que 'segment([a,b,c],[1,c,a,b,c,3])' é uma consequência de seu programa.

Várias estratégias de classificação podem ser implementadas usando listas no prólogo. Aqui está uma versão Prolog de 'merge sort,' com o perfil pretendido 'mergesort(+,-)'. 

mergesort([],[]).    /* covers special case */
mergesort([A],[A]).
mergesort([A,B|R],S) :-  
   split([A,B|R],L1,L2),
   mergesort(L1,S1),
   mergesort(L2,S2),
   merge(S1,S2,S).

split([],[],[]).
split([A],[A],[]).
split([A,B|R],[A|Ra],[B|Rb]) :-  split(R,Ra,Rb).

merge(A,[],A).
merge([],B,B).
merge([A|Ra],[B|Rb],[A|M]) :-  A =< B, merge(Ra,[B|Rb],M).
merge([A|Ra],[B|Rb],[B|M]) :-  A > B,  merge([A|Ra],Rb,M).

Segue um exemplo de objetivo: 

?- mergesort([4,3,6,5,9,1,7],S).
S=[1,3,4,5,6,7,9]

As rotinas de classificação da lista do Prolog sofrem todas as ineficiências de espaço e tempo relativas relacionadas com as estruturas dinâmicas de classificação, mas geralmente têm especificações muito convincentes no Prolog.


Exercício 2.7.9 Projete uma implementação Prolog de 'selection sort' para listas de números. Teste seu programa usando várias execuções de exemplos.


Exercício 2.7.10 Projete uma implementação Prolog de 'insertion sort' para listas de números. Teste seu programa usando várias execuções de exemplos.

Sequências

O tipo de sequência mais usado no Prolog são sequências de "vírgula". Não existe uma sequência vazia (ao contrário das listas). A sequência mais curta possui um elemento. As sequências mais longas têm elementos separados por vírgulas ",". Uma declaração apropriada para o operador vírgula seria

:- op(1000,xfy,',').

o que significa que a vírgula é associativa à direita com a precedência 1000. (Na verdade, o operador vírgula está nativo.) Aqui estão alguns comportamentos do Prolog. 

?- (H,T) = (1,2,3,4).
H = 1
T = 2,3,4 

?- (a) = a. 
Yes

?- (H,T) = (a).
No

?- (A,B,C) = (1,2,3,4,5).
A = 1
B = 2
C = 3,4,5

As cláusulas do Prolog usam sequências de vírgulas. 

?- assert((a(X) :- b(X),c(X),d(X))). %% Note parens around clause
X = G1056

?- clause(a(X),Body), Body=(First,Next).
First = b(G1176)
Next = c(G1176), d(G1176)
Body = b(G1176), c(G1176), d(G1176)
X = G1176

O processamento de sequências é semelhante ao processamento de listas, exceto que o caso base para sequências é uma sequência de unidade (um elemento), enquanto para listas o caso base é para a lista vazia. Por exemplo, aqui está um programa para anexar sequências de vírgulas ... 

sequence_append((X,R),S,(X,T)) :-
      !, 
      sequence_append(R,S,T).
sequence_append((X),S,(X,S)).

Observe o uso de 'cut' (!) para garantir que a segunda cláusula não esteja disponível como uma opção alternativa para sequências de vários elementos. 

?- sequence_append((1,2,3),(a,b,c,d),S).
S = 1, 2, 3, a, b, c, d


Exercício 2.7.11 Escreva um programa Prolog para reverter uma sequência de vírgulas.


Exercício 2.7.12 Escreva um programa Prolog para remover uma sequência de vírgulas (exclua os elementos de nível superior repetidos, mantendo primeiro, a ocorrência mais à esquerda).


Exercício 2.7.13 Escreva um programa Prolog para testar a associação em uma sequência de vírgulas (semelhante a membro para listas).

Outros tipos de sequências podem ser definidos pelo usuário. Por exemplo, para fazer sequências associativas à esquerda separadas por '#', pode-se usar uma declaração de operador como esta ... 

?- op(500,yfx,'#').
Yes

?- (A#B) = 1#2#3#4.
B = 4
A = 1 # 2 # 3

Observe como a associatividade à esquerda foi o que determinou as ligações na segunda meta!


Exercício 2.7.14 Escreva um programa Prolog para testar a associação em uma sequência com '#', conforme definido acima. Qual é o ponto principal deste exercício?


Veja Também

Disponível em “http://www.augustobaffa.pro.br/wiki/index.php?title=Listas_em_Prolog&oldid=272”