Menu Close

PFH: La semana en Exercitium (10 de diciembre de 2022)

José A. Alonso-

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:

A continuación se muestran las soluciones.

1. El tipo de las fórmulas proposicionales: Reconocedor de tautologías

El tipo de las fórmulas proposicionales se puede definir por

   data FProp = Const Bool
              | Var Char
              | Neg FProp
              | Conj FProp FProp
              | Impl FProp FProp
     deriving Show

de modo que la fórmula A → ⊥ ∧ ¬B se representa por

   Impl (Var 'A') (Conj (Const False) (Neg (Var 'B')))

Una fórmula es una tautología si es verdadera en todas sus interpretaciones. Por ejemplo,

  • (A ∧ B) → A es una tautología
  • A → (A ∧ B) no es una tautología

Definir la función

   esTautologia :: FProp -> Bool

tal que esTautologia p se verifica si la fórmula p es una tautología. Por ejemplo,

   λ> esTautologia (Impl (Conj (Var 'A') (Var 'B')) (Var 'A'))
   True
   λ> esTautologia (Impl (Var 'A') (Conj (Var 'A') (Var 'B')))
   False

1.1. Soluciones en Haskell

import Data.List (nub)
 
data FProp = Const Bool
           | Var Char
           | Neg FProp
           | Conj FProp FProp
           | Impl FProp FProp
  deriving Show
 
type Interpretacion = [(Char, Bool)]
 
esTautologia :: FProp -> Bool
esTautologia p =
  and [valor i p | i <- interpretaciones p]
 
-- (valor i p) es el valor de la fórmula p en la interpretación i. Por
-- ejemplo,
--    λ> p = Impl (Var 'A') (Conj (Var 'A') (Var 'B'))
--    λ> valor [('A',False),('B',False)] p
--    True
--    λ> valor [('A',True),('B',False)] p
--    False
valor :: Interpretacion -> FProp -> Bool
valor _ (Const b)  = b
valor i (Var x)    = busca x i
valor i (Neg p)    = not (valor i p)
valor i (Conj p q) = valor i p && valor i q
valor i (Impl p q) = valor i p <= valor i q
 
