ESTRUCTURAS DE DATOS EN PROLOG

LISTAS.

La lista es una estructura de datos muy común en la programación no numérica. Es una secuencia ordenada de elementos que puede tener cualquier longitud. Ordenada significa que el orden de cada elemento es significativo. Un elemento puede ser cualquier término e incluso otra lista. Se representa como una serie de elementos separados por comas y encerrados entre corchetes.

Para procesar una lista, la dividimos en dos partes: la cabeza y la cola. Por ejemplo:

Lista Cabeza Cola

----- ------ ----

[a,b,c,d] a [b,c,d]

[a] a [] (lista vacía)

[] no tiene no tiene

[[a,b],c] [a,b] [c]

[a,[b,c]] a [[b,c]]

[a,b,[c,d]] a [b,[c,d]]

Para dividir una lista, utilizamos el símbolo "|". Una expresión con la forma [X | Y] instanciará X a la cabeza de una lista e Y a la cola. Por ejemplo:

p([1,2,3]).

p([el,gato,estaba,[en,la,alfombra]]).

?-p([X|Y]).

X = 1,

Y = [2,3]

More (Y/N):y

X = el,

Y = [gato,estaba,[en,la,alfombra]]

LA RECURSIVIDAD.

La recursividad es un mecanismo que da bastante potencia a cualquier lenguaje de programación. Veamos un ejemplo de programación recursiva que nos permitir determinar si un tomo es miembro de una lista dada:

(1) miembro(X,[X|_]).

(2) miembro(X,[_|Y]) :- miembro(X,Y).

La regla (1) es el caso base de la recursión. Se evaluará como cierta siempre que coincida la variable X con la cabeza de la lista que se pasa como argumento. En la regla (2) está la definición recursiva. X es miembro de una lista si lo es de la cola de esa lista (la cabeza se comprueba en la regla (1)).

La regla (1) es una simplificación de la regla:

miembro(X,[Y|_]) :- X = Y.

La traza para el caso de 'miembro(b,[a,b,c]).' es la siguiente:

(1) miembro(b,[a,b,c]) :- b = a. ---> no.

(2) miembro(b,[a,b,c]) :- miembro(b,[b,c]).

(1) miembro(b,[b,c]) :- b = b. ---> yes.

Si necesitamos conocer la longitud de una lista, emplearemos una función recursiva como la siguiente:

longitud([],0).

longitud([_|Y],L1) :- longitud(Y,L2), L1 is L2 + 1.

Otro ejemplo muy típico de función recursiva es el del factorial de un número:

factorial(0,1) :- !.

factorial(X,Y) :- X1 is X-1, factorial(X1,Y1), Y is X*Y1.

ENTRADA/SALIDA.

PROLOG, al igual que la mayoría de lenguajes de programación modernos incorpora predicados predefinidos para la entrada y salida de datos. Estos son tratados como reglas que siempre se satisfacen.

write.

Su sintaxis es:

write('Hello world.').

Las comillas simples encierran constantes, mientras que todo lo que se encuentra entre comillas dobles es tratado como una lista.

También podemos mostrar el valor de una variable, siempre que esté instanciada:

write(X).

nl.

El predicado nl fuerza un retorno de carro en la salida. Por ejemplo:

write('linea 1'), nl, write('linea 2').

tiene como resultado:

linea 1

linea 2

read.

Lee un valor del teclado. La lectura del comando read no finaliza hasta que se introduce un punto ".". Su sintaxis es:

read(X).

Instancia la variable X con el valor leido del teclado.

read(ejemplo).

Se evalúa como cierta siempre que lo tecleado coincida con la constante entre paréntesis (en este caso 'ejemplo').

Construcción y acceso a Estructuras de Datos

En este punto, vamos a concretar como se construyen árboles y listas, y describiremos, de forma general, el modo de acceso a este tipo de estructuras.

ÁRBOLES.

Un árbol es una estructura con una definición puramente recursiva, ya que se puede considerar como el elemento raíz cuyos hijos son, a su vez, árboles. Si el árbol tiene únicamente dos hijos se denomina árbol binario. Este modelo específico de árbol se utiliza mucho para resolver gran cantidad de problemas en aspectos de programación.

Un árbol se puede considerar, a su vez, un caso particular de grafo, donde todos los caminos son acíclicos.

La Figura 1 muestra un ejemplo de árbol.

Figura 1

Ejemplo de árbol

Muchos problemas de Inteligencia Artificial donde interviene el concepto de búsqueda se resuelven mediante la implementación de árboles. Los árboles de juego o los utilizados en la resolución de problemas relacionados con el procesamiento de lenguaje natural son casos muy concretos y descriptivos. Por lo tanto, podemos notar que el manejo eficiente de estas estructuras es sumamente importante para conseguir programas de calidad en este ámbito de la Ciencia.

