Recuperatorio Primer Parcial 2do Cuat 2006 (Paradigmas)
Ejercicio 1: Programación funcional
En ningun item de este ejercicio se puede hacer recursion explicita, salvo que se indique explicitamente lo contrario. Este bien, mal o no resuelto un ıtem, en los ıtems subsiguientes se puede utilizar la funci´on o funciones descriptas en el enunciado como si existieran. Se recomienda no abandonar todo el ejercicio si un iıtem del medio no sale.
El objetivo final de este ejercicio es hacer un programa que busque las raices racionales de polinomios con coeficientes enteros. Consideremos la siguiente representacion de fracciones y polinomios, junto a los observadores para las fracciones 1:
data Frac = F Int Int data Poly = Var | Cst Int | Add Poly Poly | Mul Poly Poly | Neg Poly numer, den :: Frac -> Int numer (F n d) = n den (F n d) = d
Los polinomios entonces estan definidos por induccion como una variable (el polinomio P(x) = x), una constante (el polinomio P(x) = k, k != 0) o la suma, producto o negacion (opuesto) de polinomios. Notar que esta definicion permite definir cualquier polinomio de coeficientes enteros y solo estos (algunos de mas de una manera).
Ejercicio A
Escribir la funcion divisores que dado un entero devuelve la lista de sus divisores, en cualquier orden (el comportamiento esta indefinido para el 0). Notar que el parametro puede ser un entero negativo o positivo y que se deben devolver los divisores negativos y positivos del mismo. Se recomienda utilizar la funcion rem del Prelude que dados dos enteros devuelve el resto de dividir el primero por el segundo (da error si el segundo es cero).
divisores :: Int -> [Int] divisores 15 -> [1,-1,3,-3,5,-5,15,-15]
Respuesta
-- divisores divisores :: Int -> [Int] divisores x = [n | n <- [-x..x], not (n == 0) && rem x n == 0]
Ejercicio B
Escribir un esquema de recursion (fold) para el tipo Poly. Por supuesto, se puede hacer recursion explicita en este ejercicio.
foldPoly :: b -> (Int -> b) -> (b -> b -> b) -> (b -> b -> b) -> (b -> b) -> Poly -> b
Respuesta
-- foldPoly foldPoly :: b -> (Int -> b) -> (b -> b -> b) -> (b -> b -> b) -> (b -> b) -> Poly -> b foldPoly var fcst fadd fmul fneg Var = var foldPoly var fcst fadd fmul fneg (Cst c) = fcst c foldPoly var fcst fadd fmul fneg (Add a b) = fadd (rec a) (rec b) where rec = foldPoly var fcst fadd fmul fneg foldPoly var fcst fadd fmul fneg (Mul a b) = fmul (rec a) (rec b) where rec = foldPoly var fcst fadd fmul fneg foldPoly var fcst fadd fmul fneg (Neg p) = fneg (rec p) where rec = foldPoly var fcst fadd fmul fneg
Ejercicio C
Escribir las funciones addF, mulF y negF que representan la suma, multiplicacion y negacion de fracciones, respectivamente.
addF, mulF :: Frac -> Frac -> Frac negF :: Frac -> Frac
Respuesta
-- addF y mulF addF, mulF :: Frac -> Frac -> Frac negF :: Frac -> Frac addF (F a b) (F c d) = (F (a*d + b*c) (b*d)) mulF (F a b) (F c d) = (F (a*c) (b*d)) negF (F a b) = (F (-a) b)
Ejercicio D
Escribir la funcion eval que dado un polinomio P y una fraccion f, devuelve el resultado de la evaluaci´on P(f).
eval :: Poly -> Frac -> Frac
Respuesta
-- eval eval :: Poly -> Frac -> Frac eval p f = foldPoly f toFrac addF mulF negF p where toFrac x = F x 1
Ejercicio E
Escribir la funcion grado que dado un polinomio devuelve su grado.
grado :: Poly -> Int
Respuesta
-- grado grado :: Poly -> Int grado p = foldPoly 1 (\x -> 0) max (+) id p
Ejercicio F
Escribir la funcion coefIndepte que dado un polinomio devuelve su coeficiente independiente.
coefIndepte :: Poly -> Int
Respuesta
Me parece que una manera es evaluarlo en 0:
-- coefIndepte coefIndepte :: Poly -> Int coefIndepte p = numer (eval p (F 0 1))
Otra sería usando el fold.
Ejercicio G
Escribir la funcion coefPpal que dado un polinomio devuelve su coeficiente principal. Nota: El coeficiente principal de la suma de 2 polinomios no es necesariamente igual a la suma de sus coeficientes principales. 5 Para esta funcion se puede utilizar recursion explicita.
coefPpal :: Poly -> Int
Respuesta
-- coefPpal coefPpal :: Poly -> Int coefPpal Var = 1 coefPpal (Cst i) = i coefPpal (Mul a b) = (coefPpal a) * (coefPpal b) coefPpal (Neg a) = -(coefPpal a) coefPpal (Add a b) | (grado a) == (grado b) = (coefPpal a) + (coefPpal b) | (grado a) > (grado b) = coefPpal a | otherwise = coefPpal b
Ejercicio H
Segun el lema de gauss, las raices racionales de un polinomio con coeficientes enteros son de la forma p/q donde p es un divisor del coeficiente independiente y q lo es del coeficiente principal.
Escribir la funcion posRaices que dado un polinomio devuelve las posibles raices segun el lema de Gauss. No importa si se devuelven multiples representaciones de la misma fraccion, mientras la lista sea finita, incluya todas las posibilidades y no incluya ninguna posibilidad falsa. Se puede asumir que el polinomio pasado como parametro tiene coeficiente independiente distinto de 0.
posRaices :: Poly -> [Frac]
Respuesta
-- posRaices posRaices :: Poly -> [Frac] posRaices poly = [(F p q) | p <- divisoresI, q <- divisoresP] where divisoresP = divisores (coefPpal poly) divisoresI = divisores (coefIndepte poly)
Ejercicio I
Escribir la funcion raices que dado un polinomio devuelve sus raices racionales. Se recomienda fuertemente utilizar el ejercicio anterior. No importa si se devuelven multiples representaciones de la misma fraccion, mientras la lista sea finita, incluya todas las raices y no incluya ninguna raiz falsa.
raices :: Poly -> [Frac]
Respuesta
-- raices raices :: Poly -> [Frac] raices poly = filter (\x -> numer (eval poly x) == 0) (posRaices poly)
Ejercicio 2: Lambda cálculo tipado
Para un importante proyecto de computacion distribuida se desea formalizar algunas ideas. Para dar un contexto a dichas formalizaciones se creara PCF-V, una extension de PCF para dar soporte a computaciones vectoriales. Una computacion vectorial es la computacion de la misma funcion sobre muchos elementos al mismo tiempo. En una primera etapa del proyecto se extendieron los tipos y la sintaxis para soportar el nuevo tipo vectorial de la siguiente manera:
En esta notacion representa un vector de k posiciones, cada una de tipo y es la forma de construir un vector de k elementos. Las reglas de tipado y semantica de la extension ya realizadas son:
Lo que se desea, en este caso, es continuar la extensi´on con 2 construcciones mas: ++ que permite agregar resultados previos (vectores) del mismo tipo en un vector nuevo "mas grande" y que permite testear propiedades sobre los resultados. La sintaxis para esta extension es la siguiente:
La semantica de ++ es la concatenacion de 2 vectores y la de es chequear si la propiedad mencionada en N se hace verdadera reemplazando todas las apariciones libres de x en N por cada uno de los elementos del vector M. Ejemplos:
- No esta bien tipado
- No esta bien tipadoo