<div class="notebook">
<div class="nb-cell html" name="htm1">
<h3>PROGRAMACIÓN LÓGICA</h3>
<h4>3º GRADO EN INGENIERÍA INFORMÁTICA, URJC</h4>
<h4><strong> PRÁCTICA DE PROLOG Nº3: Listas y predicado de corte </strong></h4>
<h4> Soluciones propuestas, comentadas </h4>
© 2022 Ana Pradera Gómez.
Algunos derechos reservados.
Este documento se distribuye bajo la licencia
<a href="https://creativecommons.org/licenses/by-sa/4.0/deed.es">Atribución-CompartirIgual 4.0 Internacional de Creative Commons</a>.
</div>
<div class="nb-cell html" name="htm8">
<strong>Prerrequisitos</strong><br>
Para la realización de esta tercera práctica de Programación Lógica
es necesario haber leído y estudiado el tema PL2 completo, especialmente los dos últimos apartados,
dedicados al manejo de listas y al predicado de corte.
</div>
<div class="nb-cell html" name="htm2">
<h4><strong>1. Manejo básico de listas en Prolog </strong></h4>
Recuerde que en Prolog:
<ul>
<li> La lista vacía se representa mediante <code>[]</code>. </li>
<li> Toda lista no vacía se puede escribir de la forma
<code>[a1,...,an]</code> y es unificable con un patrón del tipo
<code>[C | R]</code> siempre y cuando <code>C</code> unifique con
la cabeza de la lista, <code>a1</code>, y R unifique con el resto
de la lista, <code>[a2,...,an]</code>.</li>
<li> Toda lista que tenga al menos dos elementos es unificable con un
patrón del tipo <code>[C1, C2 | R]</code> siempre y cuando
<code>C1</code> unifique con
la cabeza de la lista, <code>C2</code> unifique con su
segundo elemento y R unifique con el resto
de la lista.</li>
<li> De forma similar, <code>[C1, C2, C3 | R]</code> podría
unificar con listas de al menos tres elementos, etc.
</li></ul>
Note en particular que a la derecha de la barra vertical
<code>|</code> solo puede haber una lista o algo unificable
con una lista, por ejemplo la lista <code>[1,2]</code> se
puede escribir como <code>[1,2 | []]</code>, como
<code>[1 | [2]]</code> o como <code>[1 | [2|[]]]</code>, pero <em>no</em> como
<code>[1 | 2]</code>. Esto último <em>no</em> es una lista.
Tampoco una variable es una lista, por lo que una forma de implementar
el predicado <code>es_lista(+X)</code>, cierto si X es una
lista, sería la siguiente (SWI Prolog ofrece este predicado bajo el
nombre de <code>is_list(+X)</code>):
</div>
<div class="nb-cell program" data-background="true" name="p15">
% es_lista(+X)
% cierto si X es una lista
% X no puede ser una variable y tiene que unificar
% con la lista vacía [] o con el patrón [C|R] siendo
% R a su vez una lista:
es_lista(X) :- nonvar(X), X = [].
es_lista(X) :- nonvar(X), X = [_|R], es_lista(R).
% Cuando sepa cómo manejar el predicado de corte, !, observe que
% una implementación equivalente a la anterior sería la siguiente:
% si X es una variable, se impide el uso de las
% siguientes cláusulas (mediante el predicado de corte) y se
% devuelve falso (mediante el predicado fail, que siempre es falso):
es_list(X) :-
var(X),
!,
fail.
% si X no es una variable, tiene que unificar
% con la lista vacía [] o con el patrón [C|R] siendo
% R a su vez una lista:
es_list([]).
es_list([_|R]) :-
es_list(R).
</div>
<div class="nb-cell html" name="htm25">
Pruebe el predicado anterior con algunas consultas como las
siguientes, pensando en cómo sería el árbol de Resolución
correspondiente, y, en consecuencia, cuál(es) será(n) la(s) respuesta(s) obtenidas.
</div>
<div class="nb-cell query" name="q54">
es_lista(X).
</div>
<div class="nb-cell query" name="q55">
es_lista(a).
</div>
<div class="nb-cell html" name="htm4">
<em>Las dos consultas anteriores devuelven false: en efecto, ni las variables ni las constantes son listas.
En los árboles de Resolución con <code>es_lista</code> serían aplicables las dos cláusulas, pero ambas dan lugar a nodos fallo (en el caso
de <code>es_lista(X)</code> fallan en <code>nonvar</code> y en el caso de <code>es_lista(a)</code> fallan las unificaciones). En los árboles de Resolución con <code>es_list</code>, para la primera consulta
serían aplicables las tres cláusulas del programa, pero el corte de la primera poda las otras dos ramas. La segunda consulta solo unifica con la primera cláusula del programa
(los argumentos de las otras dos son listas, no unificables con la constante "a") y falla nada más empezar con <code>var(a)</code>. </em>
</div>
<div class="nb-cell query" name="q56">
es_lista([a,b]).
</div>
<div class="nb-cell query" name="q57">
es_lista([a|b]).
</div>
<div class="nb-cell query" name="q58">
es_lista([a|R]).
</div>
<div class="nb-cell html" name="htm6">
<em> Las dos consultas anteriores devuelven false: en efecto, lo que está a la derecha de "|" tiene que ser una lista,
y ni la constante "b" ni la variable "R" lo son.</em>
</div>
<div class="nb-cell query" name="q59">
R = [b], es_lista([a|R]).
</div>
<div class="nb-cell html" name="htm7">
<em> En este caso la respuesta es afirmativa, porque al unificar previamente la variable <code>R</code> con la lista
<code>[b]</code>, la expresión <code>[a|R]</code> se convierte en <code>[a|[b]]</code>, que sí es una lista
(la lista <code>[a,b]</code>).</em>
</div>
<div class="nb-cell query" name="q25">
R = b, es_lista([a|R]).
</div>
<div class="nb-cell html" name="htm9">
<em> La respuesta ahora es sin embargo falsa, puesto que lo que se construye es <code>[a|b]</code>, que no es una lista puesto que <code>b</code> no lo es.</em>
</div>
<div class="nb-cell html" name="htm23">
Para cada una de las siguientes consultas, piense cuál(es) sería(n) la(s) respuesta(s)
ofrecidas por Prolog y a continuación compruebe sus
respuestas ejecutándolas.
</div>
<div class="nb-cell html" name="htm13">
<em> Para comprender las unificaciones que se plantean a continuación es fundamental recordar que el patrón
<code>[C1, C2, .. | R]</code> solo unfica con listas no vacías tales que <code>C1</code> unifica con el primer elemento de la lista,
<code>C2</code> unifica con el segundo elemento de la lista, etc, y por último <code>R</code> unifica con el resto de la lista
(que siempre será, a su vez, una lista).</em>
</div>
<div class="nb-cell query" name="q1">
[] = _.
</div>
<div class="nb-cell html" name="htm12">
<em> La variable anónima, <code>_</code>, unifica con cualquier cosa, luego también, en particular, con la lista vacía.</em>
</div>
<div class="nb-cell query" name="q8">
[] = [_].
</div>
<div class="nb-cell html" name="htm10">
<em>La lista vacía, <code>[]</code>, NO unifica con <code>[_]</code>, ya que este último patrón solo unifica con listas conteniendo exactamente un elemento (que puede ser cualquiera).</em>
</div>
<div class="nb-cell query" name="q9">
[a] = [A | []].
</div>
<div class="nb-cell html" name="htm16">
<em>Cierto con <code>A=a</code> puesto que la variable <code>A</code> unifica claramente con <code>a</code>, y la lista vacía unifica
directamente con el resto
de la lista <code>[a]</code>.</em>
</div>
<div class="nb-cell query" name="q46">
[a,b] = [a | b].
</div>
<div class="nb-cell html" name="htm14">
<em> Falso puesto que el <code>b</code> de <code>[a | b]</code> NO unifica con el resto de la lista <code>[a,b]</code>,
que es <code>[b]</code>.</em>
</div>
<div class="nb-cell query" name="q47">
[a,b] = [A | [b | []]].
</div>
<div class="nb-cell html" name="htm18">
<em> Cierto con <code>A=a</code>, puesto que <code>[b | []]</code> unifica con el resto de la lista <code>[a,b]</code>,
que es <code>[b]</code>.</em>
</div>
<div class="nb-cell query" name="q48">
[X,1] = [1,1,A | R].
</div>
<div class="nb-cell html" name="htm17">
<em> Falso puesto que la lista de la izquierda tiene solo 2 elementos y la de la derecha tiene al menos 3.</em>
</div>
<div class="nb-cell query" name="q38">
[X,1,Y] = [1,_,b | Z].
</div>
<div class="nb-cell html" name="htm36">
<em>La lista de la izquierda tiene exactamente 3 elementos, que unifican sin problema con los tres primeros elementos de la lista de la derecha,
y Z tiene que ser la lista vacía, puesto que ese es el resto de la lista de la izquierda sin contar sus 3 primeros elementos.</em>
</div>
<div class="nb-cell query" name="q5">
[X,1,X] = [1,_,b | Z].
</div>
<div class="nb-cell html" name="htm37">
<em>La respuesta ahora es <code>false</code>: ¡X no puede unificar a la vez con 1 y con b!</em>
</div>
<div class="nb-cell query" name="q39">
[a,b,[c,d]] = [_, X | Y].
</div>
<div class="nb-cell html" name="htm19">
<em> Ojo, observe que la unificación que produce la consulta anterior
es <code>Y = [[c,d]]</code> y NO <code>Y = [c,d]</code>: lo que hay a la derecha de
<code>|</code> debe unificar con EL RESTO de la lista de la <code>[a,b,[c,d]]</code> una vez eliminados sus dos primeros
elementos, y ese resto es LA LISTA que contiene al único elemento que queda (<code>[c,d]</code>), es decir, <code>[[c,d]]</code>. </em>
</div>
<div class="nb-cell query" name="q40">
[a|R] = [a,b,[c],lista].
</div>
<div class="nb-cell html" name="htm39">
<em>Lo anterior es cierto siempre y cuando se unifique la variable R con el resto de la lista
de la derecha, que es la lista compuesta por todos sus elementos salvo el primero.</em>
</div>
<div class="nb-cell query" name="q41">
[a, [b]] = [A | [b]].
</div>
<div class="nb-cell html" name="htm20">
<em> Falso puesto que lo que hay a la derecha de <code>|</code>, <code>[b]</code>, NO unifica con el resto de la lista de la
izquierda, que es <code>[[b]]</code>.</em>
</div>
<div class="nb-cell query" name="q2">
[a,[b,c]] = [A|[[B,c]]].
</div>
<div class="nb-cell html" name="htm22">
<em> Cierto con <code>A=a</code> y <code>B=b</code>, puesto que:
<ul>
<li> lo que hay a la izquierda de <code>|</code>, la variable <code>A</code>, unifica con el primer
elemento de la lista <code>[a,[b,c]]</code> con <code>A=a</code>
</li><li> lo que hay a la derecha de <code>|</code>, <code>[[B,c]]</code>, unificia con el resto de la lista
<code>[a,[b,c]]</code>, que es <code>[[b,c]]</code>, con <code>B=b</code>
</li></ul></em>
</div>
<div class="nb-cell query" name="q4">
[a,b,c] = [a, B | [C]].
</div>
<div class="nb-cell html" name="htm40">
<em>Lo anterior es cierto siempre y cuando se unifique la variable B con la constante b y
el término [C] unifique con el resto de la lista
de la izquierda, que es la lista [c], y esto último se consigue sustituyendo C por c. </em>
</div>
<div class="nb-cell query" name="q3">
[[a], [b,c], [D]] = [[A] | R].
</div>
<div class="nb-cell html" name="htm42">
<em> Cierto con <code>A=a</code> y <code>R = [[b, c], [D]]</code>, puesto que:
<ul>
<li> lo que hay a la izquierda de <code>|</code>, la lista <code>[A]</code>, unifica con el primer
elemento de la lista de la izquierda, <code>[a]</code>, con <code>A=a</code>
</li><li> lo que hay a la derecha de <code>|</code>, <code>R</code>, unificia con el resto de la lista de la izquierda,
que es la lista <code>[[b, c], [D]]</code>, con <code>R = [[b, c], [D]]</code>
</li></ul></em>
</div>
<div class="nb-cell html" name="htm11">
En la siguiente consulta <code>p</code> no es más que el nombre de un término compuesto cuyo único objeto es unificar sus argumentos.
</div>
<div class="nb-cell query" name="q42">
p([C],3,[C|NL]) = p(R,N,[1,2]), [X|Y] = [N,C|R], Z is 2*X.
</div>
<div class="nb-cell html" name="htm21">
<em> Note en particular que la consulta hace la unificación <code> R = [1] </code> y NO <code> R = [C] </code>, debido a que la
sustitución inicial <code> R = [C] </code> DEBE COMPONERSE con la sustitución posterior <code> C = 1 </code>. Ojo también con <code> N </code> y <code> X </code>, AMBAS unificadas con <code> 3 </code> (aunque SWI-Prolog escriba
<code>N = X, X = 3</code>).</em>
</div>
<div class="nb-cell html" name="htm3">
<h4><strong> 2. Uso de predicados básicos sobre listas y del predicado de corte</strong></h4>
Antes de ejecutar las siguientes consultas piense qué
ocurrirá al ejecutarlas (se
producirá un error, la respuesta será false, la respuesta
será true, se producirá una computación infinita, la o las
respuestas serán ....). Tenga en cuenta en particular que las implementaciones de
<code>member</code> y <code>append</code> son las estudiadas en clase para los predicados
<code>pertenece</code> y <code>concatena</code>:
<ul>
<li> <code>member(E,L) (pertenece)</code>, usado con <code>E</code> de salida y <code>L</code> de entrada, al hacer <emph>backtracking</emph>,
va unificando <code>E</code> con los distintos elementos de la lista <code>L</code> (empezando por su cabeza).
</li><li> <code>append(L1,L2,L) (concatena) </code>, usado con <code>L1</code> y <code>L2</code> de salida y
<code>L</code> de entrada, al hacer <emph>backtracking</emph>, va unificando <code>L1</code> y <code>L2</code> con
las posibles listas que resultan de descomponer en dos trozos la lista <code>L</code> (empezando con <code>L1=[], L2=L</code>).
</li></ul>
En los apuntes puede repasar las implementaciones de estos predicados, así como algunos ejemplos de árboles de Resolución
que los involucran.
Recuerde también que el predicado de corte, <code>!</code>, impide la reevaluación por backtracking de los
sub-objetivos que le preceden: por ejemplo, en la evaluación de algo del estilo <code>Obj1, Obj2, !, Obj3</code>, el corte,
si se llega a él, impide las posibles reevaluaciones tanto de <code>Obj1</code> como de <code>Obj2</code>, pero NO impide
las posibles reevaluaciones de <code>Obj3 </code>.
</div>
<div class="nb-cell query" name="q28">
member(A,[[a,b],[c,d]]), member(B,A).
</div>
<div class="nb-cell html" name="htm43">
<em>Recuerde que Prolog evalúa de izquierda a derecha y en profundidad:
<ul>
<li> La primera solución del sub-objetivo de la izquierda es <code> A = [a,b]</code>, por lo que una vez resuelto le queda por resolver
<code>member(B, [a,b])</code>. Este último tiene dos soluciones: la primera es <code> B = a</code>, dando lugar a la solución global
<code>A = [a,b], B = a</code> y la segunda es <code> B = b</code>, dando lugar a <code>A = [a,b], B = b</code>.
</li>
<li> La segunda solución del sub-objetivo de la izquierda es <code> A = [c,d]</code>, teniendo entonces que resolver <code>member(B, [c,d])</code>,
lo cual, de forma análoga al caso anterior, da lugar a las otras dos soluciones: <code> A = [c,d], B = c</code> y <code> A = [c,d], B = d</code>.
</li></ul></em>
</div>
<div class="nb-cell query" name="q29">
member(A,[[a,b],[c,d]]), !, member(B,A).
</div>
<div class="nb-cell html" name="htm24">
<em> Observe cómo en esta última consulta:
<ul>
<li> el corte impide la reevaluación del sub-objetivo que tiene a la izquierda, por lo que desparecen las soluciones
asociadas con <code> A = [c,d]</code> que sí aparecían en la consulta previa.
</li><li> el corte NO impide la reevaluación del sub-objetivo que está a su derecha, por lo que <code>member(B,[a,b])</code> produce las dos posibles soluciones.
</li></ul></em>
</div>
<div class="nb-cell query" name="q30">
member(A,[[a,b],[c,d]]), member(B,A), !.
</div>
<div class="nb-cell html" name="htm27">
<em> Observe cómo ahora el corte impide la reevaluación de los dos sub-objetivos de la consulta,
puesto que ambos están situados antes del corte, encontrando en consecuencia solo la primera solución para cada uno de ellos.</em>
</div>
<div class="nb-cell query" name="q16">
append(X, Y, [a,b]), length(X, N), N =< 1.
</div>
<div class="nb-cell html" name="htm26">
<em> En la consulta anterior, el predicado <code>append</code> intenta, al reevaluarse, todas las posibles formas de descomponer
la lista <code>[a,b]</code> en dos trozos, <code>X e Y</code>, pero las condiciones posteriores eliminan la solución
<code> X=[a,b], Y=[]</code> puesto que en este caso la longitud de <code>X, N=2,</code> no es menor o igual que 1.</em>
</div>
<div class="nb-cell query" name="q17">
append([X|_], Y, [a,b]), length(Y, N), N > 0.
</div>
<div class="nb-cell html" name="htm28">
<em>En este caso solo hay una solución para la descomposición de <code>[a,b]</code>,
que es <code>[X|_]=[a] (es decir, X=a), Y=[b]</code>, ya que, por un lado, el patrón <code>[X|_]</code> solo unifica con
listas NO vacías, y por otro lado se exige que la lista <code>Y</code> no sea vacía puesto que tiene que tener longitud no nula.</em>
</div>
<div class="nb-cell query" name="q18">
append([X,_|_], Y, [a,b]), length(Y, N), N > 0.
</div>
<div class="nb-cell html" name="htm29">
<em> No hay solución puesto que el patrón <code>[X,_|_]</code> solo unifica con listas con al
menos DOS elementos y la lista <code>Y</code>, por las condiciones posteriores, no puede ser vacía, por lo que en total ambas
sumarían al menos TRES elementos, cuando
<code>[a,b]</code> solo tiene dos. </em>
</div>
<div class="nb-cell query" name="q19">
append(A, [_], [a,b,c]), reverse(A,B).
</div>
<div class="nb-cell html" name="htm30">
<em>Recuerde que <code>[_]</code> solo unifica con listas conteniendo exactamente UN elemento, por lo que solo puede ser <code>[_]=[c]</code>, y por lo tanto
<code>A=[a,b]</code> y <code>B=[b,a]</code>, la inversa de A.</em>
</div>
<div class="nb-cell query" name="q20">
append(A, [5], [1,2,3,4,5]), member(X,A), 1 =:= X mod 2.
</div>
<div class="nb-cell html" name="htm41">
<em>El predicado <code>append</code> solo da una solución, <code>A=[1,2,3,4]</code>. El predicado
<code>member</code> recorre, mediante backtracking, todos los elementos de A, pero la condición
siguiente solo es cierta para aquellos que son impares.</em>
</div>
<div class="nb-cell query" name="q21">
append(A, [c], [a,b,c]), member(X,A), !.
</div>
<div class="nb-cell html" name="htm32">
<em>El predicado <code>append</code> solo da una solución, <code>A=[a,b]</code>, pero a
diferencia de la consulta anterior, en esta el corte impide la reevaluación del predicado
<code>member</code> al hacer backtracking, por lo que X solo toma un valor, el primero de la lista A.</em>
</div>
<div class="nb-cell query" name="q26">
append(A, B, [a,b,c]), member(X,A).
</div>
<div class="nb-cell html" name="htm33">
<em>En esta última consulta, note que la opción <code>A=[], B=[a,b,c]</code> no aparece debido al
fallo que produce la llamada posterior a <code>member(X,[])</code>.</em>
</div>
<div class="nb-cell query" name="q27">
append([a],B,L), member(b,B).
</div>
<div class="nb-cell html" name="htm15">
<em>El <code>append</code> inicial lo único que indica es que <code>L</code> es una lista que empieza por <code>a</code> y que <code>B</code> es una lista
cualquiera. Esto último hace que el <code>member</code> siguiente vaya dando todas las posibles listas que contienen a <code>b</code> (la que
lo tiene en primera posición, la que lo tiene en segunda posición, etc).</em>
</div>
<div class="nb-cell query" name="q10">
append([C|R], S, [4, 2, 3, 1]), sumlist([C|R], N), N =< 6.
</div>
<div class="nb-cell html" name="htm44">
<em>El predicado <code>append</code> descompone la lista <code>[4, 2, 3, 1]</code> en dos trozos, pero como el primero de ellos, <code>[C|R]</code>, no puede ser
vacío, da lugar a las soluciones <code>[C|R]=[4] (C=4,R=[]), S=[2,3,1]</code>, <code>[C|R]=[4,2] (C=4,R=[2]), S=[3,1]</code>, <code>[C|R]=[4,2,3] (C=4,R=[2,3]),
S=[1]</code> y <code>[C|R]=[4,2,3,1] (C=4,R=[2,3,1]), S=[]</code>.
Sin embargo, las dos condiciones siguientes obligan a que la suma de los elementos de la lista <code>[C|R]</code> sea menor o igual que 6, lo cual hace que solo se mantegan las
dos primeras descomposiciones.</em>
</div>
<div class="nb-cell query" name="q11">
append([C|R], S, [4, 2, 3, a]), sumlist([C|R], N), N =< 6.
</div>
<div class="nb-cell html" name="htm31">
<em>El error aritmético en tiempo de ejecución lo produce el predicado <code>sumlist</code> al
llegar a la última descomposición posible, <code>[C|R] = [4,2,3,a], S=[]</code> (la
descomposición anterior falla en el último predicado al ser <code>N = 9</code>).</em>
</div>
<div class="nb-cell query" name="q12">
append([C|R], S, [4, 2, 3, a]), !, sumlist([C|R], N), N =< 6.
</div>
<div class="nb-cell html" name="htm34">
<em> Observe el efecto del corte, que poda cualquier reevaluación del predicado <code>append</code>.</em>
</div>
<div class="nb-cell query" name="q13">
append([C|R], S, [4, 2, 3, 1]), sumlist([C|R], N), N >= 20.
</div>
<div class="nb-cell html" name="htm35">
<em>Ninguno de los posibles valores para <code>[C|R]</code> cumple que sus elementos
sumen al menos 20.</em>
</div>
<div class="nb-cell query" name="q14">
p(E, [_,E|R]) = p(3, [2|[F,4]]), append(A, B, [F|R]),
length(A, LA), LA =< 1.
</div>
<div class="nb-cell html" name="htm38">
<em> Prolog evalúa los objetivos anteriores de izquierda a derecha:
<ul>
<li> En primer lugar resuelve las unificaciones <code>E=3</code> y <code>[_,3|R]=[2,F,4]</code> (puesto que E se reemplaza por 3), mediante <code>E=3, F=3, R = [4].</code>
</li><li> El siguiente objetivo tiene que dividir la lista <code>[F|R]=[3,4]</code> en dos trozos, que, dada la implementación de <code>append</code>, son inicialmente <code>A=[], B=[3,4].</code>
</li><li> por último calcula la longitud de A, que es 0, y comprueba si 0 es menor o igual que 1. Como esto último es cierto, da la primera solución:<br>
<code> E=3, R=[4], F=3, A=[], B=[3,4], LA=0 </code>
</li><li> Si se piden más soluciones, retrocede, de derecha a izquierda, en busca del primer subobjetivo reevaluable, que resulta ser el <code>append</code>,
cuya segunda solución es <code>A=[3], B=[4].</code> En este caso se tendrá <code> LA=1 </code>, por lo que sigue siendo cierta la última comprobación y se obtiene la segunda solución:<br>
<code> E=3, R=[4], F=3, A=[3], B=[4], LA=1 </code>
</li><li> Si se piden más soluciones, Prolog vuelve a retroceder y reevalúa el <code>append</code>, cuya tercera solución es <code>A=[3,4], B=[]</code>.
En este caso se tendrá <code> LA=2 </code>, por lo que la última comprobación ya no es cierta y el objetivo falla.
</li><li> Ante el fallo anterior Prolog vuelve a retroceder pero ya no le quedan objetivos reevaluables, por lo que termina.
</li></ul></em>
</div>
<div class="nb-cell query" name="q15">
q([a|[b,c]], F) = q([E,_|S], E), append(U, V, [F|S]),
length(U, LU), LU >= 1.
</div>
<div class="nb-cell html" name="htm45">
<em>Razonamiento muy similar al anterior.</em>
</div>
<div class="nb-cell html" name="htm5">
<h4><strong> 3. Implementación de algunos predicados sobre listas</strong></h4>
Implemente los predicados para el manejo de listas en
Prolog descritos a continuación y:
<ul>
<li> Compruebe que sus implementaciones son correctas
haciendo consultas para casos significativos.
</li>
<li> Pida a Prolog todas las posibles soluciones y
asegúrese de que los predicados implementados
<strong>solo devuelven la o las soluciones correctas.
En caso de que no sea así, use el predicado de corte
adecuadamente.
</strong>
</li>
<li> Cuando su implementación presente <strong>recursión lineal</strong>
(una única llamada recursiva) pero no sea <strong>recursión final</strong>
(la llamada recursiva es lo último que se ejecuta) ni <strong>recursión final módulo cons</strong>
(la llamada recursiva es lo penúltimo que se ejecuta,
siendo lo último la construcción de la cabeza de una lista), <em>implemente una segunda
versión con <strong>recursión final (o recursión final módulo cons)</strong></em> mediante el uso de parámetros de
acumulación, de forma similar a como se hace en los apuntes con
el predicado factorial o el predicado inversa.
</li>
</ul>
</div>
<div class="nb-cell program" data-background="true" name="p1">
% enesimo(?L, +N, ?E)
% cierto si E es el elemento de la lista L situado
% en la posición N, entendiendo que la cabeza de la
% lista está situada en la posición 1 (debe fallar
% en cualquier otro caso).
%
% Proporcione una implementación RECURSIVA.
enesimo(L, N, E) :-
integer(N),
N >= 1,
enesimo_aux(L, N, E).
enesimo_aux([C|_], 1, C).
enesimo_aux([_|R], N, E) :-
N > 1,
N1 is N-1,
enesimo_aux(R, N1, E).
</div>
<div class="nb-cell html" name="htm48">
<em>La comprobación N > 1 de la segunda cláusula de enesimo_aux sirve para indicar, en
caso de backtracking, que cuando sea N=1 no debe aplicarse la segunda
regla. Esta comprobación podría sustituirse por un corte en el cuerpo
de la primera cláusula del programa (es decir, sustituyendo
"enesimo([C|_], 1, C)." por "enesimo([C|_], 1, C) :- !."). En cualquier
caso esta precaución es recomendable por razones de eficiencia pero no
es imprescindible, puesto que aunque entrase por la segunda regla con
N=1 Prolog acabaría fallando al vaciarse la lista (el predicado falla
para listas vacías). Lo mismo ocurriría si "N" fuese mayor que la
longitud de L, por lo que no es necesario comprobar que no lo sea.</em>
</div>
<div class="nb-cell query" name="q6">
enesimo([],1,E).
</div>
<div class="nb-cell query" name="q7">
enesimo([1,2,3], -1, E).
</div>
<div class="nb-cell query" name="q22">
enesimo([1,2,3],2, E).
</div>
<div class="nb-cell query" name="q23">
enesimo([1,2,3], 4, E).
</div>
<div class="nb-cell program" data-background="true" name="p5">
% enesimo_norec(?L, +N, ?E)
% cierto si E es el elemento de la lista L situado
% en la posición N, entendiendo que la cabeza de la
% lista está situada en la posición 1.
%
% Proporcione una implementación NO RECURSIVA, basada en el uso
% de algunos de los predicados predefinidos para el manejo de listas.
% PISTA: si usa append para descomponer la lista L en dos trozos
% tales que el primer trozo tenga tamaño N-1, el primer elemento del
% segundo trozo será el N-ésimo de L.
%
enesimo_norec(L, N, E) :-
integer(N),
N > 0,
append(Prefijo, [E|_], L),
N1 is N - 1,
length(Prefijo, N1),
!. % por eficiencia: para de buscar una vez encontrado el
% (único) prefijo de tamaño N-1.
</div>
<div class="nb-cell html" name="htm49">
<em>Observe en el código anterior que si N es mayor que el tamaño de la lista, Prolog no será capaz de
descomponer la lista en dos trozos de forma que el primero tenga
tamaño N-1 y el segundo sea no vacío, por lo que fallará.
En otro caso, una vez encontrado el único prefijo posible de tamaño
N-1, no tiene sentido seguir buscando descomposiciones, de ahí
el corte, !, que evita el backtracking.</em>
</div>
<div class="nb-cell program" data-background="true" name="p2">
% elimina_n(?L, +N, ?NL)
% cierto si NL es la lista resultante después de
% eliminar el elemento de L situado en la posición N,
% entendiendo que la cabeza de la lista está situada
% en la posición 1. Si N es mayor que la longitud de
% L, NL será igual a L.
%
% Proporcione una implementación RECURSIVA
%
elimina_n(L, N, NL) :-
integer(N),
N >= 1,
elimina(L, N, NL).
elimina([], _ , []).
elimina([_|R], 1, R).
elimina([C|R], N, [C|NR]) :-
N > 1,
N1 is N-1,
elimina(R, N1, NR).
</div>
<div class="nb-cell html" name="htm50">
<em> En este último caso la comprobación "N > 1" de la última cláusula (que
podría sustituirse por un corte en la cláusula anterior: <code>elimina([_|R], 1, R) :-!. </code>) es imprescindible para evitar soluciones incorrectas
en caso de backtracking.</em>
</div>
<div class="nb-cell program" data-background="true" name="p8">
% elimina_n(?L, +N, ?NL)
% cierto si NL es la lista resultante después de eliminar el
% elemento de L situado en la posición N, entendiendo que la
% cabeza de la lista está en la posición 1.
% Si N es mayor que la longitud de L, NL será igual a L.
%
% Proporcione una implementación NO RECURSIVA, basada en el uso
% de algunos de los predicados predefinidos para el manejo de listas.
%
% PISTA: descomponga la lista en dos trozos adecuados y vuelva
% a componerlos obviando el elemento n-ésimo. Tenga en cuenta
% que si N es mayor que la longitud de la lista, el intento
% de descomposición fallará y tendrá que tratar ese caso aparte.
elimina_n_norec(L, N, NL) :-
integer(N),
N > 0,
append(Prefijo, [_|Sufijo], L),
N1 is N - 1,
length(Prefijo, N1),
!,
append(Prefijo, Sufijo, NL).
elimina_n_norec(L, N, L) :-
integer(N),
N > 0.
</div>
<div class="nb-cell html" name="htm46">
<em> Note que en la primera regla del programa anterior, si Prefijo tiene tamaño N-1, "_" es el elemento n-ésimo,
que hay que eliminar. Gracias al corte de la primera regla, Prolog solo llegará
a la segunda si N no cumple las condiciones o no es posible descomponer L de la
forma requerida, y esto último solo ocurrirá si N es mayor que la longitud de L.</em>
</div>
<div class="nb-cell program" data-background="true" name="p6">
% elimina_n_bis(?L, +N, ?NL)
% cierto si NL es la lista resultante después de
% eliminar el elemento de L situado en la posición N,
% entendiendo que la cabeza de la lista está situada
% en la posición 1. **El predicado debe fallar si N es mayor
% que la longitud de L**
%
% Proporcione una implementación RECURSIVA.
%
elimina_n_bis(L, N, NL) :-
integer(N),
N >= 1,
elimina_bis(L, N, NL).
elimina_bis([_|R], 1, R).
elimina_bis([C|R], N, [C|NR]) :-
N > 1,
N1 is N-1,
elimina_bis(R, N1, NR).
</div>
<div class="nb-cell program" data-background="true" name="p7">
% elimina_n_bbis(?L, +N, ?NL)
% cierto si NL es la lista resultante después de
% eliminar el elemento de L situado en la posición N,
% entendiendo que la cabeza de la lista está situada
% en la posición 1. El predicado debe fallar si N es mayor
% que la longitud de L.
%
% Proporcione una implementación NO RECURSIVA, basada en el uso
% de algunos de los predicados predefinidos para el manejo de listas.
% PISTA: descomponga la lista en dos trozos adecuados y vuelva
% a componerlos obviando el elemento n-ésimo.
%
elimina_n_bis_norec(L, N, NL) :-
integer(N),
N > 0,
append(Prefijo, [_|Sufijo], L),
N1 is N - 1,
length(Prefijo, N1),
!,
append(Prefijo, Sufijo, NL).
</div>
<div class="nb-cell program" data-background="true" name="p4">
% borrartodos(+L,+E,?NL)
% cierto si NL es la lista resultante después de
% eliminar de L todos los elementos idénticos a E
% (si los hay). Tenga en cuenta que no deben eliminarse
% elementos que sean unificables con E, sólo aquellos que
% sean idénticos. Por ejemplo,borrartodos([a,b],X,[a,b]) y
% borrartodos([a,X], a, [X]) deben ser ciertos.
borrartodos([],_,[]).
borrartodos([C|R],E,NR) :-
C == E,
!,
borrartodos(R,E,NR).
borrartodos([C|R],E,[C|NR]) :-
borrartodos(R,E,NR).
</div>
<div class="nb-cell query" name="q24">
</div>
<div class="nb-cell program" data-background="true" name="p13">
% insertardetras(+L,+E1,+E2,?NL)
% cierto si NL es la lista resultante de insertar
% E2 justo detrás de cada aparición de E1 en L
%
insertardetras([],_,_,[]).
insertardetras([E1|R],E1,E2,[E1,E2|NR]) :-
!,
insertardetras(R,E1,E2,NR).
insertardetras([C|R],E1,E2,[C|NR]) :-
insertardetras(R,E1,E2,NR).
</div>
<div class="nb-cell html" name="htm47">
<em> Los cortes de los dos predicados anteriores son
imprescindibles para evitar soluciones incorrectas en caso de
backtracking. Un efecto similar podría haberse obtenido añadiendo
las comprobaciones "C \= E" (en borrartodos) o "C \= E1"
(en insertardetras) al principio del cuerpo de su última cláusula.</em>
</div>
<div class="nb-cell program" data-background="true" name="p14">
% divide(+L, ?LNeg, ?LPos)
% cierto si L es una lista de números, LNeg es una
% lista con los números negativos de L y LPos es
% una lista con los números nulos o positivos de L,
% en ambos casos respetando el orden en el que
% aparecen en L.
% Facilite dos versiones distintas de este predicado,
% la segunda de ellas utilizando el corte.
% VERSIÓN 1: Sin utilizar el predicado de corte
divide_v1([],[],[]).
divide_v1([C|R], [C|R1], R2) :-
number(C),
C < 0,
divide_v1(R,R1,R2).
divide_v1([C|R], R1, [C|R2]) :-
number(C),
C >= 0,
divide_v1(R,R1,R2).
</div>
<div class="nb-cell program" data-background="true" name="p3">
% VERSIÓN 2: Utilizando el predicado de corte
divide_v2([],[],[]).
divide_v2([C|R], [C|R1], R2) :-
number(C),
C < 0,
!,
divide_v2(R,R1,R2).
divide_v2([C|R], R1, [C|R2]) :-
number(C),
% ya no es necesario comprobar C >= 0 puesto que solo
% se entrará por esta regla cuando eso ocurra.
divide_v2(R,R1,R2).
</div>
<div class="nb-cell program" data-background="true" name="p16">
% cuenta_const(+TC, +L, ?N)
% cierto si N es el número de apariciones del término
% constante C como elemento de la lista L. Recuerde
% que Prolog proporciona predicados predefinidos para la
% clasificación de términos, entre los que figura atomic(X),
% cierto si X es un término constante. Tenga en cuenta que
% no deben contarse elementos que sean unificables con TC,
% sólo aquellos que sean idénticos. Por ejemplo, la consulta
% “?- cuenta_const(a, [a,[a,p(a),b],X],N).” debe ser cierta con N=1,
% puesto que sólo una de las a’s que aparecen en L es un elemento de
% L (el resto de a’s están contenidas en el segundo elemento de L)
% y la variable X no debe contarse ya que, aunque es unificable con a,
% no es una a.
%
cuenta_const(TC, L, N) :-
atomic(TC),
cuenta_const1(TC, L, N).
cuenta_const1(_, [], 0).
cuenta_const1(TC, [C|R], N) :-
TC == C,
!,
cuenta_const1(TC, R, NR),
N is NR + 1.
cuenta_const1(TC, [_|R], N) :-
cuenta_const1(TC, R, N).
</div>
<div class="nb-cell program" data-background="true" name="p9">
% implementación con recursión final
cuenta_const_acc(TC, L, N) :-
atomic(TC),
cuenta_const_acc(TC, L, 0, N).
cuenta_const_acc(_, [], A, A).
cuenta_const_acc(TC, [C|R], A, N) :-
TC == C,
!,
A1 is A+1,
cuenta_const_acc(TC, R, A1, N).
cuenta_const_acc(TC, [_|R], A, N) :-
cuenta_const_acc(TC, R, A, N).
</div>
<div class="nb-cell program" data-background="true" name="p17">
% aplana(+L,?NL)
% cierto si L es una lista y NL es la lista formada por todos los
% términos que aparecen en L, quitando las listas internas de L en
% caso de que las haya. Por ejemplo, la consulta
% ?- aplana([a, [X,p(a,Z),[b,[c]]], V], A).
% debe ser cierta con A = [a, X, p(a,Z), b, c, V]
% Pista: utilice los predicados is_list/1 y append/3.
%
aplana([], []).
aplana([C|R], L) :-
is_list(C),
!,
append(C, R, NL),
aplana(NL, L).
aplana([C|R], [C|NR]) :-
aplana(R, NR).
</div>
<div class="nb-cell program" data-background="true" name="p19">
% empaqueta(+L, ?NL)
% cierto si NL contiene los mismos elementos que la lista L pero
% de forma que toda ristra de elementos iguales consecutivos
% aparece empaquetada en una sublista. Por ejemplo, la consulta
% “empaqueta([a,a,a,b,a,a,c,c,d], X).” debe devolver cierto
% con X=[[a,a,a], [b], [a,a], [c,c], [d]]. Una posible solución
% consiste en implementar y utilizar en la implementación de
% empaqueta el predicado auxiliar lista_cabeza(+L, ?LC, ?LR),
% cierto si L es una lista, LC es la lista formada por la ristra
% de elementos iguales consecutivos que encabeza L y LR es lo que
% queda en la lista. Por ejemplo, la consulta
% “?- lista_cabeza([a,a,a,b,a,a,c,c,d], X, Y).” debe se cierta
% con X=[a,a,a] e Y=[b,a,a,c,c,d].
% Implementando y usando lista_cabeza
lista_cabeza([], [], []).
lista_cabeza([C], [C], []).
lista_cabeza([C1,C2|R], [C1], [C2|R]) :-
C1 \== C2,
!.
lista_cabeza([C,C|R], [C|LC], LR) :-
lista_cabeza([C|R], LC, LR).
empaqueta([], []).
empaqueta([C|R], [LC|NR]) :-
lista_cabeza([C|R], LC, LR),
empaqueta(LR, NR).
</div>
<div class="nb-cell program" data-background="true" name="p10">
% otra posible implementación de empaqueta, sin usar lista_cabeza
empaquete([], []).
empaquete([C],[[C]]).
empaquete([C1,C2|R], [[C1]|ER]) :-
C1 \== C2,
!,
empaquete([C2|R], ER).
empaquete([C1,C2|R], [[C1|E1]|ER]) :-
empaquete([C2|R], [E1|ER]).
</div>
<div class="nb-cell program" data-background="true" name="p20">
% codifica(+L, ?NL), cierto si L es una lista y NL es una lista
% cuyos elementos son listas de la forma [E,N], donde cada uno de
% estos pares representa una ristra de N elementos E consecutivos en
% L. Por ejemplo, la consulta “?- codifica([a,a,a,b,a,a,c,c,d], LL).”
% debe ser cierta con LL = [[a,3], [b,1], [a,2], [c,2], [d,1]].
% Para la implementación de este predicado puede utilizar el
% predicado empaqueta/2 anterior así como el predicado predefinido
% length(?L, ?N), cierto si N es la longitud de la lista L.
%
codifica(L, NL) :-
empaqueta(L, LL),
transforma(LL, NL).
transforma([], []).
transforma([[C|LC]|R], [[C,N]|LR]) :-
length([C|LC], N),
transforma(R, LR).
</div>
<div class="nb-cell program" data-background="true" name="p11">
% Implementación directa de codifica, alternativa a la anterior
codific([], []).
codific([C|R], [[C,NC]|NR]) :-
codific(R, [[C,N]|NR]),
!,
NC is N + 1.
codific([C|R], [[C,1]|NR]) :-
codific(R, NR).
</div>
<div class="nb-cell program" data-background="true" name="p21">
% asteriscos(+L)
% recibe una lista de números naturales positivos y escribe para cada
% uno de ellos una línea con tantos asteriscos como indique el número
% correspondiente. Por ejemplo, la consulta “?- asteriscos([2,1,3]).”
% debe devolver cierto y debe producir el efecto
% **
% *
% ***
asteriscos([]).
asteriscos([C|R]) :-
escribe_asteriscos(C),
nl,
asteriscos(R).
escribe_asteriscos(1) :- write(*).
escribe_asteriscos(N) :-
N>1,
write(*),
N1 is N-1,
escribe_asteriscos(N1).
</div>
</div>