Las reglas que hemos visto hasta ahora estaban definidas en función de otras reglas ya existentes. La recursión es una técnica que debe ser tenida en cuanta cuando se quiere programar en Prolog. Se basa en definir relaciones en términos de ellas mismas, por ejemplo:
habla_de(A,B) :- conoce(A,B).
habla_de(A,C) :- conoce(A,B) , habla_de(B,C).
La idea que expresan es que se puede hablar de alguien si conocemos a ese alguien o si conocemos a alguien que nos habla de él.
Supongamos que agregamos los siguientes hechos:
conoce(juan,maria).
conoce(maria,jose).
conoce(maria,ana).
conoce(pedro,juan).
Y supongamos que queremos consultar lo siguiente:
?- habla_de(X,Y).
¿Cuáles serán las respuestas que obtendremos?
X=juan, Y=maria;
X=maria, Y=jose;
X=maria, Y=ana;
X=pedro, Y=juan;
Estas primeras respuestas resultan triviales y tienen que ver con el orden que siguen los hechos en nuestro programa lógico. Pero cuando a la última respuesta le agregamos “;”, gracias al backtracking intentará buscar más por alguna rama aún no explorada. Nótese que las respuestas dadas hasta ahora, se deducen de aplicar la primera regla y luego la regla 3; para la segunda respuesta, se aplicaron las reglas 1 y 4; para la tercera respuesta se aplicaron las reglas 1 y 5; y para la última respuesta se aplicaron las reglas 1 y 6. Hasta acá no se usó nunca la regla 2. Recién para dar la siguiente respuesta, aplica la regla 2 (dado que ya no tiene más combinaciones posibles de rgla1 con algún hecho) y combinándola con, por Ej., la regla 3, luego la regla 1 y luego la regla 4 obtenemos:
X=juan, Y=jose;
El resto de las respuestas serían:
X=juan, Y=ana;
X=pedro, Y=maria;
no
Pero aún podemos utilizar Prolog en su máxima potencia si trabajamos con estructuras infinitas o potencialmente infinitas, como podrían ser las listas. El poder de los programas lógicos está en su natural habilidad de manipular tipos de datos recursivos. Anteriormente vimos la definición de lista. Esta definición es recursiva, es decir, podemos decir que una lista es o la lista vacía o un par donde la segunda componente es una lista. Si hiciéramos el pasaje a cláusula de esta definición, tendriamos las siguientes reglas que nos definen una lista:
lista([]).
lista([X|Xs]):- lista(Xs).
Si tuviéramos la consulta ?- lista([1,2,3], el árbol de prueba sería:
Notar que recién en la última instancia, es decir cuando consulta con lista([]), unifica con la primera regla, en todas las consultas anteriores, siempre unifica con la segunda regla.
Podríamos utilizar el predicado write(X) si quisiéramos mostrar en pantalla los elementos de una lista, modificando nuestro predicado lista de manera muy sencilla:
lista([]).
lista([X|Xs]):- write(X), lista(Xs).
Incluso, podemos, luego de la primera escritura, y para mayor prolijidad, hacer write(‘ ‘) para dejar un espacio entre cada elemento que se imprime.
Member
Una regla elemental cuando se trabaja con listas, es determinar si un elemento pertenece o no a la lista. Para ello, debemos programar un predicado miembro que dado un elemento nos responda “yes” si pertenece a la lista y “no”en otro caso. El predicado sería:
member(X, [X|Xs]).
member(X,[Y|Ys]):- member(X,Ys).
Esto, declarativamente significa que un elemento sea miembro de una lista, o es el primer elemento de la lista o es miembro del resto de la lista. Lo interesante de este predicado es que podemos utilizarlo en muchos sentidos. Uno de ellos es con la siguiente consulta:
?- member(1, [1,2,3]).
yes
En este caso, se está consultando si 1 es miembro de la lista [1,2,3]. Si realizamos una traza paso a paso, veremos que, similarmente a lo que ocurrió con el predicado lista, obtendremos como respuesta yes. Otra forma de usar este predicado es con la consulta:
?- member(X,[1,2,3]).
Aquí estamos preguntando cuales son los elementos que conforman la lista. Prolog responderá, en orden:
X=1;
X=2;
X=3;
no
Veremos como sería la traza del programa para obtener estas respuestas:
En (1) se usa la primera regla con las sustituciones X=1, Y=[2,3]. Notar que sólo muestra la primera sustitución, dado quela variable Y no es incógnita de nuestra consulta. Lo importante aquí es que está utilizando la primera regla, y usando ella da su primera respuesta. Luego, con “;” estamos pidiendo la siguiente respuesta. Estamos obligando a Prolog a utilizar otro camino diferente, por lo tanto prueba con la segunda regla. Este es el caso (2). Aquí es como un volver a empezar. Ahora la consulta se realiza con member(X,[3]), y nuevamente por la primera regla obtenemos una respuesta, en este caso X=2. El proceso sigue hasta que finalmente en (3) debemos realizar la consulta member(X,[]). Este predicado si bien concuerda en su nombre tanto con la primera como con la segunda regla, no hay una sustitución que lo haga unificar con ninguna de ellas, por lo tanto, en esta instancia, Prolog responde “no”.
Otra consulta interesante para realizar con este predicado es member(1, X). En este caso, estamos pidiendo las listas que contienen al elemento dado (en nuestro caso al número 1). Las respuestas serían:
X=[1|Y];
X=[Y1,1|Y];
X=[Y1,Y2,1|Y];
X=[Y1,Y2,Y3,1|Y];
......
Es decir, nos está dando la lista que comienza con 1, la lista cuyo segundo elemento es un 1, la lista cuyo tercer elemento es un 1 y así indefinidamente seguiría agregando un elemento más a la lista.
Append
Otro predicado que tiene mucho uso en la programación con Prolog es append. ESte se utiliza en varias ocasiones:
-
Cuando precisamos concatenar dos listas en una tercera.
-
Cuando precisamos dividir una lista en partes.
La definición del predicado sería:
append([],X,X).
append([H|T1],X,[H|T2]) :- append(T1,X,T2).
donde la primera regla simplemente indica que dadas dos listas, la primera de ellas vacía, la concatenación de ambas resulta en la segunda lista.
La segunda regla, la regla recursiva, es un poco más complicada, pero declarativamente nos dice que si la lista X se concatena a la lista [H|T1], entonces la nueva lista tendrá también la cabeza H y la cola se formará con el resultado de concatenar X a la cola de la primera lista.
Ejemplos:
?- append([1,2,3],[4,5],[1,2,3,4,5]).
yes
En este caso, sólo estamos preguntando si la lista [1,2,3,4,5] es la concatenación de los dos priemros argumentos, a lo cual responde que sí.
?- append([1,2,3],[4,5],X).
X=[1,2,3,4,5];
no
Aquí estamos pidiendo que se concatenen los dos primeros argumentos, formando la lista resultado
?- append([1,2,3],X,[1,2,3,4,5]).
X=[4,5];
no
En esta oportunidad, se quiere saber con que lista habrá que concatenar la lista [1,2,3] para formar la lista [1,2,3,4,5]
?- append(X,Y,[1,2,3,4,5]).
X=[], Y=[1,2,3,4,5];
X=[1], Y=[2,3,4,5];
X=[1,2], Y=[3,4,5];
X=[1,2,3], Y=[4,5];
X=[1,2,3,4], Y=[5];
X=[1,2,3,4,5], Y=[];
no
Como podemos ver, en este caso estamos pidiendo que listas habría que concatenar para formar la lista [1,2,3,4,5], con lo cual obtenemos las respuestas dadas como todas las posibles combinaciones de concatenación
Sublistas
Un próximo ejemplo es el predicado sublist(X,L) que determina si X es una sublista de L. Una sublista requiere que los elementos estén consecutivos, es decir que, por ejemplo la lista [3,4] es sublista de la lista [1,2,3,4,5] pero no es sublista de [1,2,4,5,3]. Para definir este predicado, definiremos previamente los predicados prefijo y sufijo:
prefijo([],X).
prefijo([X|Xs],[X|Ys]):- prefijo(Xs,Ys).
sufijo(Xs,Xs).
sufijo(Xs,[Y|Ys]):-sufijo(Xs,Ys).
El primer predicado es verdadero si el primer argumento es sublista inicial del segundo argumento, es decir, [1,2] es prefijo de [1,2,3,4] y de [1,2] pero no de [5,4,3,1,2]
El segundo predicado es verdadero si el primer argumento es sublista final del segundo argumento, es decir, [3,4] es sufijo de [1,2,3,4] y de [3,4] pero no de [1,2,3,4,5]
Luego definiremos sublista de varias maneras:
Sufijo de prefijo:
sublista(Xs,Ys):- prefijo(Ps,Ys),sufijo(Xs,Ps).
Prefijo de sufijo:
sublista(Xs,Ys):- prefijo(Xs,Ss),sufijo(Ss,Ys).
Definición recursiva de sublista:
sublista(Xs,Ys):- prefijo(Xs,Ys).
sublista(Xs,[Y|Ys]):-sublista(Xs,Ys)
Sufijo de prefijo usando append:
sublista(Xs,AsXsBs):- append(As,XsBs,AsXsBs), append(Xs,Bs,XsBs).
Prefijo de sufijo usando append:
sublista(Xs,AsXsBs):- append(AsXs,Bs,AsXsBs), append(As,Xs,AsBs).
Otro programa recursivo. Veamos paso a paso como borrar un elemento dado de una lista. El predicado lo llamaremos borrar(L1,X,L2). La idea es recorrer L1, que es una lista, y cada vez que aparezca el elemento X, lo no lo tenemos en cuenta para armar la lista resultado, que quedará en L2.
Comencemos con el caso base, es decir con el caso que cierra el programa recursivo. Como vamos a recorrer L1, nuestro programa terminará cuando se acabe la lista L1, o sea cuando esté vacía, por lo cual nuestro caso base quedará así:
borrar([],X,[]).
Esto es que si quiero borrar X de la vacía, obtengo como resultado la lista vacía (o sea nada que hacer).
Ahora veamos que pasa si encontramos a X como elemento de la lista L1:
borrar([X|Xs], X, L2):- borrar(Xs,X,L2).
Lo que decimos es que si X es el primer elemento de la lista, entonces no lo tomo en cuenta para armar la lista resultado y llamo recursivamente a borrar con el resto de la lista para que continúe su trabajo. El tema ahora es que hacer si X no es un elemento de la lista, o también, que hacer cuando X no es un elemento de la lista. Para esos casos, precisamos una regla más:
borrar([L|Ls], X, [L|L2]):-X=\= L, borrar(Ls,X,L2).
X=\=L es verdadero si X es diferente de L. Esto quiere decir que L debe formar parte de la lista resultado, por eso en el tercer argumento se la agrega como cabeza de la lista L2. Finalmente, se llama recursivamente al predicado borrar para que continúe analizando el resto de la lista.