{"id":6740,"date":"2022-03-11T06:00:22","date_gmt":"2022-03-11T04:00:22","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6740"},"modified":"2022-03-17T21:22:59","modified_gmt":"2022-03-17T19:22:59","slug":"segmentos-maximales-de-elementos-consecutivos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/segmentos-maximales-de-elementos-consecutivos\/","title":{"rendered":"Segmentos maximales de elementos consecutivos"},"content":{"rendered":"

Definir la funci\u00f3n<\/p>\n

\n   segmentos :: (Enum a, Eq a) => [a] -> [[a]]\n<\/pre>\n
tal que (segmentos xss) es la lista de los segmentos maximales de xss formados por elementos consecutivos. Por ejemplo,<\/p>\n
\n   segmentos [1,2,5,6,4]     ==  [[1,2],[5,6],[4]]\n   segmentos [1,2,3,4,7,8,9] ==  [[1,2,3,4],[7,8,9]]\n   segmentos \"abbccddeeebc\"  ==  [\"ab\",\"bc\",\"cd\",\"de\",\"e\",\"e\",\"bc\"]\n<\/pre>\n
Soluciones<\/h4>\n
[schedule expon=’2022-03-18′ expat=\u00bb06:00″]<\/p>\n
    \n
  • Las soluciones se pueden escribir en los comentarios hasta el 18 de marzo.\n
  • El c\u00f3digo se debe escribir entre una l\u00ednea con <pre lang="haskell"> y otra con <\/pre>\n<\/ul>\n
    [\/schedule]<\/p>\n
    [schedule on=’2022-03-18′ at=\u00bb06:00″]<\/p>\n
    \r\nimport Test.QuickCheck\r\n\r\n-- 1\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nsegmentos1 :: (Enum a, Eq a) => [a] -> [[a]]\r\nsegmentos1 []  = []\r\nsegmentos1 xs = ys : segmentos1 zs\r\n  where ys = inicial xs\r\n        n  = length ys\r\n        zs = drop n xs\r\n\r\n-- (inicial xs) es el segmento inicial de xs formado por elementos\r\n-- consecutivos. Por ejemplo,\r\n--    inicial [1,2,5,6,4]    ==  [1,2]\r\n--    inicial \"abccddeeebc\"  ==  \"abc\"\r\ninicial :: (Enum a, Eq a) => [a] -> [a]\r\ninicial []      = []\r\ninicial [x]     = [x]\r\ninicial (x:y:xs)\r\n  | succ x == y = x : inicial (y:xs)\r\n  | otherwise   = [x]\r\n\r\n-- 2\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nsegmentos2 :: (Enum a, Eq a) => [a] -> [[a]]\r\nsegmentos2 []  = []\r\nsegmentos2 xs = ys : segmentos2 zs\r\n  where (ys,zs) = inicialYresto xs\r\n\r\n-- (inicialYresto xs) es par formado por el segmento inicial de xs\r\n-- con elementos consecutivos junto con los restantes elementos. Por\r\n-- ejemplo,\r\n--    inicialYresto [1,2,5,6,4]    ==  ([1,2],[5,6,4])\r\n--    inicialYresto \"abccddeeebc\"  ==  (\"abc\",\"cddeeebc\")\r\ninicialYresto :: (Enum a, Eq a) => [a] -> ([a],[a])\r\ninicialYresto []      = ([],[])\r\ninicialYresto [x]     = ([x],[])\r\ninicialYresto (x:y:xs)\r\n  | succ x == y = (x:us,vs)\r\n  | otherwise   = ([x],y:xs)\r\n  where (us,vs) = inicialYresto (y:xs)\r\n\r\n-- 3\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nsegmentos3 :: (Enum a, Eq a) => [a] -> [[a]]\r\nsegmentos3 []  = []\r\nsegmentos3 [x] = [[x]]\r\nsegmentos3 (x:xs) | y == succ x = (x:y:ys):zs\r\n                  | otherwise   = [x] : (y:ys):zs\r\n  where ((y:ys):zs) = segmentos3 xs\r\n\r\n-- 4\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nsegmentos4 :: (Enum a, Eq a) => [a] -> [[a]]\r\nsegmentos4 []  = []\r\nsegmentos4 xs = ys : segmentos4 zs\r\n  where ys = inicial4 xs\r\n        n  = length ys\r\n        zs = drop n xs\r\n\r\ninicial4 :: (Enum a, Eq a) => [a] -> [a]\r\ninicial4 [] = []\r\ninicial4 (x:xs) =\r\n  map fst (takeWhile (\\(u,v) -> u == v) (zip (x:xs) [x..]))\r\n\r\n-- 5\u00aa soluci\u00f3n\r\n-- ===========\r\n\r\nsegmentos5 :: (Enum a, Eq a) => [a] -> [[a]]\r\nsegmentos5 []  = []\r\nsegmentos5 xs = ys : segmentos5 zs\r\n  where ys = inicial5 xs\r\n        n  = length ys\r\n        zs = drop n xs\r\n\r\ninicial5 :: (Enum a, Eq a) => [a] -> [a]\r\ninicial5 [] = []\r\ninicial5 (x:xs) =\r\n  map fst (takeWhile (uncurry (==)) (zip (x:xs) [x..]))\r\n\r\n-- Comprobaci\u00f3n de equivalencia\r\n-- ============================\r\n\r\n-- La propiedad es\r\nprop_segmentos :: [Int] -> Bool\r\nprop_segmentos xs =\r\n  all (== segmentos1 xs)\r\n      [segmentos2 xs,\r\n       segmentos3 xs,\r\n       segmentos4 xs,\r\n       segmentos5 xs]\r\n\r\n-- La comprobaci\u00f3n es\r\n--    \u03bb> quickCheck prop_segmentos\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Comparaci\u00f3n de eficiencia\r\n-- =========================\r\n\r\n-- La comparaci\u00f3n es\r\n--    \u03bb> length (segmentos1 (take (10^6) (cycle [1..10^3])))\r\n--    1000\r\n--    (0.69 secs, 416,742,208 bytes)\r\n--    \u03bb> length (segmentos2 (take (10^6) (cycle [1..10^3])))\r\n--    1000\r\n--    (0.66 secs, 528,861,976 bytes)\r\n--    \u03bb> length (segmentos3 (take (10^6) (cycle [1..10^3])))\r\n--    1000\r\n--    (2.35 secs, 1,016,276,896 bytes)\r\n--    \u03bb> length (segmentos4 (take (10^6) (cycle [1..10^3])))\r\n--    1000\r\n--    (0.27 secs, 409,438,368 bytes)\r\n--    \u03bb> length (segmentos5 (take (10^6) (cycle [1..10^3])))\r\n--    1000\r\n--    (0.13 secs, 401,510,360 bytes)\r\n--\r\n--    \u03bb> length (segmentos4 (take (10^7) (cycle [1..10^3])))\r\n--    10000\r\n--    (2.35 secs, 4,088,926,920 bytes)\r\n--    \u03bb> length (segmentos5 (take (10^7) (cycle [1..10^3])))\r\n--    10000\r\n--    (1.02 secs, 4,009,646,928 bytes)\r\n<\/pre>\n
    El c\u00f3digo se encuentra en [GitHub](https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Segmentos_consecutivos.hs).<\/p>\n
    La elaboraci\u00f3n de las soluciones explica en el siguiente v\u00eddeo:<\/p>\n