Mínima suma de las ramas de un árbol
Los árboles se pueden representar mediante el siguiente tipo de datos
data Arbol a = N a [Arbol a] deriving Show
Por ejemplo, los árboles
1 1 1
/ \ / \ / \
8 3 5 3 5 3
| /|\ /|\ |
4 4 7 6 4 7 6 7
se representan por
ej1, ej2, ej3 :: Arbol Int ej1 = N 1 [N 8 [],N 3 [N 4 []]] ej2 = N 1 [N 5 [], N 3 [N 4 [], N 7 [], N 6 []]] ej3 = N 1 [N 5 [N 4 [], N 7 [], N 6 []], N 3 [N 7 []]]
Definir la función
minimaSuma :: Arbol Int -> Int
tal que (minimaSuma a) es el mínimo de las sumas de las ramas del árbol a. Por ejemplo,
minimaSuma ej1 == 8 minimaSuma ej2 == 6 minimaSuma ej3 == 10
Soluciones
data Arbol a = N a [Arbol a] deriving Show ej1, ej2, ej3 :: Arbol Int ej1 = N 1 [N 8 [],N 3 [N 4 []]] ej2 = N 1 [N 5 [], N 3 [N 4 [], N 7 [], N 6 []]] ej3 = N 1 [N 5 [N 4 [], N 7 [], N 6 []], N 3 [N 7 []]] -- 1ª definición -- ============= minimaSuma :: (Ord a, Num a) => Arbol a -> a minimaSuma a = minimum [sum xs | xs <- ramas a] -- (ramas a) es la lista de las ramas del árbol a. Por ejemplo, -- λ> ramas (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]) -- [[3,5,6],[3,4],[3,7,2],[3,7,1]] ramas :: Arbol b -> [[b]] ramas (N x []) = [[x]] ramas (N x as) = [x : xs | a <- as, xs <- ramas a] -- 2ª definición -- ============= minimaSuma2 :: Arbol Int -> Int minimaSuma2 (N x []) = x minimaSuma2 (N x as) = x + minimum (map minimaSuma2 as)