INTRODUCCIÓN.
Tal y como hemos venido trabajando, en esta ocasión nos toca trabajar mas a profundidad, como son las listas, operadores y la aritmética, los lenguajes como java, c, c++, etc. etc, sabemos que manejan listas porque lo hacen justamente para facilitar operaciones complejas y sobre todo para almacenar cierta información a procesar, ¿En prolog necesitamos listas, operadores o la aritmética? si, si las necesitamos porque trabajamos con objetos estructurados tipo árbol, ademas que tenemos que lidiar con los de tipo operador esto y mas vamos a trabajar.
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í ]
Sin embargo ésta es solamente la apariencia externa de
las listas. 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
la cola es : [ tenis,
tomás, eskí ].
En general, la cabeza puede ser
cualquier cosa (cualquier objeto Prolog, por ejemplo, un árbol ó una variable);
la cola tiene forzosamente que ser una lista. 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í, [] ))))
la siguiente figura
muestra la estructura de árbol que le corresponde :
Observe que la lista vacía
aparece en el término anterior. Esto es porque la última cola es una lista con
un sólo elemento:
[ eskí ]
esta lista tiene a su vez a la
lista vacía como cola :
[ eskí ] = .( 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:
concat( [], 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]
la figura siguiente
ilustra la concatenación de [X|L1] y otra lista L2 :
el resultado de la
concatenación es la lista [X|L3] donde L3 es la concatenación de L1 y L2. En
Prolog lo representamos:
concat( [X|L1], L2, [X|L3]) :-
concat( L1, L2, L3).
En Prolog queda así----------->
En Prolog queda así----------->
?- concat( [a,b,c], [1,2,3], L).
L = [a,b,c,1,2,3]
?- concat( [a,[b,c],d],[a,[],b],L).
L = [a, [b,c], d, a, [], b]
[Inf. Tomada por el Autor: Edgar Altamirano Carmona Universidad Autónoma de Guerrero.]
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.
eliminar3[L,L1]:-concat([X,Y,Z],L1,L).
concat([],L,L).
concat([X|L1], L2,[X|L3]):-concat(L1,L2,L3).
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.
elimina([],_X,[]):-!.
elimina([X|L],X,Z):- elimina(L,X,Z),!.
elimina([R|L],X,[R|Z]):-
elimina(L,X,Z),!.
Pruebas realizadas:
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, y (b) sin usarla.
ultimo(X,[_|L1]):-
ultimo(X,L1).
ultimo(X,[X]).
En las pruebas nos muestra si
es true que el elemento que se
indica es el último de la lista o false
si no lo es.
Adicionar
un elemento.
Para adicionar un
elemento a una lista, se puede colocar este nuevo elemento al frente de la
lista de tal modo que sea la nueva cabeza de la lista :
aumentar( X, L, [X|L]).
Eliminar
un elemento.
Para eliminar un
elemento X de una lista L se puede programar la relación:
eliminar( X, L, L1)
donde L1 es igual a
la lista L con el elemento X removido. Esta relación se puede definir de manera
similar a la relación de pertenencia, tendremos nuevamente dos casos posibles :
(1). Si X es la
cabeza de la lista, entonces el resultado después de la eliminación es la cola
de la lista.
(2). Si X está en la
cola entonces deberá eliminarse de la cola.
En Prolog:
pruebas realizadas nos dan los siguientes resultados:
3.3. Notación de los
operadores.
En matemáticas estamos acostumbrados a escribir expresiones como:
2 * a + b * c
donde + y * son operadores, 2,a,b y c son argumentos. Decimos que estos operadores son infijos porque aparecen entre dos argumentos. Estas expresiones se pueden representar como árboles y se pueden escribir como términos de Prolog con los símbolos + y * como functores:
+( *( 2, a), *( b, c))
Prolog acepta también la notación infija pero recuerde que ésta es solamente su representación externa y será automáticamente convertida a la forma normal anterior de Prolog (árbol). Es decir, si escribimos en la forma a + b, Prolog lo manejará exactamente igual que si hubiésemos escrito +( a, b).
El principal functor será siempre el operador con la más alta precedencia.
Un programador puede definir además sus propios operadores. Por ejemplo podemos definir los operadores tiene y soporta como operadores infijos y poder escribir después en nuestros programas hechos como:
pedro tiene informacion.
el_piso soporta la_mesa.
estos hechos resultan exactamente equivalentes a :
tiene( pedro, informacion)
soporta( el_piso, la_mesa)
La manera en cómo definimos operadores nuevos es insertando en el programa tipos especiales de cláusulas conocidas como directivas que actúan para definir operadores. La definición de un operador debe aparecer en el programa antes de cualquier expresión que lo contenga. Por ejemplo, el operador 'tiene' se puede definir con la siguiente directiva:
:- op( 600, xfx, tiene).
esto le dice a Prolog que queremos utilizar 'tiene' como operador y cuyo valor de precedencia es 600 y su tipo es 'xfx' que indica que se trata de un operador infijo.
Nótese que la definición del operador no especifica ninguna operación ó acción. En principio, no se asocia ninguna operación ni dato alguno con el operador definido (excepto en casos muy especiales). Los operadores se usan normalmente como functores para combinar objetos con estructuras y no invocan acciones o datos aunque la palabra operador lo sugiera.
Los nombres de los operadores deben ser átomos y su precedencia debe
estar en un rango que dependa del sistema usado. Asumiremos un rango de 1 a 1200.
Existen tres tipos de grupos de operadores:
(1). Operadores infijos de tres tipos:
xfx xfy yfx
(2). Operadores prefijos de dos tipos:
fx fy
(3). Operadores postfijos de dos tipos:
xf yf
Explicaremos ahora la diferencia entre 'x' y 'y' pero antes debemos introducir la noción de precedencia del argumento. Si un argumento se encierra entre paréntesis ó se trata de un objeto no estructurado, entonces su valor de precedencia es 0. Si un argumento es una estructura entonces su valor de precedencia es igual a la precedencia de su functor principal. 'x' representa un argumento cuyo valor de precedencia debe ser estrictamente menor que el del operador. 'y' representa un argumento cuyo valor de precedencia es menor ó igual al del operador.
Estas reglas ayudan a reconocer expresiones ambiguas con varios operadores de la misma precedencia. Por ejemplo, la expresión:
a - b - c
se entiende normalmente como (a - b) - c y no como a - (b - c). Para realizar esta interpretación el operador '-' tiene que definirse como yfx.
Como otro ejemplo consideremos el operador prefijo not. Si not se define como fy entonces la siguiente expresión es legal :
not not p
pero si se define como fx la expresión es ilegal porque el argumento del primer not es 'not p' que tiene la misma precedencia que 'not'. En este caso la expresión debe escribirse como :
not ( not p)
Prolog contiene operadores predefinidos listos para usarse y que no necesitan definirse:
:- op( 1200, xfx, ':-').
:- op( 1200, fx, [:-,?-]).
:- op( 1100, xfy, ';').
:- op( 1000, xfy, ',').
:- op( 700, xfx, [=,is,<,>,=<,>=,==,=\=,\==,=:=]).
:- op( 500, yfx, [+,-]).
:- op( 500, fx, [+,-,not]).
:- op( 400, yfx, [*,/,div]).
:- op( 300, xfx, mod).
[Inf. Tomada por el Autor: Edgar Altamirano Carmona Universidad Autónoma de Guerrero.]
3.4. Aritmética.
Los operadores
predefinidos que se pueden utilizar para las operaciones aritméticas son :
+ adición
* multiplicación
- sustracción
/ división
mod módulo (residuo de la
división entera).
Observe lo siguiente:
Si preguntamos
?- X = 1 + 2.
Prolog contestará :
Y no X = 3 como
podriamos esperar. La razón es simple: la expresión 1+2 solamente denota un
término de Prolog donde el símbolo + es el functor y 1 y 2 son sus argumentos.
No existe nada en la pregunta anterior que force a Prolog para activar la
operación de la adición. Sin embargo existe un operador predefinido de Prolog “is”
para resolver este problema. El operador is forza la evaluación. La manera
correcta de invocar a la operación aritmética es:
?- X is 1 + 2.
Otros ejemplos de uso del
operador is son:
?- X = 3/2.
X = 1.5
?- X = 3 div 2.
X = 1
Las operaciones
aritméticas también están involucradas cuando se comparan valores numéricos.
Por ejemplo,
?- 277 * 37 > 10000.
Los operadores de
comparación son los siguientes:
X > Y X es mayor
que Y
X < Y X es menor
que Y
X >= Y X es mayor
o igual que Y
X =< Y X es menor
o igual que Y
X =:= Y los valores
de X y Y son iguales
X =\= Y los valores de X y Y no son
iguales
Ejemplos.
?- 1 + 2 =:= 2 + 1.
?- 1 + 2 = 2 + 1.
?- 1 + A = B + 2.
Ejemplo.
Dados dos enteros positivos, X y Y, encontrar el máximo común
divisor D. Por ejemplo, para X=20 y Y=25 el máximo común divisor es D=5.
El máximo común
divisor puede encontrarse de acuerdo a tres casos:
(1). Si X y Y son
iguales, entonces D es igual a X.
(2). Si X < Y
entonces D es igual al máximo común divisor de X y la diferencia Y – X.
(3). Si Y < X
entonces D es igual al máximo común divisor de X y Y intercambiados.
En Prolog:
pruebas realizadas:
Ejemplo.
Encontrar la longitud de una lista de objetos.
Pensamos en dos
casos:
(1). Si la lista está
vacía entonces su longitud es 0.
(2). Si no, entonces
la lista puede verse como Lista = [Cabeza | Cola] y la longitud de la lista es
igual a 1 mas la longitud de la Cola.
En Prolog:
?- longitud([a,b,[c,d],e], N).
N = 4
Ejercicios.
1. 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.
max(X, Y, Max) :-
X > Y, !, Max is X.
max(X, Y, Max) :-
Y >= X, Max is Y.
acuérdense de aguardar su clausulas del bloc de notas con (.pl)
Pruebas realizadas:
2. Defina el
predicado maxlist(List, Max) de tal manera que Max sea el mayor número de la
lista List de números.
maxlist(Max, [X|Xs]):-
list_max2(Max, X, Xs).
list_max2(Max, Max, []):- !.
list_max2(X, Y, [Z|Zs]):-
Z >= Y,!,
list_max2(X, Z, Zs).
list_max2(X, Y, [Z|Zs]):-
Z =< Y,
list_max2(X, Y, Zs).
En las pruebas realizadas en prolog nos muestra el numero mayor de una lista.
3. Defina el
predicado sumlist(List, Sum) donde Sum es la suma de una lista de números dada
en List.
sumlist(List,Sum).
List([X,Y,Z]).
sumlist(List,Sum):-X is Y is Z=:=Sum.
Resultado realizado en prolog.
4. 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
ordenada([_]).
ordenada([X,Y|L]) :-
X =< Y,
ordenada([Y|L]).
En las pruebas realizadas nos muestra true si estan ordenada la lista de lo contrario nos muestra false.
5. 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];
subsum([],0,[]).
subsum([X|L1],Y,[X|L2]) :-
Y >= X,
Z is Y-X,
subsum(L1,Z,L2).
subsum([_|L1],Y,L2) :-
subsum(L1,Y,L2).
Pruebas realizadas en prolog nos muestra estos datos.
CONCLUSIONES:
Como ya vimos la estructura sigue siendo la misma que hemos venido trabajando solo que la lógica, almenos hasta este capitulo a incrementado, aunque esto se soluciona con estudiar los operadores aritméticos, y de entender como las interpreta Prolog por lo demás son cosas básicas para prolog muy interesante al trabajar con listas ya que se vuelve una manera mas exacta de trabajar y ya nos acercamos a lenguaje real, como también se nota que es muy parecido al trabajar con otros lenguajes de programación, java, c++, c#, c, etc, etc.
HUMOR:
 |
| facebook version (-5000) años atras. |
 |
| upss OTRA VES SE NOS FUE...JJJJJ |
BIBLIOGRAFIA:
Upuntes de Prolog.
Autor: Edgar Altamirano Carmona
Universidad Autónoma de Guerrero.
Upuntes de Prolog.
Autor: Edgar Altamirano Carmona
Universidad Autónoma de Guerrero.
