Prolog: listas
Informes
- Novas datas de prova e seminários. Veja a página de avaliações.
- Os alunos que submeteram a solução do problema das 3 casas devem explicar a sua solução.
- Revisão da última aula:
fatorial
Definição
- Sequência finita de elementos. Ex.:
[mia, vincent, jules, yolanda]
[mia, robber(honey_bunny), X, 2, mia]
[]
[mia, [vincent, jules], [butch, girlfriend(butch)]]
[[], dead(zed), [2, [b, chopper]], [], Z, [2, [b, chopper]]]
Cabeça e cauda
- Uma lista não-vazia pode ser pensada como tendo duas partes:
- cabeça (head): primeiro elemento da lista
- cauda (tail): lista que sobra quando retiramos a cabeça
Operador |
O operador |
pode ser usado para decompor uma lista em cabeça e cauda.
?- [Head|Tail] = [mia, vincent, jules, yolanda].
Head = mia
Tail = [vincent,jules,yolanda]
yes
Equivalente: [X|Y] = [mia, vincent, jules, yolanda].
Obter os dois primeiros elementos da lista
?- [X,Y | W] = [[], dead(zed), [2, [b, chopper]], [], Z].
Obter o segundo e o quarto elementos
?- [_,X,_,Y|_] = [[], dead(zed), [2, [b, chopper]], [], Z].
Exemplo mais avançado:
?- [_,_,[_|X]|_] =
[[], dead(zed), [2, [b, chopper]], [], Z, [2, [b, chopper]]].
Predicado membro
membro(X, L)
determina se o elemento X
faz parte da lista L
.
membro(X, [X|T]).
membro(X, [H|T]) :- membro(X, T).
Ou, melhor:
member(X, [X|_]).
member(X, [_|T]) :- member(X, T).
Considere a busca nas seguintes consultas:
membro(vincent,[yolanda,trudy,vincent,jules]).
membro(zed,[trudy,vincent,jules]).
Outro exemplo de consulta
membro(X,[yolanda,trudy,vincent,jules]).
Predicado a2b/2
- retorna “sim” somente se
- o 1o argumento é uma lista somente de
a
s - o 2o argumento é uma lista somente de
b
s - as listas têm o mesmo tamanho
- o 1o argumento é uma lista somente de
- Ex.:
a2b([a,a,a,a],[b,b,b,b]).
é verdadeiro - Ex.:
a2b([a,a,a,a],[b,b,b]).
é falso
a2b([], []).
a2b([a|A], [b,B]) :- a2b(A, B).
Exercícios
Exercício 31. Defina o predicado todos_as(L)
, que retorna verdadeiro somente se todos os elementos da lista L
são o átomo a
.
Exercício 32. Defina o predicado contem_1(L)
, que retorna verdadeiro somente se a lista L
contém o elemento 1
.
Exercício 33. Considere a seguinte base de conhecimento:
traducao(one,um)
traducao(two,dois)
traducao(three,tres)
traducao(four,quatro)
traducao(five,cinco)
traducao(six,seis)
traducao(seven,sete)
traducao(eight,oito)
traducao(nine,nove)
Crie uma regra, lista_traducao(E,P)
, que traduz uma lista de numerais em inglês na lista correspondente com os numerais em português. Por exemplo, lista_traducao([one,nine,two],X)
deve retornar X = [um,nove,dois]
.
Seu programa também deve funcionar no sentido inverso. Isto é, lista_traducao(X,[um,sete,seis,dois])
deve retornar X = [one,seven,six,two]
.
Dica: Para resolver esta questão, primeiro tente responder a seguinte pergunta: “Como faço para traduzir uma lista vazia de numerais?”. Este é o ponto de parada da recursividade. Para listas que não sejam vazias, primeiro, deve-se traduzir a cabeça da lista e, em seguida, traduzir a cauda utilizando recursividade.
Exercício 34. Crie uma regra duplica_elementos(E, S)
, em que o primeiro argumento (E
) é uma lista e o segundo (S
) é uma lista contendo todos os elementos de E
duplicados.
Ex. 1: duplica_elementos([a,4,relogio],X)
deve retornar X = [a,a,4,4,relogio,relogio]
.
Ex. 2: duplica_elementos([1,2,1,1],X)
deve retornar X = [1,1,2,2,1,1,1,1]
.
Dica: Para resolver esta questão, primeiro tente responder a seguinte pergunta: “O que deve acontecer quando o primeiro argumento é uma lista vazia?”. Este é o ponto de parada da recursividade. Para listas que não sejam vazias, pense no que deve acontecer com a cabeça e, utilizando recursividade, trate a cauda da lista.
Outros predicados interessantes
concatena(L1, L2, L3)
- L3 é a concatenção de L1 com L2inverte(L1, L2)
- L2 é o inverso de L1remover(X, L1, L2)
- L2 é igual a L1 removendo-se o elemento Xeh_sublista(L1, L2)
- L1 é sublista de L2permutar(L, P)
-intersecao(L1, L2, L3)
- L3 contém apenas os elementos que aparecem em L1 e L2palindrome([r,o,t,a,t,o,r])
- verdadeiro se a lista é igual a seu inverso