Estructuras Parciales

Algo ``común'' en Prolog es trabajar con estructuras parcialmente definidas.

Un ejemplo donde se ve esto, es en la definición de append

append([],L,L).
append([H|T],L,[H|R]) :-
     append(T,L,R).

El problema de esta definición es que es muy ineficiente, sobre todo si la primera lista es grande (ya que tiene que recorrerla toda antes de acabar). Si supieramos donde acaba la lista ésto se podría solucionar.

Lo podemos solucionar si representamos a una lista como un par: la lista en sí, y el resto. Es común ponerlo como diferencia de listas: L1 - L2 (pero puede usarse otra notación, e.g., L1/L2)

[1,2,3] = [1,2,3] - []
        = [1,2,3,4,5] - [4,5]
        = [1,2,3|T] - T

L1 = A1-Z1, L2 = A2-Z2, append(L1,L2,L3):

append(A1-Z1, Z1-Z2, A1-Z2).

?- append([1,2,3|T]-T,[4,5,6|R]-R,L3).
T = [4,5,6|R]
L3 = [1,2,3,4,5,6|R]-R

? - append([a,b,c,d|T1]-T1,[e,f,g|T2]-T2,Z-[]).
T1 = [e,f,g],
T2 = [],
Z = [a,b,c,d,e,f,g]

?- append([1,2,3|T]-T,[a,b,c]-[],R-[]).
T = [a,b,c],
R = [1,2,3,a,b,c]

Si queremos añadir un elemento al final de una lista:

anade(Elem,Lista-[Elem|T],Lista-T).

?- anade(a,[1,2,3|R]-R,X).
R = [a|T],
X = [1,2,3,a|T]-T

En general en todas las definiciones en donde usabamos append podemos cambiarlas para usar diferencia de listas (o estructuras incompletas). Por ejemplo para voltear una lista y para hacer quicksort.

voltea(L,LV) :- voltea2(L-[],LV-[]).

voltea2(A-Z,L-L) :- A == Z, !.
voltea2([H|T]-Z,RL-RZ) :-
     voltea2(T-Z,RL-[H|RZ]).

qsort(L,LO) :- qsort2(L,LO-[]).

qsort2([],Z-Z).
qsort2([H|T],A1-Z2) :-
     divide(H,T,Men,May),
     qsort2(Men,A1-[H|Z1]),
     qsort2(May,Z1-Z2).

Una aplicación común, es ir aumentando una estructira parcial al tener nueva información. Por ejemplo: vamos a suponer que tenemos un diccionario que tiene una secuencia de pares (Llave,Valor)

Dict = [(juan,1432), (pepe,75), (maria, 3214)|R]

?- busca(pepe,Dict,N).
N = 75

?- busca(juan,Dict,1432).
yes

?- busca(pancrasio,Dict,2816).
Dict = [(juan,1432), (pepe,75), (maria, 3214), (pancrasio,2816)|R]

busca(Llave,[(Llave,Valor)|Dict],Valor).
busca(Llave,[(Llave1,_)|Dict],Valor) :-
       Llave \= Llave1,
       busca(Llave,Dict,Valor).

Las estructuras de datos incompletas también pueden usarse en otras estructuras que no sean listas. En particular el ejemplo de arriba se puede mejorar si en lugar de listas utilizamos un árbol binario. La idea es tener del lado izquierdo del árbol elementos menores y del derecho elementos mayores que el nodo raíz.

Antes veamos como podemos representar un árbol binario:

arbol_binario(vacio).
arbol_binario(arbol(Nodo,Izq,Der)) :-
       arbol_binario(Izq),
       arbol_binario(Der).

elemento_arbol(N,arbol(N,_,_)).
elemento_arbol(N,arbol(_,Izq,_)) :-
       elemento_arbol(N,Izq).
elemento_arbol(N,arbol(_,_,Der)) :-
       elemento_arbol(N,Der).

Regresando al diccionario, el árbol lo podemos representar como sigue:
dict(Llave,Valor,Izq,Der). Asumimos que ahora las llaves son números y los valores pueden ser lo que sea. En caso de que las llaves no sean números se puede user @<, @>

busca(Llave,dict(Llave,X,Izq,Der),Valor) :-
       !, X = Valor.
busca(Llave,dict(Llave1,X,Izq,Der), Valor) :-
       Llave < Llave1,
       busca(Llave,Izq,Valor). 
busca(Llave,dict(Llave1,X,Izq,Der), Valor) :-
       Llave > Llave1,
       busca(Llave,Der,Valor). 

?- busca(2,L,b), busca(1,L,a), busca(3,L,c), busca(3,L,X).
L = dict(2,b,dict(1,a,_,_),dict(3,c,_,_)).
X = c

En el programa de arriba necesitamos el CUT por si Llave no está instanciada (ya que si llega a $< o >$ marcaría un error)