Agrupamiento por propiedad

José A. Alonso

29-01-2016

Definir la función

agrupa :: (a -> Bool) -> [a] -> [[a]]

tal que (agrupa p xs) es la lista obtenida separando los elementos consecutivos de xs que verifican la propiedad p de los que no la verifican. Por ejemplo,

agrupa odd   [1,2,0,4,9,6,4,5,7,2]  ==  [[1],[2,0,4],[9],[6,4],[5,7],[2]]
agrupa even  [1,2,0,4,9,6,4,5,7,2]  ==  [[],[1],[2,0,4],[9],[6,4],[5,7],[2]]
agrupa (> 4) [1,2,0,4,9,6,4,5,7,2]  ==  [[],[1,2,0,4],[9,6],[4],[5,7],[2]]
agrupa (< 4) [1,2,0,4,9,6,4,5,7,2]  ==  [[1,2,0],[4,9,6,4,5,7],[2]]

Comprobar con QuickCheck que para cualquier propiedad p y cualquier lista xs, la concatenación de (agrupa p xs) es xs; es decir,

prop_agrupa :: Blind (Int -> Bool) -> [Int] -> Bool
prop_agrupa (Blind p) xs =
    concat (agrupa1 p xs) == xs

Nota. Usar la librería Test.QuickCheck.Modifiers.

Soluciones

import Test.QuickCheck
import Test.QuickCheck.Modifiers

-- 1ª solución
-- ===========

agrupa1 :: (a -> Bool) -> [a] -> [[a]]
agrupa1 p [] = []
agrupa1 p xs = takeWhile p xs : agrupa1 (not . p) (dropWhile p xs)

-- 2ª solución
-- ===========

agrupa2 :: (a -> Bool) -> [a] -> [[a]]
agrupa2 p [] = []
agrupa2 p xs = ys : agrupa2 (not . p) zs
    where (ys,zs) = span p xs

-- Propiedad
-- =========

-- La propiedad es
prop_agrupa :: Blind (Int -> Bool) -> [Int] -> Bool
prop_agrupa (Blind p) xs =
    concat (agrupa1 p xs) == xs

-- La comprobación es
--    λ> quickCheck prop_agrupa
--    +++ OK, passed 100 tests.