-- (busca c t) es el valor del primer elemento de la lista de asociación
-- t cuya clave es c. Por ejemplo,
--    busca 2 [(1,'a'),(3,'d'),(2,'c')]  ==  'c'
busca :: Eq c => c -> [(c,v)] -> v
busca c t = head [v | (c',v) <- t, c == c']
 
interpretaciones :: FProp -> [Interpretacion]
interpretaciones p =
  [zip vs i | i <- interpretacionesVar (length vs)]
  where vs = nub (variables p)
 
-- (interpretacionesVar n) es la lista de las interpretaciones de n
-- variables. Por ejemplo,
--    λ> interpretacionesVar 2
--    [[False,False],
--     [False,True],
--     [True,False],
--     [True,True]]
interpretacionesVar :: Int -> [[Bool]]
interpretacionesVar 0 = [[]]
interpretacionesVar n = map (False:) bss ++ map (True:) bss
  where bss = interpretacionesVar (n-1)
 
-- (variables p) es la lista de las variables de la fórmula p. Por
-- ejemplo,
--    λ> variables (Impl (Var 'A') (Conj (Const False) (Neg (Var 'B'))))
--    "AB"
--    λ> variables (Impl (Var 'A') (Conj (Var 'A') (Neg (Var 'B'))))
--    "AAB"
variables :: FProp -> [Char]
variables (Const _)  = []
variables (Var x)    = [x]
variables (Neg p)    = variables p
variables (Conj p q) = variables p ++ variables q
variables (Impl p q) = variables p ++ variables q

1.2. Soluciones en Python

from dataclasses import dataclass
 
 
@dataclass
class FProp:
    pass
 
@dataclass
class Const(FProp):
    x: bool
 
@dataclass
class Var(FProp):
    x: str
 
@dataclass
class Neg(FProp):
    x: FProp
 
@dataclass
class Conj(FProp):
    x: FProp
    y: FProp
 
@dataclass
class Impl(FProp):
    x: FProp
    y: FProp
 
Interpretacion = list[tuple[str, bool]]
 
# busca(c, t) es el valor del primer elemento de la lista de asociación
# t cuya clave es c. Por ejemplo,
#    >>> busca('B', [('A', True), ('B', False), ('C', True)])
#    False
def busca(c: str, i: Interpretacion) -> bool:
    return [v for (d, v) in i if d == c][0]
 
def valor(i: Interpretacion, f: FProp) -> bool:
    match f:
        case Const(b):
            return b
        case Var(x):
            return busca(x, i)
        case Neg(p):
            return not valor(i, p)
        case Conj(p, q):
            return valor(i, p) and valor(i, q)
        case Impl(p, q):
            return valor(i, p) <= valor(i, q)
    assert False
 
# variables(p) es la lista de las variables de la fórmula p. Por
# ejemplo,
#    >>> variables (Impl(Var('A'), Conj(Const(False), Neg (Var('B')))))
#    ['A', 'B']
#    >>> variables (Impl(Var('A'), Conj(Var('A'), Neg (Var('B')))))
#    ['A', 'A', 'B']
def variables(f: FProp) -> list[str]:
    match f:
        case Const(_):
            return []
        case Var(x):
            return [x]
        case Neg(p):
            return variables(p)
        case Conj(p, q):
            return variables(p) + variables(q)
        case Impl(p, q):
            return variables(p) + variables(q)
    assert False
 
# interpretacionesVar(n) es la lista de las interpretaciones de n
# variables. Por ejemplo,
#    >>> interpretacionesVar 2
#    [[False, False],
#     [False, True],
#     [True, False],
#     [True, True]]
def interpretacionesVar(n: int) -> list[list[bool]]:
    if n == 0:
        return [[]]
    bss = interpretacionesVar(n-1)
    return [[False] + x for x in bss] + [[True] + x for x in bss]
 
# interpretaciones(p) es la lista de las interpretaciones de la fórmula
# p. Por ejemplo,
#    >>> interpretaciones(Impl(Var('A'), Conj(Var('A'), Var('B'))))
#    [[('B', False), ('A', False)],
#     [('B', False), ('A', True)],
#     [('B', True), ('A', False)],
#     [('B', True), ('A', True)]]
def interpretaciones(f: FProp) -> list[Interpretacion]:
    vs = list(set(variables(f)))
    return [list(zip(vs, i)) for i in interpretacionesVar(len(vs))]
 
def esTautologia(p: FProp) -> bool:
    return all((valor(i, p) for i in interpretaciones(p)))

2. Altura de un árbol binario

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

data Arbol a = Hoja a
| Nodo (Arbol a) (Arbol a)

Definir la función

   altura :: Arbol a -> Int

tal que altura t es la altura del árbol t. Por ejemplo,

   λ> altura (Hoja 1)
   0
   λ> altura (Nodo (Hoja 1) (Hoja 6))
   1
   λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Hoja 2))
   2
   λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Nodo (Hoja 2) (Hoja 7)))
   2

2.1. Soluciones en Haskell

data Arbol a = Hoja a
             | Nodo (Arbol a) (Arbol a)
 
altura :: Arbol a -> Int
altura (Hoja _)   = 0
altura (Nodo i d) = 1 + max (altura i) (altura d)

2.2. Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar
 
A = TypeVar("A")
 
@dataclass
class Arbol(Generic[A]):
    pass
 
@dataclass
class Hoja(Arbol[A]):
    x: A
 
@dataclass
class Nodo(Arbol[A]):
    i: Arbol[A]
    d: Arbol[A]
 
def altura(a: Arbol[A]) -> int:
    match a:
        case Hoja(_):
            return 0
        case Nodo(i, d):
            return 1 + max(altura(i), altura(d))
    assert False

