Primer Parcial 1er Cuat 2006 (Paradigmas)

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

• 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

• 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