PFH: La semana en Exercitium (10 de diciembre de 2022)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. El tipo de las fórmulas proposicionales: Reconocedor de tautologías
- 2. Altura de un árbol binario
- 3. Aplicación de una función a un árbol
- 4. Árboles con la misma forma
- 5. Árbol con las hojas en la profundidad dada
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
|
1 2 3 4 5 6 |
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
|
1 |
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) → Aes una tautologíaA → (A ∧ B)no es una tautología
Definir la función
|
1 |
esTautologia :: FProp -> Bool |
tal que esTautologia p se verifica si la fórmula p es una tautología. Por ejemplo,
|
1 2 3 4 |
λ> 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
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 2 3 4 5 6 |
· / \ / \ · · / \ / \ 1 4 6 9 |
se puede representar por
|
1 2 |
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
|
1 |
altura :: Arbol a -> Int |
tal que altura t es la altura del árbol t. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> 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
|
1 2 3 4 5 6 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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 2 3 4 5 6 |
· / \ / \ · · / \ / \ 1 4 6 9 |
se puede representar por
|
1 2 |
ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4)) (Nodo (Hoja 6) (Hoja 9)) |
El tipo de los árboles binarios se puede definir por
|
1 2 3 |
data Arbol a = Hoja a | Nodo (Arbol a) (Arbol a) deriving (Show, Eq) |
Definir la función
|
1 |
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,
|
1 2 |
λ> mapArbol (+ 1) (Nodo (Hoja 2) (Hoja 4)) Nodo (Hoja 3) (Hoja 5) |
3.1. Soluciones en Haskell
|
1 2 3 4 5 6 7 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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 2 3 4 5 6 |
· / \ / \ · · / \ / \ 1 4 6 9 |
se puede representar por
|
1 2 |
ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4)) (Nodo (Hoja 6) (Hoja 9)) |
El tipo de los árboles binarios se puede definir por
|
1 2 3 |
data Arbol a = Hoja a | Nodo (Arbol a) (Arbol a) deriving (Show, Eq) |
Definir la función
|
1 |
mismaForma :: Arbol a -> Arbol b -> Bool |
tal que mismaForma t1 t2 se verifica si t1 y t2 tienen la misma estructura. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 |
λ> 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
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 2 3 4 5 6 |
· / \ / \ · · / \ / \ 1 4 6 9 |
se puede representar por
|
1 2 |
ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4)) (Nodo (Hoja 6) (Hoja 9)) |
El tipo de los árboles binarios se puede definir por
|
1 2 3 |
data Arbol a = Hoja a | Nodo (Arbol a) (Arbol a) deriving (Show, Eq) |
Definir la función
|
1 |
creaArbol :: Int -> Arbol () |
tal que creaArbol n es el árbol cuyas hoyas están en la profundidad n. Por ejemplo,
|
1 2 |
λ> creaArbol 2 Nodo (Nodo (Hoja ()) (Hoja ())) (Nodo (Hoja ()) (Hoja ())) |
5.1. Soluciones en Haskell
|
1 2 3 4 5 6 7 8 9 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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) |