import Data.List (groupBy, sort)
import Data.Function (on)
data Arbol a = N a [Arbol a]
deriving Show
ej1, ej2 :: Arbol Int
ej1 = N 1 [N 2 [], N 3 [N 4 []]]
ej2 = N 3 [N 5 [N 6 []],
N 4 [],
N 7 [N 2 [], N 8 [], N 6 []]]
-- 1ª solución
-- ===========
nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima a =
[x | (s,x) <- ns, s == m]
where ns = reverse (sort (nodosSumas a))
m = fst (head ns)
-- (nodosSumas x) es la lista de los pares (s,n) donde n es un nodo del
-- árbol x y s es la suma de sus hijos. Por ejemplo,
-- λ> nodosSumas ej1
-- [(5,1),(0,2),(4,3),(0,4)]
-- λ> nodosSumas ej2
-- [(16,3),(6,5),(0,6),(0,4),(16,7),(0,2),(0,8),(0,6)]
nodosSumas :: Num t => Arbol t -> [(t,t)]
nodosSumas (N x []) = [(0,x)]
nodosSumas (N x as) = (sum (raices as),x) : concatMap nodosSumas as
-- (raices b) es la lista de las raíces del bosque b. Por ejemplo,
-- raices [ej1,ej2] == [1,3]
raices :: [Arbol t] -> [t]
raices = map raiz
-- (raiz a) es la raíz del árbol a. Por ejemplo,
-- raiz ej1 == 1
-- raiz ej2 == 3
raiz :: Arbol t -> t
raiz (N x _) = x
-- 2ª solución
-- ===========
nodosSumaMaxima2 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima2 a =
[x | (s,x) <- ns, s == m]
where ns = sort (nodosOpSumas a)
m = fst (head ns)
-- (nodosOpSumas x) es la lista de los pares (s,n) donde n es un nodo del
-- árbol x y s es el opuesto de la suma de sus hijos. Por ejemplo,
-- λ> nodosOpSumas ej1
-- [(-5,1),(0,2),(-4,3),(0,4)]
-- λ> nodosOpSumas ej2
-- [(-16,3),(-6,5),(0,6),(0,4),(-16,7),(0,2),(0,8),(0,6)]
nodosOpSumas :: Num t => Arbol t -> [(t,t)]
nodosOpSumas (N x []) = [(0,x)]
nodosOpSumas (N x as) = (-sum (raices as),x) : concatMap nodosOpSumas as
-- 3ª solución
-- ===========
nodosSumaMaxima3 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima3 a =
[x | (s,x) <- ns, s == m]
where ns = sort (nodosOpSumas a)
m = fst (head ns)
-- 4ª solución
-- ===========
nodosSumaMaxima4 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima4 a =
map snd (head (groupBy (\p q -> fst p == fst q)
(sort (nodosOpSumas a))))
-- 5ª solución
-- ===========
nodosSumaMaxima5 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima5 a =
map snd (head (groupBy ((==) `on` fst)
(sort (nodosOpSumas a))))
-- 6ª solución
-- ===========
nodosSumaMaxima6 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima6 =
map snd
. head
. groupBy ((==) `on` fst)
. sort
. nodosOpSumas |