Source: https://www.scribd.com/document/109744324/Material-Para-Aprender-Haskell
Timestamp: 2017-02-21 22:53:47+00:00

Document:
BrowseInterestsBiography & MemoirBusiness & LeadershipFiction & LiteraturePolitics & EconomyHealth & WellnessSociety & CultureHappiness & Self-HelpMystery, Thriller & CrimeHistoryYoung AdultBrowse byBooksAudiobooksNews & MagazinesSheet MusicBrowse allUploadSign inJoinProgramación Declarativa
José Carpio Cañada Gonzalo antonio aranda Corral José MarCo de la rosa
L.L. I. S. S.B.S.MATERIALES PARA LA DOCENCIA [95]
2010 © Universidad de Huelva Servicio de Publicaciones © Los Autores Maquetación COPIADORAS BONANZA. 978-84-15147-05-3
. Impresión COPIADORAS BONANZA.N.
Más bien. puede ayudar al alumno tener cerca el ordenador y probar los ejercicios propuestos y ver que realmente funcionan. ¿Cómo utilizar este material? Entender la filosofía de la programación declarativa no es tarea fácil.Programación Declarativa. Y lo que es más importante. métodos o predicados. Requiere de un cambio en la forma de pensar un programa.José carPio. empezando por ejercicios simples. C++. La idea de que a partir del caso más pequeño (n-1) deducimos el caso genérico (n) se repite en la mayoría de las sesiones. En las sesiones prácticas se proponen una serie de ejercicios que el alumnos debe programar utilizando el ordenador y el compilador o interprete de Prolog o Haskell según el caso. Al principio. El material está divido en catorce sesiones teóricas y nueve sesiones prácticas con una duración aproximada de una hora y media por sesión. Para llegar a entender el paradigma de la programación declarativa necesitamos reforzar la idea de que es posible programar cambiando el enfoque en la construcción de los programas. No todos los manuales que encontramos en la bibliografía resaltan esta idea. Hemos incluido los conocimientos teóricos básicos para que el alumno pueda empezar a programar declarativamente desde la primera sesión.
El material que aquí presentamos pretende guiar al alumno en el estudio de la Programación Lógica y la Programación Funcional. Este material tiene un enfoque eminentemente práctico. Este material utiliza un enfoque basado en el principio de inducción matemático y se apoya en este en el proceso de construcción de los programas. gonzalo antonio aranDa. No siempre resulta evidente ver que un programa declarativo funciona tras echarle un vistazo al código. Esto se consigue de forma progresiva. sintaxis del lenguaje y conjunto de funciones.
.. José marco. utilizan un enfoque similar a la descripción de otros lenguajes imperativos. Java o Perl) a describir el problema utilizando una serie de reglas (programación declarativa Prolog y Haskell). Hemos reducido al mínimo los conceptos teóricos. aumentando la dificultad hasta implementar ejercicios con estructuras de datos complejas como árboles o grafos. de que forma se ha llegado a la solución. Nosotros pensamos que en la programación declarativa es fundamental entender que es necesario cambiar el enfoque a la hora de programar y hacemos un especial hincapié en ello. incluyendo únicamente los elementos que consideramos imprescindibles para entender que es un programa declarativo. Pasamos de ordenar una serie de acciones (programación imperativa de C. Las sesiones teóricas incluyen ejercicios que sirven para reforzar los conceptos teóricos. ambos paradigmas incluidos dentro de la Programación Declarativa.
A partir de este momento. debe ser capaz de saber si el programa puede funcionar o no tras echarle un vistazo al código. Basándose en el principio de inducción.
. los ejercicios que al principio parecían imposibles de entender o programar. Esperamos que así sea y que tras el estudio de este material el alumnos entienda que se pueden hacer programas de un modo distinto.4
Materiales para la doCenCia [95]
Tras el estudio de este material. de se muestran entendibles desde la perspectiva declarativa. si el alumno ha comprendido el modo de construir los programas no necesitará seguir mentalmente la ejecución del programa para saber si este funciona.
A nuestro compañero Manuel Maestre Hachero que amablemente se ofreció a revisar el material y corregirlo desde la visión de un matemático.
Agradecimientos Queremos agradecer a los alumnos que asistieron a nuestras clases con atención e interés aportando muchas ideas que están reflejadas ahora en este manual de docencia.José carPio. Marcos del Toro Peral. gonzalo antonio aranDa.
Autores José Carpio Cañada Gonzalo Antonio Aranda Corral José Marco de la Rosa
.Programación Declarativa. A Francisco Moreno Velo.. A los profesores Jim Royer y Susan Older de la Universidad de Siracusa en Estados Unidos que amablemente nos permitieron incluir los ejercicios de la segunda sesión de Haskell de este manual. Águeda López Moreno y a Diego Muñoz Escalante que impartieron con nosotros esta asignatura y aportaron sus ideas. José marco.
Programación Declarativa. Funciones de orden superior 5. Recursividad Programación lógica con Prolog 0. José marco. Introducción 1. recursividad y notación extendida de listas en Haskell Ejercicios de Haskell de exámenes anteriores
Programación lógica con Prolog • • • • • Introducción al entorno SWI-Prolog Predicados sencillos en Prolog Predicados sobre listas en Prolog Árboles en Prolog Grafos en Prolog
.1 Listas 2.3 Grafos 3. tuplas. Prioridad de operadores 3.José carPio. Tuplas 10. Problemas de estados PRÁCTICAS Programación funcional con Haskell • • • • Introducción al entorno de programación Haskell Hugs Listas en Haskell Patrones. gonzalo antonio aranDa. Introducción 1.
TEORÍA Programación funcional con Haskell 0. Control de la ejecución 4.2 Árboles 2.. Patrones 9. Evaluación perezosa 4. Composición de funciones 7. Listas 8. Tipos de datos 2. Definición de funciones 2. Currificación 6. Unificación 2.
Introducción 1.TEORÍA
Introducción a la programación declarativa
0.2 Programación lógica 4. Programación imperativa 3. Programación declarativa 3. Paradigmas de programación 2.1 Programación funcional 3. Bibliografía
Sin embargo. gonzalo antonio aranDa. Si bien existen multitud de lenguajes de programación. incluyendo cualquier funcionalidad de interacción que podamos imaginar con los distintos componentes de la máquina.. poco comunes en otras materias de programación. los conjuntos de conceptos y visiones del dominio de problemas no son tan variados. De forma más general: un entorno filosófico o teórico de cualquier tipo.José carPio. Los diversos lenguajes de programación nos permiten comunicarnos con el ordenador con la intención de resolver un problema. José marco. así como los experimentos realizados para justificarlos. La tarea de programación dependerá totalmente de la capacidad de interpretación de código del ordenador en cuestión ya que tendremos que adaptar las descripciones generadas al lenguaje entendido por la máquina. leyes y generalizaciones de éstas. and the experiments performed in support of them are formulated. Cada lenguaje de programación aborda la solución de problemas en base a un conjunto de conceptos y una visión de cómo el ordenador debe comportarse para resolver dichos problemas. SECCIÓN 1. broadly : a philosophical or theoretical framework of any kind. Con el tiempo hemos llegado a un muy diverso abanico de lenguajes que se han ido creando de forma incremental sobre ese ‘lenguaje’ primigenio. Entenderemos problema en su forma más amplia.” “Un entorno filosófico y teórico de una escuela científica o disciplina dentro del cual son formulados teorías. laws and generalizations.” La programación de ordenadores se puede definir como la creación de descripciones codificadas que un ordenador pueda interpretar para resolver un determinado problema.Programación Declarativa. INTRODUCCIÓN El objetivo de esta asignatura es introducir al alumno en una forma de programación basada en un paradigma muy diferente al más usual paradigma imperativo.
SECCIÓN O. El paradigma declarativo provee al alumno además de un entorno conceptual frecuentemente utilizado para el estudio de determinados problemas de inteligencia artificial. Esta tarea ayudará al alumno a mejorar su capacidad de abstracción y a practicar con conceptos de programación como la recursividad o la evaluación perezosa. no es trivial establecer el modo en que es más interesante estructurar esta comunicación y varias aproximaciones diferentes han ido desarrollándose desde los inicios de la programación hasta hoy. de modo que cada conjunto tiene asociado normalmente varios lenguajes. PARADIGMAS DE PROGRAMACIÓN Paradigma: (según el diccionario Merrian-Webster) “A philosophical and theoretical framework of a scientific school or discipline within which theories. En los inicios. el ‘lenguaje de programación’ de la máquina era algo tan rudimentario como la conexión eléctrica de un punto a otro dentro de un circuito.
son: • • • • • • BASIC Lenguaje de programación C Fortran Pascal Perl PHP
. A cada uno de estos conjuntos se denomina paradigma de programación. si bien hay muchos más. Ejemplos de lenguajes imperativos. Este paradigma entiende que para resolver un problema se deben realizar una serie de pasos y el programador es el encargado de describir de forma ordenada y sistemática los pasos que debe seguir el ordenador para obtener la solución. PROGRAMACIÓN IMPERATIVA El primer paradigma que se suele estudiar es el paradigma imperativo. Ejemplos de diferentes paradigmas de programación son: • • • • • • • • • • Programación imperativa Programación estructurada Programación declarativa Programación lógica Programación funcional Programación dirigida por eventos Programación modular Programación orientada a aspectos Programación orientada a objetos Programación con restricciones
SECCIÓN 2.12
Cada uno de estos conjuntos de visión y conceptos condicionan el modo en que plantearse los problemas y las soluciones para poder expresarlos de modo que el ordenador sea capaz de resolverlos.
j++) if(lista[j] > lista[j+1]) intercambiar(&lista[j]. for(i=0. *y = temp. En programación lógica. temp = *x. burbuja(lista.i<(n-1). existen otros como los lenguajes algebraicos (por ejemplo. } void burbuja(int lista[].i++) for(j=0. en cambio. José marco.
Ejemplo de programa: ordenación con el algoritmo de la burbuja. plantea que los problemas sean descritos al ordenador con una serie de unidades conceptuales básicas que se pueden combinar según unas determinadas reglas para generar nueva información.int *y){ int temp. En esta asignatura estudiaremos dos subparadigmas del paradigma de programación declarativa: programación funcional y programación lógica.. Además de los subparadigmas mencionados. }
SECCIÓN 3... la unidad conceptual básica será el predicado lógico y en programación funcional será la función.j<(n-(i+1)). int n){ int i.. // .Programación Declarativa. *x = *y. gonzalo antonio aranDa. Declaraciones iniciales:
void intercambiar(int *x. se crearán las descripciones que representan al dominio en el cual existe el problema a resolver y se planteará el problema como una pregunta que debe ser respondida bien con alguna de las unidades conceptuales iniciales o bien con una combinación válida de ellas que es el propio ordenador quien debe buscar. Para la resolución de un problema.José carPio. SQL) o la programación basada en restricciones.&lista[j+1])..j.
. Las unidades conceptuales para la descripción del problema dependerán del subparadigma de programación concreto. }
void main(){ // .ELEMENTOS_LISTA). PROGRAMACIÓN DECLARATIVA El paradigma declarativo.
haskell. De entre los diferentes lenguajes de programación funcional existentes. http://www. • Desarrollo del programa no tan orientado a la solución de un único problema. composición de funciones básicas y el problema que queremos resolver se planteará normalmente como la evaluación de una función basadas en las previamente definidas. Esto quiere decir que en nuestro programa describiremos funciones y que estas funciones se pueden combinar unas con otras para generar nuevas funciones.org/haskellwiki/Introduction
. Con una programación adecuada.14
Ventajas: • Descripciones compactas y muy expresivas. Nuestro programa consistirá pues en la definición de una serie de funciones que son.1 Programación funcional La programación funcional es un subparadigma de la programación declarativa que utiliza la función como concepto descriptivo básico. en esta asignatura estudiaremos el lenguaje Haskell. podremos evaluarlas. Es posible describir universos de problemas con muy pocas líneas de código del lenguaje que permitan la solución de un gran número de problemas. La variedad de preguntas que se pueden responder con una única descripción del dominio de problemas concreto suele ser muy elevada. 3. basta haber descrito un dominio de problemas de forma correcta y saber formular nuestro problema como una simple consulta en dicho dominio. • No hay necesidad de emplear esfuerzo en diseñar un algoritmo que resuelva el problema. a su vez. Entre otras acciones que podremos realizar con funciones.
natural::(Num a.. José marco. De entre los diferentes lenguajes de programación funcional existentes. Nuestros problemas plantearán afirmaciones para las que el sistema será capaz de obtener una explicación lógica en base a los predicados programados en caso de que ésta existiera. http://www.Programación Declarativa.
Ejemplo de programa: comprobación de que un número es natural. en esta asignatura estudiaremos el lenguaje Prolog en concreto la versión software libre SWI-Prolog.José carPio. gonzalo antonio aranDa.org/
. Nuestro programa consistirá en una serie de predicados que describirán un mundo en el que los objetos se relacionan según las reglas de la lógica de predicados.2 Programación lógica La programación lógica es otro subparadigma de la programación declarativa que utiliza el predicado lógico como concepto descriptivo básico. Ord a)=> a -> Bool natural 1 = True natural n | n > 1 = natural (n-1) | otherwise = False
Main> natural (-1) False :: Bool Main> natural (10) True :: Bool Main> natural (12.swi-prolog.5) False :: Bool
X). yeray).Ascendiente):padre(Ascendiente.padre(juan.Descendiente).descendiente(X. X = pedro.lluis).descendiente(lluis.
.pedro). ?.16
Ejemplo de programa: relaciones de descendencia.Intermedio). false. % descendiente(Descendiente. true . padre(iker. juan). juan).Ascendiente):padre(Ascendiente. padre(pedro.Intermedio). descendiente(Descendiente. descendiente(Descendiente. Declaraciones iniciales:
% padre(Padre.Ascendiente) descendiente(Descendiente.
?.Hijo) padre(juan. ?. X = pedro . X = lluis .
Clocksin. L.
SECCIÓN 4. T. Gabriele C. Mellish Editorial: Springer Verlag Año: 1994 Prolog programming for artificial intelligence Autores: Ivan Bratko Editorial: Addison Wesley Año: 1990 Razonando con Haskell Autores: Blas C. BIBLIOGRAFÍA Bibliografía general Programación en Prolog Autores: W. Principios y paradigmas Autores: A..Programación Declarativa. Cervoni Editorial: Springer Año: 1996 An introduction to computing in Haskell Autores: Manuel M. Chakravarty. Gutiérrez. Keller Editorial: Pearson SprintPrint Año: 2002 Lenguajes de programación. Deransart. gonzalo antonio aranDa. R.José carPio.S. Tucker. José marco. F. A. EdDbali. Ruíz. C.F. y otros Editorial: Thompson Año: 2004 Bibliografía específica Prolog: the standard Autores: P. Noonan Editorial: Mc GrawHill Año: 2003
Definición de funciones 2. Funciones de orden superior 5. Tuplas 10. Introducción 1.PROGRAMACIÓN FUNCIONAL CON HASKELL
Programación funcional con Haskell 0. Composición de funciones
7. Patrones 9. Evaluación perezosa 4. Prioridad de operadores 3. Currificación 6. Recursividad
. Listas 8.
Programación Declarativa.- José carPio, gonzalo antonio aranDa, José marco.
SECCIÓN 0. INTRODUCCIÓN (http://www.haskell.org/haskellwiki/Introduction) ¿Qué es la programación funcional? Leguajes como C, Pascal, Java son lenguajes imperativos. Se llaman imperativos porque lo que hacemos al programar es indicar cómo debe resolverse algún problema. Indicamos el orden en el que deben realizarse las acciones.
main() { primero_haz_esto(); despues_esto_otro(); por_ultimo_esto(); }
El objetivo en la programación funcional es definir QUÉ CALCULAR, pero no cómo calcularlo. Un ejemplo de programación funcional es la que realizamos cuando programamos una hoja de cálculo: • No se especifica en qué orden deben calcularse las celdas. Sabemos que se realizarán los cálculos en el orden adecuado para que no existan conflictos con las dependencias. • No indicamos cómo organizar la memoria. Aparentemente nuestra hoja de cálculo es infinita, sin embargo, sólo se reserva memoria para las celdas que estamos utilizando. • Indicamos el valor de una celda utilizando una expresión, pero no indicamos la secuencia de pasos a realizar para conseguir este valor. En una hoja de cálculo no sabemos cuándo se realizan las asignaciones, por lo tanto, no podemos hacer uso de éstas. Ésta es una diferencia fundamental con los lenguajes imperativos como C o Java, en los cuales se debe hacer una cuidadosa especificación de las asignaciones y en lo que controlar el orden de las llamadas a funciones o métodos es crucial para darle sentido al programa. Ventajas de la programación funcional
• • • Programas más concisos Más fáciles de comprender Sin “core dumps”
Características de Haskell Haskell es un lenguaje de programación funcional puro, con tipos polimórficos estáticos, con evaluación perezosa (lazy), muy diferente a otros lenguajes de programación. El nombre lo toma del matemático Haskell Brooks Curry especializado en lógica matemática. Haskell está basado en el lambda cálculo. La letra griega lambda es el logotipo de Haskell • • • • • Inferencia de tipos. La declaración de tipos es opcional Evaluación perezosa: sólo se calculan los datos si son requeridos Versiones compiladas e interpretadas Todo es una expresión Las funciones se pueden definir en cualquier lugar, utilizarlas como argumento y devolverlas como resultado de una evaluación.
Implementaciones de Haskell Existen diferentes implementaciones de Haskell: GHC, Hugs, nhc98 e Yhc. Para la realización de las prácticas utilizaremos la implementación Hugs ( http://haskell.org/hugs/ ). Resumen de las implementaciones existentes de Haskell:
Mensajes Hugs GHC NHC Yhc Helium +/+ ? ? ++ Tamaño ++ + + ++ Herramientas ++ ++ ? Notas Muy utilizado para aprender Haskell. Compilación rápida. Desarrollo rápido de código. El código generado es muy rápido. Posiblemente la implementación más utilizada. Con posibilidad de profiling, debugging, tracing Todavía en desarrollo. . Creado para la enseñanza.
Para ampliar información sobre las diferentes implementaciones visitar ( http://www.haskell. org/haskellwiki/Implementations ) ¿Qué aprenderemos de Haskell? En este bloque teórico, veremos una pequeña introducción a Haskell, que nos servirá para poder construir pequeñas funciones, tener una idea del modo de programar en Haskell y una pequeña visión sobre sus posibilidades.
¿Qué nos quedará por aprender sobre Haskell? • No veremos ejemplos de conexión de Haskell con otros lenguajes. ¿Cuándo la programación en C es mejor? Por lo general, C es más rápido y dependiendo de la implementación, es posible que utilice mucha menos memoria. Haskell, necesita utilizar mucha más memoria y es más lento que C. En aquellas aplicaciones en las que la velocidad es importante, C puede ser una mejor elección que Haskell, ya que la programación en C tiene mucho más control sobre la máquina real. El lenguaje C es más cercano a la máquina que Haskell. ¿Es posible conectar Haskell con otros lenguajes de programación? HaskellDirect es una herramienta basada en IDL (Interface Description Language) que permite a los programas Haskell trabajar con componentes software. Es posible utilizar funciones C/C++ desde Haskell utilizando Green Card o C->Haskell,
------------------------------------------.5) -.devuelve True -} {.Para comentar una línea --}
Después del bloque comentado. Haskell se sirve de los operadores y las funciones utilizadas en la definición de la función. DEFINICIÓN DE FUNCIONES/ DEFINICIONES LOCALES
{.Para comentar un bloque {. Ord a)=>a->Bool {. etc. Doble. etc. Char.).DECLARACIÓN noNegativo::(Num a. .Integer.
<nombre_funcion>::<declaración_de_tipos>
El nombre de la función empieza por una letra minúscula y después puede continuar con mayúscula o minúsculas.24
SECCIÓN 1.DEFINICIÓN noNegativo x = x >= 0 {-PRUEBAS pru1 = positivo (–2.devuelve False pru2 = positivo 0-. encontramos la cabecera de la función. Para definir los tipos de la función podemos utilizar variables de tipos pertenecientes a alguna clase (Eq. Enum.-} -.Float.-}
Veamos los elementos necesarios para definir una función. será obligatoria la definición de las cabeceras de la funciones. Ord. Num. Fractional. False en otro caso -} -.------------------------------------------.) o con tipos básicos (Int. Se inferirá la cabecera más genérica posible. Lo primero que encontramos es un comentario. Para los ejercicios que se propongan en este curso.
.PROPÓSITO Devuelve True si x es >= 0. Para inferir el tipo de dato. Haskell puede inferir qué tipos de datos necesita la función.devuelve True pru3 = positivo 5-.
el tipo debe ser numérico
Hugs> :info + infixl 6 + (+) :: Num a => a -> a -> a
-.José carPio. José marco.
Hugs> :info == infix 4 == (==) :: Eq a => a -> a -> Bool -.Programación Declarativa.class member
..class member
b) Si nuestra función contiene el operador “>”.class member
c) Si nuestra función contine el operador “+”. gonzalo antonio aranDa.
Ejemplos de tipos de datos utilizados por los operadores: a) Si utilizamos el operador “==” el tipo que utilicemos debe ser comparable (de la clase Eq). el tipo debe ser ordenable (de la clase Ord)
Hugs> :info < infix 4 < (<) :: Ord a => a -> a -> Bool -.
Clasificación de tipos en Haskell:
A continuación veremos algunos ejemplos de definición de tipos de funciones: a) Función identidad:
identidad::a->a identidad x = x
Esta definición indica que la función recibe un tipo a y devuelve un tipo a.
Cannot justify constraints in explicitly typed binding *** Expression: iguales *** Type: a -> a -> a -> Bool *** Given context : () *** Constraints: Eq a
Necesitamos añadir una restricción al tipo “a”
iguales::Eq a=>a->a->a->Bool iguales x y z = x==y && y==z Main> iguales 1 1 1 True :: Bool
c) Función divide
divide::Fractional a => a -> a -> a divide x y = x / y
Tenemos diferentes posibilidades a la hora de definir funciones: • • • • • Utilizando varias ecuaciones (escribiendo cada ecuación en una línea) Guardas (en inglés “guards”. defensas.2) Guardas
factorial n |n==0= 1 |n > 0= n * factorial (n-1) |otherwise = error “valor negativo”
. José marco.\iguales.José carPio..
b) Función iguales:
iguales::a->a->a->Bool iguales x y z = x==y && y==z ERROR file:.Programación Declarativa.hs:2 . barreras.1) Utilizando varias ecuaciones
factorial::Int->Int factorial 0 = 1 factorial n = n * factorial (n-1)
1. “|”) If then else Case En definiciones locales
1. gonzalo antonio aranDa.
/.5) Definiciones locales Es posible definir una función en cualquier punto de otra función:
divisible::Int->Int->Bool divisible x y = resto == 0 where resto = mod x y
Es muy importante que la definición esté algunos espacios a la derecha de la posición en la que empieza a definirse la función. >>= =<< $.3) If then else
factorial n = if (n==0) then 1 else n*factorial (n-1)
1. $!.4) Case
traduce 1 -> 2 -> 3 -> x = case x of “A” “B” “C”
1. `rem`. ** *. >=.`elem`. PRIORIDAD DE OPERADORES En la siguiente tabla se definen las prioridades de los operadores definidos en el módulo Prelude:
Notación infixr infixl infixr infixl infixl infixr infixr infix infixr infixr infixl infixr infixr Prioridad 9 9 8 7 6 5 5 4 3 2 1 1 0 Operador
. /=.28
1. `div`. Haskell mostrará un error. <. <=.
SECCIÓN 2. `quot`. `seq`
. ^^. >.`notElem` && || >>. !! ^. : ++ ==. `mod` +. En otro caso.
es decir.Cannot infer instance
. tendrá mayor prioridad la función:
Hugs> succ 5 * 2 12 :: Integer
El operador que mayor precedencia tiene es la composición de funciones “. El error viene dado por la definición del operador “==”:
Hugs> :info == infix 4 == (==) :: Eq a => a -> a -> Bool -.”. pred 4 ERROR . gonzalo antonio aranDa.2 .class member
El operador se define para dos elementos del mismo tipo.1 -2 :: Integer
Infixr indica que.José carPio.Cannot infer instance *** Instance: Num Bool *** Expression : (1 == 1) == 1
El resultado de evaluar la primera expresión es True.. en caso de igualdad de precedencia se evaluará primero la izquierda:
Hugs> 1 .Programación Declarativa.Ambiguous use of operator “(==)” with “(==)”
Necesitamos explicitar la prioridad con paréntesis:
Hugs> (1 == 1) == 1 ERROR . que pertenecen a la clase Eq (equiparable).
Hugs> (1 == 1) == True True :: Bool
Infixl indica que.
La notación infix indica que el operador es infijo. que se escribe entre los operandos. En el caso de encadenar operadores no se define ninguna prioridad.
Hugs> 1 == 1 == 1 ERROR . en caso de igualdad de precedencia se evaluará primero el operador que está más a la derecha:
Hugs> 2 ^ 1 ^ 2 2 :: Integer
Cuando utilizamos funciones y operadores en la misma expresión.
Hugs> succ . José marco.
implementaremos la siguiente función. primero se evaluará la función:
Hugs> (succ . la evaluación se realiza de izquierda a derecha. No es posible componer una función con un número. y evitando utilizar paréntesis innecesarios
max (x. ponemos de manifiesto que entre un operador (sea cual sea) y una función.
Hugs> succ pred 4 ERROR . que convierte valores de tipo enteros a un tipo numérico general.y)= (x+y)+│x-y│ 2
max x y = fromIntegral (x+y + abs (x+y)) / 2.Cannot infer instance *** Instance: Enum (a -> a) *** Expression : succ pred 4
En caso de encadenamiento de funciones con la misma prioridad. y como la función succ está definida sólo para tipos enumerables. utilizando la función fromIntegral. El resultado es el número 3. al intentar evaluar el sucesor de pred se produce un error. Para poder realizar una composición de funciones son necesarias dos funciones. pred) 4 4 :: Integer
Como ejemplo. Después se intenta realizar la composición del número 3 con la función succ. De esta forma.30
*** Instance: Enum (b -> a) *** Expression : succ .0
Nos quedaría definir cuál es la orden precedencia entre dos funciones. pred 4
Se produce un error debido a que primero se realiza la operación pred 4.
Hugs> succ (pred 4) 4 :: Integer
. Primero se intenta evaluar succ pred.
2. José marco.
SECCIÓN 4. sin embargo en Haskell no se produce un error debido a que el segundo argumento no llega a evaluarse por no ser necesario.4] :: [Integer]
La función f que pasamos como argumento a map debe cumplir una restricción: el tipo de dato que recibe debe ser el mismo de los elementos de la lista.
SECCIÓN 5.. Esta función recibe una función y una lista y aplica la función a cada elemento de la lista:
map:: (a->b)->[a]->[b] map _ [] = [] map f (cab:resto) = f cab : map f resto Main> map succ [1. La evaluación de la expresión anterior provocaría un error en la mayoría de los lenguajes imperativos. CURRIFICACIÓN El proceso de currificación toma nombre de Haskell Brooks Curry cuyos trabajos en lógica matemática sirvieron de base a los lenguajes funcionales. gonzalo antonio aranDa. FUNCIONES DE ORDEN SUPERIOR Las funciones de orden superior son aquellas que reciben una o más funciones como argumentos de entrada y/o devuelven una función como salida.
SECCIÓN 3.3] [2.Programación Declarativa.José carPio. Un ejemplo de función de orden superior es la función map implementada en el módulo Prelude.3.
. Consiste en realizar la llamada a una función utilizando sólo algunos de los parámetros que están más a la izquierda. La expresión 7/0 en Haskell tiene el valor Infinito. EVALUACIÓN PEREZOSA Los lenguajes que utilizan esta técnica sólo evalúan una expresión cuando se necesita:
soloPrimero::a->b->a soloPrimero x _ = x Main> soloPrimero 4 (7/0) 4 :: Integer
El subrayado “_” denota que se espera un parámetro pero que no se necesita nombrarlo ya que no se va a utilizar en el cuerpo de la función.
El resultado de la composición de las dos funciones es de tipo Bool. debe ser el de entrada de la función f.g.”:
Main> :info . Veamos un ejemplo:
Main> ((==True). que es el que recibe la función (==True).4. (.3] [3. podemos comprobar que el segundo argumento es una función (c->a). COMPOSICIÓN DE FUNCIONES
f. que el primer argumento es una función (a->b).2.32
suma::Int->Int->Int->Int suma x y z = x + y + z
Podemos hacer las siguientes llamadas: a) suma 1 -> devuelve una función que recibe dos enteros y devuelve otro.”. b) suma 1 2 -> devuelve una función que recibe un entero y devuelve otro.(<0)) 5 False :: Bool
La función (<0) devuelve un tipo Bool. infixr 9 .
. La restricción más importante es que si queremos hacer la composición f. Si observamos la cabecera del operador “. éstas deben cumplir una serie de restricciones. el tipo de salida de la función g.) :: (a -> b) -> (c -> a) -> c -> b
Para poder componer dos funciones. Se trata del operador “.5] :: [Int]
SECCIÓN 6. c) suma 1 2 3 -> devuelve el entero 6 Podemos utilizar la función currificada como argumento de otra función de orden superior:
Main> map (suma 1 1) [1. que el valor al que se quiere aplicar la composición es de tipo c y que el valor de salida es de tipo c.g (x) = f(g(x))
Haskell dispone de un operador para componer funciones.
Composición de funciones 7. Listas 8. Evaluación perezosa 4.PROGRAMACIÓN FUNCIONAL CON HASKELL
0. Patrones 9. Definición de funciones 2. Funciones de orden superior 5. Prioridad de operadores 3. Recursividad
. Introducción 1. Tuplas 10. Currificación 6.
José carPio..Programación Declarativa.20] c) [15.
SECCIÓN 7. las restricciones filtran algunos elementos de los generados y la transformación utiliza los elementos seleccionados para generar una lista resultado. Funciones más usuales sobre listas Cabecera de la función
(:) :: a -> [a] -> [a] (++) :: [a] -> [a] -> [a] (!!) :: [a] -> Int -> a null :: [a] -> Bool head :: [a] -> a length :: [a] -> Int tail :: [a] -> [a]
Añade un elemento al principio de la lista Concatenar dos listas Devuelve el elemento n-ésimo Devuelve True si lista == [] Devuelve la longitud de una lista Devuelve el primer elemento Todos menos el primero Toma los primeros n elementos Elimina los n primeros elementos Invierte el orden de los elementos Crea una lista de pares zip “abc” “123” >>
take :: Int -> [a] -> [a] drop :: Int -> [a] -> [a] reverse :: [a] -> [a] zip :: [a] -> [b] -> [(a. (even es una función definida en el módulo Prelude standard de Haskell). LISTAS Haskell proporciona un mecanismo para definir fácilmente listas:
a) [1.ee/~varmo/MFP2004/PreludeTour. even x.(20-5)] d)[‘q’.. José marco.[1. True) es la transformación. El generador produce elementos de una o varias listas.20] es el generador. cs. es par y menor que 15.True) | x <. x <.[b]) sum :: Num a => [a] -> a product :: Num a => [a] -> a
A partir de una lista de tuplas genera dos listas Suma los elementos de una lista Multiplica los elementos de una lista
Consulte información sobre las funciones definidas para listas en el módulo Prelude..
[ (x.10] b) [15.True) donde x está entre 1 y 20. las restricciones son even x y x < 15.ut. 2) restriccines(puede que no haya ninguna) y 3) transformación.http://www. y (x.. 20]. gonzalo antonio aranDa.b)] unzip :: [(a.’z’] e)[14. x < 15] |______________| |______________| |____________| Transformación Generador Restricciones
En este ejemplo. Esta expresión genera una lista de pares (x..pdf
..2]
Notación extendida de listas La definición de una lista utilizando esta notación consta de tres partes: 1) generador.[1 ...b)] -> ([a].
f empareja con cualquier valor del tipo esperado (por la cabecera de la función map.
Hugs> :info : infixr 5 : (:) :: a -> [a] -> [a]
-.\eliminarTres. Por ejemplo:
eliminarTres ([x.z] ++ resto) = resto
Esta definición de la función eliminarTres provoca un error:
ERROR file:. PATRONES Veamos una implementación posible de la función map:
map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (cab:resto) = f cab : map f resto
(cab:resto) empareja con una lista (el operador “:” devuelve una lista) cuyo primer elemento
[] es el patrón que empareja con una lista vacía.
_ empareja con cualquier valor del tipo esperado.
es “cab” y el resto es “resto”.2. sin embargo. True. una forma de dividir expresiones en sub-expresiones.36
SECCIÓN 8. f debe ser una función) y f se instancia a esa función.hs:2 . etc). no se hace una asignación a la variable “_”: sencillamente se ignora el valor. de modo que no es posible hacer emparejamientos con todas las construcciones del lenguaje que nos parezcan posibles sino sólo con aquellas que nos permita Haskell. False.Syntax error in input (unexpected symbol “++”)
El problema surge porque el operador “++” no está permitido en los patrones. Un constructor tiene la forma: data Bool = True | False
data [a] = [] | a:[a] Main> :info :
. ¿Qué podemos utilizar como patrón? Existe un conjunto dado de patrones de emparejamiento. En los patrones sólo se permiten constructores y constantes (1.y. al mismo tiempo. Luego el emparejamiento de patrones es una forma de asignar valores a variables y.
Escribiremos nombre_variable@<patrón>.. cláusulas let y where. La función eliminarTres puede implementarse así:
Emliminar::[a]->[a] EliminarTres (_:_:_:resto) = resto
Es importante el tipo del constructor.
. Excepción Hay una excepción a la regla del uso de los constructores en patrones. el valor tiene que ser mayor o igual que k. puede ser interesante tener acceso a la expresión completa. una función que elimina los caracteres en blanco que se encuentran al principio de una cadena de caracteres:
quitaBlancosPrinc::String->String -. [] y “:” son constructores para listas. una versión del factorial utilizando un alias de patrón:
factorial::Integral a => a->a factorial 0 = 1 factorial m@(n+1) = m * factorial n
Utilizaremos los patrones en ecuaciones. En estos casos. Se trata del patrón
(n+k). utilizaremos los alias de patrones. Para ello.
Main> predecesor 0 {throw (PatternMatchFail (_nprint 0 (predecesor 0) []))} :: Integer
Alias de patrones Los patrones se utilizan en ocasiones para dividir expresiones. Además. expresiones case y listas.equivalente a quitaBlancosPrinc::[Char]->[Char] quitaBlancosPrinc cadena@(cab:resto) | cab == = quitaBlancosPrinc resto | otherwise = cadena
o este otro. José marco.data constructor
Cuando solicitamos información sobre un operador Haskell indica si se trata de un constructor. pero no el número.
infixr 5 : (:) :: a -> [a] -> [a]
-. predecesor::Int->Int predecesor (n+1) = n
No podemos utilizar cualquier valor para que empareje con (n+k). En el ejemplo anterior se utiliza el operador “:” como patrón tres veces.Programación Declarativa. Sólo podemos utilizar enteros (Int ó Integer).José carPio. Por ejemplo. gonzalo antonio aranDa.
primero (1.7.3) *** Type : (c.2) (1.3) ERROR . [3.z) = x Main> primero (1.’a’)) ((1.d).y) = x b) primero2 (x.Char))
-> a) Num d) =>
Algunos ejemplos de funciones con tuplas:
a) primero (x.2).[3.2). Num b.1.2).Type error in application *** Expression : Main.’a’)) :: (Num a.2) (‘a’.[Char]) Main> :t ((+).a -> a Main> :t ((1.1.2) :: (Num a. (*))
Veamos de qué tipo son las tuplas anteriores:
Main> :t (1. Por ejemplo:
a) b) c) d) (1.”Hola”) ((1.3) *** Term : (1.a.”Hola”) :: Num a => (Char.[b].2.2.a) Main> :t (‘a’.”Hola”) (‘a’.(0. Num b.y. Num c.2. Edad.4]. Num b) => (b.[3.(0.7.(*)) :: (Num a.38
SECCIÓN 9.4].d. Telefono) type Persona = String type Edad = Int type Telefono = String
.(*)) ((+).e) *** Does not match : (a.3) 1 :: Integer
Definición de tipos con tuplas Veamos el siguiente ejemplo:
type Entrada = (Persona. (0.4].1. TUPLAS Podemos agrupar expresiones de distinto tipo en una tupla.b) Main> primero2 (1.b. 7.2. ((c. Num c) => (c -> c -> c.(a.’a’)) ((+).
20. 21. 20. “635111111”)] “Pedro” [“636000000”] :: [Main.Telefono]
. “636000000”). persona == per] Main> encontrar [(“Pedro”.Telefono] Main> encontrar [(“Pedro”. 20. edad. “635444444”)] “Pedro” [“636000000”. “635111111”). “636000000”). (“Pedro”. 21. telef) <. 24.lista.”635444444”] :: [Main.”607222222”).”607222222”).
type Listin = [Entrada] encontrar::Listin -> Persona -> [Telefono] encontrar lista persona = [telef| (per. gonzalo antonio aranDa. 24.Programación Declarativa.. (“Juan”.José carPio. José marco. (“Alberto”. (“Juan”. (“Alberto”.
Evaluación perezosa 4. Funciones de orden superior 5. Introducción 1. Patrones 9. Definición de funciones 2.PROGRAMACIÓN FUNCIONAL CON HASKELL
0. Prioridad de operadores 3. Recursividad
. Composición de funciones 7. Listas 8. Tuplas 10. Currificación 6.
. el valor tiene que ser mayor que el primero. En Haskel:
natural 1 = True natural n = natural (n-1) Main> natural 5 True :: Bool
¡¡El principio de inducción funciona!! -> Vamos a utilizarlo. Una función recursiva es aquella que en su definición contiene una llamada a sí misma. gonzalo antonio aranDa.Programación Declarativa. n es natural si n-1 es natural. No hemos tenido en cuenta que. Ord a)=> a -> Bool natural 1 = True natural n | n > 1 = natural (n-1) | otherwise = False Main> natural (-1) False :: Bool
. Podemos utilizar el principio de inducción para definir los números naturales: El número 1 es natural. es decir. pero .. RECURSIVIDAD En Haskell no tenemos posibilidad de definir bucles. si P es cierta para (n-1) entonces lo será para n.5”. Una nueva versión:
natural::(Num a. José marco. La forma de “iterar” es utilizando la recursividad.
Main> natural (-3) ¡¡¡No termina!!!
Igual sucede con el número “3.
SECCIÓN 10. si es cierta para el valor anterior a n.José carPio. Este principio es ampliamente utilizado en matemáticas para demostrar que se cumple una propiedad para cualquier valor del ámbito que se esté tratando. Principio de inducción: (1) La afirmación P es cierta para un valor inicial n0 (“caso base”) (2) P será cierta para un valor n > n0.. La recursividad se apoya en el principio de inducción.
¿Cómo construimos el valor n y el n-1 con listas? Utilizaremos el patrón “cab:resto” que separa el primer elemento del resto.44
Main> natural 3. Nos centraremos en definir bien el caso base (el primer elemento que cumple la propiedad) y la relación de un valor n con el anterior. Si numElementos resto entonces numElementos (cab:resto) Si numElementos (resto) se cumple. ¿Cuál es el primer caso cierto conocido para listas? En este caso (y en la mayoría de los problemas de listas) el primer caso conocido corresponde con la lista vacía.
numElementos [] = 0
Esta ecuación cumple la propiedad: es cierto que una lista vacía tiene cero elementos. Ejemplo de recursividad con listas Trasladaremos la misma idea a la resolución de un problema recursivo con listas. Por el principio de inducción sabemos que: Si numElementos resto es cierto (devuelve el valor correcto) numElementos (cab:resto) también lo será. Ahora no tenemos un número n y un número anterior n-1 como sucedía con los naturales. El ejemplo de los números naturales dice que. se cumplirá para n. Veamos qué pasa con n. Es la lista más pequeña. y el elemento n-1 será la lista con un elemento menos (el contenido de la variable resto). Definiremos recursivamente una función que devuelva el número de elementos de una lista.
. si se cumple la propiedad para n-1.5 False :: Bool
Recomendación importante: No seguiremos mentalmente la secuencia de llamadas recursivas para resolver los problemas. Para este problema. el primer caso no es el 1. Nuestro elemento n será la lista completa. devolverá el número de elementos que contiene el resto de la lista (todos menos el primero). al igual que el 0 es el natural más pequeño.
cs. utilizando asociación por la izquierda. devuelve el elemento inicial. para saber cuántos tiene la lista completa bastará con sumar uno. Cuando la lista de entrada está vacía. José marco. Dediquemos algún tiempo a entender qué hace la función. numElementos (cab:resto) = 1+ |_____________________|
Queremos conocer este valor
numElementos resto |_________________|
Supondremos que sabemos cuánto vale
Veamos otro ejemplo algo más complicado: Deseamos implementar la función foldl definida en Haskell Prelude.. Para esto podemos realizar algún ejemplo más:
Hugs> foldl (^) 1 [] 1 :: Integer Hugs> foldl (^) 1 [2] 1 :: Integer (1^2) Hugs> foldl (^) 1 [2.pdf
Descripción: Une los elementos de una lista utilizando un operador binario y un elemento inicial. para obtener la salida total? Ésta será la pregunta que haremos siempre para resolver un problema recursivo.
¿Cuánto vale numElementos (cab:resto)? Para saber cuánto vale.ut.José carPio. gonzalo antonio aranDa.ee/~varmo/MFP2004/PreludeTour. Podemos encontrar un ejemplo en el documento “A tour of the Haskell Prelude” http://www. En este caso la transformación es sencilla. utilizaremos el valor devuelto por numElementos resto
numElementos (cab:resto) = |_____________________| Queremos conocer este valor numElementos resto |_________________| Supondremos que sabemos cuánto vale
¿Qué cambio tengo que hacer en la salida parcial.3] 1 :: Integer (1^2)^3
. Si sabemos cuántos elementos tiene una lista a la que le falta un elemento. Esta función se define para listas no vacías.Programación Declarativa.
4] -> (((1^2)^3)^4)
con un elemento menos:
foldl (^) 1 [3. Para ello lo mejor es escribir un ejemplo:
foldl (^) 1 [2. Ahora. Donde escribíamos “el”. sin tener en cuenta lo que escribamos después.
foldl f el [] = el
2) Caso recursivo. Debe ser cierto por sí sólo. vemos que la diferencia está en que la salida parcial contiene un “1” y la total contiene “1^2”.4] -> ((1^3)^4)
Ahora nos preguntaremos: ¿Qué transformación tengo que hacer en el resultado de la función que tiene un elemento menos para que se convierta en el resultado de la lista completa? Buscamos las diferencias entre la salida parcial y la total. Suele ser el caso más sencillo. separar la cabeza del resto de la lista utilizando el operador “:“.
(((1^2)^3)^4) -> Salida total (( 1 ^3)^4) -> Salida parcial
Observando las dos salidas.3. Parece que la diferencia sólo está en el segundo elemento de la función. Empezaremos planteando el caso recursivo de la siguiente forma:
foldl f el (cab:resto) foldl f el resto =
Para problemas de listas. De una forma más genérica: “f el cab” Completaremos la llamada recursiva con el cambio. como el caso de la función numElem [] cuyo resultado es 0. utilizaremos en la mayoría de los casos la misma técnica. El resto es igual. escribiremos “f el cab”. siendo 2 el primer elemento de la lista. Suele estar descrito en la definición de la función o es muy evidente. nos centraremos en averiguar qué devuelve la función llamada con una lista de un elemento menos como parámetro. El cambio que necesita la llamada a la función parcial es cambiar el elemento “el” por “el^cab”. Empecemos con la implementación: 1) Empezaremos por el caso base.46
Ahora que tenemos algo más claro que hace la función.
gonzalo antonio aranDa.Programación Declarativa. ¿cómo se llega a la solución? Respuesta: Preguntando siempre al problema con un elemento menos.3..
. ¿Se han realizado los cambios de forma correcta? En general.
foldl f el (cab:resto) foldl f el resto |___| cambiaremos el por f el cab foldl f el (cab:resto) foldl f (f el cab) resto
Finalmente la función quedará como sigue: foldl foldl foldl foldl :: (a -> b -> a) -> a -> [b] -> a f el [] = el f el (cab:resto) = f (f el cab) resto
Main> foldl2 (^) 1 [2. podemos decir que: “Si las respuestas a estas preguntas son afirmativas la función recursiva funcionará”. José marco.4] 1 :: Integer Main> foldl (++) “com” [“po”. “ner”] “componer” :: [Char]
¿Cómo comprobar si una función recursiva es correcta? Debo responder a las siguientes preguntas: 1) ¿El caso base es cierto? 2) ¿El caso recursivo tiende al caso base? 3) ¿Están contemplados todos los casos una única vez? 4) ¿A partir de la salida recursiva (n-1)puedo construir la salida general (n)? Si/No. Pero.José carPio. Si.
1+0 <--------------. 3) Si alguno de los casos no estuviese contemplado.0 ¿Qué sucede si alguna de las respuestas es negativa? 1) Si el caso base no fuese cierto. el resultado no será correcto. 2) Si el caso recursivo no tendiese al caso base. la secuencia de preguntas se romperá y no se alcanzará al caso base.1+1+0 <------------.2.
. 4) Si a partir de la llamada recursiva no puedo construir la solución general. Si no construimos bien la solución general a partir de la solución parcial (n-1). se construirá la solución a partir de una premisa errónea. no será posible encontrar la solución.3] --> num_elem [2. num_elem [1. A partir de la solución que aporta el caso base se construyen el resto de soluciones parciales hasta llegar a la primera de las preguntas. no podría asegurar que el problema termine.48
Lo que sucede es que se encadenan una serie de preguntas hasta que se alcanza el caso base.3] --> num_elem [3] --> num_elem [] │ │ 1+1+1+0 <-----------.
2 Árboles 2. Problemas de estados
.PROGRAMACIÓN LÓGICA CON PROLOG
0.1 Listas 2. Tipos de datos 2. Control de la ejecución 4.3 Grafos 3. Unificación 2. Introducción 1.
llueve.Programación Declarativa. José marco. realizaremos consultas.
SECCIÓN 0. para obtener algún resultado:
.” Escribimos la regla Si llueve -> se regaran las plantas de esta forma:
se_riegan_las_plantas :. llueve. Escribiremos reglas para indicar que si se produce un evento (antecedente) entonces se producirá una consecuencia (consecuente).
Para afirmar que llueve. Todas las cláusulas terminan con un punto “. Un “programa lógico” se compone de dos elementos: “Programa lógico” = Base de conocimiento + Consultas Sintaxis Prolog: Escribiremos las reglas empezando por el consecuente. Para afirmar que llueve necesitamos un hecho.
Primer programa Prolog utilizando sólo proposiciones:
% Mi primer programa Prolog se_riegan_las_plantas :. Con cláusulas crearemos una base de conocimiento (una representación de lo que conocemos).. no se indica que esté lloviendo. INTRODUCCIÓN Lógica Proposicional: Utiliza afirmaciones simples (proposiciones).José carPio. Debemos realizar consultas. gonzalo antonio aranDa. escribiremos el siguiente hecho: llueve.
Si llueve -> se regarán las plantas |___________| |_________________| Antecedente Consecuente |___________________________________| REGLA
Con la regla anterior. Una vez definida la base de conocimiento.llueve.
llueve |_________________| HECHO
Una cláusula es una regla o un hecho.
se_riegan_las_plantas. Prolog indica el tiempo de compilación y los bytes compilados. Yes
En la línea 1 cargamos el programa “lluvia.consult(‘d:/lluvia. el mensaje “Yes” puede sustituirse por la solución de la consulta. Reescribiremos la regla anterior utilizando el predicado se_riegan(Plantas). La siguiente pregunta es ¿se_riegan_las_plantas?. 672 bytes Yes 2 ?. se riegan los tomates y las lechugas y las fresas.52
1 ?. Yes 3 ?. Lógica de Primer Orden o Cálculo de Predicados de Primer Orden: Extiende la lógica proposicional empleando variables. Imaginemos que deseamos expresar lo siguiente: Si llueve entonces. Utilizando lógica proposicional escribiríamos lo siguiente:
Si llueve -> se_riegan_los_tomates ^ se_riegan_las_lechugas ^ se_riegan las_ fresas.llueve. Ante cualquier consulta.
Si llueve -> se_riegan(tomates) ^ se_riegan(lechugas) ^ se_riegan(fresas)
Esta nueva definición utilizando predicados permitiría preguntar ¿Qué se riega? y Prolog respondería. La respuesta es “Yes”.pl’). La respuesta es “Yes”. Dependiendo de la versión de Prolog. Prolog responde “Yes” o “No”. predicados y cuantificadores de variables. esta regla escrita de esta forma no se puede implementar directamente en Prolog ya que no es una Cláusula de Horn.
.pl” utilizando el procedimiento consult.
Para facilitar la representación del conocimiento y la asociación de conceptos se utilizan los predicados. Sin embargo.00 sec. tomates. Este predicado representa que una determinada planta se riega. En la línea 3 preguntamos si llueve. salvo error. lechugas y fresas. % d:/compiled 0.
no se podría garantizar que el algoritmo de resolución terminara. a → b˅c No es C. se_riegan(fresas):. a˄b → c C.
Cláusulas de Horn.José carPio. a → b˄c No es C. llueve.
Si llueve -> se_riegan(tomates) |_____| |________________| Término Término
Para resolver si una determinada consulta (fórmula) es cierta o falsa. gonzalo antonio aranDa. De Horn => No existe equivalencia Nuestro programa sobre la lluvia y el riego utilizando cláusulas de Horn quedaría así:
% Lluvia. de Horn => Equivalencia
3. riego y vegetales usando predicados se_riegan(tomates):.llueve. En algunos casos podemos encontrar una equivalencia para que una cláusula se escriba como cláusula de Horn.
. Este algoritmo de resolución es decidible (siempre termina con una solución válida) si las cláusulas son todas Cláusulas de Horn. de Horn
2.llueve. José marco. 1. se utiliza un algoritmo de resolución. de Horn=> Equivalencia
a → c b → c
4. En otro caso. a˅b → c No es C.. se_riegan(lechugas):.Programación Declarativa.
Podemos preguntar entonces: ¿Qué se riega? Sintaxis Prolog: Escribiremos las variables empezando por mayúscula.llueve. Una cláusula de Horn es aquella que está formada por una conjunción de cero o más términos en el antecedente y un único término en el consecuente.
Hipótesis del mundo cerrado: Lo no definido es falso.
3 ?No se_riegan(manzanas). Vegetales = tomates . se llega al acuerdo de responder como falso a todo lo no definido. Vegetales = fresas 3 ?
Para obtener todas las respuestas.
.” después de cada respuesta. escribimos “. Si hacemos alguna pregunta sobre algún valor que no existe Prolog responderá “No”.se_riegan(Vegetales). Vegetales = lechugas . Con el fin de simplificar la definición de la base de conocimiento.54
Unificación 2. Control de la ejecución 4.3 Grafos 3.1 Listas 2. Introducción 1. Problemas de estados
. Tipos de datos 2.PROGRAMACIÓN LÓGICA CON PROLOG
0.2 Árboles 2.
gonzalo antonio aranDa.Persona = manuel.X = 1. Una variable en Prolog puede instanciarse con cualquier tipo de dato (árbol. Si la variable Lista está libre (no se le asignó un valor previamente). Persona = manuel Yes ?.3] ? Lista = manuel Lista = manuel Yes
En el último de los ejemplos anteriores. Podemos asignar a una variable llamada “Lista” (que debería contener una lista) cualquier valor. Ejemplos de variables:
1) 2) 3) 4) 5) Persona Lista X Arbol _
?. Variables Libres e Instanciadas Diremos que una variable está libre si aún no se asignó un valor a través de una unificación.Lista = [1. observamos que Prolog no hace ningún tipo de comprobación a la hora de asignar valores a las variables.José carPio.3] Lista = [1. Diremos que una variable está instanciada si ya se le asignó un valor a través de una unificación.Programación Declarativa.).
. No es necesario declarar una variable para poder utilizarla.2. José marco. grafo. Una variable.2. etc. una vez que se instancia. lista.
SECCIÓN 0. INTRODUCCIÓN (CONTINUACIÓN) Variables Escribiremos las variables empezando por mayúscula. Esa variable no podrá modificar su valor. No ?. será posible realizar la siguiente unificación Lista=manuel y Prolog responderá que es cierto si Lista se instancia al valor “manuel”. no cambia su valor. X = 2..
etc.X=1. sin embargo no existe conexión entre ellas.
Código 2: Segunda versión del predicado suma Esta segunda versión de la implementación del predicado suma.X.Z):. Esto permite que. Esta es una diferencia importante de Prolog respecto a lenguajes de programación.
Código 1: Primera versión del predicado suma En el ejemplo anterior la variable X y la variable Z aparecen en las dos cláusulas. suma(N. la variable puede ser referenciada desde cualquier punto de la función. podamos saber si es correcta o no. funciona exactamente igual que la anterior. independientemente de lo que se escriba a continuación. Decimos que el ámbito de la variable es la función en la que está definida.Z):.Z is X + X. Véase el siguiente ejemplo:
suma(X.X \= Y.58
?. suma(X.N.R is N + N..si las variables contienen listas. Más allá de esa cláusula.X \= Y. Podemos cambiar el nombre de las variable y el programa funcionará de la misma forma. Z is X + Y. Variable anónima (“_” )
Por legibilidad. Z is Y + Z.Y.R):. X=2. Ámbito de una variable Es común en otros lenguajes de programación que si una variable se define dentro de una función. debemos asignar a las variables nombres representativos de lo que contendrán: si las variables contienen números podemos llamarlas X. En Prolog el ámbito de una variable está restringido a una cláusula. Y. Esto nos ayudará a entender más fácilmente los programas.Y. ListaR.
suma(X.Z):. las llamaremos Lista. observando únicamente una cláusula. etc. la variable no puede ser referenciada. Z.
no es necesario darle un nombre.se_riega(Planta). José marco.
se_riega(_):. que cuando llueve se riegan todas las plantas puedo escribir:
se_riegan(Planta):. pero no nos importa cuál sea ese valor.Programación Declarativa.pl:1): Singleton variables: [Planta]
Este mensaje indica que una variable aparece una única vez en una cláusula.
Cuando queramos indicar que un argumento tenga un valor. utilizaremos la variable anónima.pl:1): Singleton variables: [Plamta. es muy posible que no hagamos ningún caso al aviso. Este mensaje es sólo un aviso con lo que el programa se podrá ejecutar. Realmente quiero indicar que haya una variable pero no utilizaré su valor.llueve. por tanto.
Warning (d:/llueve4. en cuyo caso escribiremos
se_riegan(_):-llueve..llueve. gonzalo antonio aranDa. Prolog mostrará el siguiente mensaje:
Warning (d:/llueve4.
Al ejecutar el programa anterior. La variable anónima tiene un sentido de “todo” o “cualquier valor”. Por ejemplo: Si quiero indicar. Esto puede suceder por dos razones: 1) Que sea correcto.
Provocará el siguiente aviso. Planta]
. Si nos acostumbramos a verlos. debemos corregirlos.
2) Que haya escrito mal el nombre de una variable.José carPio. que se representa con el carácter “_”. cuando nos equivoquemos realmente al escribir el nombre de una variable. sin embargo. en cuyo caso debo corregir el error:
crece(Plamta):. lo que significa que no existe ninguna restricción sobre el valor que puede tomar la variable y.
X = mujer(maria). 2) Si tienen variables.X=1. “<”. X=2.X=1.
. Antes de unificar una variable a un valor diremos que la variable está “libre” o “sin instanciar”. No
Operadores Los operadores más utilizados en Prolog son “=”. No ?.(1+2) = 1+2.X=2+X. Tras unificar un valor a una variable. unifican si son idénticos. unifican si es posible encontrar una sustitución de las variables de forma que lleguen a ser idénticos.60
SECCIÓN 1.X = 2 + 3. Ejemplos:
?. la variable deja de estar libre y diremos que la variable está “instanciada”. Yes ? 1+1 = +(1. X = mujer(maria) Yes ?. UNIFICACIÓN Diremos que dos términos unifican: 1) Si no tienen variables. “=<”. X=+** Yes ?. Yes ? (1+1)+1 = 1+(1+1). X=2+3 Yes ?. X=Y. “=:=”. “=“ unificador: El operador de unificación no evalúa operaciones aritméticas. X=1 Yes ?. “is”. “==”.1). “>=”.
José carPio.X is 1+1. ERROR: is/2: Arguments are not sufficiently instantiate
.2 + 3 is X. No.X is 2 + 3.X = 1+1. X = 5.2 == X.
?.X is 2 + 3.
?. ?.Programación Declarativa. ”is” evaluador de expresiones aritméticas:
Evalúa a la derecha y unifica con la izquierda. Yes
”==” comparador de identidad: Es verdadero si los valores comparados son exactamente el mismo valor. X = 2
“=:=” evaluador y comparador de expresiones aritméticas: Evalúa a derecha e izquierda y es cierto si el resultado de las evaluaciones es idéntico. todas las variables que estén a la derecha del operador tienen que estar instanciadas.2 == 2.
?. X = 1+1. Para poder realizar una operación aritmética. No ?. José marco. Yes
?. X = 2 + 3.
?. En otro caso se producirá un error..2 == 1+1. X=5 Yes ?. No. gonzalo antonio aranDa. ?. Yes.2 =:= 1+1.
X = 5. mod. 6 = X + 1. @=<. -. X=0. 6 is X + 1.6 is X + 1. =<. (Ejemplo: X is 2/2/2. =:=. \==. No ?.yfx: asociativo por la izquierda. =@=.62
?. X=5 Yes ?. /. .5). @>=. \ * ^
500 500 400 200 200
yfx fx yfx xfx xfy
*. ERROR: is/2: Arguments are not sufficiently instantiate
Precedencia 1200 1000 900 Notación xfx xfx fy Operador :.
. X = 5. @<. (Ejemplo: X is 2^1^2. >. ==. -. \=. X=2). =\=.Las operaciones cuyo operador tiene un número de precedencia menor se realizarán antes. Para obtener un listado completo de operadores ejecutar apropos(operators). >=. @<. @>. =. ?.. =. xor +. \+ <.xfy: asociativo por la derecha. is +. . rem
.X is 5..
Control de la ejecución 4.1 Listas 2.3 Grafos 3.2 Árboles 2. Problemas de estados
. Introducción 1. Unificación 2. Tipos de datos 2.PROGRAMACIÓN LÓGICA CON PROLOG
2.[Lista] = [1.. Un error frecuente es el siguiente:
?. etc. constantes o estructuras) en general.2.b.2.).3]] [[1. Notaremos la lista vacía (“[]”) con un corchete de apertura y otro de cierre.pedro]
Nota: Si queremos que una variable se instancie a una lista.3. En todo caso. gonzalo antonio aranDa. 2.3.2. En esta sección veremos cómo representar y utilizar algunos importantes tipos de datos con Prolog. Es posible anidar listas.c. Éstas son algunas características de las listas en Prolog: Las listas contienen términos (variables.3.3.4]
Recuerde que. con lo que no se restringe a que contengan valores de uno de esos tipos en concreto o con una notación uniforme (sólo números.4] Lista=[1.Programación Declarativa.6]] [se_riegan(Plantas).4].
. sólo variables. una variable libre se puede instanciar con cualquier tipo de dato.b.
SECCIÓN 1. José marco. TIPOS DE DATOS Aunque Prolog no es un lenguaje tipado.[5.4] [] [a. Ejemplos de listas:
[1.d] [1.Lista = [1.4].[3.X. sí que existen determinados valores con peculiaridades de notación y predicados asociados que los diferencian del resto de valores convirtiéndolos en una especie de tipo de datos. necesitaremos delimitar grupos de valores que actúen como tipos de datos diferenciados en nuestros programas.1 Listas Notaremos las listas entre corchetes.2. lo haremos de la siguiente forma:
?.4] No
Con [Lista] hacemos referencia a una lista que contiene un único término.2].[3.’a’. separando los elementos por comas.José carPio.[1.
2. Cuando tratamos listas. para separar el primer elemento de una lista del resto. R=[]. El caso base no debe depender de otras reglas que hagan referencia al predicado definido.[Cabeza|Resto] = [1] Cabeza=1 Resto=[] 3 ?.66
Operador “|” Utilizaremos el operador “|” (barra vertical).
.0). siendo el resto una lista vacía “[]”. En el segundo de los ejemplos anteriores [C|R]=[1].3]] Cabeza=[1.2. Este operador es muy útil para construir predicados recursivos y lo utilizaremos frecuentemente.3] Resto = []
Nota: Hemos de tener en cuenta que el resto siempre es una lista.3] 2 ?.C2|Resto] = [1.2.3] Cabeza=1 Resto=[2.
% num_elem(+List. Suele ser el más sencillo. -Int) num_elem([]. Ejemplos:
1 ?.[Cabeza|Resto] = [1.2. Implementaremos el predicado en varios pasos: Paso 1) Caso base. Veamos ahora algunos ejemplos de predicados que trabajan con listas: Implementaremos el predicado num_elem/2 que cuenta el número de elementos de una lista. es posible la unificación.[C1.3] C1=1 C2=2 Resto=[3] 4 ?. el caso base suele hacer referencia a la lista vacía.[_|_]= [] No 5 ? [Cabeza|Resto] = [[1.
cierto(N) :. devolverá el número de elementos del resto. num_elem([Cabeza|Resto]. un elemento ya que el resto puede estar vacío pero la cabeza debe unificar forzosamente con un término. comprobamos que todos los casos están contemplados una única vez.
Paso 4) Por último. tenemos un caso para listas vacías y un caso genérico para una lista de 1 o más elementos. En este ejemplo. para obtener el total. obtenemos el resultado total. ):-
Si la llamada recursiva funciona. gonzalo antonio aranDa. Paso 3 ) A partir del caso recursivo (resultado parcial). NumLista ):num_elem(Resto. NumLista ):num_elem(Resto.
num_elem( [Cabeza|Resto]. Hemos contemplado todos los tamaños de listas posibles. al menos. En este caso. En lugar de una variable Lista. que separará el primero de la lista del resto. Construimos el caso recursivo con un tamaño del problema algo menor. NumResto).
num_elem([Cabeza|Resto].0).
Paso 2) Planteamos el caso recursivo. Recuerde el principio de inducción: Si es cierto para n0 y es cierto para n-1 con n>n0. El programa quedaría así:
% num_elem(+List.José carPio. Tendremos en cuenta que al escribir [Cabeza|Resto] obligamos a que la lista tenga.. num_elem(Resto. numLista is NumResto + 1. -Int) num_elem([]. cierto(Nmenos1). José marco.Programación Declarativa. numLista is NumResto + 1. Num_resto) . basta con sumar 1 a NumResto.Nmenos1 is N-1. escribimos [Cabeza|Resto]. entonces es cierto para cualquier n>n0 Ejemplo en Prolog. NumResto).
. Usualmente con el resto.
encontramos información sobre la notación utilizada en la descripción de los predicados: ? indica que el argumento puede ser de entrada o de salida. aniadir_final(+Elem.help(4-1). Obtendremos el siguiente resultado:
length(?List. . -ListaR) que es cierto cuando ListaR unifica con una lista que contiene los mismos elementos que la lista Lista más el elemento Elem añadido al final. elemento_enesimo(+Pos.68
Ejercicios: Implementar los siguientes predicados utilizando recursividad:
reverse(+List. Predicados predefinidos
que es cierto cuando Elem unifica con el ele-
Existen predicados predefinidos en Prolog para listas que podemos utilizar en nuestros programas. Can be used to create a list holding only variables.
Nota: En la sección 4. +Lista. a nuestro predicado num_elem/2 implementado anteriormente. +Lista. -ListR) que es cierto cuando ListR unifica con una lista que contiene los mismos elementos que List pero en orden inverso. + indica que el argumento es usualmente de entrada. Si hacemos la siguiente consulta help(length). -Elem)
mento que ocupa la posición Pos dentro de Lista. ?Int) True if Int represents the number of elements of list List.
Otros predicados predefinidos para listas son:
append/3 member/2 reverse/2 nth0/3 nth1/3
.indica que el argumento es usualmente de salida.1 del manual de SWI-Prolog ( ?.
3]. y esperamos que Prolog encuentre una posible lista de longitud 3. es decir introduciendo unos valores en las entradas._ G337 identifican variables). Sin embargo.length([1. Esta forma de uso de los predicados no se encuentra en los lenguajes imperativos. 3).José carPio.Programación Declarativa. _G334. de ser utilizados de forma reversible. Longitud=3 7 ? length(Lista. Podemos utilizarlos de forma similar a una función. Bibliografía Ayuda de SWI-Prolog
._G334.2. introduciendo la salida esperando que Prolog encuentre la/s entrada/s necesarias para hacer cierto el predicado.. también podemos utilizarlos al revés. en este caso la longitud de la lista. Indicamos cual es la salida. Debemos hacer uso de la reversibilidad de los predicados. unifiquen con el resultado. gonzalo antonio aranDa. por ejemplo). Ejercicios: 1) Comprobar el funcionamiento de los predicados predefinidos en Prolog para listas. 3 ) Revisar los exámenes de años anteriores y realizar los problemas de listas que se encuentren. es decir. La respuesta de Prolog en Lista=[_G331. Longitud). Veamos un ejemplo:
Predicados reversibles Una de las características que diferencia a Prolog de otros lenguajes de programación es la capacidad que tienen los predicados (a diferencia de una función definida en C._G334. Es la forma que tiene Prolog de hacer referencia a una lista de tres elementos cualesquiera (_G331._G337]. José marco. cuando sea posible. Lista = [_G331. _G337]
En el ejemplo 7 hemos utilizado el predicado length/2 de forma contraria a la habitual. esperando que las variables de salida. 2) Comprobar si la implementación del predicado num_elem/2 vista en este tema es reversible y razone por qué.
Tipos de datos 2.3 Grafos 3. Introducción 1.PROGRAMACIÓN LÓGICA CON PROLOG
0. Unificación 2. Control de la ejecución 4.2 Árboles 2.1 Listas 2. Problemas de estados
Invertir una lista 2. Si después de resolver el problema de esta forma.1 Listas (continuación) Las listas son el tipo de dato más utilizado en Prolog ya que se sirven de ellas otros tipos de datos. etc. El profesor David Enrique Losada Carril de la Universidad Santiago de Compostela en la página web de la asignatura Programación Declarativa da algunas claves para resolver problemas declarativamente: “piensa en especificar el problema y sus restricciones y no en secuenciar instrucciones. José marco. cómo deben construirse los predicados recursivos. Permutar los elementos de una lista
. Si entendemos bien estos conceptos. plantear ¿Qué cambios se han de realizar a la salida de la llama recursiva (“parcial”) para obtener la salida “total”? (la del caso general n.). es posible que lleguemos a ser unos buenos programadores declarativos. Ordenación por inserción 5.José carPio. no existiera la seguridad de que funciona… ¡Probarlo en SWI-Prolog! Veamos los siguientes ejemplos: 1. Es muy importante que comprendamos bien el funcionamiento de las listas y. • Pensar el los predicados como algo estático. Ordenación por Quicksort 6.). árboles genéricos y grafos. qué tengo en la salida “parcial”? (Utilizar un ejemplo sencillo si es necesario para entender qué contienen las variables de salida de la llamada recursiva). como por ejemplo. Seguir los siguientes pasos: 1) Plantear el caso recursivo con el tamaño de la llamada recursiva un poco más pequeño (n-1. etc. gonzalo antonio aranDa.Programación Declarativa. TIPOS DE DATOS (CONTINUACIÓN) 2. es muy posible que necesitemos demasiado tiempo para resolver los problemas y terminemos por pensar que la Programación Declarativa es demasiado compleja y que no merece la pena utilizarla. Ordenación por burbuja 4..” Recomendaciones importantes para resolver los ejercicios: • No intentar seguir la ejecución paso a paso de los predicados para hallar la solución. Encontrar los primos entre X e Y 7. En otro caso.
SECCIÓN 2. sobre todo. 3) Una vez aclarado esto. 4) Por último comprobar que el caso base es correcto y que todos los posibles casos están contemplados. de la lista completa. Concatenar dos listas 3. 2) Entonces plantear: ¿Si la llamada recursiva funciona. el resto de una lista.
RT). E1>E2. %----------------------------------------------------ordenada([]).
3) Ordenación por burbuja
%----------------------------------------------------% ordena_burbuja(+Lista. append(Ini.ordenada(Lista). %es cierto cuando ListaR unifica con una lista %que contiene los elementos de la lista List1 %en el mismo orden y seguidos de los elementos %de la lista List2 en el mismo orden. -ListaR). ordenada([_]). [E2. RT). Lista):. RT) :invertir(Resto. append(R. [Cab|R]):concatena(Resto. -ListR). RT):append(Ini. %----------------------------------------------------invertir([]. concatena([Cab|Resto]. Cab2|Resto]):Cab1 =< Cab2. -ListaR) es cierto cuando ListaR % unifica con una lista que contiene los mismos % elementos que Lista en orden inverso. %es cierto cuando ListaR unifica con una lista que %contiene los mismos elementos que Lista ordenados %de menor a mayor. %----------------------------------------------------% ordenada(+Lista) %es cierto cuando Lista unifica con una lista %que contiene sus elementos ordenados de menor a %mayor. List2.
2) Concatenar dos listas
%----------------------------------------------------% concatena(+List1. +List2.R). ordena_burbuja(R. ordena_burbuja(Lista. [Cab]. invertir([Cab|Resto].E2|Fin].[E1. Encontrar el elemento que aparece más veces en una lista 1) Invertir una lista
%----------------------------------------------------% invertir(+Lista.E1|Fin]. L).
. R). ordenada([Cab2|Resto]). ordenada([Cab1.List2. %----------------------------------------------------ordena_burbuja(Lista.74
8. R). []). L. %----------------------------------------------------concatena([]. Lista).
divide(Elem. [Cab|R]):Elem > Cab.[].
4) Ordenación por inserción
%----------------------------------------------------% inserta_en_list_ord(+Elem. Resto. +Lista.[]).R. R). divide(Elem. Menores. José marco. -ListaR). +Lista. %----------------------------------------------------inserta_en_list_ord(Elem. RT). gonzalo antonio aranDa. %es cierto cuando ListaR unifica con una lista %que contiene los elementos de la lista ordenada %Lista. inserta_en_list_ord(Elem. %--------------------------------------------------% ordena_quick(+Lista. %es cierto cuando ListaR unifica con una lista que
. con el elemento Elem insertado de forma %ordenada. -ListaR).
5) Ordenación por Quicksort
%----------------------------------------------------% divide(+Elem. Resto. Cab|Resto]):Elem =< Cab. R). []. [Cab|Mayores]):Cab > Elem. [Elem]). [Elem. ordena_insercion([Cab|Resto]. -ListaR). [Cab|Resto]. %-----------------------------------------------------divide(_.Programación Declarativa. [Cab|Resto]. %----------------------------------------------------% ordena_insercion(+Lista. Mayores):Cab =< Elem.[]). Mayores). [Cab|Resto].[]. inserta_en_list_ord(Elem. %es cierto cuando ListaR unifica con una lista que %contiene los mismos elementos que Lista ordenados %de menor a mayor. -Menores. divide(Elem. divide(Elem.. Menores. %----------------------------------------------------ordena_insercion([]. -Mayores) %es cierto cuando Menores unifica con una lista que %contiene los elemenentos de Lista que son menores %o iguales que Elem y Mayores unifica con una lista %que contiene los elementos de Lista que son %mayores que Elem. [Cab|Resto]. inserta_en_list_ord(Cab. Mayores). Menores. RT):ordena_insercion(Resto. Resto.José carPio. inserta_en_list_ord(Elem. [Cab|Menores].
[X|R]):. lista_divisores(X. May). [Y|R]):Y > 1. primosEntrexy(X. R). %es cierto cuando ListaR unifica con una lista %que contiene a los números cuyo resto %de la división entera de X entre Z es igual a 0 %para valores de Z entre 1 e Y. -ListaR) %es cierto cuando ListaR unifica con una lista %que contiene a los primos que van desde X hasta %Y ambos incluidos en orden ascendente. R).[X. append(RMen. %--------------------------------------------------primosEntrexy(X.X<Y.X<Y. lista_divisores(X. Y2 is Y-1.[]).Y.
. Y. %-------------------------------------------------ordena_quick([].X. 1.
6) Encontrar los primos entre X e Y
%-----------------------------------------------% lista_divisores(+X. lista_divisores(_. RMay). Y. +Y. R):. Men. Z is X mod Y. primo(X). R):Y > 1.X.
%--------------------------------------------------% primo(+X) %es cierto si X unifica con un número primo.1]). primosEntrexy(X2. [Cab|RMay].Y.[]). %--------------------------------------------------% primosEntrexy(+X. %--------------------------------------------------primo(X):. ordena_quick(Men. 0 is X mod Y. lista_divisores(X.Y. RMen). R).Y2.Y. R). primosEntrexy(X2.Y2. [1]).76
%contiene los mismos elementos que Lista ordenados %de menor a mayor. lista_divisores(X. R):divide(Cab. primosEntrexy(X. X2 is X+1. ordena_quick([Cab|Resto]. X2 is X+1. \+ primo(X). Resto. Z \== 0. R).lista_divisores(X. -ListaR). Y2 is Y-1. ordena_quick(May. +Y.
8) Encontrar el elemento que aparece más veces en una lista
%-----------------------------------------------------% mas_veces(+Lista.0). Este predicado genera todas las %listas posibles por backtraking. Ca=El.José carPio. Ca. N):mas_veces(Co. E. %-----------------------------------------------------mas_veces([]. R). %-------------------------------------------------selecciona_uno([Ca|R]. en el mismo orden menos el elemento %Elem. selecciona_uno([Ca|Co]. N2 is N+1. ListaR). E. Ca. -Elem. %-------------------------------------------------permuta([]. mas_veces([Ca|Co].. [Ca|R]):selecciona_uno(Co. permuta(R. E.El. %es cierto cuando ListaR unifica con una lista %que contiene los elementos de Lista en orden %distinto. R).N). permuta(L. El.Programación Declarativa. R). %-------------------------------------------------% permuta(Lista. gonzalo antonio aranDa. RP). N2):mas_veces(Co. -Elem. mas_veces([Ca|Co].
. José marco. [E|RP]):selecciona_uno(L. -Num) %es cierto cuando Elem unifica con el elemento %que se repite más veces en la lista Lista %y Num unifica con el número de veces que se %repite dicho elemento.
7) Permutar los elementos de una lista
%-------------------------------------------------% selecciona_uno(+Lista. Ca\=El._. -Resto) %es cierto cuando Elem unifica con cualquier %elemento de la lista Lista y Resto unifica %con una lista que contiene los elementos de %Lista. []).N).
3 Grafos 3. Unificación 2.2 Árboles 2. Problemas de estados
. Tipos de datos 2.1 Listas 2. Control de la ejecución 4.PROGRAMACIÓN LÓGICA CON PROLOG
nil).nil. R is RI + RD + 1. a(g. cuenta_nodos(A.a(e.a( g. HD). a(b.nil) o el árbol vacío A3 = nil Veamos un ejemplo con el predicado cuenta_nodos para árboles binarios. A1=a(a. o bien.nil). cuenta_nodos(HD. a(f..nil. HD).a(e.a(d. gonzalo antonio aranDa. nil.nil. donde “Et” representa la etiqueta de la raiz y HI y HD son los subárboles Izquierdo y derecho respectivamente.nil).nil.nil.a(f.nil).
En Prolog representaremos un árbol nulo con el átomo ‘nil’ y el árbol no vacío con el término a(Et.dato(A). • Una estructura compuesta por un elemento y dos sucesores que son árboles binarios. nil)).nil. R):cuenta_nodos(HI. HI.nil))) Otros ejemplos son un árbol que sólo contiene un nodo A2 = a(a.
/* cuenta_nodos(+Arbol_binario. nil). 0).nil)).a(f. dato(a(a.a(d. nil). N). a(e. a(d.nil.
SECCIÓN 2.a(c.TIPOS DE DATOS (CONTINUACIÓN) 2. cuenta_nodos(a(_.a(g.José carPio.Programación Declarativa.2 Árboles Árboles binarios Un árbol binario es • Árbol nulo. A = a(a. nil))) N = 7 */
. nil. RD). ?Num_nodos) es cierto cuando Num_nodos unifica con el numero de nodos del árbol "Arbol_binario" */ cuenta_nodos(nil.nil)))).a(b. RI). nil.nil. HI.a(c.a(b.nil)). a(c. nil.nil. José marco. /* 1 ?.
?Lista_hojas)
es cierto cuando Lista_hojas unifica con una lista que contiene las etiquetas de las hojas del árbol “Arbol_binario” */ lista_hojas(nil.82
Otro ejemplo es el predicado lista_hojas para árboles binarios
/* lista_hojas(+Arbol_binario.a(g.LD):HD \=nil. LI):HI \= nil.nil)))). HD). A = a(a. e. lista_hojas(HI. g] */
. lista_hojas(HD. /* 1 ?. a(f.nil.nil). nil))) R = [d. LR):HI \= nil. nil. lista_hojas(a(Et. lista_hojas(HI. a(e. lista_hojas(a(_. LI).a(c. lista_hojas(A.dato(A). LR). a(d.a(e. nil)). nil. HI. nil. LD). LD). R).a(b. nil). LI). nil. HD). append(LI. nil.a(f.nil. lista_hojas(a(_. [Et]).nil.HI.
dato(a(a. a(c.nil). []). lista_hojas(HD. LD. a(b.a(d. lista_hojas(a(_.nil)).ni l. a(g. nil.nil). HD\=nil. nil).nil).
. A = a(a.Un caso recursivo. que será por lo general. seguiremos el mismo principio utilizado en las listas. escribiremos unas cláusulas que unifiquen con una estructura de árbol y otra/s cláusula/s que unificarán con listas de árboles. realiza la llamada recursiva sobre el resto de la lista (en este caso de árboles) y.[]).[a(d. gonzalo antonio aranDa.a(c.. . que separa el primero del resto.[a(g.Un caso base. no tendremos un equivalente al árbol nulo de los árboles binarios.[]). José marco. para simplificar consideraremos que un árbol genérico no estará nunca vacío.a(e. ListaHijos).[a(f.[])]). a partir del resultado. lista vacía.Programación Declarativa.José carPio. En el caso de las cláusulas para listas de árboles. es decir.[])])]) Metodología para la implementación de árboles genéricos Con la idea de simplificar la implementación de los predicados de árboles genéricos.
Árboles genéricos Un árbol genérico está compuesto por una raíz y por una lista de sucesores que son a su vez árboles genéricos. El árbol del ejemplo lo representaremos con el siguiente término Prolog. dónde Et es la etiqueta de la raíz y ListaHijos es una lista con los árboles descendientes. Implementaremos el predicado cuenta_nodos para árboles genéricos como ejemplo:
. construye la solución.
En Prolog representaremos un árbol genérico por el término a(Et. Aunque podríamos establecer una representación en nuestra aproximación.a(b.
?Num_nodos)
es cierto cuando Num_nodos unifica con el numero de nodos del árbol “Arbol_generico” */ %cláusula para un árbol genérico cuenta_nodos(a(_. a(b. R):cuenta_nodos(Lista_hijos. [a(g. NCab). % cláusulas para lista de árboles cuenta_nodos([]. [])]). []). ):cuenta_nodos(Cab. lo encontramos en el predicado profundidad para árboles genéricos:
. [a(f.[]). cuenta_nodos([Cab|Resto].[]). R is Ncab + Nresto.[])]).84
cuenta_nodos(+Arbol_generico. cuenta_nodos(Resto. [])])]) N = 7 */
Otro ejemplo.[a(f.[a(g. Lista_hijos). a(e. [a(d.a(e.N). NResto). A = a(a.a(c. a(c. /* dato(A). cuenta_nodos(A. N). 0).a(b. dato(a(a.[a(d. []). R is N + 1.[])])])).
/* profundidad_ag(+Arbol_generico, ?P) es cierto cuando P unifica con la profundidad del árbol genérico “Arbol_genérico” */ profundidad_ag(a(_, Lista_hijos), R):profundidad_ag(Lista_hijos, PH), R is PH+1. profundidad_ag([], 0). profundidad_ag([Cab|Resto], PCab):profundidad_ag(Cab, PCab), profundidad_ag(Resto, PResto), PCab >= PResto. profundidad_ag([Cab|Resto], PResto):profundidad_ag(Cab, PCab), profundidad_ag(Resto, PResto), PCab < PResto. dato(a(a,[a(f,[a(g,[])]),a(c,[]),a(b,[a(d,[]),a(e,[])])])). /* dato(A), profundidad_ag(A,N). A = a(a, [a(f, [a(g, [])]), a(c, []), a(b, [a(d, []), a(e, [])])]) N = 3
Ejercicio: Plantear cómo se podría extender la representación de árboles genéricos propuesta para representar árboles genéricos nulos.
0. Introducción 1. Unificación 2. Tipos de datos 2.1 Listas 2.2 Árboles 2.3 Grafos 3. Control de la ejecución 4. Problemas de estados
f).f).h)]) arista(b.ch/hew1/informatik3/prolog/p-99 Un grafo se define como un conjunto de nodos y un conjunto de aristas.[a(b.g.José carPio.3 Grafos Referencia: Ninety-Nine Prolog Problems: https://prof.k).h)])
.b).f. Siguiendo la definición dada anteriormente de un grafo como un par de dos conjuntos (aristas y nodos). gonzalo antonio aranDa..
o de una forma más compacta
grafo([b. a(b.f).d.ti.h.
SECCIÓN 2.f). donde cada arista une a dos nodos..h.c.[arista(b.c. .g). Otro método consiste en representar todo el grafo en un único objeto. Para representar el siguiente grafo con este método escribiremos:
arista(h.f).c). Existen diferentes modos de representar un grafo en Prolog.f.
Podemos denominar a esta representación “Representación Cláusula-arista”.k]. arista(c. a(f.Programación Declarativa. Uno de estos métodos consiste en representar cada arco con una cláusula (hecho) independiente.g. Con este método no podemos representar los nodos aislados (en el ejemplo anterior el nodo “d”). arista(f. arista(k. Esta representación puede hacer la implementación del camino algo más sencilla. TIPOS DE DATOS (CONTINUACIÓN) 2.k]. arista(f. a(c. podemos utilizar el siguiente término en Prolog para representar nuestro grafo ejemplo:
grafo([b. a(g. José marco.d. arista(g..c).k).bfh. sin embargo complica bastante tareas como recorrer todas las aristas o visitar todos los nodos.
ch/hew1/informatik3/prolog/p-99/ Las aristas pueden ser dirigidas. una arista desde el nodo x al nodo y se representa como a(x.
Pueden consultarse otras representaciones en “Ninety-Nine Prolog Problems” https://prof. o no dirigidas cuando enlazan a los nodos en ambos sentidos. Denominaremos a los grafos que añaden información adicional a vértices o aristas “Grafos etiquetados”. Tendremos en cuenta que el conjunto se representa con una lista sin elementos repetidos.x) no aparece en la lista. como por ejemplo el coste de recorrerlas. es posible también añadir información a las aristas. Cuando las aristas están dirigidas llamaremos al grafo Grafo dirigido. En SWI Prolog existen predicados predefinidos para trabajar con conjuntos. Ejemplo:
. por ejemplo el nombre de la ciudad y el código postal ciudad(‘Huelva’. Ejecute help(111-1). por ejemplo.90
Denominaremos a esta representación “Representación Término-Grafo”.y) y el término a(y.ti.27002). Es posible sustituir el nombre del nodo por una estructura que contenga. Por otro lado. Los nodos y las aristas de los grafos dirigidos y no dirigidos pueden incorporar información adicional.bfh. Cada arista aparece sólo una vez en la lista de aristas. cuando sólo enlazan a los nodos implicados en sentido origen -> destino y no en el contrario. en SWI Prolog para obtener información sobre la sección “Set Manipulation”. Dependiendo del problema a resolver necesitaremos usar un tipo de grafo u otro. La Representación Término-Grafo es la representación que utilizaremos por defecto.
_. +Visitados. Fin. Los predicados que encuentran un camino en un grafo son recursivos.7). la lista de Visitados es irrelevante. []).
Representación Cláusula-Arista arista(m.[arista(m.5). <Camino2> : En ocasiones es necesario indicar tanto la lista de nodos visitados como la lista de aristas visitados. arista(p. ?Camino. En el caso base.
Hemos indicado antes que la lista de visitados tiene como única función evitar que el predicado caiga en un bucle infinito.Programación Declarativa.. José marco.m. al no tener llamada recursiva.
. que se utiliza para evitar que el predicado se quede iterando en un ciclo. El predicado camino tendrá la siguiente cabecera
camino(+Inicio.<?Peso_total>. <Peso_total> : En ocasiones es necesario indicar cual es el peso total del camino.q.9).q. +Grafo. +Fin.arista (p.arista(p.m. independientemente de los puntos por los que haya pasado.José carPio. ciudades visitadas y kilómetros recorridos.m. Los campos anteriores son necesarios en la mayoría de los problemas de grafos.5).q].p. Camino: Lista de nodos o de aristas (dependiendo del caso) que representa el camino. <?Camino2>)
Inicio: Representa al nodo inicial del camino Fin: Representa al nodo final del camino Grafo: Grafo en el que buscamos el camino Visitados: Lista de nodos o de aristas (dependerá del caso). Caso base: Primera posibilidad y más habitual. Ejemplo carreteras visitadas.q. arista(p.9)])
Construcción de un camino en grafos Gran cantidad de los problemas de grafos se resuelven construyendo un camino que una dos nodos del grafo.
camino(Fin.p. gonzalo antonio aranDa.7). Representación Término-Grafo grafo([k. Podemos hacer el siguiente razonamiento: Si ya estoy en el final del camino he terminado.
[arista(Inicio.member(arista(Inicio. \+ visitado(Inicio. Camino).
En este predicado el corte “!” (que veremos con detalle en la sección 3) tiene como finalidad evitar que Prolog intente buscar una solución por un camino que sabemos no devolverá ninguna solución válida. Visitados. Fin. Aristas).member(arista(Fin. _.
Inicio ----→ TMP ----------------------→ Fin camino(Inicio. +Fin. Aristas). Fin. Fin). Aristas):. Aristas). grafo(Vertices. Predicado conectado en grafos dirigidos:
% conectado(+Inicio. en este caso será una lista vacía o bien una lista con el nodo Fin si lo que deseo devolver es la lista de nodos que he visitado.TMP)|Camino]):conectado(Inicio. +Aristas) conectado(Inicio.92
La variable de salida Camino.
Lo utilizaremos sólo cuando sea imprescindible. Aristas):. Fin. Inicio). Aristas). [arista(Inicio. Un tipo de problemas en el que utilizaremos este caso base alternativo es el de la obtención de los ciclos de un grafo. Caso recursivo: Para construir el caso recursivo buscaremos avanzar a algún vértice TMP y a partir de ese punto buscaremos un camino hasta el final. Fin). camino(TMP. TMP)|Visitados]. Visitados).
Dependiendo del tipo de grafo y del objetivo perseguido.member(arista(Inicio. +Fin. Fin. Fin)]):arista(Inicio. Fin. Aristas):. conectado(Inicio. [arista(Inicio. Fin. TMP. Por lo general el caso base anterior funciona bien y es más sencillo. Fin). Caso base alternativo:
camino(Inicio.
. Fin. Predicado conectado en grafos no dirigidos:
% conectado(+Inicio. los predicados conectado y visitado podemos implementarlos de forma distinta. Aristas). +Aristas) conectado(Inicio.
cadiz].
.a44.
% conectado(+Inicio.ap4. arista(granada. jaen.K). +Fin. a49. 97).member(arista(Inicio.
Predicado visitado en grafos dirigidos:
% visitado(+Inicio. arista(jaen. a4. Fin. José marco.C.
A4(400)
A44(97)
A49(94) AP4(125)
A92(125)
En este caso. madrid. Fin. a4. Aristas):. jaen. 335). Visitados). cordoba. +Visitados) visitado(Inicio. se trata de un grafo no dirigido. Fin). +Fin. +Visitados) visitado(Inicio. Visitados). Fin. huelva. 256). +Fin. Aristas. arista(sevilla. Inicio). sevilla. Aristas).
Predicado visitado en grafos no dirigidos:
% visitado(+Inicio. K):member(arista(Inicio. 400)] )). [arista(huelva. a4. granada.member(arista(Fin. cadiz. arista(cordoba. arista(sevilla.. -Kilometros) conectado(Inicio. Aristas):. sevilla. granada.member(arista(Inicio. a92. Fin). +Aristas. cordoba. Visitados). Aristas):. 125). arista(sevilla. visitado(Inicio.José carPio.Programación Declarativa. Fin. C.madrid. gonzalo antonio aranDa. 94).
dato(grafo([madrid. 138). -Carretera. Fin.
K = 1182 . 125). a4. a4]._)|Visitados]. visitado(Inicio._. Carreteras. huelva. granada. 97). madrid. cadiz. % visitado(+Inicio. [arista(huelva. ap4. 138). arista(sevilla. Grafo. Ca = [huelva. a4. a49. Kilometros). arista(granada.C. G. Fin. a4. Ciudades. madrid. jaen. a4. Visitados):.dato(G). 256). a44. Ca = [huelva. % dato(G). conectado(Inicio. Ciudades. Fin. C = [a49. %camino(Inicio. a4. Fin. a4. arista(cordoba. cordoba. granada. Carretera. Visitados. a4]. arista(sevilla. cordoba. Fin. madrid. sevilla.TMP. Kilometros) camino(Fin. G. granada. En este caso queremos encontrar las alternativas para llegar desde Huelva a Córdoba. C = [a49. 94). K):-member(arista(Fin. K2 is Kilometros + K. 0). madrid. 138). [Fin]. camino(huelva._). _.
. G = grafo([madrid. Aristas. cordoba]. 256). sevilla. sevilla. madrid. jaen. [arista(Inicio. [Inicio|Ciudades]. granada. jaen. granada. Visitados):-member(arista(Inicio. camino(TMP.Carreteras. a4. Aristas). arista(sevilla. cadiz]. arista(cordoba. arista(sevilla. G. G = grafo([madrid. 125). madrid. a92. arista(sevilla. 97)._. cordoba. Visitados).K). []. ap4.
Ejecutaremos el objetivo camino para encontrar las soluciones.Ca.[]. arista(granada.[Carretera|Carreteras]. a44. cordoba]. Fin. +Visitados) visitado(Inicio. 335). a92. false. arista(sevilla. +Fin. 94). _. cordoba. sevilla. a49. La primera opción pasa por Granada y Madrid recorriendo 1182 kilómetros y la segunda tiene una longitud de 232 kilómetros. Fin. 400)]).C. Fin._. cadiz].K).94
conectado(Inicio. C. camino(Inicio. a44. arista(jaen. sevilla. Visitados. Fin._). a92. TMP. TMP. K). Ca. cordoba. Inicio. arista(jaen. jaen. G. Aristas). [arista(huelva.
1 ?. jaen. huelva.Inicio. \+ visitado(Inicio. Visitados).C.member(arista(Fin. Visitados). K = 232 . sevilla.K). cadiz. Aristas. K2):G = grafo(_. camino(huelva. []. 400)]). 335).
Unificación 2.PROGRAMACIÓN LÓGICA CON PROLOG
0.2 Árboles 2. Problemas de estados
.3 Grafos 3. Introducción 1. Control de la ejecución 4.1 Listas 2. Tipos de datos 2.
Consideremos que fue invocada por un objetivo G que unifica con H. cuenta_hojas(a(_.Bm se mantienen pero cualquier otra alternativa para estos objetivos es descartada.!. José marco. !. 2..
En este ejemplo.. Ejemplo:
1. Lo que algunos autores llaman cortes verdes y cortes rojos.B1.HI. Para el resto de los objetivos Bm+1.0)..... En programación declarativa no importa el orden en que se escriban las cláusulas.Programación Declarativa. Sin embargo el uso de cortes rojos impide que las cláusulas se puedan cambiar de orden. Bm+1. gonzalo antonio aranDa.nil).B2.
.. las soluciones deben ser las mismas.. cuenta_hojas(a(_. Bn. el sistema ya ha encontrado soluciones para los términos B1. Segundo efecto del corte: Cualquier intento de satisfacer el objetivo G con otra cláusula es descartada.
3.. son aquellos que no modifican las soluciones del programa. CONTROL DE LA EJECUCIÓN El corte Notaremos el corte con un cierre de admiración “!”. RI).. Es decir. Bm.nil. R):cuenta_hojas(HI. RD). R is RI+RD.. para la consulta cuenta_hojas(a(1. .Bm. R). el predicado daría dos soluciones una correcta (R=1) y otra incorrecta (R=0). cuenta_hojas(nil... Las soluciones encontradas para B1. Existen dos modos de uso del corte. Primer efecto del corte: En el momento en el que se alcanza el corte... Los cortes rojos son aquellos que modifican las soluciones del programa (al quitar el corte las soluciones son distintas). Se utiliza para mejorar la eficiencia de ejecución.. cuenta_hojas(HD. que con corte y sin corte el programa produce las mismas soluciones. Dada la siguiente cláusula que contiene el corte:
H:. Este tipo de cortes hacen los programas menos declarativos y deben utilizarse con reservas..José carPio.nil).HD)..
SECCIÓN 2. 1):. si eliminamos el corte. sí se aplicarán las técnicas de backtraking habituales. B2.B2.Bn. Los cortes verdes.nil.
cuenta_hojas(HD. Por ejemplo. Si no existiesen ramas al mismo nivel. Árbol de resolución También conocido como árbol de deducción. Algoritmo de resolución. pasaríamos al nivel superior empezando por la rama que esté más a la izquierda. nil. cuenta_hojas(nil.!. se produce un fallo y se explora la siguiente rama inmediatamente a la derecha en el mismo nivel. 5. RD). cuenta_hojas(HI. RI). Repetir mientras queden términos: 1) Buscamos en la base de conocimiento de arriba abajo unificaciones del término objetivo en las cabezas de las reglas y en los hechos. cuenta_hojas(a(_. !. RI):HD \= nil. nil). HI \= nil. 3.HI.nil. RD). cuenta_hojas(a(_. HD \= nil. representa el modo en el que Prolog resuelve una determinada consulta.0). el corte evita que se realicen algunas comprobaciones. HD). cuenta_hojas(HD. a) Abrimos tantas ramas de ejecución como unificaciones y empezamos a resolver por la que está más a la izquierda. R is RI + RD. RI).
En este otro ejemplo. cuenta_hojas(HI. ):-
4. En este caso. no tiene sentido buscar una solución en las cláusulas que aparecen a continuación. !. si llegamos al corte de la cláusual 2. 2. cuenta_hojas(a(_. 1):. cuenta_hojas(a(_. RD):HD \= nil.98
Otra versión del mismo problema con cortes “verdes”:
1.HD).
. b) Si no hubiese ninguna unificación. al eliminar los cortes el programa obtiene las mismas soluciones.nil). HI.
c(2). b(3).2):. b(4).Y):. 9.Y):. d(Y).c(Y). a(2). p(1.. 2. 8. p(X. sustituimos la cabeza por el cuerpo de la regla intanciando las variables. 6. c(3).c(X). José marco. p(X. d(2). Fijamos como término objetivo actual el que está más a la izquierda y vovelmos al paso 1. 4. 10.
2) En la rama actual.a(X).Programación Declarativa.
.José carPio. !. 11. d(3). 7. a(1). 12. gonzalo antonio aranDa. c(Y). b(X). Ejemplo:
1. 5. a(3). c(1). 3. 13.
Tratamiento del corte en los árboles de resolución Cuando alcancemos un corte en un árbol de resolución.. 3) Identificaremos al objetivo que intentábamos satisfacer (G) que unificó con la cabeza (H) de la regla que contiene al corte y. no seguiremos comprobando el resto de términos... Tal y como indica la definición del corte H:.. 3) Dibujaremos tantas ramas como unificaciones haya y etiquetaremos cada rama con el número de la cláusula.100
Pasos para la creación de los árboles de resolución 1) Numeraremos las cláusulas del programa de arriba abajo en orden ascendente. .B1. 2) Escribiremos el objetivo propuesto y buscaremos unificaciones del objetivo en las cabezas de las reglas y en los hechos. B2. marcando con ‘Rama podada” las ramas correspondientes a las alternativas para los términos que están antes del corte.
.Bm. 5) Anotaremos la sustitución de variables en la rama y sustituiremos la cabeza por el cuerpo de la regla. Si uno de los términos fuese false. lo eliminamos y seguimos resolviendo el resto de izquierda a derecha. ..!.. aplicando el segundo efecto. 6) Resolveremos los términos de izquierda a derecha. Si no existiese ninguna unificación anotaremos un fallo para el objetivo. Recuerde que para que el consecuente sea cierto deben ser ciertos todos los términos del antecedente... G. los términos que están antes del corte B1. 8) Cuando hagamos todos los términos... marcaremos como ‘Rama podada’las ramas correspondientes al intento de satisfacer el objetivo G con otras cláusulas. Bm+1. marcaremos esa rama con “éxito” y anotaremos los valores de las soluciones para las variables del objetivo... sin olvidar los términos anteriores si los hubiese. seguiremos los siguientes pasos: 1) Identificaremos la cláusula que contiene al corte y los elementos H. Bn. Bn.. B2.. Si existen tendremos que aplicar el primer efecto del corte. 2) Comprobaremos si existen términos antes del corte. 4) Empezaremos resolviendo por la rama que está más a la izquierda. 7) Cuando un término se hace cierto. Bm y los que están después Bm+1.
. José marco. repeat. gonzalo antonio aranDa. read(X). escribe adios y lee un término por teclado. Veamos un ejemplo:
1. Si el término es igual a fin. write(‘adios’). tiene un efecto similar a un término que tuviese infinitas unificaciones.Programación Declarativa.José carPio.write(‘hola’). Si no se introduce fin. !. X=’fin’.
Término “repeat” El término repeat. p(X):..
Este ejemplo muestra una vez hola. se alcanza el corte y se eliminan todas las ramas del repeat y el programa termina. el programa no termina.
5.uma.[N]]. r([[]]). q([C. 4. 6. q([C|R]. la mejor opción es implementarlo.
SLD-Draw Puede utilizarse la herramienta SLD-Draw (http://www.”.
.es/~pacog/sldDraw/) para dibujar los árboles de resolución que no contengan ‘repeat’. ésta se hace falsa. 3.0):-s(C). s(1):-q([].1). r([next(a)]).r([C]). 7.!. introducirlo en Prolog y solicitar todas las soluciones utilizando “.lcc.t(R). r(1). t(1):-fail.N is 2+3.102
Elemento ‘fail’ Cuando se alcanza el término fail en una cláusula. 9. Ejemplo para probar:
1.1).q(R. q([C. Si existen dudas de si un árbol de resolución es correcto.1):-r([C]). 8.1):-!.next(a)]. Prolog nos dará en todos los casos todas las soluciones válidas. SLD-Draw en algunas ocasiones no produce todas las soluciones válidas. s(R):-!. 2.
Introducción 1.3 Grafos 3. Tipos de datos 2.PROGRAMACIÓN LÓGICA CON PROLOG
0. Problemas de estados
.2 Árboles 2. Unificación 2. Control de la ejecución 4.1 Listas 2.
en otro caso los misioneros se convertirían en la cena de los caníbales. De esta forma. • Utilizando la información del término estado( … ) debemos ser capaces de representar el problema sin perder información relevante evitando duplicar información. • El número de caníbales en cada orilla nunca debe ser mayor al número de misioneros. Encontramos una relación entre los problemas de estados y los grafos asociando nodos con estados y aristas con movimientos. Construiremos la solución en cuatro pasos: 1) Definición de un estado genérico y de los estados inicial y final..José carPio. PROBLEMAS DE ESTADOS Un método para resolver problemas haciendo uso de la programación lógica consiste en trazar un camino que transcurre por diferentes situaciones (estados) hasta llegar a una solución. Caníbales y misioneros Enunciado del problema: • Hay tres misioneros y tres caníbales en la orilla izquierda de un río • Tanto los misioneros como los caníbales. Representaremos el problema como un conjunto de: . 2) Implementación de los movimientos. 3) Implementación del camino. • El estado no incluir en el estado información de las acciones.
.Estados: que representan una instantánea del problema. • Planee una secuencia de movimientos para cruzar a los misioneros y los caníbales de forma que al final estén todos sanos y salvos en la orilla de la derecha. y en base a estos dos elementos se construirá un camino que parte de un estado inicial y tras una secuencia de movimientos alcanza un estado final. gonzalo antonio aranDa. disponen de una barca que puede transportar sólo a dos personas a la vez.
SECCIÓN 3. • Un estado representa un instante del problema. Si recordamos la forma de construir un camino en los grafos.Programación Declarativa. Explicaremos la resolución de problemas de estados utilizando el ejemplo de los caníbales y los misioneros. Una transición de un estado a otro se produce realizando un movimiento. 1) Definición de un estado genérico y de los estados inicial y final. la secuencia de movimientos de un problema de estados tendrán básicamente la misma estructura. José marco. 4) Implementación del predicado solución. desean cruzar a la orilla derecha de río.Movimientos: que transforman un estado en otro. . • Para cruzar. la clave para resolver un problema con esta metodología consistirá en definir un estado y unos movimientos.
Pos_barca)
Utilizando esta representación. podemos representar este estado con un término de 3 argumentos.?Estado_anterior. Pasar dos misioneros a la izquierda o a la derecha. MI2 is MI + 1. Para poder implementar los movimientos.izq)). En el caso del problema de los caníbales y los misioneros tendríamos los siguientes movimientos: • • • • • Pasar un misionero a la izquierda o a la derecha. tendrá por lo general. Por ejemplo.
mov(pasar_un_mis_izq. definiremos los estados inicial y final:
inicial(estado(3. es decir como debe ser el estado anterior al movimiento. En Prolog. podemos obtenerla a partir de estos tres datos.?Estado_posterior)es cierto cuando Movimiento unifica con un Movimiento válido. Toda la información necesaria para resolver el problema.0. Pasar un misionero y un caníbal a la izquierda o a la derecha. la siguiente cabecera:
/*mov(?Movimiento. Pasar dos caníbales a la izquierda o a la derecha. dch). CI)):MI < 3. final(estado(0. estado(MI2. estado(MI. Misioneros_izq.
El predicado mover. es necesario pensar en las condiciones necesarias antes de realizar el movimiento.
. podemos asociar un coste en tiempo a cada movimiento. El siguiente paso consiste en definir los movimientos posibles.3. la información que necesitamos para representar el problema es: • El número de misioneros en la orilla de la izquierda • El número de caníbales en la orilla de la izquierda • El lugar en el que se encuentra la barca. Estado_anterior unifica con un estado válido y Estado_posterior unifica con el estado resultante de aplicar el movimiento “Movimiento” al estado “Estado_anterior” */
Es posible que para algún tipo de problema sea necesario incluir algún argumento más.106
Volviendo ahora al problema de los caníbales y los misioneros. para poder pasar un misionero a la izquierda es necesario que exista al menos un misionero a la izquierda y que la barca esté a la derecha. si quisiéramos calcular cuanto tiempo es necesario para llegar a la solución.dch)). escrito ‘mov’. Por ejemplo.
2) Implementación de los movimientos.
estado(Caníbales_izq. Pasar un caníbal a la izquierda o a la derecha. CI.
1.C. M =< MI. pasar(2.1.
No estamos comprobando si el estado nuevo es un estado válido. C =< CI. CD.C. mov(pasar(M. dch). NT =< 2. NT =< 2.izq). gonzalo antonio aranDa. NT is M + C. pasar(0.2. pasar(1. pasar(0. Utilizaremos un predicado pasar que representaremos mediante 10 hechos. CI. Otra forma de escribir los movimientos es hacerlos más genéricos para evitar escribir varios movimientos muy parecidos. dch)):pasar(M.CI.. estado(MI.C. izq). CD is CI + C. ?Num_canibales. C. pasar(1.
pasar(?Num_misioneros.dch). M =< MI.dch).1. A continuación se propone una simplificación para los movimientos que los reduce sólo a dos cláusulas más un conjunto de 10 hechos.dch). Cuando tenemos muchos movimientos (en este caso hay 10 movimientos) interesa no incluir en los movimientos las comprobaciones de si el estado nuevo es válido ya que repetiríamos en cada movimiento la misma comprobación.0. C. pasar(2. estado(MD. dch). ?Lugar) será cierto cuando Num_misioneros y Num_canibales unifica con una combinación de misioneros y caníbales válida según la especifi-
cación del problema y cuando lugar unifica con ‘izq’ o ‘dch’. estado(MD.dch).dch). NT is M + C. José marco. pasar(0.0. NT >= 1. pasar(1. cuando Estado sea un estado válido.izq).izq). MD is MI -M. Es mejor incluir un predicado valido(Estado) que será cierto.izq).José carPio.1.0.
Los movimientos quedarían de la siguiente forma
mov(pasar(M. MD is MI + M. C =< CI. Sin embargo.izq).0. pasar(0.
.Programación Declarativa. NT >= 1. CD is CI . CD. izq).
pasar(1. esta simplificación no siempre es fácil de encontrar.izq).2. izq)):pasar(M.dch). estado(MI.
Fin. La implementación de este camino es básicamente la misma que utilizamos en el recorrido de los grafos. Visitados. Su objetivo es hacer la llamada de forma correcta al predicado camino. _. L < 10. \+ member(Int. Camino). Esta limitación tiene sentido cuando las posibilidades de exploración sean muchas y sepamos que en un número de pasos como máximo está la solución. hace que el problema evolucione hasta el estado final deseado.
solucion(Camino):. +Visitados. Por último. Inicio. utilizando estados en lugar de nodos y movimientos en lugar de aristas. En este caso la comprobación se realiza dentro del predicado mov. camino(Int.
Dependiendo del problema. -Camino) es cierto cuando Estado_inicial y Estado_final unifican con estados válido. Camino). camino(Inicio. por ejemplo. Visitados).
A continuación se muestra la implementación completa de la solución:
. +Estado_final. [Int|Visitados]. Int).[Ei]. camino(Ei. Esta comprobación la haremos con un predicado de validación que llamaremos valido(Estado).108
3) Implementación del camino.inicial(Ei). La solución a este tipo de problemas viene dada por una secuencia de movimientos que. Es importante remarcar que la lista de estados visitados inicialmente debe contener al estado inicial. Inicio. indicar que la lista de visitados contendrá estados. [Mov|Camino]):length(Visitados. el predicado camino puede tener algún argumento más si queremos. Este camino tiene la particularidad de limitar como mucho a 11 (10 visitados + 1 paso final) la longitud del camino. 4) Implementación del predicado solución Este predicado hace uso de camino y los estados inicial y final y su implementación es muy sencilla. El predicado camino tendrá como mínimo los siguientes argumentos:
/* camino(+Estado_inicial. mov(Mov. Visitados unifica con una lista de estados visitados. []). partiendo de un estado inicial. guardar el coste total del camino. final(Ef). Fin. ya que es posible repetir el mismo movimiento siempre que no se pase dos veces por un mismo estado (para evitar caer en un bucle infinito). Ef. */ camino(Inicio. L). Podemos asimismo incluir la comprobación de si el nuevo estado es correcto después de realizar el movimiento.
dch). Misioneros_izq. Inicio. CI.José carPio.2. pasar(0. []).1. C =< CI.dch). MD is MI -M. izq).C.0. mov(Mov. +Visitados.izq).dch).
/* estado(Canibales_izq.izq). C.dch). Visitados. NT >= 1.C.1.C. L). CD.3. M =< MI.au/~billw/cs9414/notes/mandc/mandc.0. CD is CI . estado(MI. mov(pasar(M.izq).unsw.dch). MD is MI + M. camino(Inicio.izq). NT is M + C. NT >= 1. dch). Visitados).0. Pos_barca) */ inicial(estado(3. Fin. */ pasar(1. estado(MI.CI. CD is CI + C. ?Lugar) es cierto cuando Num_misioneros y Num_canibales unifica con una combinación válida de misioneros y misioneros válida según la especificación del problema y cuando lugar unifica con ‘izq’ o ‘dch’. Inicio. +Estado_final. izq)):pasar(M. final(estado(0. CD. Int).dch). José marco. NT =< 2. pasar(1. pasar(1.Programación Declarativa. /* camino(+Estado_inicial. pasar(2. pasar(0.izq). dch)):pasar(M. _. M =< MI. Camino).dch)). /* pasar(?Num_misioneros.cse. Estado_anterior unifica con un estado válido y Estado_posterior unifica con el estado resultante de aplicar el movimiento “Movimiento” al estado “Estado_anterior” */ mov(pasar(M. /* mov(?Movimiento. [Int|Visitados]. Fin. pasar(2. [Mov|Camino]):length(Visitados. dch). pasar(0. C.izq)).0. pasar(1. ?Num_canibales. pasar(0.
Referencias: Problem Solving in Prolog: Bratko capítulo 12 http://www. C =< CI. camino(Int. gonzalo antonio aranDa. NT is M + C.html
. estado(MD.2. NT =< 2. ?Estado_posterior) es cierto cuando Movimiento unifica con un Movimiento válido. estado(MD.izq). -Camino) es cierto cuando Estado_inicial y Estado_final unifican con estados válido. L < 10.1. Visitados unifica con una lista */ camino(Inicio.1. \+ member(Int.0. ?Estado_anterior..edu. izq).
PRÁCTICAS CON HASKELL
CUENTA DE USUARIO Cada alumno puede disponer de una cuenta de usuario. Cuando escribimos una expresión en esta ventana y pulsamos ↵ . EMPEZANDO • Seleccionar el arranque del sistema Operativo Windows XP. José marco.
INTRODUCCIÓN AL ENTORNO DE PROGRAMACIÓN HASKELL HUGS En esta primera práctica nos familiarizaremos con el entorno de programación de Hugs y veremos los tipos de datos básicos. Recuerde su password. gonzalo antonio aranDa. El modo de funcionamiento de esta ventana es muy similar al de una calculadora. ya que no será posible consultar su password con posterioridad SECCIÓN 1. sólo como espacio de almacenamiento temporal..José carPio. SECCIÓN 1. SECCIÓN 0. • Introducir el login proporcionado por el profesor/a. La primera vez que inicie el sistema debe cambiar el password. Después de cada sesión guardaremos los ficheros en una memoria USB o bien los enviaremos a nuestra cuenta de correo electrónico. Se recomienda no dejar ningún material importante en esta cuenta. pedimos al interprete que nos muestre el resultado de la expresión. Utilizaremos este espacio.
. La cuenta tiene asociado un espacio en disco.Programación Declarativa. EJECUTAR HUGS • En el menú “Inicio” de Windows seleccionar el programa WinHugs
• Aparecerá una ventana como esta: • Desde esta ventana cargaremos los programas y haremos las consultas.
Antes de empezar con la edición de los ficheros.hs.hs:
Guardaremos el contenido del fichero y cerraremos la ventana. Escribiremos lo siguiente en el fichero suma. ESCRIBIR UN PROGRAMA Para escribir un programa utilizaremos un editor de texto que no introduzca caracteres especiales. dejando esta expresión invariante. Podemos cambiar este editor utilizando el comando “:set”. crearemos el directorio “H:\declarativa”.114
Ejecutar en Hugs:
Hugs> 1+1
comprobar que el intérprete muestra “2”. escribiremos :load <nombre_fichero>:
Hugs> :load “H:\\declarativa\\suma.hs”
. La forma más sencilla de escribir un nuevo programa es introduciendo :edit <nombre_fichero> en el prompt de Hugs:
Hugs> :edit “H:\\declarativa\\suma. SECCIÓN 2. se ha utilizado una función “show” que muestra el resultado de la expresión.hs”
Este comando editará el fichero suma. Para ello. Hugs tiene configurado éste como editor por defecto. A continuación cargaremos el fichero. Nos servirá el bloc de notas de Windows. Durante la edición del fichero no podremos acceder a la ventana de Hugs. ejecutar
Hugs> :type $$ Hugs muestra “1+1 :: Num a => a”
La expresión inicial no se ha reducido.
Integer. Float y Double.hs”
.José carPio. por ejemplo incluye a los tipos Int.
Podemos comprobar si se han cargado las funciones en memoria ejecutando :info <nombre_función>:
Hugs> :info suma suma :: Int -> Int -> Int
El resultado es la cabecera de la función suma. La clase Fractional incluye al tipo Float y al tipo Double.. gonzalo antonio aranDa.Programación Declarativa. José marco. SECCIÓN 4. A continuación veremos algunos ejemplos que muestran particularidades de Haskell con los tipos de datos:
Hugs> :edit “H:\\declarativa\\tipos. TIPOS DE DATOS En el siguiente gráfico se muestra la relación entre las clases que agrupan los diferentes tipos de datos:
La clase Num.
veamos qué tipo de dato esperaba la función “/” (divide). a) La primera es dejando igual la cabecera y utilizando una de las funciones que convierten tipos. es decir Float o Double y que todos los argumentos son del mismo tipo.hs:3 .116
A continuación guardaremos el fichero y lo cargaremos en memoria:
Hugs> :load “H:\\declarativa\\tipos. Ejecutaremos antes :load sin argumentos para que elimine de la memoria el fichero con el error y podamos proseguir.
Hugs> :load Hugs> :info / infixl 7 / (/) :: Fractional a => a -> a -> a
-. Para solucionar el problema. Por esta razón no podemos definir la función divide del tipo Int->Int->Float Podemos solucionar este problema de dos formas.hs”
Al cargar el fichero aparece el siguiente mensaje de error:
ERROR file:h:\declarativa\tipos. En este caso utilizaríamos la función fromIntegral:
Hugs> :edit “H:\\declarativa\\tipos.hs”
.Type error in explicitly typed binding *** Term : divide *** Type : Int -> Int -> Int *** Does not match : Int -> Int -> Float
Este error indica que no coincide la definición que hemos dado a la cabecera con la cabecera que Hugs ha deducido.class member
La cabecera indica que el tipo de dato que acepta la función “/” es de tipo Fractional.
Hugs> :load “H:\\declarativa\\tipos.hs” Main> divide 4 2 2.0
Nótese que el prompt Hugs> indica que no hay ningún módulo cargado y que el prompt Main> indica que hay al menos un fichero cargado en memoria. b) La segunda solución pasa por cambiar la cabecera para que acepte valores de entrada de tipo Fractional:
Main> :edit “H:\\declarativa\\tipos.hs”
Main> :load “H:\\declarativa\\tipos.hs” Main> divide 4 2 2.0
Para terminar con los tipos de datos, recordar que aunque Haskell es capaz de inferir una cabecera para la función a partir de la implementación, nosotros escribiremos siempre la cabecera. SECCION 3. RESUMEN
:t :type :? $$ :load :edit :r :reload :set :set +/-opción :set +t :q Muestra el tipo de dato de la expresión Muestra el tipo de dato de la expresión Muestra la lista de comandos básicos Última expresión introducida Cargar un fichero Abre el editor por defecto Actualiza los módulos cargados Actualiza los módulos cargados Muestra la lista de opciones para activar/desactivar Activa o desactiva una opción. Activa la opción que muestra el tipo de dato Salir de Hugs
Material complementario - Utilizar el manual: “A tour of the Haskell Prelude” http://www.cs.ut.ee/~varmo/MFP2004/PreludeTour.pdf para consultar las funciones más usuales definidas por defecto en Hugs. Ejercicios 1. Implementar la función doble que recibe un número y devuelve el doble. 2. Implementar la función cuadrado que recibe un número y devuelve su cuadrado. 3. Implementar la función esPositivo que sea verdad cuando su único argumento sea mayor que 0 4. Dada la siguiente definición del máximo de dos números: max (x,y)= implementar una función que devuelva el mayor de dos números de tipo Float.
(x+y)+│x-y│ 2
5. Utilizando la función anterior, definir una nueva función que calcule el máximo de tres números. 6. Escribir la función entre 0 y 9 que tome un entero y devuelva True si está entre 0 y 9 y False en otro caso. 7. Implementar la función esMultiploDe3 que tome un entero y devuelva True si éste es múltiplo de 3 o False en otro caso. 8. Definir la función loscuatroiguales::Int->Int->Int->Int->Bool que devuelva True si los cuatro argumentos son iguales. 9. Utilizar la función anterior para crear una nueva llamada lostresiguales que reciba tres enteros y sea cierta si los tres enteros son iguales. 10. Definir la función cuantosiguales::Int->Int->Int->Int que recibe tres enteros y devuelve un entero indicando cuántos de los tres argumentos de entrada son iguales. 11. Implementar la función del ejercicio 4 utilizando sólo valores enteros.
Listas en Haskell En esta sesión veremos algunos mecanismos de Haskell para definir listas. SECCIÓN 1. LISTAS En Haskell, una lista es una secuencia de valores del mismo tipo, por ejemplo [1,2,3,4,5] es una lista de 5 enteros (tipo Int), por otro lado [True, False, False, True] es una lista de 4 elementos booleanos (tipo Bool). Haskell permite definir listas infinitas, por ejemplo [1..] es una lista infinita de enteros. Una cadena de texto (tipo String), es una lista de caracteres (tipo Char). Si pedimos a Haskell que evalúe la lista [‘a’, ‘b’, ‘c’] responderá que el resultado es “abc”. Haskell proporciona un mecanismo para definir fácilmente listas. Evaluar las siguientes listas en el prompt de Hugs:
a) [1..10] b) [15..20] c) [15..(20-5)] d) [‘q’ .. ‘z’] e) [14 .. 2]
¿Los resultados son los esperados? Para números, caracteres y otros tipos enumerados (cualquier tipo en el que tenga sentido hablar del sucesor), la expresión [m..n] genera la lista [m,m+1,m+2,..,n]. Si n es menor que m (como en el ejemplo e) anterior), Haskell devuelve una lista vacía. De forma más general, la expresión [m,p..n] genera la lista:
[m,m+(p-m), m+2(p-m),m+3(p-m)..n’]
dónde n’ es el mayor valor de la forma m+k*(p-m) ≤ n. Con el fin de aclarar esta notación, ejecutar los siguientes ejemplos en Hugs:
a) [1,3..10] b) [15,15.5..20] c) [1,1.2..2.0] d) [‘a’,’d’..’z’] e) [10,8 .. -3] f) [1,2 .. 0]
¿Qué sucederá al evaluar esta expresión: [1,1..5]? Utilizar el menú Actions -> Stop, si fuese necesario.
4). Ejemplo:
[(x.(1.(7.y) | x <.(4. Las variables se definen en el generador.[1. los elementos aparecen en el orden que fueron generados.(8.Int)] -> [[Int]] aniadirPares listaPares = [[m+n] | (m. la siguiente función es una generalización de la expresión anterior:
aniadirPares::[(Int. y (x. es par y menor que 15 (even es una función definida en el módulo Prelude estándar de Haskell). Compruebe como los elementos aparecen en el orden generado.. x < 15]
De nuevo.6). Evaluar:
[[m+n]|(m. 20]. no es posible utilizarla en otra. 2) Restricciones (puede que no haya ninguna) y 3) Transformación...8)]. even x.n) <listaPares.3).19 . Haskell muestra el siguiente error Undefined variable “y” .3). Por ejemplo.
.20] es el generador. 1]. Esta expresión genera una lista de pares (x. y == 1]
En este caso. n == 2*m]
La declaración de tipos de la función especifica que acepta una lista de pares de enteros y devuelve una lista de listas de enteros.. El generador produce elementos de una lista. Podemos utilizar la notación extendida de listas para definir funciones más generales. las restricciones filtran algunos elementos de los generados y la transformación utiliza los elementos seleccionados para generar una lista resultado.True)|x<-[20. NOTACIÓN EXTENDIDA DE LISTAS La definición de una lista con esta definición consta de tres partes: 1) Generador.True) | x <. True) es la transformación. x < 15]
En la expresión anterior.120
SECCIÓN 2.n)<-[(3. Si una variable no aparece en esta sección.[1 . Ahora probar la siguiente expresión:
[(x. x <. Comprobar el resultado anterior.n) para aislar una determinada componente de la tupla.True) donde x está entre 1 y 20. con aquellos pares cuya segunda componente es el doble que la primera.[1.even x.5]. con la evaluación de:
[(x. Esta expresión demuestra como utilizar plantillas (m.n==2*m]
Esta expresión. las restricciones son even x y x < 15. genera una lista de listas de enteros.
3 .3).. doblarTodos [1.. el siguiente ejemplo muestra cómo utilizar la notación extendida de listas como parte de una función un poco más compleja.(1.x `mod` 2==0]) todosImpares lista=([]==[x|x<-lista. UTILIZACIÓN DE PLANTILLAS CON LISTAS La siguiente función utiliza la notación extendida de listas.lista y una transformación 2*x. 20] todosImpares [1.n):resto) = [m+n] : aniadirPares resto
todosPares.6).(7.(8. todosImpares::[Int]->Bool todosPares lista=(lista==[x|x<-lista.5] devuelve una lista con cinco elementos. una versión de doblarTodos utilizando recursividad:
doblarTodos::[Int]->[Int] doblarTodos [] = [] doblarTodos (cab:resto)=2*cab : doblarTodos resto
A continuación..3 .8)] aniadirPares [(3. evaluar las siguientes expresiones:
todosPares [1 . 20] todosPares [1. una versión recursiva de la función aniadirPares. El resultado de la lista contiene siempre el mismo número de elementos que la lista original puesto que la definición no incluye ninguna restricción. 20] todosImpares [1 . Recibe una lista como argumento y devuelve otra lista con todos sus elementos multiplicados por 2.Programación Declarativa..(1.4.4). Por ejemplo.
Probar la función con los siguientes argumentos:
aniadirPares [(3.(8. implementada en la sección anterior:
aniadirPares [] = [] aniadirPares ((m.José carPio..9).3. gonzalo antonio aranDa.3)]
Por último.7).
doblarTodos::[Int]->[Int] doblarTodos lista = [2*x |x <. A continuación .20] todosPares []
SECCIÓN 3.x `mod` 2==0])
Por ejemplo.2. Las siguientes funciones indican cuándo una lista contiene sólo valores pares (o sólo valores impares). José marco.lista]
Esta definición de lista incluye el generador x <.3).(4.
eliminando el resto:
doblarAlgunos::[Int]->[Int] doblarAlgunos lista = [ 2*x | x <. SECCIÓN 4. SELECCIONANDO ELEMENTOS Hemos visto que utilizando la notación extendida de lista podemos filtrar algunos elementos de la lista original añadiendo restricciones. la notación extendida de listas no sirve para encontrar el máximo de una lista. Por ejemplo. Podemos utilizar para este propósito el mismo tipo de plantillas que hemos visto en las funciones recursivas. En esta versión sólo añadimos a la lista aquellos elementos que satisfacen que x < 10. Por ejemplo. consideremos la siguiente función que suma los elementos de una lista de enteros:
sumaLista::[Int]->Int sumaLista [] = 0 sumaLista (cab:resto) = cab + sumaLista resto
. podemos comprobar cómo la definición recursiva utiliza exactamente la misma transformación que la implementación utilizando notación extendida de listas.lista. no proporciona un modo de convertir listas en algo que no sea una lista. COMBINANDO RESULTADOS La notación extendida de listas es útil para convertir listas en otras nuevas listas. Por ejemplo. La idea es que podemos combinar un elemento de la lista con el resultado obtenido por la llamada recursiva.n):resto) | n == 2*m = [m+n] : aniadirPares resto | otherwise = aniadirPares resto
SECCIÓN 5. Otro ejemplo similar es esta implementación de la función aniadirPares utilizando recursividad:
aniadirPares [] = [] aniadirPares ((m. x < 10]
A continuación una versión de la función doblarAlgunos utilizando recursividad:
doblarAlgunos [] = [] doblarAlgunos (cab:resto) | cab < 10 = 2*cab : doblarAlgunos resto | otherwise = cab : doblarAlgunos resto
Esta función es similar a la función doblarTodos excepto porque no se añaden todos los elementos 2*x.122
Un vez más. la siguiente función acepta una lista de enteros y devuelve el doble de todos los elementos menores que 10. sin embargo.
no utilizar reverse [x | x <.[10.6. y por que no tiene sentido devolver una lista vacía en la primera ecuación..8.16. A continuación veremos otros dos ejemplos de funciones recursivas que combinan el primer elemento de la lista con el resultado de evaluar el resto de misma.11.[8]. De la misma forma.(6. (18. José marco. [[10].9].8.6.8.8.[10.False)] 6. la respuesta debe utilizar el generador x<.[4].9.[4].7.4.True.6.False).20)] 8.(17. ya que sumaLista devuelve un entero.[5.13]] 9. [[2].(19.12..[5.4].(9.4].True. [11.False.7. [[4].[6].10] como generador.6.False)] 7. gonzalo antonio aranDa.18.6.9.2. [[5.False. salvo por el uso del operador “+” para combinar los resultados.
1.[2].3.7.[1 .8.7.19.(15. [(3..8.
Podemos comprender cómo esta definición es similar a la que hemos visto anteriormente.12.. En la primera función se utiliza el operador “+” para sumar el cuadrado (cabeza*cabeza) del primer elemento:
sumaCuadrados::[Int]->Int sumaCuadrados [] = 0 sumaCuadrados (cab:resto) = cab*cab + sumaCuadrados resto
En el segundo ejemplo se utiliza el operador “++” para concatenar la primera de las listas con el resultado de evaluar el resto de una lista de listas:
concatena::[[a]]->[a] concatena [] = [] concatena (cab:resto) = cab ++ concatena resto
Ejercicios Generar cada una de las siguientes listas utilizando la notación extendida de listas.[6.4]]
.6.False). [(5. y no debe añadir a esta definición ninguna llamada a función: por ejemplo.[10]] 3.. cada solución debe tener la siguiente forma.14).15.José carPio. 10]] para crear la lista [10.[7].(15.True).14.13.reverse[1 .1].10.[5.16.17.7].(10.[12.False).True).10.True. [(11.True).[5].False] 5. [21.False.[1 .11.9.4].False). Es decir.6.[1.(15.[8.18).True.(13.[6].. 10].10]] también están prohibidas.5.(40.10.[1]] 4.1]] y [x|x <.[9]. 11]. donde se deben completar los blancos y sólo los blancos:
[ ________________ | x <.[3]. modificaciones del tipo [x|x <.Programación Declarativa. [True. con la lista [1.12).1] 10.16).6. 10] _________________]
De forma más explícita.20] 2.9..True).6.(12. False. en vez del operador “:”.[8].
3.(-3.True]. Crear una expresión con la que se obtengan los primos entre 1 y 100.[6.6]. Por ejemplo:
Main> evaluaciones [1.[False.”. 3. Programar una función evaluaciones con la siguiente cabecera evaluaciones::[a]->[(a->b)]->[[b]] La lista de listas resultante contiene listas con los resultados de aplicar a cada uno de los valores de la primera lista las funciones de la segunda lista. Llamar a las nuevas funciones mapea y filtra. 4. 1.2. Implementar una función que devuelva la descomposición en factores primos de un número entero. tuplas.9]
Main> divisores 9 [1.(3.False ].124
Patrones.[False.[True. tuplas.((-3.9]]
6.14. Componer la lista de funciones utilizando el operador de composición “.
.14)] cumplen que el seno es mayor que 0.False. El resultado para este ejemplo será:
[[False. triple] [[2. 5.False. Averiguar cómo funcionan las funciones map y filter e implementarlas utilizando la notación extendida de listas.False]. Utilizar la función anterior para evaluar si los siguientes valores [0.False.3]. 3. La función devolverá una lista de tuplas tal que la primera componente será el factor primo y la segunda será el número de veces que dicho factor primo divide al argumento original.False.3] [doble.False.False].14/2). Utilizar la notación extendida de listas para este ejercicio.[True. Utilizando la función anterior.False]]
7.14)/2). el coseno es 0 y la tangente es 0. recursividad y notación extendida de listas.[4. recursividad y notación extendida de listas en Haskell En esta sesión realizaremos ejercicios utilizando patrones. No consideraremos al número 1 como primo. Implementar la función divisores que recibe un argumento entero y que devuelva la lista de sus divisores. programar la función primo que devuelva verdadero en caso de que su único argumento entero sea un número primo.
gonzalo antonio aranDa.2.10]
9.(5.1)]
8.1).. Programar la función quita_blancos que elimine los blancos iniciales de una cadena de caracteres.6. Revisar los ejercicios realizados e intentar localizar los puntos en los que se utilizó alguna de las características más importante de Haskell: currificación y funciones de orden superior.Programación Declarativa.
.4] Main> eliminarMientras (<5) [1.
Main> descomposicion 60 [(2.(3.
Main> tomarMientras (<5) [1.2).7.José carPio.3...8.
Main> quitaBlancos “ “bcd fgh” bcd fgh”
10.10] [5. Averiguar qué devuelven las funciones takeWhile y dropWhile e implementar su propia versión.9. Llamar a las nuevas funciones tomarMientras y eliminarMientras. José marco.10] [1.
Implementar una función que aproxime el cálculo de la integral de una función en el intervalo [a. Esto nos dará un valor aproximado de pi. En el centro del cuadrado fijaremos en centro de referencia (0. Por último.a2.
integral funcion a b t
2. b] y dado un factor de precisión t. Para obtener el valor aproximado de pi utilizaremos un cuadrado de lado 2.y2): d=
√ (x
.y1) y (x2. (Febrero 2006) Implementar una función que aproxime el valor de pi .x1)2 + (y2 . Cuanto menor sea t. (Noviembre de 2006) Implementar en Haskell una función que calcule la clave hash de una cadena. contaremos cuantos centros de los cuadrados de la rejilla están dentro del círculo. 1.….0).
Ejercicios de Haskell de exámenes anteriores En esta última sesión de Haskell realizaremos algunos ejercicios aparecidos en exámenes anteriores. más precisión tendrá la aproximación. Haremos una rejilla dentro del cuadrado de lado t.
Área del círculo: A = � * r2 Distancia entre los puntos (x1.an] ) = a1*pn+a2*pn-1+…+p1*an. La función hash utilizada es:
f ( [a1.y1)2
union conjunto1 conjunto2: devuelve una lista que es la unión de los dos conjuntos (SIN REPETICIONES).José carPio.Programación Declarativa. False en caso contrario.. implementar las funciones: pertenece elemento conjunto: devuelve True si un elemento pertenece a ese conjunto. 4. p4=7 … ). iguales conjunto1 conjunto2: devuelve True si dos conjuntos son iguales. gonzalo antonio aranDa. (Septiembre 2007) Suponiendo que se implementan en Haskell los conjuntos como LISTAS SIN REPETICION. p2=3.
Donde los ai son los caracteres incluidos en la lista y pi son los i-esimos números primos ( p1=2.
. p3=5. subconjunto conjunto1 conjunto2: devuelve True si el primer argumento es subconjunto del segundo. José marco.
PRÁCTICAS CON PROLOG
pl’)). La forma más sencilla de escribir editar un nuevo programa es escribir
edit(file(‘nombre_fichero.José carPio. gonzalo antonio aranDa. SWI-Prolog tiene configurado este editor por defecto. EMPEZANDO • Seleccionar el arranque del sistema Operativo Windows XP. Utilizaremos la extensión “. El fichero se guardará por defecto en el directorio “Mis documentos\Prolog”. EJECUTAR SWI-PROLOG • En el menú “Inicio” de Windows seleccionar el programa SWI-Prolog
• Aparecerá una ventana como ésta:
• Desde esta ventana cargaremos los programas y haremos las consultas. José marco. SECCIÓN 5..
Introducción al entorno SWI-Prolog En esta primera práctica nos familiarizaremos con el entorno de programación de SWI-Prolog. SECCIÓN 4. SECCIÓN 1.pl’.pl’)).pl” para los programas Prolog. ESCRIBIR UN PROGRAMA Para escribir un programa utilizaremos un editor de texto que no introduzca caracteres especiales.Programación Declarativa. Nos servirá el bloc de notas de Windows.
Este comando editará el fichero ‘nuevo. Escribiremos lo siguiente teniendo en cuenta que los predicados y las constantes empiezan con minúscula:
. en el prompt de SWI-Prolog: 1? – edit(file(‘nuevo.
? – consult(‘nuevo.
Podemos comprobar si.
Por la hipótesis del mundo cerrado. efectivamente se cargó el fichero utilizando la orden listing.pl’). Durante la edición del fichero no podemos acceder a la ventana de SWI-Prolog.futbol). Yes ?-
A partir de este momento podemos empezar a hacer consultas
? – hombre(antonio). Yes ? – hombre(federico).132
Guardaremos el contenido del fichero y cerraremos la ventana. Modificaremos el programa anterior para incluir las siguientes líneas:
hombre(persona):. lo no definido es falso.gusta(Persona. Yes ? – hombre(manuel). hombre(antonio). que mostrará el programa cargado. hombre(federico). gusta(manuel.
.listing. No. hombre(luis). Cargaremos el fichero con la orden consult(‘<nombre_fichero>’).
? .futbol).
Después de modificar un fichero.
Realizaremos ahora la consulta anterior ¿Hombre manuel?
? hombre(manuel).
?. no cambia de valor. X = 1+1.José carPio.make.
Dos términos unifican: 1) Si no tienen variables.. Tras unificar un valor a una variable. actualizamos los cambios ejecutando la orden “make”. unificarán si es posible encontrar una sustitución de las variables de forma que lleguen a ser idénticos. Yes
Los operadores más utilizados en Prolog son “=”. José marco. “==”. una vez que se instancia. ”=” leeremos unificación. la variable deja de estar libre y diremos que la variable está instanciada. El operador de unificación no evalúa operaciones aritméticas.Programación Declarativa. Yes ”==” identidad
. unifican si son idénticos (iguales carácter a carácter). Una variable.
Tendremos en cuenta que Persona es una variable y la escribiremos en mayúscula. 2) Si tienen variables. “is” y “=:=”. Antes de unificar una variable a un valor diremos que la variable está “libre” o “sin instanciar”. gonzalo antonio aranDa.
0):. Fuera de una cláusula la variable no puede ser referenciada. X = 2 ?-
“=:=” evalúa expresiones aritméticas y compara. Evalúa expresiones aritméticas a derecha e izquierda y es cierto si el resultado de las evaluaciones es el mismo valor. Yes
SECCIÓN 6.2 == 1+1. Evalúa a la derecha y unifica con la izquierda.
”is” evalúa expresiones aritméticas.X = uno.
.X is 1+1.X = cero. Decimos que el ámbito de la variable es la función en la que está definida. En Prolog el ámbito de una variable está restringida a una cláusula.
?. en el programa Prolog:
nombre_numero(X. SECCIÓN 7. ÁMBITO DE UNA VARIABLE En la mayoría de los lenguajes de programación. si la variable se define dentro de una función.134
?. Esta es una de las diferencias más importantes de Prolog respecto a la mayoría de lenguajes de programación. No. 1):. De este modo.
la variable X que aparece en el consecuente de la primera cláusula es la misma que la que aparece en el antecedente de esa misma cláusula pero es diferente de la variable X que aparece en consecuente y antecedente de la segunda cláusula. nombre_numero(X.2 =:= 1+1. la variable puede ser referenciada desde cualquier punto de la función. PREDICADOS DE AYUDA Podemos consultar información sobre cualquier predicado con el comando “apropos”
apropos(unification).
SECCIÓN 8. La siguiente consulta que realicemos después del predicado “trace” se ejecutará paso a paso. Yes ? – hombre(manuel).
?. Para avanzar la ejecución pulsaremos la barra espaciadora o utilizaremos los iconos de avance y retroceso. tiene aridad 2. Si el depurador gráfico está habilitado se mostrará la siguiente ventana.trace.guitracer.. Los predicados en Prolog se nombran de la siguiente forma nombre_predicado/aridad. % The graphical front-end will be used for subsequent tracing Yes
Para depurar un programa Prolog utilizaremos el comando “trace”. gonzalo antonio aranDa.
?. José marco.José carPio.
Invocaremos a esta misma ventana con el predicado help.
. Por ejemplo. DEPURADOR Habilitaremos el depurador gráfico con el predicado “guitracer”. La aridad es el número de argumentos que tiene el predicado. el predicado unificación =/2.Programación Declarativa.
X=1. X=2*Y.
. Y). X = Y. X = 2 + 3. = 2. (1+2) = 1+2. b) = f(a. 1+1 = +(1. X = 5. + 3 is X. Comprobar si unifican los siguientes términos:
(a) (b) (c) (d) (e) (f) (g) (h) X X 2 X X 6 Y Y is 2 + 3. X = Y. Ejercicios de Aritmética y Unificación. Y= 7. 2*X is Y*(Y+3). is X + 1. Z is Y*(Y+3). X = mujer(maria). X=Y. is 5.1). Y=1. X=3+4. X = 5. X=2+X. Y=1+1. 5 = 2 + 3. Unificación.136
Ejercicios 1. 2 + 3 = 2 + Y. = 5. X = 2*6.
2. Comprobar si unifican los siguientes términos:
(a) (b) (c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m) (n) (o) (p) X=1. (1+1)+1 = 1+(1+1). 2*X = Y*(3+Y). X = 2 + 3. = 2. X=2. 6 = X + 1. X=2. f(X. is 2 + 3. 6 is X + 1. X=1. X=Y.
.. Implementar el predicado fib(N. no
2.. Precio). José marco. segundo plato y postre con su respectivo precio asociado. fib(4)=3. clasificados en primer plato. fib(3)=2.. fib(5)=5.
?. Resultado) que será cierto si Resultado unifica con el factorial de “Numero”. elaborar un predicado que encuentre un menú completo por un coste menor a N.. Implementar el predicado suma(X. F).
Predicados sencillos en Prolog En esta sesión implementaremos algunos predicados sencillos utilizando recursividad en la mayoría de los casos. gonzalo antonio aranDa.
0=0 1 = s(0) 2 =s(s(0)) 3=s(s(s(0)))
4. Que será cierto cuando “F unifique con el N-ésimo número de Fibonacci”. Ejemplo:
menu(Primer_plato. Implementar natural(X) que será cierto si X es un número natural. . Precio < 50. Implementar el predicado Prolog factorial(Número. fib(2)=1. Dada una serie de platos. Postre.. Estos números son:
fib(1)=1.nat(6). Segundo_plato. Ejercicios 1. yes ?. 3.Programación Declarativa. Primer_plato=sopa Segundo_plato=jamon Postre=helado
5. fib(n)=fib(n-1) + fib(n-2).nat(-13).José carPio.Z) que representa la suma de dos números naturales utilizando la representación del matemático italiano Giuseppe Peano (1858–1932) que está basada en la utilización del símbolo 0 y el predicado s(X) que representa el siguiente de X.
Z) y producto(X.F) sea reversible. Este ejercicio es algo más complicado que los anteriores y para solucionarlo será necesario utilizar la aritmética de G.Z).Y.s(s(0))) N=s(s(s(0))) Yes
. es decir. implementar los predicados resta(X.Z).138
…… suma(s(0). que sea posible hacer la llamada dejando el primer argumento libre e instanciando el segundo.s(0). Utilizando la representación del ejercicio anterior.Y. 7. Ejemplo:
fib(N. Z=s(s(0)) Yes
6. Implementar el ejercicio 3 de forma que el predicado fib(N. Peano.
generar otra lista de longitud 2n que sea un palíndromo. [X.Programación Declarativa. Z| A] = [a. Z] = [a. crear una lista con esos dos elementos. Ejercicios 1. b. b. d]. e ) Borrar un elemento en una lista: 1) Borrando sólo una aparición del elemento. c. Y] Y| Y| Y. b. 2) Cambiar todas las apariciones de ese elemento. Y| = [a. Tratar de predecir la unificación que resulta en los siguientes ejemplos y confirmar luego ejecutando cada uno:
???????[X| [X. b].. Z]. g) Dada una lista de longitud n. Y. 3) En la posición N de una lista. a] = [Z. [X. b. Z] = [a. 2) Al final de la lista. d]. Definir en Prolog los siguientes predicados recursivos para manejar listas: a) Dados dos elementos. W]. b) Insertar un elemento en una lista: 1) Al comienzo de la lista.
Predicados sobre listas en Prolog En esta sesión implementaremos algunos predicados sobre listas. 2) Borrando todas las apariciones de ese elemento. José marco. c].José carPio. f) Cambiar un cierto elemento por otro: 1) Cambiar sólo una aparición del elemento. c) Concatenar dos listas y usar ese predicado para implementar los predicados: 1) prefijo 2) sufijo 3) sublista d) Invertir una lista.
2. Z] = [a. b. Y. [X. [X. Z| A] = [a.
. c. c]. gonzalo antonio aranDa. [X.
y es también una lista ordenada..8.1. Menores).V). +L2. -Men) que se cumpla si la lista May contiene los elementos mayores de un número N de la lista LOrig y Men contiene los elementos menores de un número N de la lista LOrig. Escribir un predicado pEscalar(+L1.[2.2...4..2. Los dos vectores vienen dados por las dos listas de enteros L1 y L2.. 6. -Resul) de forma que.x2. i) Desplazar una posición a la izquierda todos los elementos de una lista. L es la lista de divisores de N en orden creciente.3. P = [1.3.1. 2.[0. si N es 24... +LOrig. pasar de la lista [x1..3.3] daría P = [1. Con divisores(6. 1. R) que se cumple si la lista R contiene los elementos ordenados de Lista. pasar de la lista [x. 2. 5. 3. Mayores. permuta(+L.1]) ha de responder NO (la lista no esta ordenada!).x1.xn] a la lista [x2.xn] a la lista [xn.5]. 7]
5.1. y P no..24]. siendo L1 y L2 dos listas ordenadas. -May. deben permitirse permutaciones repetidas.. V = [1. -P). El predicado debe fallar si los dos vectores tienen una longitud distinta. Resul). Debe contestar YES si una L dada es la lista de los divisores de un N dado y NO en caso contrario. divisores(+N. Por ejemplo. 8.. P = [2.2..2.
?-ordena([3.3].140
h) Desplazar una posición a la derecha todos los elementos de una lista. Definir un predicado mezclar_ord(+L1. Definir un predicado dividir(+N. Dado un natural N. Ejemplo: L = [1. se cumple que la lista Resul contiene la mezcla de los elementos de las dos listas L1 y L2.0].
?-dividir(4. Resul = [0.
?-mezclar_ord([1. ordenación y mezcla. 3]
a) Como permutaciones de una lista. 3. -P) que significa “P es el producto escalar de los dos vectores L1 y L2”.2].[3.7].x2.5. En el caso de que la lista a permutar tuviera elementos repetidos.2.6. y debe poder generar L para un N dado. Escribir un predicado prod(+L.3].
.. 9. +L2. b) Como separación de listas. Por ejemplo. ?L).x1]. 2. L será [1.xn-1]. ?P) que significa “P es el producto de los elementos de la lista de enteros L”. “La lista P contiene una permutación de los elementos de la lista L”.2]. etc. Por ejemplo. La lista L inicialmente estará instanciada.xn.6. Debe poder generar la P y también comprobar una P dada. 0]
4. 3.. Definir un predicado ordena(Lista. 7. Mayores = [5] Menores = [1.. 3. hasta que encuentre la ordenada..
c) Unir dos conjuntos. Adoptando esta representación. f ) Dada una lista de elementos con repeticiones. b) Incorporar un elemento a un conjunto. 11.
. a) Determinar si un elemento pertenece a un conjunto. multiplicidad). construir un conjunto que contenga todos los elementos de esa lista.Programación Declarativa. a) Determinar si un elemento pertenece a un conjunto. Adoptando esta representación. e) Calcular la diferencia entre dos conjuntos. implementar las siguientes operaciones sobre conjuntos en lenguaje Prolog. José marco..
10. Un MULTI-conjunto puede ser modelado mediante una lista de elementos (elemento. d) Hallar la intersección de dos conjuntos. b) Calcular la multiplicidad de un elemento. Un conjunto puede ser modelado mediante una lista de elementos sin repeticiones.José carPio. implementar las siguientes operaciones sobre conjuntos en lenguaje Prolog. gonzalo antonio aranDa.
inorden/2 preorden/2 postorden/2 anchura/2 (de izquierda a derecha)
Árboles genéricos Repetir los ejercicios anteriores. 2. Escribir el predicado miembro/2 que indique si un elemento X. retornando el nuevo árbol en NA (asumir que si el elemento a ser insertado ya pertenece al árbol. Implementar el predicado profundidad/2 que será cierto cuando el segundo argumento unifique con la profundidad del árbol. preorden y postorden del ejercicio 9. 9. Implementar los predicados iguales/2.
. 4. considerando árboles genéricos en lugar de binarios. Implementar el predicado cuenta_nodos/2 que cuente el número de nodos que tiene un árbol binario. A. insertar(E. 8. Implementar el predicado cuenta_hojas/2 que cuente el número de nodos HOJA (que no tienen ningún hijo) que tiene un árbol. simetricos/2 e isomorfo/2 que serán ciertos cuando dos árboles cumplan dichas propiedades. 6. excepto los recorridos en inorden.142
Árboles en Prolog Árboles binarios 1. Implementar los siguientes predicados que transforman los recorridos de un árbol en una lista. Implementar el predicado cuenta_internos/2 que cuente el número de nodos INTERNOS (que tienen al menos un hijo) que tiene un árbol binario. Implementar en Prolog los siguientes predicados: crearArbolVacio(X): retorna en X un árbol vacío. NA): inserta el elemento E en el árbol A. 7. 5. 3. pertenece a un árbol. entonces se retorna el mismo árbol). Árboles binarios de búsqueda. Implementar el predicado suma_nodos/2 que sume el contenido de todos los nodos de un árbol. Implementar el predicado balanceado/1 que será cierto cuando el árbol esté balanceado.
5.nil..t(7.nil.nil. equilibrado(A): determina si el árbol A está equilibrado o no. Implementar un predicado que construya un árbol binario de búsqueda a partir de una lista de números enteros.
altura(A. Post.nil)))
. Post e In sus recorridos en preorden. X): retorna en X la altura del árbol A.1].José carPio.t(5. recorridos(A. Ejemplo:
?.construir([3. In): a partir del árbol A retorna en Pre. postorden e inorden respectivamente. gonzalo antonio aranDa. T = t(3.t(2.T).Programación Declarativa.7. Pre. José marco.2.t(1.nil).nil).
Gr) que nos diga el grado de un nodo dentro de un grafo.Cam). El grado de un nodo es el número de nodos con los que se conecta. que calcule la distancia entre cualquier par de vértices.130 Km. que compruebe que un grafo es totalmente conexo.N. ○ pintargrafo(G. recorre el grafo pasando exactamente una vez por cada arco.N2. Mediante backtraking deberá encontrar todos los caminos posibles. ○ grado(G. ○ conexo(G). Representar el grafo de la figura en Prolog: Escribir un programa Prolog que encuentre todos los caminos posibles entre Madrid y Oviedo. Implementar dos versiones: una que admita ciclos y otra que no. que encuentre el camino entre dos nodos y devuelva una lista con los nodos por donde pasa. Se dice que un grafo es totalmente conexo cuando existen caminos entre todos sus nodos. introducir dos arcos más en el grafo: • León-Palencia (N 610. aj).) y comprobar el comportamiento del programa. ¿Qué ocurriría si el grafo propuesto no fuera dirigido y acíclico como el propuesto? Para analizar esta posible circunstancia.Ciclo) .N1.N1.144
Grafos en Prolog 1. • La distancia recorrida por cada uno de ellos.
. ○ listagrados(G. de forma que dos nodos adyacentes no pueden tener el mismo color. es decir.) • Palencia-Valladolid (N 620. Crear un programa en Prolog con los predicados: ○ camino(G. 47 Km. construyendo una lista de las ciudades por las que pasa.L) que genere una lista con todos los nodos y sus grados. 2. Proponer una solución para evitar los bucles e implementarla.LC. 3. Escribir un programa Prolog que pinte un sobre como el de la figura sin levantar el lápiz del papel. ○ ciclos(G.LNod) que pinte el grafo G con una lista de colores LC y nos devuelva una lista LNod con cada uno de los nodos y su color. Esto consiste en encontrar un camino que vaya de un nodo a él mismo. etiquetados por la distancia que separa al vértice ai del vértice aj. ○ distancia(G. Añadir los elementos necesarios para que calcule: • La lista de las carreteras por las que pasa cada camino. que encuentre los ciclos dentro de un grafo. A). Un grafo puede ser expresado como G = (V. donde V es el conjunto (lista sin repetición) de vértices y A el conjunto de arcos (ai.N2.D).
More From This UserSkip carousel125 AngularJS and IonicJs StringsDiagrama Carro Seguidor de LineasResponsive Web Desing (Generalidades)Guia Optimizacion Motores BusquedaLinux Commands on AndroidSeñales y Sistemas - FiltrosVoice Production Death Metal SingersAndroid Java Tutorial 4Android Java Tutorial 3Android Java Tutorial 1Informacion General de Haskell - Haskell BegginersAlgunos Metodos Nuemricos Con HaskellIntHaskell98Calculo de Parciales en Ma Thematic AAjuste de Curvas
Sign up to vote on this titleUsefulNot usefulMaterial Para Aprender Haskell by Jonathan Neyra Nieves0.0 (0)EmbedDownloadRead on Scribd mobile: iPhone, iPad and Android.Copyright: Attribution Non-Commercial (BY-NC)List price: $0.00Download as PDF, TXT or read online from ScribdFlag for inappropriate contentMore informationShow less
RelatedGuia de Ejercicios y Comandos para el uso de Haskellby gubatronLenguaje Haskellby shoykeEjemplos Haskellby Santiago Alboej_prog_Haskellby Jose Astuvilca FusterAprende Haskell Por El Bien de Todos-reducidoby Harold AponteFo-1.Opengl Es-opengl Es Androidby Ivan Arley Osorio FigueroaTecnologias de Ethernetby Giancarlo Villanueva Andrade2013-Temas de PF Con Haskellby Ariadnhe CorleoneGuiaParadigmasdeProgramacionby Francisco Javier Garcia GilUnidad 1 Automatas Finitos Deterministasby Eduardo Cano VelaPiensa en Haskellby Yüriique Yûmme TskiinoHaskellby rbarr114354294941-Ejercicios-prologby alexdazaoProgramacion Logica y Funcionalby Abraham HernandezEjercicios Prologby Tulio RomeroConstrucción modular de una Máquina de Turingby Ivan Hdztrabajo final1_VHDLby Elyel Surco MProyecto Prolog PDFby ebudhyManual de Prologby mili-23Misioneros y Canibales Solucionby Ernesto Lee RuizIde Avanzado de Visual Prologby DREYKKONEjercicios de Vhdl Para Examenby Luisangelmtz Mtz[002] Manual SWI Prolog - Interfaces Graficasby Gust AvitoUnidad3Tecnologias inalambricasby Esoj LiñablaSimilar to Material Para Aprender HaskellSkip carouselGuia de Ejercicios y Comandos para el uso de HaskellLenguaje HaskellEjemplos Haskellej_prog_HaskellAprende Haskell Por El Bien de Todos-reducidoFo-1.Opengl Es-opengl Es AndroidTecnologias de Ethernet2013-Temas de PF Con HaskellGuiaParadigmasdeProgramacionUnidad 1 Automatas Finitos DeterministasPiensa en HaskellHaskell54294941-Ejercicios-prologProgramacion Logica y FuncionalEjercicios PrologConstrucción modular de una Máquina de Turingtrabajo final1_VHDLProyecto Prolog PDFManual de PrologMisioneros y Canibales SolucionIde Avanzado de Visual PrologEjercicios de Vhdl Para Examen[002] Manual SWI Prolog - Interfaces GraficasUnidad3Tecnologias inalambricasAct 6.4.5 - Reto de sumarización de rutaEstructuras en ensamblador(data, stack, code, model)Material Para Aprender Haskell

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución