Primer Parcial 1er Cuat 2006 (Paradigmas)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 1[editar]

Dos anagramas determinan una transposicion de los caracteres de una tercer cadena. Por ejemplo, los anagramas “abcde” y “eabcd” definen la transposicion en la que el ultimo caracter de una cadena de 5 caracteres es movido al principio. Definir la funcion transpose :: String -> String -> String -> String que permite transponer los caracteres de una cadena segun se especifica a traves de dos anagramas. Por ejemplo, transpose "UVWXYZ" "fedcba" "ecabdf" debe devolver "VXZYWU".

locate:: String -> Char -> Int
locate s c = foldr (\t r1 -> if (t==c) then 0 else 1+r1) 0 s

transpose:: String-> String -> String -> String
transpose s1 s2 s3 = foldr (\c r1 -> (s1 !! (locate s2 c)) : r1) [] s3

Otra solución posible (usando map):

transpose :: String -> String -> String -> String
transpose t o p = map mover p
    where mover e = t !! (locate e o)

Ejercicio 2[editar]

Consideremos una representacion estandar de arboles binarios:

data BinTree a = Nil | Branch a (BinTree a) (BinTree a)

Item A[editar]

(5 puntos) Un operador de recursion primitiva es aquel en el que el resultado no depende unicamente de el o los llamados recursivos correspondientes sino tambien de los elementos que componen la estructura recursiva. Por ejemplo, el recursor primitivo para listas (llamado recr en las transparencias de la teorica) es:

primFold :: b -> ([a] -> a -> b -> b) -> [a] -> b
primFold z f [] = z
primFold z f (x:xs) = f xs x (primFold z f xs)

Definir el operador de recursion primitiva para arboles binarios:

primFoldBinTree :: (BinTree a -> BinTree a -> a -> b -> b -> b) -> b -> BinTree a -> b

Item B[editar]

(5 puntos) Dar el tipo de foldBinTree, un esquema de recursion “clasico” (en el sentido que lo es foldr para listas) para arboles binarios, y definirlo usando primFoldBinTree.

Item C[editar]

(10 puntos) Un arbol binario de busqueda es un arbol en el cual cada nodo es mayor o igual que todos los nodos en el subarbol izquierdo, y menor que todos los del subarbol derecho. De este modo, la operacion de busqueda de un elemento es mas eficiente que en el caso de un arbol sin esta propiedad.

type SearchTree a = BinTree a

Definir sin usar recursion explıcita la funcion elemSearchTree :: Ord a => a -> SearchTree a -> Bool que decida si un elemento esta en el arbol o no aprovechando la propiedad de ser un arbol de busqueda. ¿Esta funcion es realmente mas eficiente que en un arbol ordinario? En otras palabras, ¿efectivamente la busqueda se hace solo sobre los subarboles que corresponden? Justificar brevemente.

Item D[editar]

(10 puntos) Definir sin usar recursion explıcita la funcion insertSearchTree :: Ord a => a -> SearchTree a -> SearchTree a que inserta el elemento en el lugar apropiado del arbol, manteniendo la propiedad de ser un arbol binario de busqueda.

Respuestas[editar]

Pueden usar el siguiente codigo para mostrar los árboles

showTree Nil = "#"
showTree (Branch e i d) = "(" ++ showTree i ++ " :" ++ show e ++ ": " ++ showTree d ++ ")"

instance (Show a) => Show (BinTree a) where
    show = showTree

Item A[editar]

primFoldBinTree::(BinTree a->BinTree a->a->b->b->b)->b->BinTree a->b
primFoldBinTree f z Nil = z
primFoldBinTree f z (Bin n i d) = f i d n (primFoldBinTree f z i) (primFoldBinTree f z d)

Item B[editar]

foldBinTree::(a->b->b->b)->b->BinTree a->b
foldBinTree g z a = primFoldBinTree (\_ _ n r1 r2 -> g n r1 r2) z a

Item C[editar]

elemSearchTree::Ord a=>a->SearchTree a->Bool
elemSearchTree e a = foldBinTree (\n x1 x2 -> if n==e then true else if n>e then x1 else x2) false a

No está aprovechando la propiedad, siempre se recorre toda la estructura.

Item D[editar]

insertSearchTree :: Ord a => a -> SearchTree a -> SearchTree a
insertSearchTree e a = primFoldBinTree ifBranch ifNull a
    where ifNull = Branch e Nil Nil
          ifBranch i d el ri rd | el == e = Branch e i d
                                | el > e = Branch el ri d
                                | el < e = Branch el i rd

