Ciencias de la Computación FAMAF

• Dada la siguiente base de conocimiento en prolog, que especifica tres ingredientes necesarios para cocinar un platillo y los que tengo en la casa, crear las reglas necesarias para saber si podremos cocinar un platillo.

ingredientes(tortilla,huevos,aceite,papa).
ingredientes(pizza,prepizza,salsa,queso).
ingredientes(ensalada,lechuga,tomate,aceitunas).
tengo(huevos).
tengo(aceite).
tengo(papa).

Ejemplo: ''puedoCocinar(tortilla). true. puedoCocinar(pizza). false.''

puedoCocinar(X) :- 
   ingredientes(X,A,B,C) ,
   tengo(A) , tengo(B) , tengo(C).

• Definir la función sumaPar :: (Int,Int) → Bool, que, dado un par de enteros, devuelve true si la suma de ambos es par.

Ejemplo: ''sumaPar (2,5) = false.''

sumaPar :: (Int,Int) -> Bool
sumaPar (x,y) = mod (x+y) 2 == 0

• Definir la función sumaMayoresQueN :: Int → [Int] → Int, que, dado un entero n y una lista de enteros, devuelve la suma de todos los elementos de la lista mayores que n.

Ejemplo: ''sumaMayoresQueN 3 [3,5,2,4] = 9''.

sumaMayoresQueN :: Int -> [Int] -> Int
sumaMayoresQueN n [] = 0
sumaMayoresQueN n (x:xs) | x > n     = x + sumaMayoresQueN n xs
                         | otherwise = sumaMayoresQueN n xs

• Usando map, filter y foldr, definir la función porCientoMayorQue :: Int → Int → [Int] → Int, que dado un número n, otro número m y una lista de enteros, devuelve la suma de todos los porcentajes mayores que n. Ayuda: definir una función auxiliar PorCiento :: Int → Int → Int que use la función div que devuelve la división entera de dos enteros.

Ejemplo: porCientoMayorQue 10 50 [22,4,30,10] = 26.

porCientoMayorQue :: Int -> Int -> [Int] -> Int
porCientoMayorQue n m xs = foldr (+) 0 ( filter (>n) ( map (porCiento m) xs ) )

• Definir la parte del sistema de préstamos de una biblioteca que determina si un usuario puede tomar prestado un libro o, si ya está prestado, reservarlo, cumpliendo las siguientes condiciones:
  • un usuario puede tener en préstamo un máximo de seis libros simultáneamente
  • un usuario puede tener un máximo de tres reservas
  • un libro se puede prestar si no está en préstamo ni está reservado por otro usuario

Para plantear el problema, deben definir dos funciones (o predicados) con la siguiente semántica:

puedeTomarPrestado -> usuario -> libro -> Bool
puedeReservar -> usuario -> libro -> Bool

Para plantear el problema en haskell, deben definir las dos funciones principales y la estructura de funciones auxiliares, incluyendo sus signaturas de tipos. Fíjense que eso incluye también definir las estructuras de datos que representarán los libros, los usuarios y cómo se registran los préstamos.

Para plantear el problema en prolog, deben definir los hechos y las reglas. Fíjense que eso incluye definir los predicados para libros, usuarios y préstamos.

Deben plantear el problema en los dos lenguajes, y resolverlo completamente en uno de los dos.

En este problema se pueden plantear muy distintas soluciones, ya que el problema es bien complejo y se puede ver de muchas formas.

Una posible solución en prolog:

%% definimos los usuarios como un predicado con tres argumentos: 
  %% el nombre del usuario (o su identificador si el nombre no alcanza para hacerlos únicos)
  %% el número de libros que tiene en préstamo
  %% el número de libros que tiene reservado
%% dejamos para otra regla la actualización de esos números 
 % cuando alguien toma prestado o reserva un libro

usuario(pepe,6,3).
usuario(maría,5,2).
usuario(carla,6,1).
usuario(esteban,0,0).
usuario(marisol,3,3).

