Refinamiento de montículos

José A. Alonso

28-05-2015

Definir la función

refina :: Ord a => Monticulo a -> [a -> Bool] -> Monticulo a

tal que (refina m ps) es el montículo formado por los elementos del montículo m que cumplen todos los predicados de la lista ps. Por ejemplo,

λ> refina (foldr inserta vacio [1..22]) [(<7), even]
M 2 1 (M 4 1 (M 6 1 Vacio Vacio) Vacio) Vacio
λ> refina (foldr inserta vacio [1..22]) [(<1), even]
Vacio

Soluciones

refina :: Ord a => Monticulo a -> [a-> Bool] -> Monticulo a
refina m ps | esVacio m   = vacio
            | cumple x ps = inserta x (refina r ps)
            | otherwise   = refina r ps
            where x = menor m
                  r = resto m

-- (cumple x ps) se verifica si x cumple todos los predicados de ps. Por
-- ejemplo,
--    cumple 2 [(<7), even]  ==  True
--    cumple 3 [(<7), even]  ==  False
--    cumple 8 [(<7), even]  ==  False
cumple :: a -> [a -> Bool] -> Bool
cumple x ps = and [p x | p <- ps]

-- La función cumple se puede definir por recursión:
cumple2 x []     = True
cumple2 x (p:ps) = p x && cumple x ps