Ejercicio 3[editar]

El presente ejercicio consiste en definir una lenguaje llamado PCF* que introduce construcciones que permiten hacer pattern matching sobre pares y sobre funciones. PCF* resulta de modificar la sintaxis de arboles de terminos de PCF de la siguiente manera: se eliminan las proyecciones de pares y , y la aplicacion M N (dado que son expresables con las construcciones nuevas que se agregan) y se agregan construcciones de matching para pares y funciones:

Construccion de matching para pares[editar]

Sintaxis[editar]

Si M, P son arboles de terminos PCF* y x, y son variables, entonces

es un arbol de terminos de PCF*.

Comportamiento[editar]

Se evalua M hasta que de un par ordenado <Q1, Q2>. Luego se evalua P donde todas las ocurrencias libres de x e y se reemplazan por Q1 y Q2, respectivamente. El valor arrojado por esta ultima expresion es el valor de toda la expresion.

Ejemplos[editar]

Observar que puede definirse como syntactic sugar para , y de manera analoga se puede proceder con .

Construccion de matching para funciones[editar]

Sintaxis[editar]

Si M,N, P son arboles de terminos PCF* y x es una variable, entonces match M using N with x in P es un arbol de termino PCF*.

Comportamiento[editar]

Se evalua M hasta que de una funcion λz.Q. Luego se evalua P donde se reemplazan todas las ocurrencias libres de la variable x por Q{z := N}.

Ejemplos[editar]

Observar que la aplicacion de PCF (λx.Q) R puede definirse como syntactic sugar para

Se pide[editar]

Para ambas construcciones definir:

  • a) (15 puntos) Las reglas de tipado.
  • b) (10 puntos) Las reglas de semantica operacional call-by-name small-step (M ->CBN N).
  • c) (10 puntos) Las reglas de semantica operacional call-by-name big-step (M ↓ N).

Respuestas[editar]

Item A[editar]

Item B[editar]



Item C[editar]

Ejercicio 4[editar]

Resolver los siguientes items, justificando en todos los casos a traves del arbol de inferencia.

  • a) (10 puntos) Mostrar que el algoritmo de inferencia falla con la siguiente expresion, donde id es una constante cuyo tipo es id :: a -> a.
(λ.f f (f 3)) id
  • b) (10 puntos) Mostrar que, sin embargo, el algoritmo de inferencia es capaz de inferir el tipo de la expresion
id id (id 3)
  • c) (5 puntos) ¿Que sucede con la siguiente expresion cuando es alimentada al algoritmo de inferencia?
(λx.x) (λx.x) ((λx.x) 3)

Respuestas[editar]

Item A[editar]

Error al representar (función desconocida «\extendlatex»): {\displaystyle \extendlatex \def\regla{\scriptsize} \def\rm{\textrm} \Tree [.{$\left(\lambda f. f f \left(f\ 3\right)\right)$ id}\\{\regla (I-APP)} [.{$\left(\lambda f. f f \left(f\ 3\right)\right)$}\\{\regla (I-ABS)} [.{$\left(f f\right)\ \left(f\ 3\right)$}\\{\regla (I-APP)} [.{$f f$}\\{\regla (I-APP)}\\{$\nexists \rm{MGU}\{\rm{s}\doteq\rm{r}\rightarrow\beta,\rm{r}\doteq\rm{s}\}$} [.{$f$}\\{\regla (I-VAR)}\\{$\{f:\rm{s}\} \triangleright f : \rm{s}$} ] [.{$f$}\\{\regla (I-VAR)}\\{$\{f:\rm{r}\} \triangleright f : \rm{r}$} ] ] [.{$f\ 3$}\\{\regla (I-APP)} [.{$f$}\\{\regla (I-VAR)}\\{$\{f:\rm{t}\} \triangleright f : \rm{t}$} ] [.{$3$}\\{\regla (I-ZERO, I-SUCC)}\\{$\emptyset \triangleright 3:\textrm{Int}$} ] ] ] ] [ .id\\{\regla (I-ID)}\\{$\emptyset \triangleright \textrm{id}:\textrm{s}\rightarrow\textrm{s}$} ] ] }

La unificación falla en el término "f f".

Item B[editar]

