Aula 13

Prolog online

1 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.

1.1 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.

1.2 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.

1.3 IF THEN ELSE

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

a :- teste 
       -> then 
       ;  else.

1.4 IF THEN

a :- teste 
     -> then
     ;  true.

1.5 multiplos IFs

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

2 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.

Na proxima aula vamos passar estruturas p/ predicados "de alto nível" (similar a funcoes que recebem funções em Haskell).

2.1 arvores

arv(NO, AE, AD) ou vazia

2.2 dicionários

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

3 Exercicios

3.1 arvores

  • acha um item em uma arvore de busca binaria
  • verifica se uma arvore é um abb
elem(IT,arv(IT,_,_)).
elem(IT,arv(X,AE,AD)) :- IT < X 
                         -> elem(IT,AE)
                         ;  elem(IT,AD).
  • insere um item numa abb
  • remove um item de uma abb
  • calcula a profundidade maxima de uma abb
  • converte uma abb numa lista em ordem infixa (arvore-esquerda, no, arvore-direita)
  • converte uma abb numa lista em ordem prefixa (no, ae, ad)
  • converte uma lista em uma abb

3.2 dicionarios

  • dado um dicionário acesse o valor associado a uma chave, falha se a chave não esta no dicionário
acesse(CH,[dic(CH,V)|_],V).
acesse(CH,[_|DIC],V) :- acesse(CH,DIC,V).

ou usando a "append magico" 

acesse(CH,DIC,V) :- append(_,[dic(CH,V)|_],DIC).
  • insere um par chave valor no dicionário (ou troca o valor associado a chave se ela ja esta no dicionário)
  • remove uma chave (e seu valor) do dicionário.
  • contador: dicionario onde valor associado é um inteiro. Implemente o soma1 que dado um contador soma um ao valor associado a uma chave, ou se ela nao estiver no dicionario, acrescenta a chave com valor 1.