Relaciones arbóreas
Como se explica en el ejercicio Relación definida por un árbol, cada árbol binario define una relación binaria donde un elemento x está relacionado con y si x es el padre de y.
Una relación binaria es arbórea si
- hay exactamente un elemento que no tiene ningún (la raíz del árbol) y
- todos los elementos tienen dos hijos (los nodos internos) o ninguno (las hojas del árbol).
Definir la función
|
1 |
arborea :: Eq a => [(a,a)] -> Bool |
tal que (arborea r) se verifica si la relación r es arbórea. Por ejemplo,
|
1 2 3 |
arborea [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] == True arborea [(8,3),(8,5),(10,2),(2,2),(2,0)] == False arborea [(10,8),(8,3),(8,5),(10,2),(8,2),(2,0)] == False |
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 |
import Data.List ((\\), elemIndices, isPrefixOf, nub, sort) -- 1ª solución -- =========== arborea :: Eq a => [(a,a)] -> Bool arborea r = length [x | x <- nodos r, null (padres r x)] == 1 && all (`elem` [0,2]) [length (hijos r x) | x <- nodos r] -- (nodos r) es el conjunto de los nodos de la relación r. Por ejemplo, -- λ> nodos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] -- [10,8,3,5,2,0] nodos :: Eq a => [(a,a)] -> [a] nodos r = nub (concat [[x,y] | (x,y) <- r]) -- (padres r x) es la lista de los padres de x en la relación r. Por -- ejemplo, -- padres [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 8 == [10] -- padres [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 10 == [] padres :: Eq a => [(a,a)] -> a -> [a] padres r x = [y | (y,x') <- r, x' == x] -- (hijos r x) es la lista de los hijos de x en la relación r. Por -- ejemplo, -- hijos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 10 == [8,2] -- hijos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 5 == [] hijos :: Eq a => [(a,a)] -> a -> [a] hijos r x = [y | (x',y) <- r, x' == x] -- 2ª solución -- =========== arborea2 :: Eq a => [(a,a)] -> Bool arborea2 xs = length (nub padres \\ nub hijos) == 1 && and [cuenta x padres == 2 | x <- nub padres] where (padres, hijos) = unzip xs -- (cuenta x ys) es el número de ocurrencias de x en ys. Por ejemplo, -- cuenta 7 [7,2,7,7,5] == 3 cuenta :: Eq a => a -> [a] -> Int cuenta i = length . elemIndices i |