Diferencia entre revisiones de «Primer Parcial 1er Cuat 2006 (Paradigmas)»
De Cuba-Wiki
Línea 1: | Línea 1: | ||
==Ejercicio 1== | ==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::String->String->Nat |
Revisión del 01:28 1 may 2008
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
- 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