Los \u00e1rboles se pueden representar mediante el siguiente tipo de datos<\/p>\n
\n data Arbol a = N a [Arbol a]\n deriving Show\n<\/pre>\nPor ejemplo, los \u00e1rboles<\/p>\n
\n 1 3\n \/ \\ \/|\\\n 2 3 \/ | \\\n | 5 4 7\n 4 | \/\\\n 6 2 1\n<\/pre>\nse representan por<\/p>\n
\n ej1, ej2 :: Arbol Int\n ej1 = N 1 [N 2 [],N 3 [N 4 []]]\n ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]\n<\/pre>\nDefinir la funci\u00f3n<\/p>\n
\n mayorProducto :: (Ord a, Num a) => Arbol a -> a\n<\/pre>\ntal que (mayorProducto a)<\/code> es el mayor producto de las ramas del \u00e1rbol a<\/code>. Por ejemplo,<\/p>\n\n \u03bb> mayorProducto (N 1 [N 2 [], N 3 []])\n 3\n \u03bb> mayorProducto (N 1 [N 8 [], N 4 [N 3 []]])\n 12\n \u03bb> mayorProducto (N 1 [N 2 [],N 3 [N 4 []]])\n 12\n \u03bb> mayorProducto (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])\n 90\n \u03bb> mayorProducto (N (-8) [N 0 [N (-9) []],N 6 []])\n 0\n \u03bb> a = N (-4) [N (-7) [],N 14 [N 19 []],N (-1) [N (-6) [],N 21 []],N (-4) []]\n \u03bb> mayorProducto a\n 84\n<\/pre>\nSoluciones<\/h4>\n\nimport Test.QuickCheck\n\ndata Arbol a = N a [Arbol a]\n deriving Show\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmayorProducto1 :: (Ord a, Num a) => Arbol a -> a\nmayorProducto1 a = maximum [product xs | xs <- ramas a]\n\n-- (ramas a) es la lista de las ramas del \u00e1rbol a. Por ejemplo,\n-- \u03bb> ramas (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])\n-- [[3,5,6],[3,4],[3,7,2],[3,7,1]]\nramas :: Arbol b -> [[b]]\nramas (N x []) = [[x]]\nramas (N x as) = [x : xs | a <- as, xs <- ramas a]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmayorProducto2 :: (Ord a, Num a) => Arbol a -> a\nmayorProducto2 a = maximum (map product (ramas a))\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmayorProducto3 :: (Ord a, Num a) => Arbol a -> a\nmayorProducto3 = maximum . map product . ramas\n\n-- 4\u00ba soluci\u00f3n\n-- ===========\n\nmayorProducto4 :: (Ord a, Num a) => Arbol a -> a\nmayorProducto4 = maximum . productosRamas\n\n-- (productosRamas a) es la lista de los productos de las ramas\n-- del \u00e1rbol a. Por ejemplo,\n-- \u03bb> productosRamas (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])\n-- [90,12,42,21]\nproductosRamas :: (Ord a, Num a) => Arbol a -> [a]\nproductosRamas (N x []) = [x]\nproductosRamas (N x xs) = [x * y | a <- xs, y <- productosRamas a]\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nmayorProducto5 :: (Ord a, Num a) => Arbol a -> a\nmayorProducto5 (N x []) = x\nmayorProducto5 (N x xs)\n | x > 0 = x * maximum (map mayorProducto5 xs)\n | x == 0 = 0\n | otherwise = x * minimum (map menorProducto xs)\n\n-- (menorProducto a) es el menor producto de las ramas del \u00e1rbol\n-- a. Por ejemplo,\n-- \u03bb> menorProducto (N 1 [N 2 [], N 3 []])\n-- 2\n-- \u03bb> menorProducto (N 1 [N 8 [], N 4 [N 3 []]])\n-- 8\n-- \u03bb> menorProducto (N 1 [N 2 [],N 3 [N 4 []]])\n-- 2\n-- \u03bb> menorProducto (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])\n-- 12\nmenorProducto :: (Ord a, Num a) => Arbol a -> a\nmenorProducto (N x []) = x\nmenorProducto (N x xs)\n | x > 0 = x * minimum (map menorProducto xs)\n | x == 0 = 0\n | otherwise = x * maximum (map mayorProducto2 xs)\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nmayorProducto6 :: (Ord a, Num a) => Arbol a -> a\nmayorProducto6 = maximum . aux\n where aux (N a []) = [a]\n aux (N a b) = [v,u]\n where u = maximum g\n v = minimum g\n g = map (*a) (concatMap aux b)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- (arbolArbitrario n) es un \u00e1rbol aleatorio de orden n. Por ejemplo,\n-- > sample (arbolArbitrario 5 :: Gen (Arbol Int))\n-- N 0 [N 0 []]\n-- N (-2) []\n-- N 4 []\n-- N 2 [N 4 []]\n-- N 8 []\n-- N (-2) [N (-9) [],N 7 []]\n-- N 11 []\n-- N (-11) [N 4 [],N 14 []]\n-- N 10 [N (-3) [],N 13 []]\n-- N 12 [N 11 []]\n-- N 20 [N (-18) [],N (-13) []]\narbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)\narbolArbitrario n = do\n x <- arbitrary\n ms <- sublistOf [0 .. n `div` 2]\n as <- mapM arbolArbitrario ms\n return (N x as)\n\n-- Arbol es una subclase de Arbitraria\ninstance Arbitrary a => Arbitrary (Arbol a) where\n arbitrary = sized arbolArbitrario\n\n-- La propiedad es\nprop_mayorProducto :: Arbol Integer -> Bool\nprop_mayorProducto a =\n all (== mayorProducto1 a)\n [f a | f <- [ mayorProducto2\n , mayorProducto3\n , mayorProducto4\n , mayorProducto5\n , mayorProducto6\n ]]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_mayorProducto\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> ejArbol <- generate (arbolArbitrario 600 :: Gen (Arbol Integer))\n-- \u03bb> mayorProducto1 ejArbol\n-- 2419727651266241493467136000\n-- (1.87 secs, 1,082,764,480 bytes)\n-- \u03bb> mayorProducto2 ejArbol\n-- 2419727651266241493467136000\n-- (1.57 secs, 1,023,144,008 bytes)\n-- \u03bb> mayorProducto3 ejArbol\n-- 2419727651266241493467136000\n-- (1.55 secs, 1,023,144,248 bytes)\n-- \u03bb> mayorProducto4 ejArbol\n-- 2419727651266241493467136000\n-- (1.60 secs, 824,473,800 bytes)\n-- \u03bb> mayorProducto5 ejArbol\n-- 2419727651266241493467136000\n-- (0.83 secs, 732,370,352 bytes)\n-- \u03bb> mayorProducto6 ejArbol\n-- 2419727651266241493467136000\n-- (0.98 secs, 817,473,344 bytes)\n--\n-- \u03bb> ejArbol2 <- generate (arbolArbitrario 700 :: Gen (Arbol Integer))\n-- \u03bb> mayorProducto5 ejArbol2\n-- 1044758937398026715504640000000\n-- (4.94 secs, 4,170,324,376 bytes)\n-- \u03bb> mayorProducto6 ejArbol2\n-- 1044758937398026715504640000000\n-- (5.88 secs, 4,744,782,024 bytes)\n<\/pre>\nEl c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\nLa elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n