%% definimos los libros como un predicado con tres argumentos:
  %% el título del libro (o su identificador si el nombre no alcanza para hacerlos únicos)
  %% si está prestado o no
  %% si está reservado o no
libro("la isla del tesoro",pres,nores).
libro("el lazarillo de tormes",nopres,nores).
libro("los hombres que no amaban a las mujeres",pres,res).
libro("la chica que soñaba con una cerilla y un bidón de gasolina",nopres,res).

%% después de los hechos, definimos las reglas
puedeTomarPrestado(Usuario,Libro) :-
  usuario(Usuario,Prestados,_),
  libro(Libro,nopres,nores),
  Prestados < 6.

puedeReservar(Usuario,_) :-
  usuario(Usuario,_,Reservados),
  Reservados < 3.

Una posible solución en haskell:

puedeTomarPrestado :: (String,Int,Int) -> (String,Bool,Bool) -> Bool
puedeTomarPrestado (_,lp,_) (_,p,r) = lp < 6 && not(p) && not(r)

puedeReservar :: (String,Int,Int) -> (String,Bool,Bool) -> Bool
puedeReservar (_,_,lr) _ = lr < 3

Bonus Track: Definir la función tieneSegmentoOrdenado :: Int → [Int] → Bool, que dado un entero n y una lista de enteros, determina si la lista tiene un segmento de longitud mayor o igual a n cuyos elementos están ordenados de menor a mayor.

Ejemplo: tieneSegmentoOrdenado 3 [5,1,4,11,3,2] = true.
	   tieneSegmentoOrdenado 4 [5,1,4,11,3,2] = false.

Hemos planteado una posible solución que va recorriendo la lista y va contando cuántos elementos encuentra que estén ordenados de menor a mayor. Cuando el número de elementos ordenados alcanza el número de elementos que pedimos que tenga el segmento, la función termina y devuelve True. Cuando encuentra un elemento que es menor al elemento anterior, deja de contar, es decir, pone el contador en 1. Cuando llega a la lista vacía devuelve False.

La función principal es tieneSegmentoOrdenado, que lo único que hace es añadir el argumento contador y pasarle todos los argumentos a la función cuantosOrdenados. La función cuantosOrdenados va comprobando en cada momento si hemos alcanzado la longitud de segmento que estábamos buscando, con la guarda c >= n. Fíjense que si la longitud que buscamos es 0 o 1, nos va a devolver True sin hacer ningún llamado a la función recursiva. Si no, llama a la función recursiva para que recorra la lista y vaya contando la longitud de los segmentos ordenados que encuentra.

La función recursiva es cuentaOrdenado, que va recorriendo la lista. Si encuentra una lista vacía o una lista con un solo elemento, devuelve False, porque llegó al final de la lista sin poder encontrar el segmento que buscaba. Para listas de por lo menos dos elementos, los compara y si el primero es menor que el segundo, entonces suma uno al contador y llama a la función cuantosOrdenados, que comprueba si el segmento que vamos encontrando ya es de la longitud que se pedía en el argumento. Si es así, la función termina con True, si no, vuelve a llamar a cuentaOrdenado. Si el primer elemento es mayor que el segundo, entonces el contador vuelve a su estado inicial, 1, es decir, empieza a contar de nuevo.

tieneSegmentoOrdenado :: Int -> [Int] -> Bool
tieneSegmentoOrdenado n xs = cuantosOrdenados 1 n xs

cuantosOrdenados :: Int -> Int -> [Int] -> Bool
cuantosOrdenados c n xs | c >= n    = True
                        | otherwise = cuentaOrdenado c n xs

cuentaOrdenado :: Int -> Int -> [Int] -> Bool
cuentaOrdenado c n [] = False
cuentaOrdenado c n [x] = False
cuentaOrdenado c n (x:y:xs) | x <= y    = cuantosOrdenados (c+1) n (y:xs)
                            | otherwise = cuentaOrdenado 1 n (y:xs)