Aula 14

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(X,[X|_]).
elem(IT,[_|R]) :- elem(IT,R).

ou

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

Este ultimo codigo é um exemplo de algo qu eu chamo de append magico. O append é pensado no modo ++- (eu te dou 2 listas e voce me retorna a concatenação delas). Mas ele funciona nos outros modos tambem. Neste caso eu estou “usando”no modo –+ (voce me devolve 2 listas que concatenadas é a lista que eu passei). No exemplo, eu estou quebrando a lista L em 2 partes, e a segunda começa com IT. Se o append nao consegue quebrar L desta forma é porque o IT não esta em L.

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)

ou

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],[X|RR]) :- remove(IT,R,RR).

ou 

remove(IT,L,LL) :- append(X,[IT|Y],L),
                   append(X,Y,LL).

de novo o append magico. O append vai gerando listas de tamanho crescente no primeiro argumento. (Exemplo no prolog interativo).

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)

tarefa 7

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

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.