Aula 13

Exercicios

Da aula 1 e 2 - use acumuladores quando necessario.

tamanho de uma lista
soma dos elementos de uma lista soma(+LISTA,-SOMA)
soma dos números pares de uma lista somap(+LISTA,-SOMA)
soma dos elementos nas posições pares da lista ( o primeiro elemento esta na posicao 1) somapares(+LISTA,-SOMA)

somapares([],0).
somapares([_],0).
somapares([A,B|R],S) :- somapares(R,SS), S is SS+B.

existe item na lista elem(+IT,+LISTA)

elem(IT,[IT|_]).
elem(IT,[_|R]) :- elem(IT,R).

posição do item na lista: 1 se é o primeiro, falha se nao esta na lista pos(+IT,+LISTA,-POS)

pos(IT,L,P) :- pos(IT,L,P,1).
pos(IT,[X|_],P,N) :- X=IT,P=N.
pos(IT, [_|R],P,N) :- NN is N+1, pos(IT,R,P,NN)


pos(IT,L,P) :- pos(IT,L,P,1).
pos(IT,[IT|_],P,P).
pos(IT, [_|R],P,N) :- NN is N+1, pos(IT,R,P,NN)

conta quantas vezes o item aparece na lista (0 se nenhuma) conta(+IT,+LISTA,-CONTA)

conta(_,[],0).
conta(X,[X|R],N) :- conta(X,R,NN), N is NN+1.
conta(X,[_|R],N) :- conta(X,R,N).

reverte uma lista -

rev(L,B) :- rev(L,B,[]).
rev([],A,A).
rev([X|R],B,A) :- rev(R,B,[X|A]).

Voce pode usar o mesmo nome. O predicado é a combinação do nome e do numero de argumentos. No prolog o predicado é chamado de rev\2 e rev\3.

intercala 2 listas (intercala1 e intercala2)

intercala1([1,2,3], [4,5,6,7,8], X).
 X =  [1,4,2,5,3,6]

intercala1([],_,[]).
intercala1(_,[],[]).
intercala1([A|RA],[B|RB],[A,B|RR] ) :- intercala1(RA,RB,RR).

intercala2([1,2,3], [4,5,6,7,8], Y),
 Y =   [1,4,2,5,3,6,7,8]

a lista ja esta ordenada?

ordenada([]).
ordenada([_]).
ordenada([A,B|R]):- A =< B, ordenda([B|R]).

dado n gera a lista de n a 1

gera(1,[1]).
gera(N,L) :- NN is N-1, gera(NN,LL), L = [N|LL].

retorna o ultimo elemento de uma lista

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

retorna a lista sem o ultimo elemento

semult(L,LS) :- rev(L,[_|LL]),rev(LL,LS).

shift right

shiftr([],[]).
shiftr([X],[X]).
shiftr(L,LS) :- ultimo(L,U),
                semult(L,LL),
                LS = [U|LL].

shiftr n lista (shift right n vezes)
shift left
shift left n vezes
remove item da lista (1 vez so)

remove(_,[],[]).
remove(IT,[IT|R],R).
remove(IT,[X|R],SAIDA) :- remove(IT,R,RR),
                          SAIDA = [X|RR]

remove item da lista (todas as vezes)
remove item da lista n (as primeiras n vezes)
remove item da lista (a ultima vez que ele aparece) **
troca velho por novo na lista (1 so vez) troca(+LISTA,+VELHO,+NOVO,-ListaNova)

troca1([],_,_,[]).
troca1([V|R],V,N,[N|R]).
troca1([X|R],V,N,LN) :- troca1(R,V,N,LR),LN = [X|LR].

troca velho por novo na lista (todas vezes)
troca velho por novo na lista n (as primeiras n vezes)

Estruturas

tipo de dado com o mesmo formato que um predicado

pai(antonio,ana)

arv(NO,AE,AD)

Estruturas unificam entre si da mesma forma que predicados

nome (functor) igual,
mesmo numero de argumentos
cada argumento correspondente nas 2 estruturas unifica recursivamente

a(X, B, f(4)) = a(3, C, f(Z))
X = 3, B = C, Z = 4.

arvores

arv(NO, AE, AD) ou vazia

dicionários

[ dic(CHAVE, VALOR), ...]

Predicados de alta ordem

Predicados que recebem outros predicados/estruturas como argumentos

call

transforma uma estrutura em um query

?- P = pai(X,ana), call(P).

P = pai(antonio, ana),
X = antonio.

univ =..

constroi uma estrutura de uma lista (ou quebra uma estrutura em seus componentes)

?- X =.. [a,4,5].

X = a(4, 5)

?- Y = pai(a,b), Y =.. Z.

Z = [pai, a, b].

map

mapeia um predicado em 1 lista (map1) ou em duas listas (map2), etc

map1(_, []).
map1(P, [X|R]) :- G=..[P,X], call(G),
                 map1(P,R)

map2(_, [], []).
map2(P, [X|RX], [Y|RY]) :- G =.. [P,X,Y], call(G),
                         map2(P,RX,RY).