3. Aplicación de una función a un árbol

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol a = Hoja a
                | Nodo (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir la función

   mapArbol :: (a -> b) -> Arbol a -> Arbol b

tal que mapArbol f t es el árbolo obtenido aplicando la función f a los elementos del árbol t. Por ejemplo,

   λ> mapArbol (+ 1) (Nodo (Hoja 2) (Hoja 4))
   Nodo (Hoja 3) (Hoja 5)

3.1. Soluciones en Haskell

data Arbol a = Hoja a
             | Nodo (Arbol a) (Arbol a)
  deriving (Show, Eq)
 
mapArbol :: (a -> b) -> Arbol a -> Arbol b
mapArbol f (Hoja a)   = Hoja (f a)
mapArbol f (Nodo l r) = Nodo (mapArbol f l) (mapArbol f r)

3.2. Soluciones en Python

from dataclasses import dataclass
from typing import Callable, Generic, TypeVar
 
A = TypeVar("A")
B = TypeVar("B")
 
@dataclass
class Arbol(Generic[A]):
    pass
 
@dataclass
class Hoja(Arbol[A]):
    x: A
 
@dataclass
class Nodo(Arbol[A]):
    i: Arbol[A]
    d: Arbol[A]
 
def mapArbol(f: Callable[[A], B], a: Arbol[A]) -> Arbol[B]:
    match a:
        case Hoja(x):
            return Hoja(f(x))
        case Nodo(i, d):
            return Nodo(mapArbol(f, i), mapArbol(f, d))
    assert False

4. Árboles con la misma forma

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol a = Hoja a
                | Nodo (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir la función

   mismaForma :: Arbol a -> Arbol b -> Bool

tal que mismaForma t1 t2 se verifica si t1 y t2 tienen la misma estructura. Por ejemplo,

   λ> arbol1 = Hoja 5
   λ> arbol2 = Hoja 3
   λ> mismaForma arbol1 arbol2
   True
   λ> arbol3 = Nodo (Hoja 6) (Hoja 7)
   λ> mismaForma arbol1 arbol3
   False
   λ> arbol4 = Nodo (Hoja 9) (Hoja 5)
   λ> mismaForma arbol3 arbol4
   True

4.1. Soluciones en Haskell

import Test.QuickCheck
 
data Arbol a = Hoja a
             | Nodo (Arbol a) (Arbol a)
  deriving (Show, Eq)
 
-- 1ª solución
-- ===========
 
mismaForma1 :: Arbol a -> Arbol b -> Bool
mismaForma1 (Hoja _)   (Hoja _)     = True
mismaForma1 (Nodo l r) (Nodo l' r') = mismaForma1 l l' && mismaForma1 r r'
mismaForma1 _          _            = False
 
-- 2ª solución
-- ===========
 
mismaForma2 :: Arbol a -> Arbol b -> Bool
mismaForma2 x y = f x == f y
  where
    f = mapArbol (const ())
 
-- (mapArbol f t) es el árbol obtenido aplicando la función f a los
-- elementos del árbol t. Por ejemplo,
--    λ> mapArbol (+ 1) (Nodo (Hoja 2) (Hoja 4))
--    Nodo (Hoja 3) (Hoja 5)
mapArbol :: (a -> b) -> Arbol a -> Arbol b
mapArbol f (Hoja a)   = Hoja (f a)
mapArbol f (Nodo i d) = Nodo (mapArbol f i) (mapArbol f d)
 
-- Comprobación de equivalencia
-- ============================
 
-- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo,
--    λ> sample (arbolArbitrario 3 :: Gen (Arbol Int))
--    Nodo (Nodo (Nodo (Hoja 0) (Hoja 0)) (Hoja 0)) (Hoja 0)
--    Nodo (Nodo (Hoja 4) (Hoja 8)) (Hoja (-4))
--    Nodo (Nodo (Nodo (Hoja 4) (Hoja 10)) (Hoja (-6))) (Hoja (-1))
--    Nodo (Nodo (Hoja 3) (Hoja 6)) (Hoja (-5))
--    Nodo (Nodo (Hoja (-11)) (Hoja (-13))) (Hoja 14)
--    Nodo (Nodo (Hoja (-7)) (Hoja 15)) (Hoja (-2))
--    Nodo (Nodo (Hoja (-9)) (Hoja (-2))) (Hoja (-6))
--    Nodo (Nodo (Hoja (-15)) (Hoja (-16))) (Hoja (-20))
arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)
arbolArbitrario n
  | n <= 1    = Hoja <$> arbitrary
  | otherwise = do
      k <- choose (2, n - 1)
      Nodo <$> arbolArbitrario k <*> arbolArbitrario (n - k)
 
-- Arbol es subclase de Arbitraria
instance Arbitrary a => Arbitrary (Arbol a) where
  arbitrary = sized arbolArbitrario
  shrink (Hoja x)   = Hoja <$> shrink x
  shrink (Nodo l r) = l :
                      r :
                      [Nodo l' r | l' <- shrink l] ++
                      [Nodo l r' | r' <- shrink r]
 
-- La propiedad es
prop_mismaForma :: Arbol Int -> Arbol Int -> Property
prop_mismaForma a1 a2 =
  mismaForma1 a1 a2 === mismaForma2 a1 a2
 
-- La comprobación es
--    λ> quickCheck prop_mismaForma
--    +++ OK, passed 100 tests.

4.2. Soluciones en Python

from dataclasses import dataclass
from typing import Callable, Generic, TypeVar
 
A = TypeVar("A")
B = TypeVar("B")
 
@dataclass
class Arbol(Generic[A]):
    pass
 
@dataclass
class Hoja(Arbol[A]):
    x: A
 
@dataclass
class Nodo(Arbol[A]):
    i: Arbol[A]
    d: Arbol[A]
 
# -- 1ª solución
# -- ===========
 
def mismaForma1(a: Arbol[A], b: Arbol[B]) -> bool:
    match (a, b):
        case (Hoja(_), Hoja(_)):
            return True
        case (Nodo(i1, d1), Nodo(i2, d2)):
            return mismaForma1(i1, i2) and mismaForma1(d1, d2)
        case (_, _):
            return False
    assert False
 
# -- 2ª solución
# -- ===========
 
# mapArbol(f, t) es el árbolo obtenido aplicando la función f a
# los elementos del árbol t. Por ejemplo,
#    >>> mapArbol(lambda x: 1 + x, Nodo(Hoja(2), Hoja(4)))
#    Nodo(i=Hoja(x=3), d=Hoja(x=5))
def mapArbol(f: Callable[[A], B], a: Arbol[A]) -> Arbol[B]:
    match a:
        case Hoja(x):
            return Hoja(f(x))
        case Nodo(i, d):
            return Nodo(mapArbol(f, i), mapArbol(f, d))
    assert False
 
def mismaForma2(a: Arbol[A], b: Arbol[B]) -> bool:
    return mapArbol(lambda x: 0, a) == mapArbol(lambda x: 0, b)

5. Árbol con las hojas en la profundidad dada

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol a = Hoja a
                | Nodo (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir la función

   creaArbol :: Int -> Arbol ()

tal que creaArbol n es el árbol cuyas hoyas están en la profundidad n. Por ejemplo,

   λ> creaArbol 2
   Nodo (Nodo (Hoja ()) (Hoja ())) (Nodo (Hoja ()) (Hoja ()))

5.1. Soluciones en Haskell

data Arbol a = Hoja a
             | Nodo (Arbol a) (Arbol a)
  deriving (Show, Eq)
 
creaArbol :: Int -> Arbol ()
creaArbol h
  | h <= 0    = Hoja ()
  | otherwise = Nodo x x
  where x = creaArbol (h - 1)

5.2. Soluciones en Python

from dataclasses import dataclass
from typing import Any, Generic, TypeVar
 
A = TypeVar("A")
 
@dataclass
class Arbol(Generic[A]):
    pass
 
@dataclass
class Hoja(Arbol[A]):
    x: A
 
@dataclass
class Nodo(Arbol[A]):
    i: Arbol[A]
    d: Arbol[A]
 
def creaArbol(h: int) -> Arbol[Any]:
    if h <= 0:
        return Hoja(None)
    x = creaArbol(h - 1)
    return Nodo(x, x)
PFH