Ya vimos que Prolog es un lenguaje que se adapta adecuadamente a este tipo de problemas. De hecho la técnica de resolución que utiliza Prolog se basa en la construcción de un árbol de búsqueda de soluciones, luego podemos concluir que el conocimiento de esta estructura es clave para este tipo de metodología declarativa.

Como en cualquier lenguaje, lo que necesitamos saber es la forma de declarar el árbol, ya que su implementación se puede realizar de muchas formas, por ejemplo, aunque una lista es un caso particular de árbol, un árbol se puede representar a través de listas, como veremos en el siguiente apartado.

Hemos dicho que un árbol está formado por la raíz y un conjunto de hijos, por tanto, para representar un árbol en Prolog podemos utilizar la siguiente notación:

oración (sujeto (artículo (el), sustantivo (hombre)), predicado (verbo (come), CD (pan)))

El árbol generado se muestra en la Figura 2.

Figura 2

Árbol de análisis de una frase en español

Como se observa, el uso de un predicado con dos argumentos en el caso de árbol binario o N argumentos en el caso de árbol N-ario es una forma sencilla de representar un árbol.

Una vez conocida la representación de árbol es necesario estudiar cómo se lleva a cabo la representación de listas en Prolog, ya que en esta clase de lenguajes este tipo de estructura es muy utilizada en la resolución de gran cantidad de problemas.

Una lista se puede considerar como un caso particular de árbol del modo que se muestra en la Figura 3. Observamos que la lista [1,2,3] se puede escribir como ‘·’(1,’·’(2,3)), sin embargo, la primera representación es mucho más cómoda.

Figura 3

Lista implementada en forma de árbol

A su vez, una lista se puede considerar de forma recursiva. Es decir, siempre está formada por un elemento seguido de otra lista (ver Figura 4). Cuando la lista tienen un sólo elemento podemos considerar que está formada por dicho elemento y la lista vacía. Esta definición es muy interesante, ya que su conocimiento nos permitirá llevar a cabo todos las operaciones que se pueden realizar sobre las listas con poco esfuerzo.

Figura 4

Definición recursiva de una lista

Hemos de recordar que en Prolog no existen estructuras para realizar bucles luego todo los algoritmos que representemos se definirán de forma recursiva. El hecho de que la implementación de la lista sea también recursiva facilita la construcción de operaciones sobre la misma.

El siguiente programa calcula el factorial de un número N. El ejemplo es: FACTO(1,1,N) se deben poner siempre los 2 primeros unos y calcula el factorial.

DOMAINS

NUM = INTEGER

PREDICATES

FACTO(NUM,NUM,NUM)

CLAUSES

FACTO(A,B,C):-X=B+1,Z=A*X,X<=C,

WRITE(Z),NL,FACTO(Z,X,C).

El siguiente programa calcula la potencia de un numero, para ello se deben ingresar los datos de la siguiente forma: exponente(A, B, C, D). A es el número base y B es el exponente, en C coloca un 1 y D toma el mismo valor de A. Quedaria asi: exponente(3,2,1,3) para obtener como resultado 9.

domains

var = real

predicates

exponente(var, var, var, var)

clauses

exponente(A, B, C, D):- Y = C+1, N = A * D, C < B, write("EXP = ", D, "*", A, "=", N), nl, exponente(A, B, Y, N)

domains

var = real

predicates

mult(var, var, var, var)

clauses

mult(A,B,C,D):- Z = C + 1, L=A + D, C < B, write("MULTIPLICACION = ",D," + ",A," = ", L), nl, mult(A,B,Z,L).

EJEMPLOS

** insertar en una lista:

/* formato: insert(elemento_a_insertar,lista_original,lista_resultado).

Nuestro único hecho (y no hay reglas): */

insert(X,L,[X|L]). /* la relación "insertar el elemento X a una lista

* L da como resultado una lista cuya cabeza es X y

* cuyo 'resto' es L" es verdadera */

Consultas:

?- insert(5,[1,2,3,4],X). /* Para qué lista se cumple que X = "5 insertado

* en la lista [1,2,3,4]? */

X = [5,1,2,3,4]

Yes

?- insert(4,X,[4,2,1]). /* En qué lista tendría que insertar 4 para resultar

* en la lista [4,2,1]? */

X = [2,1]

Yes

?- insert(4,X,[2,1]). /* En qué lista tendría que insertar 4 para resultar

* en la lista [2,1]? */

No /* no se puede */

?- insert(X,[4,5],[4,4,5]). /* Qué elemento tendría que insertar en la lista

* [4,5] para que resulte [4,4,5]? */

?- insert(X,[4,5],[4,5,4,5]). /* Qué elemento tendría que insertar en la lista

* [4,5] para que resulte [4,5,4,5]? */

No /* no se puede */

/*ARBOL BINARIO*/

arbol_binario(v).

arbol_binario(nodo(Raiz,Izq,Der)) :- arbol_binario(Izq),

arbol_binario(Der).