Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. El tipo de las expresiones aritméticas: Valor de una expresión
- 2. El tipo de las expresiones aritméticas: Valor de la resta
- 3. El tipo de las expresiones aritméticas: Número de operaciones en una expresión
- 4. Número de hojas de un árbol binario
- 5. Profundidad de un árbol binario
A continuación se muestran las soluciones.
1. El tipo de las expresiones aritméticas: Valor de una expresión
Se considera el tipo de las expresiones aritméticas definido por
data Expr = Lit Int | Suma Expr Expr | Op Expr | SiCero Expr Expr Expr deriving (Eq, Show) |
formado por
- literales (p.e. Lit 7),
- sumas (p.e. Suma (Lit 7) (Suma (Lit 3) (Lit 5)))
- opuestos (p.e. Op (Suma (Op (Lit 7)) (Suma (Lit 3) (Lit 5))))
- expresiones condicionales (p.e. (SiCero (Lit 3) (Lit 4) (Lit 5))
Definir la función
valor :: Expr -> Int |
tal que valor e
es el valor de la expresión e
(donde el valor de SiCero e e1 e2
es el valor de e1
si el valor de e
es cero y el es el valor de e2
, en caso contrario). Por ejemplo,
valor (Op (Suma (Lit 3) (Lit 5))) == -8 valor (SiCero (Lit 0) (Lit 4) (Lit 5)) == 4 valor (SiCero (Lit 1) (Lit 4) (Lit 5)) == 5 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
data Expr = Lit Int | Suma Expr Expr | Op Expr | SiCero Expr Expr Expr deriving (Eq, Show) valor :: Expr -> Int valor (Lit n) = n valor (Suma x y) = valor x + valor y valor (Op x) = - valor x valor (SiCero x y z) | valor x == 0 = valor y | otherwise = valor z |
from dataclasses import dataclass @dataclass class Expr: pass @dataclass class Lit(Expr): x: int @dataclass class Suma(Expr): x: Expr y: Expr @dataclass class Op(Expr): x: Expr @dataclass class SiCero(Expr): x: Expr y: Expr z: Expr def valor(e: Expr) -> int: match e: case Lit(n): return n case Suma(x, y): return valor(x) + valor(y) case Op(x): return -valor(x) case SiCero(x, y, z): return valor(y) if valor(x) == 0 else valor(z) assert False |
2. El tipo de las expresiones aritméticas: Valor de la resta
Se considera el tipo de las expresiones aritméticas definido por
data Expr = Lit Int | Suma Expr Expr | Op Expr | SiCero Expr Expr Expr deriving (Eq, Show) |
formado por
- literales (p.e. Lit 7),
- sumas (p.e. Suma (Lit 7) (Suma (Lit 3) (Lit 5)))
- opuestos (p.e. Op (Suma (Op (Lit 7)) (Suma (Lit 3) (Lit 5))))
- expresiones condicionales (p.e. (SiCero (Lit 3) (Lit 4) (Lit 5))
La función para calcular el valor de una expresión es
valor :: Expr -> Int valor (Lit n) = n valor (Suma x y) = valor x + valor y valor (Op x) = - valor x valor (SiCero x y z) | valor x == 0 = valor y | otherwise = valor z |
Definir la función
resta :: Expr -> Expr -> Expr |
tal que resta e1 e2
es la expresión correspondiente a la diferencia de e1
y e2
. Por ejemplo,
resta (Lit 42) (Lit 2) == Suma (Lit 42) (Op (Lit 2)) |
Comprobar con QuickCheck que
valor (resta x y) == valor x - valor y |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
module Valor_de_la_resta where import Test.QuickCheck data Expr = Lit Int | Suma Expr Expr | Op Expr | SiCero Expr Expr Expr deriving (Eq, Show) valor :: Expr -> Int valor (Lit n) = n valor (Suma x y) = valor x + valor y valor (Op x) = - valor x valor (SiCero x y z) | valor x == 0 = valor y | otherwise = valor z resta :: Expr -> Expr -> Expr resta x y = Suma x (Op y) -- Comprobación de la propiedad -- ============================ -- (exprArbitraria n) es una expresión aleatoria de tamaño n. Por -- ejemplo, -- λ> sample (exprArbitraria 3) -- Op (Op (Lit 0)) -- SiCero (Lit 0) (Lit (-2)) (Lit (-1)) -- Op (Suma (Lit 3) (Lit 0)) -- Op (Lit 5) -- Op (Lit (-1)) -- Op (Op (Lit 9)) -- Suma (Lit (-12)) (Lit (-12)) -- Suma (Lit (-9)) (Lit 10) -- Op (Suma (Lit 8) (Lit 15)) -- SiCero (Lit 16) (Lit 9) (Lit (-5)) -- Suma (Lit (-3)) (Lit 1) exprArbitraria :: Int -> Gen Expr exprArbitraria n | n <= 1 = Lit <$> arbitrary | otherwise = oneof [ Lit <$> arbitrary , let m = div n 2 in Suma <$> exprArbitraria m <*> exprArbitraria m , Op <$> exprArbitraria (n - 1) , let m = div n 3 in SiCero <$> exprArbitraria m <*> exprArbitraria m <*> exprArbitraria m ] -- Expr es subclase de Arbitrary instance Arbitrary Expr where arbitrary = sized exprArbitraria -- La propiedad es prop_resta :: Expr -> Expr -> Property prop_resta x y = valor (resta x y) === valor x - valor y -- La comprobación es -- λ> quickCheck prop_resta -- +++ OK, passed 100 tests. |
from dataclasses import dataclass from random import choice, randint from hypothesis import given from hypothesis import strategies as st @dataclass class Expr: pass @dataclass class Lit(Expr): x: int @dataclass class Suma(Expr): x: Expr y: Expr @dataclass class Op(Expr): x: Expr @dataclass class SiCero(Expr): x: Expr y: Expr z: Expr def valor(e: Expr) -> int: match e: case Lit(n): return n case Suma(x, y): return valor(x) + valor(y) case Op(x): return -valor(x) case SiCero(x, y, z): return valor(y) if valor(x) == 0 else valor(z) assert False def resta(x: Expr, y: Expr) -> Expr: return Suma(x, Op(y)) # -- Comprobación de la propiedad # -- ============================ # exprArbitraria(n) es una expresión aleatoria de tamaño n. Por # ejemplo, # >>> exprArbitraria(3) # Op(x=Op(x=Lit(x=9))) # >>> exprArbitraria(3) # Op(x=SiCero(x=Lit(x=6), y=Lit(x=2), z=Lit(x=6))) # >>> exprArbitraria(3) # Suma(x=Lit(x=8), y=Lit(x=2)) def exprArbitraria(n: int) -> Expr: if n <= 1: return Lit(randint(0, 10)) m = n // 2 return choice([Lit(randint(0, 10)), Suma(exprArbitraria(m), exprArbitraria(m)), Op(exprArbitraria(n - 1)), SiCero(exprArbitraria(m), exprArbitraria(m), exprArbitraria(m))]) # La propiedad es @given(st.integers(min_value=1, max_value=10), st.integers(min_value=1, max_value=10)) def test_mismaForma(n1: int, n2: int) -> None: x = exprArbitraria(n1) y = exprArbitraria(n2) assert valor(resta(x, y)) == valor(x) - valor(y) # La comprobación es # src> poetry run pytest -q valor_de_la_resta.py # 1 passed in 0.21s |
3. El tipo de las expresiones aritméticas: Número de operaciones en una expresión
Se considera el tipo de las expresiones aritméticas definido por
data Expr = Lit Int | Suma Expr Expr | Op Expr | SiCero Expr Expr Expr deriving (Eq, Show) |
formado por
- literales (p.e. Lit 7),
- sumas (p.e. Suma (Lit 7) (Suma (Lit 3) (Lit 5)))
- opuestos (p.e. Op (Suma (Op (Lit 7)) (Suma (Lit 3) (Lit 5))))
- expresiones condicionales (p.e. (SiCero (Lit 3) (Lit 4) (Lit 5))
Definir la función
numeroOps :: Expr -> Int |
tal que numeroOps e
es el número de operaciones de e
. Por ejemplo,
numeroOps (Lit 3) == 0 numeroOps (Suma (Lit 7) (Op (Lit 5))) == 2 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
data Expr = Lit Int | Suma Expr Expr | Op Expr | SiCero Expr Expr Expr deriving (Eq, Show) numeroOps :: Expr -> Int numeroOps (Lit _) = 0 numeroOps (Suma x y) = 1 + numeroOps x + numeroOps y numeroOps (Op x) = 1 + numeroOps x numeroOps (SiCero x y z) = 1 + numeroOps x + numeroOps y + numeroOps z |
from dataclasses import dataclass @dataclass class Expr: pass @dataclass class Lit(Expr): x: int @dataclass class Suma(Expr): x: Expr y: Expr @dataclass class Op(Expr): x: Expr @dataclass class SiCero(Expr): x: Expr y: Expr z: Expr def numeroOps(e: Expr) -> int: match e: case Lit(n): return 0 case Suma(x, y): return 1 + numeroOps(x) + numeroOps(y) case Op(x): return 1 + numeroOps(x) case SiCero(x, y, z): return 1 + numeroOps(x) + numeroOps(y) + numeroOps(z) assert False |
4. Número de hojas de un árbol binario
El árbol binario
9 / \ / \ 3 7 / \ 2 4 |
se puede representar por
N 9 (N 3 (H 2) (H 4)) (H 7) |
El tipo de los árboles binarios se puede definir por
data Arbol a = H a | N a (Arbol a) (Arbol a) |
Definir las funciones
nHojas :: Arbol a -> Int nNodos :: Arbol a -> Int |
tales que
- (nHojas x) es el número de hojas del árbol x. Por ejemplo,
nHojas (N 9 (N 3 (H 2) (H 4)) (H 7)) == 3 |
- (nNodos x) es el número de nodos del árbol x. Por ejemplo,
nNodos (N 9 (N 3 (H 2) (H 4)) (H 7)) == 2 |
Comprobar con QuickCheck que en todo árbol binario el número de sus hojas es igual al número de sus nodos más uno.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
import Test.QuickCheck data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) nHojas :: Arbol a -> Int nHojas (H _) = 1 nHojas (N _ i d) = nHojas i + nHojas d nNodos :: Arbol a -> Int nNodos (H _) = 0 nNodos (N _ i d) = 1 + nNodos i + nNodos d -- Comprobación de equivalencia -- ============================ -- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo, -- λ> sample (arbolArbitrario 3 :: Gen (Arbol Int)) -- N 0 (H 0) (H 0) -- N 1 (N (-2) (H (-1)) (H 1)) (H 2) -- N 3 (H 1) (H 2) -- N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4)) -- H 7 -- N (-8) (H (-8)) (H 9) -- H 2 -- N (-1) (H 7) (N 9 (H (-2)) (H (-8))) -- H (-3) -- N 0 (N 16 (H (-14)) (H (-18))) (H 7) -- N (-16) (H 18) (N (-19) (H (-15)) (H (-18))) arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a) arbolArbitrario 0 = H <$> arbitrary arbolArbitrario n = oneof [H <$> arbitrary, N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)] -- Arbol es subclase de Arbitrary instance Arbitrary a => Arbitrary (Arbol a) where arbitrary = sized arbolArbitrario -- La propiedad es prop_nHojas :: Arbol Int -> Bool prop_nHojas x = nHojas x == nNodos x + 1 -- La comprobación es -- λ> quickCheck prop_nHojas -- OK, passed 100 tests. |
from dataclasses import dataclass from random import choice, randint from typing import Generic, TypeVar from hypothesis import given from hypothesis import strategies as st A = TypeVar("A") @dataclass class Arbol(Generic[A]): pass @dataclass class H(Arbol[A]): x: A @dataclass class N(Arbol[A]): x: A i: Arbol[A] d: Arbol[A] def nHojas(a: Arbol[A]) -> int: match a: case H(_): return 1 case N(_, i, d): return nHojas(i) + nHojas(d) assert False def nNodos(a: Arbol[A]) -> int: match a: case H(_): return 0 case N(_, i, d): return 1 + nNodos(i) + nNodos(d) assert False # Comprobación de equivalencia # ============================ # (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo, # >>> arbolArbitrario(4) # N(x=2, i=H(x=1), d=H(x=9)) # >>> arbolArbitrario(4) # H(x=10) # >>> arbolArbitrario(4) # N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6)) def arbolArbitrario(n: int) -> Arbol[int]: if n <= 1: return H(randint(0, 10)) m = n // 2 return choice([H(randint(0, 10)), N(randint(0, 10), arbolArbitrario(m), arbolArbitrario(m))]) # La propiedad es @given(st.integers(min_value=1, max_value=10)) def test_nHojas(n: int) -> None: a = arbolArbitrario(n) assert nHojas(a) == nNodos(a) + 1 # La comprobación es # src> poetry run pytest -q numero_de_hojas_de_un_arbol_binario.py # 1 passed in 0.10s |
5. Profundidad de un árbol binario
El árbol binario
9 / \ / \ 3 7 / \ 2 4 |
se puede representar por
N 9 (N 3 (H 2) (H 4)) (H 7) |
El tipo de los árboles binarios se puede definir por
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) |
Definir la función
profundidad :: Arbol a -> Int |
tal que profundidad x
es la profundidad del árbol x
. Por ejemplo,
profundidad (N 9 (N 3 (H 2) (H 4)) (H 7)) == 2 profundidad (N 9 (N 3 (H 2) (N 1 (H 4) (H 5))) (H 7)) == 3 profundidad (N 4 (N 5 (H 4) (H 2)) (N 3 (H 7) (H 4))) == 2 |
Comprobar con QuickCheck que para todo árbol biario x, se tiene que
nNodos x <= 2^(profundidad x) - 1 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
import Test.QuickCheck data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) profundidad :: Arbol a -> Int profundidad (H _) = 0 profundidad (N _ i d) = 1 + max (profundidad i) (profundidad d) -- Comprobación de equivalencia -- ============================ -- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo, -- λ> sample (arbolArbitrario 3 :: Gen (Arbol Int)) -- N 0 (H 0) (H 0) -- N 1 (N (-2) (H (-1)) (H 1)) (H 2) -- N 3 (H 1) (H 2) -- N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4)) -- H 7 -- N (-8) (H (-8)) (H 9) -- H 2 -- N (-1) (H 7) (N 9 (H (-2)) (H (-8))) -- H (-3) -- N 0 (N 16 (H (-14)) (H (-18))) (H 7) -- N (-16) (H 18) (N (-19) (H (-15)) (H (-18))) arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a) arbolArbitrario 0 = H <$> arbitrary arbolArbitrario n = oneof [H <$> arbitrary, N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)] -- Arbol es subclase de Arbitrary instance Arbitrary a => Arbitrary (Arbol a) where arbitrary = sized arbolArbitrario -- La propiedad es prop_nNodosProfundidad :: Arbol Int -> Bool prop_nNodosProfundidad x = nNodos x <= 2 ^ profundidad x - 1 -- (nNodos x) es el número de nodos del árbol x. Por ejemplo, -- nNodos (N 9 (N 3 (H 2) (H 4)) (H 7)) == 2 nNodos :: Arbol a -> Int nNodos (H _) = 0 nNodos (N _ i d) = 1 + nNodos i + nNodos d -- La comprobación es -- λ> quickCheck prop_nNodosProfundidad -- OK, passed 100 tests. |
from dataclasses import dataclass from random import choice, randint from typing import Generic, TypeVar from hypothesis import given from hypothesis import strategies as st A = TypeVar("A") @dataclass class Arbol(Generic[A]): pass @dataclass class H(Arbol[A]): x: A @dataclass class N(Arbol[A]): x: A i: Arbol[A] d: Arbol[A] def profundidad(a: Arbol[A]) -> int: match a: case H(_): return 0 case N(_, i, d): return 1 + max(profundidad(i), profundidad(d)) assert False # Comprobación de equivalencia # ============================ # (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo, # >>> arbolArbitrario(4) # N(x=2, i=H(x=1), d=H(x=9)) # >>> arbolArbitrario(4) # H(x=10) # >>> arbolArbitrario(4) # N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6)) def arbolArbitrario(n: int) -> Arbol[int]: if n <= 1: return H(randint(0, 10)) m = n // 2 return choice([H(randint(0, 10)), N(randint(0, 10), arbolArbitrario(m), arbolArbitrario(m))]) # nNodos(x) es el número de nodos del árbol x. Por ejemplo, # nNodos(N(9, N(3, H(2), H(4)), H(7))) == 2 def nNodos(a: Arbol[A]) -> int: match a: case H(_): return 0 case N(_, i, d): return 1 + nNodos(i) + nNodos(d) assert False # La propiedad es @given(st.integers(min_value=1, max_value=10)) def test_nHojas(n: int) -> None: a = arbolArbitrario(n) assert nNodos(a) <= 2 ** profundidad(a) - 1 # La comprobación es # src> poetry run pytest -q profundidad_de_un_arbol_binario.py # 1 passed in 0.11s |