En la librería Data.Tree se definen los árboles y los bosques como sigue
|
1 2 |
data Tree a = Node a (Forest a) type Forest a = [Tree a] |
Por ejemplo, los árboles
|
1 2 3 4 5 6 |
1 3 / \ /|\ 6 3 / | \ | 5 4 7 1 | /\ 3 6 5 |
se representan por
|
1 2 3 |
ej1, ej2 :: Tree Int ej1 = Node 1 [Node 6 [],Node 3 [Node 1 []]] ej2 = Node 3 [Node 5 [Node 3 []], Node 4 [], Node 7 [Node 6 [], Node 5 []]] |
Definir la función
|
1 |
minimaProfundidad :: Ord a => a -> Tree a -> Maybe Int |
tal que (minimaProfundidad x ns) es justamente la mínima donde aparece x en el árbol ns, si aparece y Nothing, en caso contrario. Por ejemplo,
|
1 2 3 4 5 6 7 |
minimaProfundidad 1 ej1 == Just 0 minimaProfundidad 3 ej1 == Just 1 minimaProfundidad 2 ej1 == Nothing minimaProfundidad 3 ej2 == Just 0 minimaProfundidad 4 ej2 == Just 1 minimaProfundidad 6 ej2 == Just 2 minimaProfundidad 9 ej2 == Nothing |
|
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 |
import Data.Tree (Tree (Node), levels) import Data.Maybe (isNothing, fromJust, listToMaybe) ej1, ej2 :: Tree Int ej1 = Node 1 [Node 6 [],Node 3 [Node 1 []]] ej2 = Node 3 [Node 5 [Node 3 []], Node 4 [], Node 7 [Node 6 [], Node 5 []]] -- 1ª definición minimaProfundidad1 :: Ord a => a -> Tree a -> Maybe Int minimaProfundidad1 x (Node y ns) | x == y = Just 0 | null zs = Nothing | otherwise = Just (1 + minimum zs) where zs = [z | Just z <- filter (/=Nothing) (map (minimaProfundidad1 x) ns)] -- 2ª definición minimaProfundidad2 :: Ord a => a -> Tree a -> Maybe Int minimaProfundidad2 x (Node y ns) | x == y = Just 0 | z == Nothing = Nothing | otherwise = Just (1 + fromJust z) where z = minimum (map (minimaProfundidad2 x) ns) -- 3ª definición minimaProfundidad3 :: Ord a => a -> Tree a -> Maybe Int minimaProfundidad3 x (Node y ns) | x == y = Just 0 | otherwise = Just (+1) <*> minimum (map (minimaProfundidad3 x) ns) -- 4ª definición minimaProfundidad4 :: Ord a => a -> Tree a -> Maybe Int minimaProfundidad4 x ns | null zs = Nothing | otherwise = Just (head zs) where zs = [z | (z,ys) <- zip [0..] (levels ns), x `elem` ys] -- 5ª definición minimaProfundidad5 :: Ord a => a -> Tree a -> Maybe Int minimaProfundidad5 x ns = listToMaybe [z | (z,ys) <- zip [0..] (levels ns), x `elem` ys] |