Primer Parcial 1er Cuat 2007 (Paradigmas)
Ejercicio 1: Programación funcional
Durante todo este ejercicio no se puede usar recursion explicita, a menos que se especifique explicitamente lo contrario. Para hacer un item pueden utilizarse como existentes las solucio- nes a todos los items anteriores, independientemente de si fueron resueltos correctamente o no.
Consideremos la siguiente representacion de intervalos de enteros:
data LimitVal = MenosInf | MasInf | Cte Int type Inter = (LimitVal,LimitVal)
que representa el conjunto de todos los enteros que estan entre la primer coordenada del par y la segunda, inclusive en los casos no degenerados. Si la primer coordenada es mayor a la segunda, se considerara el intervalo como vacio.
Ejercicio A
Escribir una funcion compare que dados dos LimitVal, devuelva una de las constantes LT, GT o EQ (todas del tipo Ordering) segun el primer parametro sea menor, mayor o igual que el segundo, respectivamente.
compare :: LimitVal → LimitVal → Ordering
A partir de aqui se puede tomar LimitVal como perteneciente a las clases Eq y Ord, por lo cual tiene bien definidos los operadores <, <=, ==, >, >= y /= y todas las operaciones que requieren Eq u Ord son utilizables.
Respuesta
compare MenosInf MenosInf = EQ compare MasInf MasInf = EQ compare (Cte a) (Cte b) = compare a b compare MenosInf _ = LT compare MasInf _ = GT compare _ MenosInf = GT compare _ MasInf = LT
Ejercicio B
Escribir las funciones empty, que devuelve un intervalo vacio, isEmpty que determina si un intervalo es vacio e incl que dice si el primer parametro esta enteramente incluido (como conjunto) en el segundo.
empty :: Inter isEmpty :: Inter → Bool incl :: Inter → Inter → Bool
Nota: Cuidar que incl funcione bien para todos los intervalos considerados vacios.
Respuesta
empty = (MasInf,MenosInf) isEmpty (a,b) = (a==MasInf) | | (b==MenosInf) | | (a>b) incl (a,b) (c,d) = (isEmpty (a,b)) | | ((a>=c) && (b<=d))
Ejercicio C
Escribir la funcion compress que dada una lista estrictamente ascendiente (sin repetidos) de enteros devuelve su respresentacion como union de la minima cantidad posible de intervalos. Se debe devolver una lista con dichos intervalos.
compress :: [Int] → [Inter]
Ejemplo:
compress [-1,0,1,2,3,5,7,8,9,11] → [(Cte (-1),Cte 3),(Cte 5,Cte 5),(Cte 7,Cte 9),(Cte 11,Cte 11)]
Respuesta
compress = foldr insert [] where insert e r = if (length r > 0 && value (fst (head r)) == e+1) then (Cte e,snd (head r)):(tail r) else (Cte e,Cte e):r
Ejercicio D
¿Funciona la funcion anterior asi como esta con listas infinitas? (es decir, ¿va devolviendo los intervalos a medida que los va reconociendo terminados?) ¿Seria posible hacer una que funcione? Si la respuesta es si, comentar como, si es no, justificar informalmente por que.
Respuesta
No funciona asi como esta, pero si es posible hacer una.
compress [] = [] compress [x] = [(Cte x,Cte x)] compress (x:y:xs) = if (x<y-1) then ((Cte x,Cte x):(compress (y:xs))) else (insert x (compress y:xs))
donde insert es la misma funcion de la solucion original.
Ejercicio E
Escribir la funcion expand que, dado un intervalo, devuelve el conjunto equivalente por extension como una lista (eventualmente infinita) de enteros. El orden de la lista no importa, pero se debe asegurar que todo miembro del conjunto aparece exactamente una vez.
Respuesta
expand (Cte a, Cte b) = [a..b] expand (MenosInf,Cte a) = map (λx-> (-x)) [-a..] expand (Cte a,MasInf) = [a..] expand (MenosInf,MasInf) = 0:[x*s | x<-[1..],s<-[-1,1]] expand _ = []
Ejercicio F
Escribir una funcion que dado un conjunto no vacio de intervalos por extension, devuelve la interseccion de todos ellos.
inters :: [Inter] → Inter
Ejemplo:
inters [(MenosInf,Cte 5),(Cte (-3),Cte 9),(Cte 0,MasInf)] → (Cte 0, Cte 5)
Respuesta
inters = foldr1 inter2 where inter2 a b = (max (fst a) (fst b),min (snd a) (snd b))
Ejercicio G
Dado el tipo de los arboles binarios y un esquema de recursion (fold) para hacer funciones sobre ellos, escribir una funci´on que verifique si un arbol binario de inter- valos cumple con el invariante de heap, es decir, el intervalo de un nodo contiene a todos los intervalos de sus descendientes. El nodo raiz, por lo tanto, debe contener a todos los intervalos del arbol.
data ArbolBin a = Nil | Bin (ArbolBin a) a (ArbolBin a) foldBin :: (a → b → b → b) → b → (ArbolBin a) → b foldBin _ c Nil = c foldBin f c (Bin i a d) = f a (foldBin f c i) (foldBin f c d) esHeap :: (ArbolBin Inter) → Bool
Respuesta
esHeap = snd.(foldBin heapInt (empty,True)) where heapInt h (i,b1) (d,b2) = (h,b1 && b2 && (incl i h) && (incl d h))
Ejercicio H
Se desea modelar expresiones aritmeticas de operaciones sobre intervalos, pero aun no se ha definido que funciones se van a utilizar, por lo que se tiene un tipo que permite modelar operaciones unarias y binarias cualesquiera. Este tipo representa las constantes mediante el constructor Const y las operaciones mediante los constructores Op1 y Op2 (para unarias y binarias respectivamente) que se acompanan de una funcion para indicar su comportamiento (aparte de las expresiones que toma como parametros). Se pide, entonces, escribir el esquema de recursion (fold) para este tipo. Para este ejercicio se puede, por supuesto, usar recursion explicita.
data Expr = Op1 (Inter → Inter) Expr | Op2 (Inter → Inter → Inter) Expr Expr | Const Inter foldExpr :: ((Inter → Inter) → b → b) → ((Inter → Inter → Inter) → b → b → b) → (Inter → b) → Expr → b
Respuesta
foldExpr f1 f2 c (Const a) = c a foldExpr f1 f2 c (Op1 f e) = f1 f (foldExpr f1 f2 c e) foldExpr f1 f2 c (Op2 f e1 e2) = f2 f (foldExpr f1 f2 c e1) (foldExpr f1 f2 c e2)
Ejercicio I
Usando el esquema del punto anterior, sin recursion explicita ni pattern matching, escribir la funcion eval que dada una expresi´on devuelve el resultado de evaluarla.
eval :: Expr → Inter
Respuesta
eval = foldExpr id id id
Ejercicio 2: Lambda cálculo tipado
Se cuenta con un lengua je de lambda calculo tipado extendido para soportar naturales (se tienen los terminos 0, pred(M), succ(M) e isZero(M) donde las constantes naturales notadas con n abrevian como fue visto en la teorica). Ejemplos: 0 y 2 son las constantes que representan el 0 y el 2 respectivamente. Se pueden asumir las reglas de tipado y semantica correctas para los enteros como fueron dados.
El objetivo del ejercicio es extender este lenguaje para soportar una estructura switch que sea el equivalente a if pero para naturales. La sintaxis sera similar a la que usan C y C++ para el switch. La sintaxis del lengua je, entonces, sera la siguiente:
Aquı los representan numeros naturales y k es un entero positivo. La idea del comportamiento del switch es que primero evalue su condicion (lo que esta entre parentesis) y luego el resultado de toda la expresion se decide seguun el case que matchee el valor al que se evaluo la expresion (parecido al comportamiento del if.then.else). Esta prohi- bido incluir dos case con igual constante y tambien no incluir ninguno (esto no se asume, sino que se debe forzar con las reglas que correspondan). Si ningun case matchea el valor evaluado, la expresion debe quedar indefinida.
Ejercicio A
Introducir las reglas de tipado para la extension propuesta.
Respuesta
No se bien como restringir los casos que piden, se me ocurrió esto:
para
Ejercicio B
Indicar formalmente como se modifica el conjunto de valores.
Respuesta
Creo que funciona como el lambda:
Ejercicio C
Dar la semantica operacional de a un paso para la extension propuesta.
Respuesta
Ejercicio D
Decir si con las reglas introducidas existe un termino cerrado (sin variables libres) que este en forma normal y no sea un valor. Si lo hay, mostrar un ejemplo, y si no, justificar informalmente por que.
Respuesta
Creo que no hay porque todo switch introducido es un valor (por como definí los valores).
Para mi este no es valor: switch(2){case 1 : true}
Ejercicio E
Modificar la sintaxis, las reglas de tipado y de semantica operacional rea- lizadas para que se pueda incluir tambien opcionalmente un label def ault : que debe aparecer una sola vez al final de los case y se utiliza para dar valor a toda la expresion en caso de que ningun case matchee. Se pueden reutilizar cosas introducidas en los items anteriores, pero debe especificarse exactamente que reglas se mantienen (si alguna regla debe ser modificada aunque sea levemente, se ruega reescribirla entera a fin de no generar problemas de interpretacion al corregir).
Ejercicio F
Escribir isZero en funcion de la extension realizada en el punto anterior.
Respuesta
isZero x = switch(x) { case 0: true, default: false }
Ejercicio 3: Inferencia de tipos
a) λx. λy. (x y) (λz. x) No tipa.
b) λx. λy. λz. x (y z) (b -> c) -> (a -> b) -> a -> c Toma dos funciones y devuelve su composicion.
c) λx. λy. (x y) (x y) No tipa.
d) W(caseNat U of 0 -> V ; Succ(x) -> W) =def SΓ1 U SΓ2 U SΓ3 |> S(caseNat M of 0 -> N ; Succ(x) -> O) : Sw donde W(U) = Γ1 |> M : s W(V) = Γ2 |> N : t W(W) = Γ'3 |> O : v Si x : p E Γ'3 entonces Γ3 = Γ'3 - {x : p},H = {p = Nat} sino Γ3 = Γ'3,H = Ø S = MGU(H U {w = t, t = v, s = Nat} U {p1 = p2 | y : p1 E Γi, y : p2 E Γj , i <> j}