Prolog (2da parte)
►Generate
& Test.
►Árboles de derivación.
►Tratamiento de repeticiones.
Generar y Testear
La intuición es aprovechar el orden de
evaluación de Prolog, para definir la
siguiente estrategia para resolver
problemas:
1) Generar todas las posibles respuestas.
2) Filtrar las respuestas obtenidas en 1,
obteniendo la respuesta buscada.
Esquema general
► Un
predicado que utiliza generate & test
consta de dos partes:
predicado(x) :- generate(x), test(X)
► “generate”
instanciará la variable x.
► “test” verificará si x es o no una solución
válida, puede asumir que la variable está
instanciada.
Un generador
El predicado entre(+X,
los Z entre X e Y.
+Y, -Z)
devuelve todos
Pensarlo unos minutos…
entre(X,Y,X):- X=<Y.
entre(X,Y,Z):- X<Y, W is X+1, entre(W,Y,Z).
Ejercicio
Generar los pares menores a X.
Nuevamente unos minutos para pensarlo, con
la siguiente ayudita:
par(X):- 0 is X mod 2.
paresMenoresA(X, Y) :- entre(0,X,Y), par(Y).
► entre
es el encargado de ir generando
todos los números menores a X, luego par
actúa como filtro.
Arboles de Derivación
[Ver Recorrido.ppt]
Soluciones repetidas…
usaJogging(pablo).
usaJogging(alejo).
programaBien(pablo).
programaBien(diego).
programaBien(alejo).
esWinner(pablo).
esWinner(diego).
puedeSerGroso(X):- programaBien(X).
puedeSerGroso(X):- esWinner(X).
esGroso(X):- puedeSerGroso(X),usaJogging(X).
Consulta…
Consulta
? esGroso(X).
Pensar unos minutos qué respuestas daría y
en qué orden.
Respuestas:
X = pablo ;
X = alejo ;
X = pablo ;
No
► Hay
varias maneras de encarar el problema de
soluciones repetidas.
¿Cómo evitar repeticiones?
1) Usar cláusulas excluyentes
puedeSerGroso2(X):- programaBien (X).
puedeSerGroso2(X):- esWinner(X), not(programaBien(X)).
(¡OJO CON EL ORDEN! primero instanciamos los Winners y luego los
filtramos)
esGroso2(X):-puedeSerGroso2(X),usaJogging(X).
Probemos…
? esGroso2(X).
X = pablo ;
X = alejo ;
No
El metapredicado “not”
► not:
el not es un metapredicado (recibe un
predicado cómo parámetro).
► Falla si P tiene éxito.
► Tiene éxito si P falla.
► Pertenece al los aspectos extralógicos del
lenguaje.
Otra forma de evitar repeticiones
2) usando setOf y member
setof(X, p(X), L) devuelve en L todos los
valores de X que cumplen con el
predicado p.
member(X, L) dice si X es miembro de L.
esGroso3(X):-setof(Y, puedeSerGroso(Y), L),
member(X,L),
usaJogging(X).
Árboles
Sea un árbol binario representado por:
► nil
► nodo(X, SI, SD)
Dado
append( [ ], L, L).
append( [X|XS], L, [X|R]):-append(XS,L,R).
donde append(A,B,C) equivale a decir C = A++B
Se pide: Obtener una lista con todos los nodos
1
Ejemplo
2
3
?- listaNodos(nodo(1,
nodo(2,nil,nil),
nodo(3,nil,nil)),
L).
L = [1,2,3];
No.
Solución
Pensarla unos minutos (¡¡último ejercicio de la
clase!!)
listaNodos(nil,[]).
listaNodos(nodo(V,SI,SD),[V|Y]):listaNodos(SI, NI),
listaNodos(SD, ND),
append(NI,ND,Y).
Descargar

Document