Resolución del ej-02.pl

Comenzamos con el esqueleto:

	secuenciaFaltante(_, _).

	secuenciaFaltante(L1, L2).

Como en todo programa que involucra listas, nos preguntamos cómo sería 
esto en Lisp.  Debemos pensar en resolver las cosas trabajando solamente 
con el primer elemento (cabeza) de la lista y con el resto de la lista 
(cola).

Hay una cosa que debe ser siempre cierto en nuestro problema: la lista
L1 debe tener al menos dos elementos numéricos, de los cuales el primero
debe ser menor al segundo, o sino se debe fallar.  Veamos esto en parte:

	secuenciaFaltante([X,Y|Z], _).

Que X < Y es un control de sanidad que podemos hacer o no, según las
diferentes escuelas de pensamiento hacerlo es deseable ---programación
defensiva--- o nocivo ---según Bertrand Meyer.

Si X e Y son consecutivos, ambos estarán ausentes de la lista resultado, 
y se puede procesar la lista de entrada como si X no existiera.

Por otro lado, si X e Y no son consecutivos, hay que pasar a la lista de 
salida todos los enteros entre X e Y y continuar procesando la lista de 
entrada como si X no existiera. Estos dos párrafos se ven en Prolog 
como sigue:

	secuenciaFaltante([X,Y|Z], F) :-
		X < Y,			/* la lista está ordenada*/
		sucesor(X, Y),		/* son consecutivos */
		secuenciaFaltante([Y|Z], F).

	secuenciaFaltante([X,Y|Z], F1) :-
		X < Y,			/* la lista está ordenada*/
		sucesor(X, X1),		/* no son consecutivos */
		X1 =\= Y,
		secuencia_enteros(X,Y,Faltante),
		secuenciaFaltante([Y|Z], F2),
		append(Faltante, F2, F1).

Vamos a necesitar dos predicados auxiliares secuencia_enteros/3 y 
append/3 que se desarrollarán al final.  append/3 no necesita demasiadas 
explicaciones.

El caso de secuencia_enteros/3 lo que hace es tomar dos enteros como
argumento y genera una lista de enteros en el intervalo de los dos
datos, sin incluirlos.  Si observamos la segunda regla, vemos que se ha 
recurrido a hacer el append/3 entre la secuencia de enteros Faltante y 
el resultado recursivo F2 para lograr el resultado final.  Cabe 
preguntarnos que pasa si Faltante es vacía, por ejemplo si los números 
fuesen consecutivos: la solución calculada por la segunda regla sería la 
correcta en todos los casos.

Entonces podemos mejorar la definición de secuencia_enteros/3 para que 
incluya el caso en el cual sus dos enteros de entrada son consecutivos, 
para que devuelva la lista vacía.  De este modo podemos eliminar la 
primer regla de secuenciaFaltante/2 sin causar problemas a la solución.

Por supuesto que una solución recursiva no está terminada hasta que no 
se define el caso base.  Lo que tenemos como programa hasta ahora es:

        secuenciaFaltante([X,Y|Z], F1) :-
                X < Y,                  /* la lista está ordenada*/
                sucesor(X, X1),         /* no son consecutivos */
                X1 =\= Y,
                secuencia_enteros(X,Y,Faltante),
                secuenciaFaltante([Y|Z], F2),
                append(Faltante, F2, F1).


Se puede observar que la llamada recursiva a secuenciaFaltante/2 elimina 
de a uno los elementos de la primera lista argumento.  Eventualmente 
esta lista será vacía.  Pero esperar hasta que esté vacía no nos va a 
ayudar en nada, porque ya hemos aclarado que solamente hay sentido en 
las secuencias mientras hay al menos dos elementos en la primera lista 
argumento.  Usemos este conocimiento para el caso base:

	secuenciaFaltante([X,Y], Faltante) :-
                secuencia_enteros(X,Y,Faltante).

Cuáles son los casos en los cuales debe funcionar esto:

  - Cuando X e Y son consecutivos, debe devolver una lista vacía
  - Cuando X e Y no son consecutivos, debe devolver la lista de los 
    enteros en dicho intervalo, sin incluir X ni Y.

Pero eso es exactamente la definición que hemos acordado para 
secuencia_enteros/3, así que lo tenemos garantizado.

Para no necesitar un predicado nuevo para sucesor/2 lo podemos sustituir 
in-line por la suma más uno que sería su implantación.  Entonces 
secuenciaFaltante/2 nos queda:


secuenciaFaltante([X,Y], Faltante) :-
    secuencia_enteros(X,Y,Faltante).

secuenciaFaltante([X,Y|Z], F1) :-
    X < Y,                  /* la lista está ordenada*/
    X1 is X + 1,         /* no son consecutivos */
    X1 =\= Y,
    secuencia_enteros(X,Y,Faltante),
    secuenciaFaltante([Y|Z], F2),
    append(Faltante, F2, F1).
 


Resolvamos secuencia_enteros/3.  El esquema será:

   secuencia_enteros(+desde_entero, +hasta_entero, ?lista_enteros)


Pensamos recursivamente de nuevo, y entonces podemos imaginar que si
ambos enteros son consecutivos, entonces será el caso base, en el cual
la lista_enteros se hará concordar con la lista vacía:

	secuencia_enteros(X, Y, []) :- 
		Y is X + 1.

El otro caso es que no sean consecutivos, y por lo tanto habrá que 
agregar algún entero a la lista resultado.

	secuencia_enteros(X, Y, [Z|Zs]) :-
		Z is X + 1,	/* el sucesor de X */
		Z =\= Y,		/* que no es Y */
		secuencia_enteros(Z, Y, Zs).

Y la llamada recursiva toma al recién calculado Z como inicio del 
intervalo, hasta Y.  Cuando se dé el caso que el Z calculado sea el 
antecesor de Y, la llamada recursiva concordará con el caso base, y 
terminará la recursión.



EOF ej-02.txt