Árbol de profundidad n con nodos iguales
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) |
Definir las funciones
|
1 2 |
repeatArbol :: a -> Arbol a replicateArbol :: Int -> a -> Arbol a |
tales que
repeatArbol xes es árbol con infinitos nodosx. Por ejemplo,
|
1 2 3 |
takeArbol 0 (repeatArbol 3) == H 3 takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3) takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3)) |
replicate n xes el árbol de profundidadncuyos nodos sonx. Por ejemplo,
|
1 2 3 |
replicateArbol 0 5 == H 5 replicateArbol 1 5 == N 5 (H 5) (H 5) replicateArbol 2 5 == N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5)) |
Comprobar con QuickCheck que el número de hojas de replicateArbol n x es 2^n, para todo número natural n.
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 60 61 62 63 64 65 66 67 68 69 |
import Test.QuickCheck data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) repeatArbol :: a -> Arbol a repeatArbol x = N x t t where t = repeatArbol x replicateArbol :: Int -> a -> Arbol a replicateArbol n = takeArbol n . repeatArbol -- (takeArbol n t) es el subárbol de t de profundidad n. Por ejemplo, -- 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) 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 -- ===================================== -- (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 nHojas :: Arbol a -> Int nHojas (H _) = 1 nHojas (N _ i d) = nHojas i + nHojas d -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_replicateArbol :: Int -> Int -> Property prop_replicateArbol n x = n >= 0 ==> nHojas (replicateArbol n x) == 2^n -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=7}) prop_replicateArbol -- +++ 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 |
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 replicateArbol(n: int, x: A) -> Arbol[A]: match n: case 0: return H(x) case n: t = replicateArbol(n - 1, x) return N(x, t, t) 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 # ===================================== # 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 def nHojas(a: Arbol[A]) -> int: match a: case H(_): return 1 case N(_, i, d): return nHojas(i) + nHojas(d) assert False # Comprobación de la propiedad # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=10), st.integers(min_value=1, max_value=10)) def test_nHojas(n: int, x: int) -> None: assert nHojas(replicateArbol(n, x)) == 2**n # La comprobación es # src> poetry run pytest -q arbol_de_profundidad_n_con_nodos_iguales.py # 1 passed in 0.20s |
Para definir la función repeatArbol, podemos usar recursión infinita:
Para definir la función replicateArbol, podemos usar una función auxiliar que construye un árbol de profundidad n y cuyos nodos son x:
Para comprobar que el número de hojas de replicateArbol n x es 2^n para todo número natural n, podemos usar QuickCheck y la función leaves, que cuenta el número de hojas de un árbol:
Ejecutamos QuickCheck para comprobar la propiedad:
Pregunta ¿Y el generador de los árboles para QuickCheck?
Respuesta Para poder usar QuickCheck con la estructura de datos Arbol, necesitamos definir un generador de árboles. Una forma de hacerlo es usar la siguiente función:
Esta función toma un generador de elementos (de tipo a) y devuelve un generador de árboles de elementos de tipo a. El tamaño del árbol se determina por la función getSize. Si el tamaño es 0, se devuelve un árbol hoja con el elemento generado. Si el tamaño es mayor que 0, se generan dos árboles más pequeños y se combinan en un árbol con un nodo interno.
Por ejemplo, podemos usar este generador para generar árboles de números enteros aleatorios:
Podemos usar este generador en la propiedad prop_replicateArbol para hacer pruebas aleatorias:
Pregunta ¿No hay que declarar Arbol una instancia de Arbitrary?
Respuesta Sí, para poder usar QuickCheck con la estructura de datos Arbol, es necesario declararla una instancia de la clase Arbitrary. Esto se hace mediante la siguiente definición:
La primera parte de la instancia especifica cómo generar árboles aleatorios usando el generador genArbol. La segunda parte especifica cómo reducir el tamaño de un árbol durante el proceso de minimización de QuickCheck. En este caso, se reduce el tamaño de un árbol convirtiéndolo en un árbol hoja o reduciendo el tamaño de sus hijos.
Para resolver este problema, podemos definir la función replicateArbol utilizando recursión. Si n es cero, entonces el árbol es un nodo hoja con valor x. Si n es mayor que cero, entonces el árbol es un nodo con valor x y dos subárboles, cuyos valores también son x, y cuyas profundidades son n – 1. Esto se puede implementar de la siguiente manera:
Para comprobar con Hypothesis que el número de hojas de replicateArbol(n, x) es 2^n, podemos utilizar la siguiente función de prueba:
La función contarHojas recorre el árbol y cuenta el número de nodos hoja que encuentra. La función de prueba test_replicate_arbol utiliza la función contarHojas para comprobar que el número de hojas del árbol generado por replicateArbol es 2^n.
Para ejecutar estas pruebas con Hypothesis, debemos instalar la biblioteca y luego ejecutar el siguiente comando: