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

• 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