Error al representar (función desconocida «\extendlatex»): {\displaystyle \extendlatex \def\regla{\scriptsize} \def\rm{\textrm} \Tree [.{$\left(\rm{id\ id}\right) \left(\rm{id\ }3\right)$}\\{\regla (I-APP)}\\{$\emptyset \triangleright \left(\rm{id\ id}\right) \left(\rm{id\ }3\right) : \rm{Int}$} [.{$\left(\rm{id\ id}\right)$}\\{\regla (I-APP)}\\{$\emptyset \triangleright \rm{id\ id}:b\rightarrow b\;\;(S_1)$} [.{$\rm{id}$}\\{\regla (I-ID)}\\{$\emptyset \triangleright \rm{id_a}:a\rightarrow a$} ] [.{$\rm{id}$}\\{\regla (I-ID)}\\{$\emptyset \triangleright \rm{id_b}:b\rightarrow b$} ] ] [.{$\left(\rm{id\ }3\right)$}\\{\regla (I-APP)}\\{$\emptyset \triangleright \rm{id\ }3:\rm{Int}$} [.{$\rm{id}$}\\{\regla (I-ID)}\\{$\emptyset \triangleright \rm{id_s}:s\rightarrow s$} ] [.{$3$}\\{\regla (I-ZERO, I-SUCC)}\\{$\emptyset \triangleright 3:\rm{Int}$} ] ] ] $$S_1 = \rm{MGU}\{a\rightarrow a \doteq b\rightarrow b \rightarrow t\} = \{a\mapsto b\rightarrow b, t\mapsto b\rightarrow b\}$$ }

Item C[editar]

Error al representar (función desconocida «\extendlatex»): {\displaystyle \extendlatex \def\regla{\scriptsize} \def\rm{\textrm} \Tree [.{$\left(\lambda x.x\right) \left(\lambda x.x\right) \left(\left(\lambda x.x\right) 3\right)$}\\{\regla (I-APP)}\\{$\emptyset \triangleright \left(\lambda x.x\right) \left(\lambda x.x\right) \left(\left(\lambda x.x\right) 3\right) : \rm{Int}\;\;(S_3)$} [.{$\left(\lambda x.x\right) \left(\lambda x.x\right)$}\\{\regla (I-APP)}\\{$\emptyset \triangleright \left(\lambda x.x\right) \left(\lambda x.x\right) : t_2\rightarrow t_2\;\;(S_1)$} [.{$\left(\lambda x.x\right)$}\\{\regla (I-ABS)}\\{$\emptyset \triangleright \left(\lambda x.x\right) : t_1\rightarrow t_1$} [.{$x$}\\{\regla (I-VAR)}\\{$\{x:t_1\}\triangleright x : t_1$} ] ] [.{$\left(\lambda x.x\right)$}\\{\regla (I-ABS)}\\{$\emptyset \triangleright \left(\lambda x.x\right) : t_2\rightarrow t_2$} [.{$x$}\\{\regla (I-VAR)}\\{$\{x:t_2\}\triangleright x : t_2$} ] ] ] [.{$\left(\lambda x.x\right) 3$}\\{\regla (I-APP)}\\{$\emptyset \triangleright \left(\lambda x.x\right) 3 : \rm{Int}\;\;(S_2)$} [.{$\left(\lambda x.x\right)$}\\{\regla (I-ABS)}\\{$\emptyset \triangleright \left(\lambda x.x\right) : t_1\rightarrow t_1$} [.{$x$}\\{\regla (I-VAR)}\\{$\{x:t_1\}\triangleright x : t_1$} ] ] [.{$3$}\\{\regla (I-ZERO, I-SUCC)}\\{$\emptyset \triangleright 3 : \rm{Int}$} ] ] ] \bigskip $S_1 = \rm{MGU}\{t_1\rightarrow t_1 \doteq (t_2\rightarrow t_2)\rightarrow t\}=\{t_1\mapsto t_2\rightarrow t_2, t\mapsto t_1\}$ $S_2 = \rm{MGU}\{t_3\rightarrow t_3 \doteq \rm{Int}\rightarrow t\}=\{t_3\mapsto \rm{Int}, t\mapsto \rm{Int}\}$ $S_3 = \rm{MGU}\{t_2\rightarrow t_2 \doteq \rm{Int}\rightarrow t\}=\{t_2\mapsto \rm{Int}, t\mapsto \rm{Int}\}$ }