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
arborea :: Eq a => [(a,a)] -> Bool
tal que (arborea r) se verifica si la relación r es arbórea. Por ejemplo,
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
import Data.List (nub, sort, isPrefixOf) 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]