ndice:
1. Estructuras y rboles
Estructuras de Datos en PROLOG
2. Listas 3. Pertenencia a una lista 4. Prctica: Alterar frase alfabtica 5. Prctica: Ordenacin alfabtica 6. Predicado append
UNIVERSIDAD DE VALLADOLID
7. Prctica: inventario de piezas
Estructuras y rboles
Una estructura de datos en PROLOG se representa mediante un rbol
padres(hijo, madre, padre) padres(carlos, isabel, felipe) padres carlos isabel felipe verbo nombre frase(nombre, sintagma_verbal(verbo, nombre)) frase
Listas (I)
Lista es una secuencia ordenada de trminos (constantes, variables, estructuras, e, incluso, otras lista). La lista es utilizada: anlisis sintctico, gramticas, diagramas de flujo, grafos, etc. Manejo especfico de listas -> LISP. La lista es un caso particular de estructura en PROLOG => recursividad en la definicin.
nombre
Sintagma_verbal
a+b*c a
+ juan * b c frase(nombre(juan), sintagma_verbal(verbo(come), nombre(pan))) come pan
Listas (II)
Tipo particular de rbol: cabeza y cola
Funtor es . El final de la lista es []
Lista de un solo elemento: .(a, []) a . []
Pertenencia (I)
Saber si un objeto pertenece a lista.
[carlos_i, felipe_ii, felipe_iii, felipe_iv, carlos_ii]
Representacin habitual de las listas: [a,b,c] [los, hombres, [van, a, pescar]] Cabeza es el primer trmino. Cola es una lista que contiene al resto. Un forma de instanciar a una lista con cabeza X y cola Y sera: [X|Y]
Construir el predicado miembro:
miembro(X, [X|_]). miembro(X, [Y|_]):- X=Y. (slo comprueba coincidencia con la cabeza) aadir: miembro(X, [_|Y]) :- miembro(X,Y).
Lista: a, b, c a
. . b c
.(a, .(b, .(c,[])))
. []
Verifica la coincidencia con la cola y de forma recursiva va operando sobre otra lista progresivamente ms pequea:
?- miembro(felipe_ii, [carlos_i, felipe_ii, felipe_iii, felipe_iv, carlos_ii]). ?- miembro(X, [carlos_i, felipe_ii, felipe_iii, felipe_iv, carlos_ii]).
Pertenencia (II)
Evitar definiciones circulares:
padre(X, Y) :- hijo(Y, X). hijo(A, B) :- padre(B, A).
(se entra en un bucle infinito)
Prctica: alterar frase
Dilogo:
Usuario: tu eres un ordenador Prolog: yo no soy un ordenador Usuario: hablas francs Prolog: no_hablo alemn
Recursin por la izquierda:
persona(X) :- persona(Y), madre(X, Y). persona(adan). ?- persona(X).
(_ simula a ,)
Reglas:
Aceptar frase en formato lista: [tu, eres, un ordenador] Cambiar cada eres por un no soy. Cambiar cada hablas por un no_hablo. Cambiar cada francs por un alemn.
Intercambiar el orden de las lneas del programa
Solucin: alterar frase
cambiar(tu, yo). cambiar(eres, [no, soy]). cambiar(hablas, [no_, hablo]). cambiar(frances, aleman). cambiar(X,X). alterar([], []). alterar([H|T], [X|Y]):cambiar(H,X), alterar(T,Y). ?- alterar([tu, hablas, frances], X). X = [yo, [no_, hablo], aleman] ; X X X X X X X = = = = = = = [yo, [no_, hablo], frances] ; [yo, hablas, aleman] ; [yo, hablas, frances] ; [tu, [no_, hablo], aleman] ; [tu, [no_, hablo], frances] ; [tu, hablas, aleman] ; [tu, hablas, frances] ;
Prctica: ordenacin alfabtica (I)
Las palabras se considerarn una lista de nmeros (enteros) correspondiente a su secuencia ASCII. Obtener la lista asociada a cada palabra:
?- name(pala, X). X=[112, 97, 108, 97].
Comparacin:
amenor(X, Y) :- name(X, L), name(Y, M), amenorx(L, M). amenorx([], [_|_]). amenorx([X|_], [Y|_]) :- X<Y. amenorx([A|X], [B|Y]) :- A=B, amenorx(X, Y).
Prctica: ordenacin alfabtica (II)
Ejercicios:
qu sucede si se elimina la relacin amenor([], [_|_])? Modifquese el fichero PROLOG para admitir dentro de amenor el caso de dos palabras iguales.
Predicado append
Predicado predefinido:
?- append([a, b, c], [1, 2, 3], X). X=[a, b, c, 1, 2, 3] ?- append(X, [b, c, d], [a, b, c, d]). X=[a] ?- append([a], [1, 2, 3], [a, 1, 2, 3]). Yes ?- append([a], [1, 2, 3], [alfa, beta, gamma]). No
Definicin:
append([], L, L). append([X|L1], L2, [X|L3]) :- append(L1, L2, L3).
Prctica: inventario de piezas (I)
bicicleta
Prctica: inventario de piezas (II)
Definir el rbol mediante las relaciones:
pieza_basica(cadena). ensamblaje(bicicleta, [rueda_delantera, cuadro, rueda_trasera]).
rueda_delantera
cuadro
rueda_trasera
llanta radios
eje
manillar
silln
traccin
llanta radios
eje
piones
Construir relaciones piezas_de, que sirva para obtener la lista de piezas bsicas para construir una determinada parte de (o toda) la bicicleta.
eje
plato
pedales
cadena
