Livro texto

Prolog online

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), ...]

Exercicios

arvores

• acha um item em uma arvore de busca binaria (modo + + )

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

dicionarios

• dado um dicionário acesse o valor associado a uma chave, falha se a chave não esta no dicionário (Modo + + -)

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.

Predicado de alta ordem

Predicados que recebem outros predicados 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) 
                        -> Lout = [X| RR]
                        ;  Lout = RR
                        ), filter(T,R,RR).

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

contaelementos(L,DIC) :- foldl(soma1,L,[],DIC).

soma1(CH,DIC,NovoDIC) :- append(A,[d(CH,V)|B],DIC),!,
                         V1 is V+1,
                         append(A,[d(CH,V1)|B],NovoDic).
soma1(CH,DIC,[d(CH,1)|DIC]).

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)

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

Outros meta predicados

once transforma um predicado em deterministico

once(G) :- call(G),!.

ignore tenta rodar um predicado, mas dá certo de qq forma

ignore(G) :- call(G),!.
ignore(_).

once e ignore permite isolar partes do projeto sem que o backtrack de uma parte volte para outras partes

once(ledados(D)), processa(D,SAIDA), ignore(imprime(SAIDA)).

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(_,_)).

fatos como dicionários

:- dynamic c/2.
c(a,4).
c(b,5).
c(c,10).

get(CH,V) :- c(CH,V).
set(CH,V) :- ( c(CH,_) 
             -> retract(c(CH,_)), asserta(c(CH,V))
             ;  asserta(c(CH,V))
             ).
clear(CH) :- retractall(c(CH,_)).
clearall() :- retractall(c(_,_))
soma1(CH) :- ( c(CH,V) 
             -> retract(c(CH,V)), VV is V+1, asserta(c(CH,VV))
             ;  asserta(c(CH,1))
             ).