Recuperatorio Primer Parcial 1er Cuat 2006 (Paradigmas)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 1: Programación Funcional[editar]

Item A[editar]

Insertar enunciado.

Respuesta[editar]

groupBy :: (a -> a -> Bool) -> [a] -> a
groupBy p = foldr juntar []
    where juntar e [] = e
          juntar e (x:xs) | p e (head x) = (e:x):xs
                          | otherwise = [e]:x:xs

Item B[editar]

Insertar enunciado.

Respuesta[editar]

compactar :: Eq a => [a] -> [(a, Int)]
compactar l = map (\x -> (head x, length x)) (groupBy (==) l)

Item C[editar]

Insertar enunciado.

Respuesta[editar]

expandir :: [(a, Int)] -> [a]
expandir = foldr f []
    where f (x,c) r = (replicate c x) ++ r


Ejercicio 2: Programación Funcional[editar]

Item A[editar]

Insertar enunciado.

type Symbol = Char
data Term =  TVar String | TOp Symbol [Term] deriving Show

Respuesta[editar]

foldTermPrim :: (Symbol -> Term -> [b] -> b) -> (String -> b) -> Term -> b
foldTermPrim opf varf t =
    case t of
        (TVar s) -> varf s
        (TOp s lt) -> opf s t (map rec lt)
    where rec = foldTermPrim opf varf

foldTerm :: (Symbol -> [b] -> b) -> (String -> b) -> Term -> b
foldTerm opf varf = foldTermPrim (\x y -> opf x) varf

Item B[editar]

Insertar enunciado.

type Subst = String -> Term

Respuesta[editar]

applySubst :: Subst -> Term -> Term
applySubst s = foldTerm opf s
    where opf sym rec = (TOp sym rec)

Item C[editar]

Insertar enunciado.

Respuesta[editar]

makeMatch :: Term -> (Term -> Bool)
makeMatch = foldTerm opf varf
    where varf s = (\x -> True)
          opf s xs =
            (\t -> if isVar t then False
                   else (length xs == length (subterms t)) &&
                        symbol t == s &&
                        fit xs (subterms t))
          subterms (TOp _ l) = l
          symbol (TOp ss _) = ss
          isVar (TVar _) = True
          isVar (TOp _ _) = False
          fit ps xs = all (==True) (zipWith app ps xs)
          app x y = x y

match :: Term -> Term -> Bool
match = makeMatch

Para probar

t1 = TOp 'f' [TOp 'g' [TVar "x", TVar "y"]]
t2 = TOp 'h' [TOp 'g' [TVar "x", TVar "y"]]
t3 = TOp 'h' [TOp 'f' [TVar "x", TVar "y"]]
p1 = TOp 'f' [TVar "x"]
p2 = TOp 'f' [TVar "x", TVar "y"]

Item D[editar]

Insertar enunciado.

Respuesta[editar]

anyMatch :: Term -> Term -> Bool
anyMatch p = foldTermPrim opf varf
    where varf s = False
          opf s t lt = any (==True) lt || (match p t)

Item E[editar]

Insertar enunciado.

idSubs :: Subst
idSubs s = TVar s

joinSubs :: Subst -> Subst -> Subst
joinSubs s t =
    \x -> case s x of
        (TVar x) -> t x
        _ -> s x

Respuesta[editar]

computeSubs :: Term -> (Term -> Subst)
computeSubs = foldTerm opf varf
    where varf _ = (\t s -> t)
          opf _ xs = (\t -> join (aplicar (subterms t) xs))
          aplicar lt xs = zipWith app xs lt
          join xs = foldr joinSubs idSubs xs
          subterms (TOp _ l) = l
          app x y = x y

Ejercicio 3: PCF[editar]

Item A[editar]

Insertar enunciado.

Respuesta[editar]

Item B[editar]

Insertar enunciado.

Respuesta[editar]

Item C[editar]

Insertar enunciado.

Respuesta[editar]

Ejercicio 4: Inferencia[editar]

Item A[editar]

Insertar enunciado.

Respuesta[editar]

Item B[editar]

Insertar enunciado.

Respuesta[editar]