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
PROCESAMIENTO DE LISTA
Lista es una estructura de datos directamente apoyada en PROLOG a través de operaciones para acceder la cabeza y la cola de la lista. Sin embargo, la lista es aún un término de PROLOG tradicional, si alguien usa la notación punto obvia. Describimos la manipulación con listas en la sección "Representando Estructuras de Datos" así miraremos sólo listas diferenciales aquí y continuaremos presentando áreas de uso de listas.
LISTAS DIFERENCIALES o en diferencias.
El problema principal de la implementación de PROLOG de listas es su naturaleza un-camino (one-way). Que significa que si uno quiere acceder al elemento n-th, el / ella tiene que acceder todos los elementos previos en la lista. En particular, si uno quiere agregar un elemento al final de la lista, es necesario ir a través de todos los elementos en la lista como el siguiente programa muestra (compárelo con la implementación de agregar):
adicionar2final(X,[H|T],[H|NewT]) :- agregar(X,T,NewT).
adicionar2final(X,[],[X]).
Pero hay una técnica, llamada listas diferenciales, que permite agregar listas o agregar elementos al final de la lista en un paso. Sin embargo debería ser notado que esta técnica no remueve la desventaja de visitar todos los elementos previos en la lista si el elemento n-th es accesado.
Una lista diferencial consiste de dos partes A-B y representa la lista que es obtenida desde A removiendo la cola B, ejemplo, [1,2,3,4]-[3,4] representa la lista [1,2]. Por supuesto, si ambas listas A y B son básicas, entonces no hay ventaja de usar listas diferenciales, pero si ésta técnica es combinada con las ventajas de variables libres y unificación, podemos obtener resultados impresionantes. A saber, la lista [1,2] puede ser representada por la lista diferencial [1,2|X]-X.
Si estandarizamos las listas diferenciales en la última forma, podemos escribir procedimientos en un sólo paso para agregar listas y adicionar elementos al final de la lista:
agregar(A-B,B-D,A-D).
adicionar2final(X,A-B,[A|NuevoB]-NuevoB) :- NuevoB=[X|B].
Notar, que la otra lista de operaciones, ejemplo, miembro, tienen que también ser reescritas para trabajar con listas diferenciales.