Primer Parcial 1er Cuat 2006 (Paradigmas)

Ejercicio 1

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