Los árboles binarios se pueden representar mediante el tipo Arbol definido por
data Arbol a = H a | N (Arbol a) a (Arbol a) deriving Show |
Por ejemplo, el árbol
"B" / \ / \ / \ "B" "A" / \ / \ "A" "B" "C" "C" |
se puede definir por
ej1 :: Arbol String ej1 = N (N (H "A") "B" (H "B")) "B" (N (H "C") "A" (H "C")) |
Definir la función
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,
λ> enumeraArbol ej1 N (N (H 0) 1 (H 2)) 3 (N (H 4) 5 (H 6)) |
Gráficamente,
3 / \ / \ / \ 1 5 / \ / \ 0 2 4 6 |
Soluciones
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>