Prolog — Estructuras de datos incompletas

Listas abiertas y listas diferencia

Las estructuras de datos incompletas proporcionan una técnica de programación propia de Prolog que permite incrementar la eficiencia de los programas lógicos y simplificar su diseño. Estas estructuras se apoyan en el uso de variables lógicas para representar huecos, los cuales simbolizan partes de las estructuras que todavía no han sido computadas. La estructura incompleta más utilizada es la lista diferencia.

El problema de la concatenación de listas

Predicado append/3 en Prolog

La definición de la concatenación de listas usual no tiene ningún misterio: el predicado append/3 es cierto cuando la tercera lista es la concatenación de las dos primeras.

Mediante esta definición, para concatenar dos listas se deben recorrer todos los elementos de la primera hasta llegar al final, donde se inserta la segunda. Por lo tanto, este predicado tiene complejidad lineal respecto al tamaño de la primera lista.

La concatenación es la base para la implementación de muchas de las operaciones sobre listas: permutar, rotar, aplanar, etcétera; donde la eficiencia se ve afectada por esta operación.

Predicado permutation/2 en Prolog

Listas abiertas y listas diferencia

Ejemplo de listas abiertas

Una lista abierta es una lista que tiene como cola una variable libre, la cual es llamada hueco. Esta variable puede unificar con otra lista, resultando así en una concatenación de listas.

Una lista diferencia es un par formado por una lista abierta y su hueco. En Prolog, representaremos este par como L-H, donde L es una lista abierta que tiene como hueco a la variable H. Por ejemplo: [1, 2, 3|X]-X.

Nota. Aunque -/2 tiene connotaciones de resta, no hay porqué preocuparse, puesto que en este contexto es simplemente un operador infijo que no será interpretado.

Predicado append_diff/3 en Prolog

Utilizando esta representación, la concatenación de [1, 2, 3] y [4, 5, 6] será la concatenación de [1, 2, 3|X]-X y [4, 5, 6|Y]-Y, obteniendo una lista diferencia [1, 2, 3, 4, 5, 6|Y]-Y.

Predicado append_diff/3 en Prolog

Podemos reescribir el predicado append_diff/3 anterior de forma más sintética.

Ahora es posible concatenar cualquier par de listas diferencia en tiempo constante, aunque este predicado no permite obtener por reevaluación todos los pares de listas tal que al concatenarlos producen una determinada lista, tal y como se haría con append(-Xs, -Ys, +Zs).

Manipulando listas diferencia

Cuando trabajamos con listas diferencia, debemos manipular siempre la estructura adecuada L-H en todos los predicados involucrados.

La lista diferencia vacía se representa como X-X. Para transformar una lista diferencia en una lista estándar simplemente hay que unificar el hueco de la lista diferencia con la lista vacía [].

Ejemplo. El predicado flatten/2 es cierto cuando la segunda lista es la concatenación de todas las sublistas contenidas en la primera lista (análogamente el predicado flatten_diff/2 con listas diferencia).

Predicados flatten/2 y flatten_diff/2 en Prolog

La complejidad del predicado flatten_diff/2 es lineal respecto al número de sublistas diferencia que contiene la primera lista, independientemente de la longitud de dichas sublistas. Sin embargo, el predicado flatten/2 concatena las sublistas con append/3 desde la última sublista hasta la primera, teniendo que recorrer así una vez todos los elementos de todas las sublistas excepto de la última. Por lo tanto, flatten/2 tiene una complejidad lineal en el número de sublistas más el número de elementos de todas las sublistas excepto de la última.