Primer Parcial 1er Cuat 2006 (Paradigmas)

De Cuba-Wiki

Ejercicio 1

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->String->Nat
locate s c = foldr (\t r1 -> if (t==c) then 1+r1 else r1) 0 s

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

Ejercicio 2

Consideremos una representacion estandar de arboles binarios: data BinTree a = Nil | Branch a (BinTree a) (BinTree a)

  • a) (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

  • b) (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.

  • c) (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.

  • d) (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

  • a)
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)
  • b)
foldBinTree::(a->b->b->b)->b->BinTree a->b
foldBinTree g z a = primFoldBinTree (\a1 a2 n r1 r2 -> g n r1 r2) z a
  • c)
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
  • d)
insertSearchTree::Ord a=>a->SearchTree a->SearchTree a
insertSearchTree e a = primFoldBinTree (\i d n ri rd -> if e>=n then Branch n i rd) else (Branch n ri d)) (Branch e Nil Nil) a

Ejercicio 3

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 PI1(M) y PI2(M), 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:
    • Sintaxis:

Si M, P son arboles de terminos PCF? y x, y son variables, entonces match M with <x, y> in P es un arbol de terminos de PCF?.

    • Comportamiento:

Se evalua M hasta que de un par ordenado hQ1,Q2i. 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


match <2, 3> with <x, y> in x + y ↓ 5
match (<λx.<x, 3>) (λx.x) with <x, y> in x y ↓ 3 Observar que PI1(M) puede definirse como syntactic sugar para match M with <x, y> in x,y de manera analoga se puede proceder con PI2(M).

  • Construccion de matching para funciones:
    • Sintaxis:

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:

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


match (λx.x + x) using 2 with y in y + 3 ↓ 7
match ((λy.(λx.x 2 + y)) 3) using (λz.z) with y in y + 3 ↓ 8
Observar que la aplicacion de PCF (�x.Q) R puede definirse como syntactic sugar para match �λ.Q using R with y in y .

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

  • a)
    Γ |> M: s1xs2 ; Γ,x:s1,y:s2 |> p:t
----------------------------------------------------------------
     Γ |> match M with <x,y> in p : t



    Γ |> M:s1->s2 ; Γ|>N:s1 ; Γ,x:s2 |> p:t
----------------------------------------------------------------
      Γ |> match M using N with x in P : t
  • b)
                    M ->cbn M'
----------------------------------------------------------------
 match M with <x,y> in P ->cbn match M' with <x,y> in P



----------------------------------------------------------------
 match <Q1,Q2> with <x,y> in P ->cbn P{x<-Q1,y<-Q2}



                    M ->cbn M'
----------------------------------------------------------------
 match M using N with x in P ->cbn match M' using N with x in P



----------------------------------------------------------------
  match (λz.Q) using N with x in P ->cbn P{x<-Q{z<-N}}
  • c)
     M ↓ <Q1,Q2> ; P{x<-Q1,y<-Q2} ↓ V
----------------------------------------------------------------
      match M with <x,y> in P ↓ V



     M ↓ (λz.Q) ; P{x<-Q{z<-N}} ↓ V
----------------------------------------------------------------
      match M using N with x in P ↓ V

Ejercicio 4

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

  • a)
    (λf.(f f)(f 3)) id
           |         | APP
 λf.(f f)(f 3)     id:a->a
           | ABS
      (f f)(f 3) :E
      |           | APP
    f  f :R->E   f  3 :B
    |  |         |  |
   f:w f:t      f:s 3:int

B=R, w=t->R, t=R->E --> w=(R->E)->(R->E). En la abstraccion se tiene λf.(f f)(f 3):E->E, con f:E, pero f:w --> f:(R->E)->(R->E). Entonces el algoritmo falla.

  • b)
         (id id)(id 3) :int
         |               | APP
      id id :c=b->b      id 3 :int
       |     | APP       |     | APP
   id:c->c id:b->b    id:a->a  3:int

c=b->b, b=int, a=int

  • c)
       ((λx.x)(λx.x))((λx.x) 3) :int
         |                       | APP
      (λx.x) (λx.x) :t->t      (λx.x) 3 :int
        |             | APP      |          | APP
   (λx.x):s->s (λx.x):t->t     (λx.x):w->w  3:int
        | ABS            | ABS    | ABS
       x:s              x:t      x:w

s=t->t, t=int, w=int

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Primer_Parcial_1er_Cuat_2006_(Paradigmas)&oldid=5332»