Enumeración de árboles binarios
Los árboles binarios se pueden representar mediante el tipo Arbol definido por
|
1 2 3 |
data Arbol a = H a | N (Arbol a) a (Arbol a) deriving Show |
Por ejemplo, el árbol
|
1 2 3 4 5 6 7 |
"B" / \ / \ / \ "B" "A" / \ / \ "A" "B" "C" "C" |
se puede definir por
|
1 2 |
ej1 :: Arbol String ej1 = N (N (H "A") "B" (H "B")) "B" (N (H "C") "A" (H "C")) |
Definir la función
|
1 |
enumeraArbol :: Arbol t -> Arbol Int |
tal que (enumeraArbol a) es el árbol obtenido numerando las hojas y los nodos de a desde la hoja izquierda hasta la raíz. Por ejemplo,
|
1 2 |
λ> enumeraArbol ej1 N (N (H 0) 1 (H 2)) 3 (N (H 4) 5 (H 6)) |
Gráficamente,
|
1 2 3 4 5 6 7 |
3 / \ / \ / \ 1 5 / \ / \ 0 2 4 6 |
Soluciones
|
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 |
import Test.QuickCheck (Arbitrary, Gen, arbitrary, quickCheck, sized) import Control.Monad.State (State, evalState, get, put) data Arbol a = H a | N (Arbol a) a (Arbol a) deriving (Show, Eq) ej1 :: Arbol String ej1 = N (N (H "A") "B" (H "B")) "B" (N (H "C") "A" (H "C")) -- 1ª solución -- =========== enumeraArbol1 :: Arbol t -> Arbol Int enumeraArbol1 a = fst (aux a 0) where aux :: Arbol t -> Int -> (Arbol Int, Int) aux (H _) n = (H n, n+1) aux (N i _ d) n = (N i' n1 d', n2) where (i', n1) = aux i n (d', n2) = aux d (n1+1) -- 2ª solución -- =========== enumeraArbol2 :: Arbol t -> Arbol Int enumeraArbol2 a = evalState (aux a) 0 where aux :: Arbol t -> State Int (Arbol Int) aux (H _) = H <$> contador aux (N i _ d) = do i' <- aux i n1 <- contador d' <- aux d return (N i' n1 d') contador :: State Int Int contador = do n <- get put (n+1) return n -- 3ª solución -- =========== enumeraArbol3 :: Arbol t -> Arbol Int enumeraArbol3 a = evalState (aux a) 0 where aux :: Arbol t -> State Int (Arbol Int) aux (H _) = H <$> contador aux (N i _ d) = N <$> aux i <*> contador <*> aux d -- Comprobación de equivalencia -- ============================ -- (arbolArbitrario n) genera un árbol aleatorio de orden n. Por -- ejemplo, -- λ> generate (arbolArbitrario 3 :: Gen (Arbol Int)) -- N (N (H 19) 0 (H (-27))) 21 (N (H 2) 17 (H 26)) arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a) arbolArbitrario n | n <= 0 = H <$> arbitrary | otherwise = N <$> subarbol <*> arbitrary <*> subarbol where subarbol = arbolArbitrario (n `div` 2) -- Arbol es una subclase de Arbitrary. instance Arbitrary a => Arbitrary (Arbol a) where arbitrary = sized arbolArbitrario -- La propiedad es prop_enumeraArbol :: Arbol Int -> Bool prop_enumeraArbol a = all (== enumeraArbol1 a) [enumeraArbol2 a, enumeraArbol3 a] -- La comprobación es -- λ> quickCheck prop_enumeraArbol -- +++ OK, passed 100 tests. |
El código se encuentra en GitHub.
La elaboración de las soluciones se describe en el siguiente vídeo
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
[/schedule]