Consideraciones sobre la resolución del ejercicio de subsec/2 Recordemos la solución final: subsec([X|_], [X]). /* un elemento de la lista es una */ /* subsecuencia creciente */ subsec([X|Xs], [X|Ys]) :- /* un elemento estará en la */ subsec(Xs,Ys), /* subsecuencia ssi es menor */ minimo(Ys,Ymin), /* a todos los que siguen */ X < Ymin. subsec([_|Xs], Y) :- /* si elimino el primer elemento, */ subsec(Xs,Y). /* puedo armar una subsecuencia */ /* creciente con el resto */ Vamos ahora a ver cómo se llegó a dicha solución. Primero se parte de la declaración del esqueleto del predicado, a los fines de poder definir las pruebas: subsec(_,_). Esta es la definición más simple ---y más equivocada--- de dicho predicado. Lo que dice es básicamente que cualquier cosa que se le pase como argumento, lo hará acertar. Los signos '_' son variables anónimas, todas diferentes, y a las cuales no les queremos poner nombre porque no las vamos a referenciar. Recordemos que la subsecuencia era monótona creciente. De alguna manera debemos tener en cuenta esta condición que se debe complir. Como cada vez que trabajamos en listas al estilo Lisp, lo hacemos con el horizonte del primer elemento y el resto, debemos pensar una forma de asegurarnos que una lista será creciente solamente pensando en esos términos. Uno puede pensar que una lista es estrictamente creciente si el primer elemento es estrictamente menor que el menor del resto de la lista, y que ese menor elemento está a la cabeza de dicho resto. Entonces, para una lista dada, su primer elemento X será parte de la subsecuencia resultado [X|Ys], si la propia subsecuencia tiene un mínimo Ymin, que a su vez satisface X < Ymin. En Prolog será: subsec([X|Xs], [X|Ys]) :- /* un elemento estará en la */ subsec(Xs,Ys), /* subsecuencia ssi es menor */ minimo(Ys,Ymin), /* a todos los que siguen */ X < Ymin. Con esta regla podemos "pasar" elementos X desde la lista hacia la subsecuencia resultado. Por el contrario, si un elemento X no satisface la desigualdad final, ese elemento no deberá estar en la subsecuencia resultado. Esto lo podríamos poner en Prolog como: subsec([X|Xs], Ys) :- subsec(Xs,Ys), minimo(Ys,Ymin), X >= Ymin. Nos faltaría ahora poner un caso base o embrionario a la recursión. Vemos que la lista primer argumento se va reduciendo átomo a átomo, hasta que eventualmente llega a ser la lista vacía. Entonces parece razonable usar el caso de la lista vacía como caso base. Lo podemos expresar como: subsec([],[]). Que dice que una lista vacía genera como subsecuencia ordenada a la lista vacía. Esto no es muy cierto desde el punto de vista lógico, pero lo podemos dejar pasar por alto por ahora. Si llega a ser problemático como solución espúrea, lo que haremos será corregirlo más adelante. El programa nos queda ahora como: (ej-01a.pl) subsec([],[]). subsec([X|Xs], [X|Ys]) :- /* un elemento estará en la */ subsec(Xs,Ys), /* subsecuencia ssi es menor */ minimo(Ys,Ymin), /* a todos los que siguen */ X < Ymin. subsec([X|Xs], Ys) :- subsec(Xs,Ys), minimo(Ys,Ymin), X >= Ymin. Corremos la prueba 1: | ?- prueba_1. prueba 1: subsec([2,4,8,3,100,93,50,55,89,3,1], [2,4,8,100]) -> esperado=acerto/real=fallo y vemos que falla. Activamos el trace: | ?- trace. The debugger will first creep -- showing everything (trace) (10 ms) yes {trace} | ?- y probamos de nuevo prueba_1: | ?- prueba_1. 1 1 Call: prueba_1 ? 2 2 Call: prueba_subsec_1(_76,_77) ? 2 2 Exit: prueba_subsec_1([2,4,8,100],acerto) ? 3 2 Call: prueba_cte([2,4,8,100],acerto) ? 4 3 Call: secuencia(_132) ? 4 3 Exit: secuencia([2,4,8,3,100,93,50,55,...]) ? 5 3 Call: write('prueba 1: subsec(') ? prueba 1: subsec( 5 3 Exit: write('prueba 1: subsec(') ? 6 3 Call: write([2,4,8,3,100,93,50,55,...]) ? [2,4,8,3,100,93,50,55,89,3,1] 6 3 Exit: write([2,4,8,3,100,93,50,55,...]) ? 7 3 Call: write(', ') ? , 7 3 Exit: write(', ') ? 8 3 Call: write([2,4,8,100]) ? [2,4,8,100] 8 3 Exit: write([2,4,8,100]) ? 9 3 Call: write(') -> esperado=') ? ) -> esperado= 9 3 Exit: write(') -> esperado=') ? 10 3 Call: write(acerto) ? acerto 10 3 Exit: write(acerto) ? 11 3 Call: write('/real=') ? /real= 11 3 Exit: write('/real=') ? 12 3 Call: subsec([2,4,8,3,100,93,50,55,...],[2,4,8,100]) ? Hasta acá sólo fuimos dando ENTER, para que siga paso a paso la ejecución. Ahora viene lo bueno porque comienza la llamada a subsec/2, que es lo que nos interesa: 12 3 Call: subsec([2,4,8,3,100,93,50,55,...],[2,4,8,100]) ? 13 4 Call: subsec([4,8,3,100,93,50,55,89,...],[4,8,100]) ? 14 5 Call: subsec([8,3,100,93,50,55,89,3,...],[8,100]) ? 15 6 Call: subsec([3,100,93,50,55,89,3,1],[100]) ? 16 7 Call: subsec([100,93,50,55,89,3,1],[100]) ? 17 8 Call: subsec([93,50,55,89,3,1],[]) ? 18 9 Call: subsec([50,55,89,3,1],[]) ? 19 10 Call: subsec([55,89,3,1],[]) ? 20 11 Call: subsec([89,3,1],[]) ? 21 12 Call: subsec([3,1],[]) ? 22 13 Call: subsec([1],[]) ? 23 14 Call: subsec([],[]) ? 23 14 Exit: subsec([],[]) ? 24 14 Call: minimo([],_636) ? 24 14 Fail: minimo([],_624) ? Vemos que en cada paso, se hacen concordar los elementos de una y otra lista, y se van eliminando. Esto sigue hasta que la segunda lista se vacía. De allí en más se vacía la primera lista, y cuando ambas están vacías, entonces hace match la primer regla de subsec/2, con lo cual acierta en 23. Sin embargo, la segunda y tercer regla, luego de conseguir una subsecuencia Ys, lo que hacen es buscar el mínimo de la misma. Y cuál es el mínimo de una lista vacía? Estamos en problemas. Una alternativa sería proponer un mínimo de mínimos, si lo hubiera, y adoptar eso dentro de mínimo/2; pero esta solución es claramente una cosa rara; las listas vacías no tienen mínimo, y por lo tanto minimo/2 debería fallar y no devolver cualquier cosa. Lo que se debe hacer es revisar nuestras suposiciones para las subsecuencias. La suposción actual es que subsec([],[]). es el caso base, y ésa es la que podría estar equivocada. Planteamos una alternativa: subsec([X],[X]). Lo que dice esto es que si a uno lo queda un único elemento en una lista, entonces ese único elemento es una subsecuencia ordenada. Esto no tiene problemas de interpretación ni de soluciones espúreas, así que por ahora lo tomamos. El programa nos queda ahora como: (ej-0b.pl) subsec([X],[X]). subsec([X|Xs], [X|Ys]) :- /* un elemento estará en la */ subsec(Xs,Ys), /* subsecuencia ssi es menor */ minimo(Ys,Ymin), /* a todos los que siguen */ X < Ymin. subsec([X|Xs], Ys) :- subsec(Xs,Ys), minimo(Ys,Ymin), X >= Ymin. Corremos la prueba 1: | ?- prueba_1. prueba 1: subsec([2,4,8,3,100,93,50,55,89,3,1], [2,4,8,100]) -> esperado=acerto/real=fallo yes | ?- Nuevamente obtenemos un resultado que no es el esperado, y analizamos la traza paso a paso: | ?- trace. The debugger will first creep -- showing everything (trace) yes {trace} | ?- prueba_1. 1 1 Call: prueba_1 ? 2 2 Call: prueba_subsec_1(_76,_77) ? 2 2 Exit: prueba_subsec_1([2,4,8,100],acerto) ? 3 2 Call: prueba_cte([2,4,8,100],acerto) ? 4 3 Call: secuencia(_132) ? 4 3 Exit: secuencia([2,4,8,3,100,93,50,55,...]) ? 5 3 Call: write('prueba 1: subsec(') ? prueba 1: subsec( 5 3 Exit: write('prueba 1: subsec(') ? 6 3 Call: write([2,4,8,3,100,93,50,55,...]) ? [2,4,8,3,100,93,50,55,89,3,1] 6 3 Exit: write([2,4,8,3,100,93,50,55,...]) ? 7 3 Call: write(', ') ? , 7 3 Exit: write(', ') ? 8 3 Call: write([2,4,8,100]) ? [2,4,8,100] 8 3 Exit: write([2,4,8,100]) ? 9 3 Call: write(') -> esperado=') ? ) -> esperado= 9 3 Exit: write(') -> esperado=') ? 10 3 Call: write(acerto) ? acerto 10 3 Exit: write(acerto) ? 11 3 Call: write('/real=') ? /real= 11 3 Exit: write('/real=') ? 12 3 Call: subsec([2,4,8,3,100,93,50,55,...],[2,4,8,100]) ? 13 4 Call: subsec([4,8,3,100,93,50,55,89,...],[4,8,100]) ? 14 5 Call: subsec([8,3,100,93,50,55,89,3,...],[8,100]) ? 15 6 Call: subsec([3,100,93,50,55,89,3,1],[100]) ? 16 7 Call: subsec([100,93,50,55,89,3,1],[100]) ? 17 8 Call: subsec([93,50,55,89,3,1],[]) ? 18 9 Call: subsec([50,55,89,3,1],[]) ? 19 10 Call: subsec([55,89,3,1],[]) ? 20 11 Call: subsec([89,3,1],[]) ? 21 12 Call: subsec([3,1],[]) ? 22 13 Call: subsec([1],[]) ? 23 14 Call: subsec([],[]) ? 23 14 Fail: subsec([],[]) ? Vemos que la situación ha sido parecida a la que ya habíamos pasado. Cuál es el problema con este enfoque? Lo que sucede es que el 100 se elimina y nos queda la segunda lista vacía. Como ya no existe caso base con listas vacías, es claro que la búsqueda fallará. Lo que debemos lograr es que al eliminar el último elemento de la segunda lista, se logre hacer match con la primera, aunque a esta le queden más símbolos restantes (en este caso 93,50,55,89,3,1). Debemos reformar nuestro caso base de nuevo: subsec([X|_], [X]). Ahora queda más claro: un elemento de la primer lista es una subsecuencia ordenada, no importa si le siguen otros elementos. El programa nos queda ahora como: (ej-0c.pl) subsec([X|_], [X]). subsec([X|Xs], [X|Ys]) :- /* un elemento estará en la */ subsec(Xs,Ys), /* subsecuencia ssi es menor */ minimo(Ys,Ymin), /* a todos los que siguen */ X < Ymin. subsec([X|Xs], Ys) :- subsec(Xs,Ys), minimo(Ys,Ymin), X >= Ymin. Corremos la prueba 1: | ?- prueba_1. prueba 1: subsec([2,4,8,3,100,93,50,55,89,3,1], [2,4,8,100]) -> esperado=acerto/real=fallo (10 ms) yes | ?- Revisamos paso a paso (abreviamos la parte introductoria) 12 3 Call: subsec([2,4,8,3,100,93,50,55,...],[2,4,8,100]) ? 13 4 Call: subsec([4,8,3,100,93,50,55,89,...],[4,8,100]) ? 14 5 Call: subsec([8,3,100,93,50,55,89,3,...],[8,100]) ? 15 6 Call: subsec([3,100,93,50,55,89,3,1],[100]) ? 16 7 Call: subsec([100,93,50,55,89,3,1],[100]) ? 16 7 Exit: subsec([100,93,50,55,89,3,1],[100]) ? 17 7 Call: minimo([100],_468) ? 17 7 Exit: minimo([100],100) ? 18 7 Call: 3>=100 ? 18 7 Fail: 3>=100 ? 16 7 Redo: subsec([100,93,50,55,89,3,1],[100]) ? 17 8 Call: subsec([93,50,55,89,3,1],[]) ? 18 9 Call: subsec([50,55,89,3,1],[]) ? 19 10 Call: subsec([55,89,3,1],[]) ? 20 11 Call: subsec([89,3,1],[]) ? 21 12 Call: subsec([3,1],[]) ? 22 13 Call: subsec([1],[]) ? 23 14 Call: subsec([],[]) ? 23 14 Fail: subsec([],[]) ? 22 13 Fail: subsec([1],[]) ? 21 12 Fail: subsec([3,1],[]) ? 20 11 Fail: subsec([89,3,1],[]) ? 19 10 Fail: subsec([55,89,3,1],[]) ? 18 9 Fail: subsec([50,55,89,3,1],[]) ? 17 8 Fail: subsec([93,50,55,89,3,1],[]) ? 17 8 Call: subsec([93,50,55,89,3,1],[100]) ? 18 9 Call: subsec([50,55,89,3,1],[100]) ? 19 10 Call: subsec([55,89,3,1],[100]) ? 20 11 Call: subsec([89,3,1],[100]) ? 21 12 Call: subsec([3,1],[100]) ? 22 13 Call: subsec([1],[100]) ? 23 14 Call: subsec([],[100]) ? 23 14 Fail: subsec([],[100]) ? 22 13 Fail: subsec([1],[100]) ? 21 12 Fail: subsec([3,1],[100]) ? 20 11 Fail: subsec([89,3,1],[100]) ? 19 10 Fail: subsec([55,89,3,1],[100]) ? 18 9 Fail: subsec([50,55,89,3,1],[100]) ? 17 8 Fail: subsec([93,50,55,89,3,1],[100]) ? 16 7 Fail: subsec([100,93,50,55,89,3,1],[100]) ? 15 6 Fail: subsec([3,100,93,50,55,89,3,1],[100]) ? 15 6 Call: subsec([3,100,93,50,55,89,3,1],[8,100]) ? 16 7 Call: subsec([100,93,50,55,89,3,1],[8,100]) ? 17 8 Call: subsec([93,50,55,89,3,1],[8,100]) ? 18 9 Call: subsec([50,55,89,3,1],[8,100]) ? 19 10 Call: subsec([55,89,3,1],[8,100]) ? 20 11 Call: subsec([89,3,1],[8,100]) ? 21 12 Call: subsec([3,1],[8,100]) ? 22 13 Call: subsec([1],[8,100]) ? 23 14 Call: subsec([],[8,100]) ? 23 14 Fail: subsec([],[8,100]) ? 22 13 Fail: subsec([1],[8,100]) ? 21 12 Fail: subsec([3,1],[8,100]) ? 20 11 Fail: subsec([89,3,1],[8,100]) ? 19 10 Fail: subsec([55,89,3,1],[8,100]) ? 18 9 Fail: subsec([50,55,89,3,1],[8,100]) ? 17 8 Fail: subsec([93,50,55,89,3,1],[8,100]) ? 16 7 Fail: subsec([100,93,50,55,89,3,1],[8,100]) ? 15 6 Fail: subsec([3,100,93,50,55,89,3,1],[8,100]) ? 14 5 Fail: subsec([8,3,100,93,50,55,89,3,...],[8,100]) ? 14 5 Call: subsec([8,3,100,93,50,55,89,3,...],[4,8,100]) ? 15 6 Call: subsec([3,100,93,50,55,89,3,1],[4,8,100]) ? 16 7 Call: subsec([100,93,50,55,89,3,1],[4,8,100]) ? 17 8 Call: subsec([93,50,55,89,3,1],[4,8,100]) ? 18 9 Call: subsec([50,55,89,3,1],[4,8,100]) ? 19 10 Call: subsec([55,89,3,1],[4,8,100]) ? 20 11 Call: subsec([89,3,1],[4,8,100]) ? 21 12 Call: subsec([3,1],[4,8,100]) ? 22 13 Call: subsec([1],[4,8,100]) ? 23 14 Call: subsec([],[4,8,100]) ? 23 14 Fail: subsec([],[4,8,100]) ? 22 13 Fail: subsec([1],[4,8,100]) ? 21 12 Fail: subsec([3,1],[4,8,100]) ? 20 11 Fail: subsec([89,3,1],[4,8,100]) ? 19 10 Fail: subsec([55,89,3,1],[4,8,100]) ? 18 9 Fail: subsec([50,55,89,3,1],[4,8,100]) ? 17 8 Fail: subsec([93,50,55,89,3,1],[4,8,100]) ? 16 7 Fail: subsec([100,93,50,55,89,3,1],[4,8,100]) ? 15 6 Fail: subsec([3,100,93,50,55,89,3,1],[4,8,100]) ? 14 5 Fail: subsec([8,3,100,93,50,55,89,3,...],[4,8,100]) ? 13 4 Fail: subsec([4,8,3,100,93,50,55,89,...],[4,8,100]) ? 13 4 Call: subsec([4,8,3,100,93,50,55,89,...],[2,4,8,100]) ? 14 5 Call: subsec([8,3,100,93,50,55,89,3,...],[2,4,8,100]) ? 15 6 Call: subsec([3,100,93,50,55,89,3,1],[2,4,8,100]) ? 16 7 Call: subsec([100,93,50,55,89,3,1],[2,4,8,100]) ? 17 8 Call: subsec([93,50,55,89,3,1],[2,4,8,100]) ? 18 9 Call: subsec([50,55,89,3,1],[2,4,8,100]) ? 19 10 Call: subsec([55,89,3,1],[2,4,8,100]) ? 20 11 Call: subsec([89,3,1],[2,4,8,100]) ? 21 12 Call: subsec([3,1],[2,4,8,100]) ? 22 13 Call: subsec([1],[2,4,8,100]) ? 23 14 Call: subsec([],[2,4,8,100]) ? 23 14 Fail: subsec([],[2,4,8,100]) ? 22 13 Fail: subsec([1],[2,4,8,100]) ? 21 12 Fail: subsec([3,1],[2,4,8,100]) ? 20 11 Fail: subsec([89,3,1],[2,4,8,100]) ? 19 10 Fail: subsec([55,89,3,1],[2,4,8,100]) ? 18 9 Fail: subsec([50,55,89,3,1],[2,4,8,100]) ? 17 8 Fail: subsec([93,50,55,89,3,1],[2,4,8,100]) ? 16 7 Fail: subsec([100,93,50,55,89,3,1],[2,4,8,100]) ? 15 6 Fail: subsec([3,100,93,50,55,89,3,1],[2,4,8,100]) ? 14 5 Fail: subsec([8,3,100,93,50,55,89,3,...],[2,4,8,100]) ? 13 4 Fail: subsec([4,8,3,100,93,50,55,89,...],[2,4,8,100]) ? 12 3 Fail: subsec([2,4,8,3,100,93,50,55,...],[2,4,8,100]) ? Bueno, se acaba de reproducir todo el paso a paso hasta el fracaso del predicado subsec/2. Es un espectáculo dantesco, no? Trataremos ahora de vadear por este mar de idas, vueltas, y retrocesos, de manera de entender qué es lo que está pasando. Antes que nada, hay que hacer una observación muy importante, que es válida para la depuración en cualquier lenguaje de programación y paradigma: "el programa debe hacer lo que el programador quiere que haga". Un corolario no menos importante es entonces: "el programador debe saber qué es lo que quiere hacer". En lugar de tratar de entender todo el vuelco de traza anterior, lo que haremos es fijar "cómo" queremos que trabaje, y ver "dónde" falla nuestra manera de hacer las cosas en la traza. En los primeros renglones aparece el problema: 12 3 Call: subsec([2,4,8,3,100,93,50,55,...],[2,4,8,100]) ? 13 4 Call: subsec([4,8,3,100,93,50,55,89,...],[4,8,100]) ? 14 5 Call: subsec([8,3,100,93,50,55,89,3,...],[8,100]) ? 15 6 Call: subsec([3,100,93,50,55,89,3,1],[100]) ? 16 7 Call: subsec([100,93,50,55,89,3,1],[100]) ? 16 7 Exit: subsec([100,93,50,55,89,3,1],[100]) ? 17 7 Call: minimo([100],_468) ? 17 7 Exit: minimo([100],100) ? 18 7 Call: 3>=100 ? 18 7 Fail: 3>=100 ? 16 7 Redo: subsec([100,93,50,55,89,3,1],[100]) ? El fallo en 18/7 es la causa del Redo en 16/7. Qué se estaba ejecutando cuando se llegó al 18/7? Es la llamada siguiente: 15 6 Call: subsec([3,100,93,50,55,89,3,1],[100]) ? Note que el 3 es el primer elemento de la lista, y [100,93,50,55,89,3,1] es el resto de la lista. Dicho resto hace match con [100] gracias a la primer regla de subsec/2. Vemos entonces que la comprobación 3>=100 se está dando en la tercera regla, que reproduciremos nuevamente a continuación: subsec([X|Xs], Ys) :- subsec(Xs,Ys), minimo(Ys,Ymin), X >= Ymin. Esta regla dice que si el X que es el primer elemento de la lista no está ordenado crecientemente, entonces no debe formar parte de la subsecuencia resultado. Analicemos un poco más esto. En realidad, para cualquier X de la lista original, X puede o no estar en la secuencia resultado. Por ejemplo pensemos en una subsecuencia ordenada que comience con el segundo elemento de la primer lista. Entonces esta regla no es correcta. Reformulemos esta regla de acuerdo a nuestra mejor comprensión actual: subsec([_|Xs], Y) :- /* si elimino el primer elemento, */ subsec(Xs,Y). /* puedo armar una subsecuencia */ /* creciente con el resto */ El programa nos queda ahora como: (ej-0d.pl) subsec([X|_], [X]). subsec([X|Xs], [X|Ys]) :- /* un elemento estará en la */ subsec(Xs,Ys), /* subsecuencia ssi es menor */ minimo(Ys,Ymin), /* a todos los que siguen */ X < Ymin. subsec([_|Xs], Y) :- /* si elimino el primer elemento, */ subsec(Xs,Y). /* puedo armar una subsecuencia */ /* creciente con el resto */ Se deja al lector comprobar que las pruebas ahora pasan satisfactoriamente. EOF ej-01.txt