Llanuras de longitud dada
Enunciado
1 2 3 4 5 6 7 8 |
-- Una llanura de longitud n de una lista xs es una sublista de xs -- formada por n elementos iguales. -- -- Definir la función -- llanuras :: Eq a => Int -> [a] -> [[a]] -- tal que (llanuras n xs) es la lista de las llanuras de xs que tienen -- n elementos como mínimo. Por ejemplo, -- llanuras 3 "aabbbcddddffxffxx" == ["bbb","dddd"] |
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 44 45 |
import Data.List (group) import Test.QuickCheck -- 1ª definición (por comprensión): llanuras :: Eq a => Int -> [a] -> [[a]] llanuras n xs = [ys | ys <- group xs, length ys >= n] -- 2ª definición (por recursión con takeWhile y dropWhile): llanuras2 :: Eq a => Int -> [a] -> [[a]] llanuras2 _ [] = [] llanuras2 n xs@(x:_) | length ys >= n = ys : llanuras2 n (dropWhile (x==) xs) | otherwise = llanuras2 n (dropWhile (x==) xs) where ys = takeWhile (x==) xs -- 3ª definición (por recursión con span): llanuras3 :: Eq a => Int -> [a] -> [[a]] llanuras3 _ [] = [] llanuras3 n xs@(x:_) | length ys >= n = ys : llanuras3 n zs | otherwise = llanuras3 n zs where (ys,zs) = span (x==) xs -- 4ª definición (por recursión con span): llanuras4 :: Eq a => Int -> [a] -> [[a]] llanuras4 n = aux where aux [] = [] aux xs@(x:_) | length ys >= n = ys : llanuras4 n zs | otherwise = llanuras4 n zs where (ys,zs) = span (x==) xs -- --------------------------------------------------------------------- -- § Verificación -- -- --------------------------------------------------------------------- -- Las definiciones son equivalentes prop_equivalencia :: Int -> [Int] -> Bool prop_equivalencia n xs = llanuras2 n xs == ys && llanuras3 n xs == ys where ys = llanuras n xs -- La comprobación es -- ghci> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. |
Referencias
Esté ejercicio está basado en el problema Llanura de números iguales con longitud igual a n propuesto Solveet!
Usando una función lambda para no definir el predicado p: