LISTAS,
OPERADORES Y ARITMETICA
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)
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
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
casosposibles :
(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:
eliminar( X, [X|Cola], Cola).
eliminar( X, [Y|Cola], [Y|Cola1])
:-
eliminar(X, Cola, Cola1).
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.
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).
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á : X = 1 + 2
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.
X = 3
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.
?- 1 + 2 =:= 2 + 1.
Yes
?- 1 + 2 = 2 + 1.
No
Ejemplo2.
Ejemplo3. 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:
mcd(X,X,X).
mcd(X,Y,D) :-
X < Y,
Y1 is Y – X,
mcd(X,Y1,D).
mcd(X,Y,D) :-
Y < X,
mcd(Y,X,D).
PLUS
Plus sirve para sumar los argumentos recibidos,
ejemplo:
BETWEEN
Encuentra un número en un rango,
ejemplo:
SUCC
Devuelve verdadero si el 2º
argumento es= 1º + 1 y si el 1º >= 0, ejemplo:
IS
Es un predicado que define una
expresión, ejemplo:
FUNCIONES
Función
|
Descripción
|
Abs
|
Valor absoluto
|
sign
|
Signo de un numero
|
Min
|
Valor minimo
|
Max
|
Valor maximo
|
Random
|
Numero aleatorio.
|
round
|
Redondeo
|
Floor
|
Redondeo hacia arria
|
ceiling
|
Redondeo hacia abajo
|
sqrt
|
Raiz
|
powm
|
Potencia
|
pi
|
Valor de pi
|
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.
2. Defina el predicado
maxlist(List, Max) de tal manera que Max sea el mayor
número de la lista List de
números.
3. Defina el predicado
sumlist(List, Sum) donde Sum es la suma de una lista de
números dada en List.
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
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];
