Ejercicio. 3

3. Listas, operadores y aritmética.

3.1. Representación de listas.

La "lista" es una estructura de datos ampliamente utilizada en la programación no numérica. Una lista es una secuencia de cualquier número de elementos, tales como los objetos ana, tenis, tomás, eskí. Esta lista se puede escribir en Prolog como:

[ ana, tenis, tomás, eskí ]

En Prolog todos los objetos estructurados son árboles y las listas no son una excepción.

¿Cómo puede una lista representarse como un objeto Prolog? Tenemos que considerar dos casos: si la lista está ó no vacía. En el primer caso la lista se escribe como un átomo Prolog : [].

En el segundo caso la lista puede verse como formada por dos cosas:

• (1). el primer elemento, llamado "cabeza" de la lista.

• (2). los elementos restantes, llamados en conjunto: "cola" de la lista.

Para el ejemplo anterior : [ ana, tenis, tomás, eskí ] la cabeza es : ana y la cola es : [ tenis, tomás, eskí ].

La cabeza y la cola se combinan en una estructura con un functor especial. El símbolo para este functor
depende de la implementación de Prolog. Asumiremos que se trata del punto [.] .

.( Cabeza, Cola)

Debido a que la cola es a su vez una lista, se tratará de una lista vacía ó una lista con cabeza y cola. Por lo tanto para representar listas de cualquier longitud no se necesita establecer ningún principio adicional. El ejemplo anterior se representa con el término:

.( ana, .( tenis, .( tomás, .( eskí, [] ))))

3.2. Operaciones sobre listas.

Las listas se pueden utilizar para representar conjuntos aunque se debe tomar en cuenta que existen diferencias: el orden de los elementos en un conjunto no interesa mientras que en una lista sí, además los objetos se pueden repetir en una lista y en un conjunto no. Aún con estas diferencias, las operaciones más frecuentes sobre listas son semejantes a las operaciones sobre conjuntos:

Pertenencia a una lista.

Implementaremos la relación miembro como:
miembro( X, L) donde X es un objeto y L es una lista. La meta miembro( X, L) es cierta si X es miembro de la lista L, por ejemplo :

miembro( b, [ a, b, c]) es cierta, y miembro( b, [ a, [ b, c] ]) no es cierta, pero miembro( [ b, c], [ a, [ b, c]])
es cierta. El programa para la relación de pertenencia se puede basar en la siguiente observación :

X es un miembro de L si,

• (1) X es la cabeza de L, ó

• (2) X es un miembro de la cola de L.

Esto puede representarse con dos cláusulas, la primera es un hecho simple y la segunda es una regla:

miembro( X, [ X | Cola]).
miembro( X, [ Cabeza | Cola] ) :- miembro( X, Cola).

Concatenación.

Para la operación de concatenación definiremos la relación:

concat( L1, L2, L3) donde L1 y L2 son dos listas y L3 es su concatenación. Por ejemplo:
concat( [a,b], [c,d], [a,b,c,d]) es cierta, pero concat( [a,b], [c,d], [a,b,a,c,d]) es falsa. En la definición de concat tendremos dos casos dependiendo del primer argumento L1:

• (1) Si el primer argumento es la lista vacía entonces el segundo y el tercer argumento deben ser la misma lista:c oncat( [], L, L).

• (2). Si el primer argumento de concat no es una lista vacía, entonces tiene cabeza y cola, es decir, se ve como : [ X | L1]

Ejercicios.

1. Escriba una meta, usando concat, para eliminar los tres últimos elementos de una lista L produciendo otra lista L1. Recomendación: L es la concatenación de L1 y una lista de tres elementos.

Solucion:
eliminar3(L, L1) :- concat([X,Y,Z], L1, L).
concat( [], L, L).
concat( [X|L1], L2, [X|L3]) :- concat( L1, L2, L3).
Ejecucion:
?- eliminar3([a,b,c,d,e], L).
L = [d, e] ;
No

2. Escriba una secuencia de metas para eliminar los tres primeros elementos y los tres
últimos elementos de una lista L produciendo la lista L2.

Solucion:
eliminar3(L, L1) :- concat([X,Y,Z], L1, L).
concat( [], L, L).
concat( [X|L1], L2, [X|L3]) :- concat( L1, L2, L3).
Ejecucion:
?- eliminar3([a,b,c,d,e], L).
L = [d, e] ;
No

3. Defina la relación: ultimo( Elemento, Lista) de tal modo que Elemento sea el último elemento de la lista Lista. Escriba dos versiones:

(a) usando la relación concat
(b) sin usarla.

4. Defina la relación max(X,Y,Max) de tal modo que Max sea el mayor valor de los
dos números X y Y.


5. Defina el predicado maxlist(List, Max) de tal manera que Max sea el mayor
número de la lista List de números.
6. Defina el predicado sumlist(List, Sum) donde Sum es la suma de una lista de
números dada en List.

7. Defina el predicado ordenada(List) el cual es cierto (devolverá yes) si List es una
lista ordenada de números en forma ascendente o descendente, por ejemplo,
?- ordenada(1,5,6,6,9,12).
Yes

8. Defina el predicado subsum(Set, Sum, Subset) donde Set es una lista de números,
Subset es un subconjunto de esta lista y Sum es la suma de los números en
Subset. Por ejemplo,
?- subsum([1,2,5,3,2], 5, Sub).
Sub = [1,2,2];
Sub = [2,3];
Sub = [5];
...