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:

$\sigma ::\ ...\;|\;\sigma ^{k}$

$M::\ ...\;|\;(M_{1},...,M_{k})$

En esta notacion $\sigma ^{k}$ representa un vector de k posiciones, cada una de tipo $\sigma$ y $(M_{1},...,M_{k})$ es la forma de construir un vector de k elementos. Las reglas de tipado y semantica de la extension ya realizadas son:

${\frac {\Gamma \triangleright M_{1}:\sigma ,...,\Gamma \triangleright M_{k}:\sigma }{\Gamma \triangleright (M_{1},...,M_{k}):\sigma ^{k}}}$

${\frac {M_{i}\rightarrow _{cbn}M_{i}'}{(M_{1},...,M_{i},...,M_{k})\rightarrow _{cbn}(M_{1},...,M_{i}',...,M_{k})}}$

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 $\forall$ que permite testear propiedades sobre los resultados. La sintaxis para esta extension es la siguiente:

$M::=...\;|\;(M_{1},...,M_{k})\;|\;M++N\;|\;\forall x\in M{\textrm {\ check\ }}N$

La semantica de ++ es la concatenacion de 2 vectores y la de $\forall$ 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:

• $(1,2,3)\;++\;(4,5)\rightarrow (1,2,3,4,5)$
• $(1,2,3)\;++\;(true,false)$ No esta bien tipado
• $\forall x\in (1,2,3)\;{\textrm {Eq?}}\;x\;1\rightarrow false$
• $\forall x\in (1,1,1)\;{\textrm {Eq?}}\;x\;1\rightarrow true$
• $\forall x\in (1,3,5)\;(\lambda x.{\textrm {Eq?}}\;x\;1)$ No esta bien tipadoo

Ejercicio A

Reglas de tipado.

Ejercicio B

Semantica operacional small-step solo para la construccion ++.

Ejercicio C

Semantica operacional big-step para ambas construcciones.

Respuesta

No se ve más y no se como hacerlo, clausura? $\rightarrow ^{*}$?