UNIVERSIDAD DE LOS ANDES
COORDINACION GENERAL DE ESTUDIOS INTERACTIVOS A DISTANCIA
MERIDA - VENEZUELA
Curso de Lógica y Matemática
Postgrado en Modelado y Simulación de Sistemas
MANUAL de PROLOG - BRATKO
CONJUNTOS EN PROLOG
Los Conjuntos son una poderosa estructura de datos que pueden ser naturalmente expresados usando listas en PROLOG. Para mejorar la eficiencia de la implementación usamos listas ordenadas como representación de conjuntos. Así, definimos la relación "menor que " y "está en la lista" de la siguiente manera:
lista([]).
lista([_|_]).
lt(X,Y) :- var(X);var(Y).
lt(X,Y) :- nonvar(X),nonvar(Y),X<Y.
UNIÓN, INTERSECCIÓN, DIFERENCIA Y SELECCIÓN
Ahora, agregamos definiciones para operaciones de conjuntos obvias como unión, intersección y diferencia. Notar, como explotamos el orden de los elementos del conjunto en los procedimientos siguientes.
union([],S,S).
union(S,[],S) :- S\=[].
union([X|TX],[X|TY],[X|TZ]) :-
union(TX,TY,TZ).
union([X|TX],[Y|TY],[X|TZ]) :-
lt(X,Y),
union(TX,[Y|TY],TZ).
union([X|TX],[Y|TY],[Y|TZ]) :-
lt(Y,X),
union([X|TX],TY,TZ).
interseccion([],S,[]).
interseccion(S,[],[]) :- S\=[].
interseccion([X|TX],[X|TY],[X|TZ]) :-
interseccion(TX,TY,TZ).
interseccion([X|TX],[Y|TY],TZ) :-
lt(X,Y),
interseccion(TX,[Y|TY],TZ).
interseccion([X|TX],[Y|TY],TZ) :-
lt(Y,X),
interseccion([X|TX],TY,TZ).
diferencia([],S,[]).
diferencia(S,[],S) :- S\=[].
diferencia([X|TX],[X|TY],TZ) :-
diferencia(TX,TY,TZ).
diferencia([X|TX],[Y|TY],[X|TZ]) :-
lt(X,Y),
diferencia(TX,[Y|TY],TZ).
diferencia([X|TX],[Y|TY],TZ) :-
lt(Y,X),
diferencia([X|TX],TY,TZ).
Podemos también definir una operación selección la cual selecciona los elementos satisfaciendo una condición dada desde un conjunto. Noten como usamos copiar_term y llamada para probar la condición. También, usamos la operación si-entonces-sino (Cond -> entonces_rama ; sino_rama) para acortar el procedimiento.
seleccionar([],X,Cond,[]).
seleccionar([H|T],X,Cond,Sel) :-
copiar_term(X-Cond,XC-CondC),
H=XC,
(llamada(CondC) -> Sel=[H|R] ; Sel=R),
seleccionar(T,X,Cond,R).
Si no comprendes completamente el significado y uso de la operación selección intenta ejemplos como el siguiente:
?-seleccionar([1,2,3,4],X, X>2,Resultado).
SUBCONJUNTO Y MEMBRESÍA
Es también posible definir relaciones naturales entre conjuntos como subconjunto y membresía. Otra vez notar el uso del orden del elemento que mejora la eficiencia de los procedimientos.
subconjunto([],V).
subconjunto([H|T1],[H|T2]) :- subconjunto(T1,T2).
subconjunto([H1|T1],[H2|T2]) :- lt(H2,H1),subconjunto([H1|T1],T2).
in(X,[X|T]).
in(X,[Y|T]) :- lt(Y,X),in(X,T).
OPERADORES PARA CONJUNTOS
Finalmente, definimos operadores los cuales nos ayudan a escribir operaciones de conjuntos y relaciones de una manera natural. Notar la prioridad diferente de los operadores.
:- op(400,yfx,/-\). % interseccion
:- op(500,yfx,\-/). % union
:- op(600,yfx,\). % diferencia
:- op(700,xfx,es_conjunto).
:- op(700,xfx,esta_in).
:- op(700,xfx,es_subconjunto).
La operación "es_conjunto" evalúa la expresión con conjuntos. Corresponde a la operación de PROLOG "is".
S es_conjunto S1 \-/ S2 :-
SS1 es_conjunto S1,
SS2 es_conjunto S2,
union(SS1,SS2,S).
S es_conjunto S1 /-\ S2 :-
SS1 es_conjunto S1,
SS2 es_conjunto S2,
interseccion(SS1,SS2,S).
S es_conjunto S1 \ S2 :-
SS1 es_conjunto S1,
SS2 es_conjunto S2,
diferencia(SS1,SS2,S).
S es_conjunto sel(X,Cond,Set) :-
SSet es_conjunto Set,
seleccionar(SSet,X,Cond,S).
S es_conjunto S :- Lista(S).
Podemos agregar las operaciones miembro y subconjunto.
X is_in S :- SS es_conjunto S, in(X,SS).
U is_subconjunto V :- US es_conjunto U, VS es_conjunto V, subconjunto(US,VS).
Ok, ahora podemos usar conjuntos en una forma obvia.
?- [1,2,3] /-\ [2,3,4] es_subconjunto [1,2,3] \-/ [2,3,4].
?- S es_conjunto ([1,2,3] \ [2,4,5] /-\ [2,6,7])\-/[2,3,6].
?- X is_in [1,2,3] \-/ [3,4,5].
...
REPRESENTACIÓN COMPACTA
La representación de arriba de conjuntos es satisfactoria para los conjuntos pequeños, pero no es eficiente para conjuntos grandes que contienen bloques compactos. Asi, ofrecemos la siguiente representacion compacta de conjuntos:
conjunto [1,2,3,4,5,7,8,9] es representado como [1...5,7...9]
Para usar esta representación definimos "el operador compacto ..." primero:
op(100,xfx,'...')
Por supuesto, tenemos que redefinir los procedimientos de arriba para unión, intersección, diferencia, seleccionar, subset, y in.
c_in(X,[X|T]) :- X\=A...B.
c_in(X,[A...B|T]) :- in_intervalo(X,A,B).
c_in(X,[Y|T]) :- Y\=A...B,lt(Y,X),c_in(X,T).
c_in(X,[A...B|T]) :- lt(B,X),c_in(X,T).
in_intervalo(X,X,B).
in_intervalo(X,A,B) :- nonvar(X),X=B.
in_intervalo(X,A,B) :- nonvar(X),lt(A,X),lt(X,B).
in_intervalo(X,A,B) :- var(X),lt(A,B),A1 is A+1,in_intervalo(X,A1,B).
Reescriba los otros procedimientos como tarea.
La representación compacta en conjunción con la poderosa operación seleccionar permite compactar la descripción de diversos conjuntos.
sel(X,par(X),[1...100]) % conjunto de números pares entre 1 y 100.
Los operadores pueden mejorar legibilidad de los programas PROLOG.