Na verdade é possível usar o mesmo nome map pois o predicado so unifica com um outro predicado de mesmo nome e mesmo numero de argumentos.

map(_, []).
map(P, [X|R]) :- G=..[P,X], call(G),
                map(P,R)

map(_, [], []).
map(P,[X|RX],[Y|RY]) :- G =.. [P,X,Y], call(G),
                         map(P,RX,RY).

se distingue as duas versões de map por map/2 e map/3

O map ja esta implementado em SWIProlog apply em listas como maplist

filter

%  filter(+Teste, +Lin, -Lout)
filter(_, [], []).
filter(T, [X|R], Lout) :- G =.. [P,X],
                        call(G), filter(T,R,RR), 
                        Lout = [X| RR].
                        
filter(T, [_|R], Lout):-filter(T, R, Lout).

ja implementado como include no SWIProlog

foldl

foldl(+P, +Lista, +Val_inicial, -Val_final)

P tem que ser um predicado de 3 argumentos

P( +Dado, +Acumulador, -NovoAcum)

foldl(_,[],ACC,FINAL).
foldl(P,[X|R],ACC,FINAL) :-
    G =.. [P,X,ACC,NACC],
    call(G),
    foldl(P,R,NACC,FINAL).

foldl ja esta implementado no SWIProlog.

Todas as soluções

pai(a,b).
pai(a,c).
pai(b,e).
pai(c,f).

ant(A,B) :- pai(A,B).
ant(A,B) :- pai(A,C),ant(C,B).

findall

findall( padrao, query, lista-com-os-resultados)

lista-com-os-resultados acumula todos os valores que padrao assume nas solucoes de query

todos filhos de a:

findall(X, pai(a,X), L).
L = [b, c].

todos os pais de e:

?- findall(X,pai(X,e),L).       
L = [].

todos filhos de alguém:

findall(X, pai(Z,X), L).
L = [b, c, e, f].

Veja que o Z aparece no query mas nao no padrão. Assim eles podem assumir qualquer valor nas varias soluçoes do query.

pares (lista de 2) de pais/filhos:

findall( [X,Y], pai(X,Y), L).

L = [[a, b], [a, c], [b, e], [c, f]].

Todos os pares (uma estrutura zz(filho, ai)) de pais e filhos que sao decendentes de a.

findall(zz(X,Y), (ant(a,X),pai(Y,X)), L).

Há 2 outros predicados parecidos mas com comportamento diferente em casos particulares bagof e setof

Alterando o banco de dados

assertz

assertz insere um fato no final do BD.

:- dynamic pai/2.

?- assertz(pai(f,h)).
?- listing(pai/2).

asserta insere no inicio do BD.

retract

remove o 1o fato que unifica como o argumento do retract

?- retract(pai(a,Z)).

retractall

remove todos os fatos que unificam com o argumento.

?- retractall(pai(_,_)).

Operadores IF-THEN-ELSE (1a versão)

Not

\+ (predicado)

A ; B

IF then else como OR

(teste, then) ; else

IF THEN ELSE (2a versão)

p :- teste, then.
p :- else.

IF THEN ELSE (3a versão)

Novo operador ->

A ser explicado logo abaixo

teste -> then ; else

Cut !

nota(N,L) :- N>9,L=a.
nota(N,L) :- N>7,L=b.
nota(N,L) :- N>5,L=c.
nota(_,d).

?- nota(8.5,X).

O predicado funciona na primeira chamada mas erra os resultados no backtracking/next.

O que precisamos é um jeito de dizer ao prolog que se ele decidiu por uma das regras, mesmo no backtrack ele nao pode escolher outra regra.

nota(N,L) :- N>9,!, L=a.
nota(N,L) :- N>7,!, L=b.
nota(N,L) :- N>5,!, L=c.
nota(_,d).

?- nota(8.5,X).

a :- b, c, !, d, e.
a :- f, g.

Se a execuçao passa pelo cut ela esta comprometida com essa regra. No backtraking o pedicado a vai falhar (e nao tentar provar na regra abaixo).

predicados deterministicos

nao geram outra solução no backtracking
falham no backtraking

..., A+1 > 2*B, proximo(A,B).

a :- b, c, !.
a :- d, e, f, !.
a: - g.

Cut no final torna o predicato deterministico.

fail e true.

fail é um predicado que sempre falha.

true é um predicado que sempre da certo.

Como indicar que um predicado deve falhar numa certa condição

elem(_,[]) :- !, fail.

O fail sozinho nao funciona pois ele vai forçar o bracktracking. o cut + fail funcional

IF THEN ELSE

a :- teste, !, then.
a :- else.

a :- teste -> then ; else

a :- antes, (teste 
            -> then 
            ;  else).

IF THEN

a :- antes, (teste 
            -> then
            ;  true).

Infelizmente precisa do true na posição do else.

multiplos IFs

a :- teste1, !, then1.
a :- teste2, !, then2.
a :- teste3, !, then3. 
a :- else.