Subárbol de profundidad dada
El árbol binario
1 2 3 4 5 6 |
9 / \ / \ 3 7 / \ 2 4 |
se puede representar por
1 |
N 9 (N 3 (H 2) (H 4)) (H 7) |
El tipo de los árboles binarios se puede definir por
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) |
La función take está definida por
1 2 3 4 |
take :: Int -> [a] -> [a] take 0 = [] take (n+1) [] = [] take (n+1) (x:xs) = x : take n xs |
Definir la función
1 |
takeArbol :: Int -> Arbol a -> Arbol a |
tal que takeArbol n t
es el subárbol de t
de profundidad n
. Por ejemplo,
1 2 3 4 |
takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9 takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7) takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7) takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7) |
Comprobar con QuickCheck que la profundidad de takeArbol n x
es menor o igual que n
, para todo número natural n
y todo árbol x
.
Soluciones
A continuación se muestran las soluciones en Haskell y las 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 |
import Test.QuickCheck data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) takeArbol :: Int -> Arbol a -> Arbol a takeArbol _ (H x) = H x takeArbol 0 (N x _ _) = H x takeArbol n (N x i d) = N x (takeArbol (n-1) i) (takeArbol (n-1) d) -- Generador para las comprobaciones -- ================================= -- (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 -- Función auxiliar para la comprobación -- ===================================== -- (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 profundidad :: Arbol a -> Int profundidad (H _) = 0 profundidad (N _ i d) = 1 + max (profundidad i) (profundidad d) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_takeArbol :: Int -> Arbol Int -> Property prop_takeArbol n x = n >= 0 ==> profundidad (takeArbol n x) <= n -- La comprobación es -- λ> quickCheck prop_takeArbol -- +++ OK, passed 100 tests. |
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 |
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 takeArbol(n: int, a: Arbol[A]) -> Arbol[A]: match (n, a): case (_, H(x)): return H(x) case (0, N(x, _, _)): return H(x) case (n, N(x, i, d)): return N(x, takeArbol(n - 1, i), takeArbol(n - 1, d)) assert False # Generador para las comprobaciones # ================================= # (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))]) # Función auxiliar para la comprobación # ===================================== # 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 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 la propiedad # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=12), st.integers(min_value=1, max_value=10)) def test_takeArbol(n: int, m: int) -> None: x = arbolArbitrario(m) assert profundidad(takeArbol(n, x)) <= n # La comprobación es # src> poetry run pytest -q subarbol_de_profundidad_dada.py # 1 passed in 0.23s |
Podemos definir la función takeArbol de la siguiente manera:
La idea es que si el número de profundidad es 0, entonces devolvemos el nodo actual como hoja (H x). Si no, continuamos recursivamente con los hijos izquierdo y derecho, disminuyendo en 1 el número de profundidad restante.
Para comprobar con QuickCheck que la profundidad del subárbol resultante es menor o igual que n, podemos definir la función profundidad que calcula la profundidad de un árbol, y luego escribir la propiedad que queremos probar:
Para comprobar esta propiedad con QuickCheck, podemos usar la siguiente función:
Ejecutando este código, QuickCheck generará aleatoriamente valores de n y árboles x, y comprobará que la propiedad se cumple para todos ellos. Si QuickCheck no encuentra ningún caso en el que la propiedad no se cumpla, entonces podemos estar seguros de que la función takeArbol está implementada correctamente.
Pregunta ¿Se puede reducir el número de ecuaciones de takeArbol?
Respuesta Sí, es posible reducir el número de ecuaciones de takeArbol a una sola, usando una condición if para decidir si devolver el nodo actual como hoja (H x) o continuar recursivamente con los hijos. La definición de la función quedaría de la siguiente manera:
En este caso, la propiedad que queremos comprobar con QuickCheck sigue siendo válida,