{"id":7719,"date":"2022-04-17T11:24:27","date_gmt":"2022-04-17T09:24:27","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7719"},"modified":"2022-04-17T11:24:27","modified_gmt":"2022-04-17T09:24:27","slug":"pfh-la-semana-en-exercitium-del-11-al-15-de-abril","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/pfh-la-semana-en-exercitium-del-11-al-15-de-abril\/","title":{"rendered":"PFH: La semana en Exercitium (del 11 al 15 de abril)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. Trenzado de listas<\/a><\/li>\n<li><a href=\"#ej2\">2. N\u00fameros triangulares con n cifras distintas<\/a><\/li>\n<li><a href=\"#ej3\">3. Enumeraci\u00f3n de \u00e1rboles binarios<\/a><\/li>\n<li><a href=\"#ej4\">4. Elementos de una matriz con alg\u00fan vecino menor<\/a><\/li>\n<li><a href=\"#ej5\">5. Reiteraci\u00f3n de una funci\u00f3n<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. Trenzado de listas<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   trenza :: [a] -> [a] -> [a]\n<\/pre>\n<p>tal que (trenza xs ys) es la lista obtenida intercalando los elementos de xs e ys. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   trenza [5,1] [2,7,4]             ==  [5,2,1,7]\n   trenza [5,1,7] [2..]             ==  [5,2,1,3,7,4]\n   trenza [2..] [5,1,7]             ==  [2,5,3,1,4,7]\n   take 8 (trenza [2,4..] [1,5..])  ==  [2,1,4,5,6,9,8,13]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ntrenza1 :: [a] -> [a] -> [a]\ntrenza1 []     _      = []\ntrenza1 _      []     = []\ntrenza1 (x:xs) (y:ys) = x : y : trenza1 xs ys\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ntrenza2 :: [a] -> [a] -> [a]\ntrenza2 (x:xs) (y:ys) = x : y : trenza2 xs ys\ntrenza2 _      _      = []\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ntrenza3 :: [a] -> [a] -> [a]\ntrenza3 xs ys = concat [[x,y] | (x,y) <- zip xs ys]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\ntrenza4 :: [a] -> [a] -> [a]\ntrenza4 xs ys = concat (zipWith par xs ys)\n\npar :: a -> a -> [a]\npar x y = [x,y]\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\n-- Explicaci\u00f3n de eliminaci\u00f3n de argumentos en composiciones con varios\n-- argumentos:\n\nf :: Int -> Int\nf x = x + 1\n\ng :: Int -> Int -> Int\ng x y = x + y\n\nh1, h2, h3, h4, h5, h6, h7 :: Int -> Int -> Int\nh1 x y  = f (g x y)\nh2 x y  = f ((g x) y)\nh3 x y  = (f . (g x)) y\nh4 x    = f . (g x)\nh5 x    = (f .) (g x)\nh6 x    = ((f .) . g) x\nh7      = (f .) . g\n\nprop_composicion :: Int -> Int -> Bool\nprop_composicion x y =\n  all (== h1 x y)\n      [p x y | p <- [h2, h3, h4, h5, h6, h7]]\n\n-- \u03bb> quickCheck prop_composicion\n-- +++ OK, passed 100 tests.\n\n-- En general,\n--    f . g             --> \\x -> f (g x)\n--    (f .) . g         --> \\x y -> f (g x y)\n--    ((f .) .) . g     --> \\x y z -> f (g x y z)\n--    (((f .) .) .) . g --> \\w x y z -> f (g w x y z)\n\ntrenza5 :: [a] -> [a] -> [a]\ntrenza5 = (concat .) . zipWith par\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_trenza :: [Int] -> [Int] -> Bool\nprop_trenza xs ys =\n  all (== trenza1 xs ys)\n      [trenza2 xs ys,\n       trenza3 xs ys,\n       trenza4 xs ys,\n       trenza5 xs ys]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_trenza\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> last (trenza1 [1,1..] [1..4*10^6])\n--    4000000\n--    (2.33 secs, 1,472,494,952 bytes)\n--    \u03bb> last (trenza2 [1,1..] [1..4*10^6])\n--    4000000\n--    (2.24 secs, 1,376,494,928 bytes)\n--    \u03bb> last (trenza3 [1,1..] [1..4*10^6])\n--    4000000\n--    (1.33 secs, 1,888,495,048 bytes)\n--    \u03bb> last (trenza4 [1,1..] [1..4*10^6])\n--    4000000\n--    (0.76 secs, 1,696,494,968 bytes)\n--    \u03bb> last (trenza5 [1,1..] [1..4*10^6])\n--    4000000\n--    (0.76 secs, 1,696,495,064 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Trenzado_de_listas.hs\">GitHub<\/a>.<\/p>\n<p>La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n<p><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/zAqtMXDBt7A\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. N\u00fameros triangulares con n cifras distintas<\/h3>\n<p>Los n\u00fameros triangulares se forman como sigue<\/p>\n<pre lang=\"text\">\n   *     *      *\n        * *    * *\n              * * *\n   1     3      6\n<\/pre>\n<p>La sucesi\u00f3n de los n\u00fameros triangulares se obtiene sumando los n\u00fameros naturales. As\u00ed, los 5 primeros n\u00fameros triangulares son<\/p>\n<pre lang=\"text\">\n    1 = 1\n    3 = 1 + 2\n    6 = 1 + 2 + 3\n   10 = 1 + 2 + 3 + 4\n   15 = 1 + 2 + 3 + 4 + 5\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   triangularesConCifras :: Int -> [Integer]\n<\/pre>\n<p>tal que <code>(triangulares n)<\/code> es la lista de los n\u00fameros triangulares con <code>n<\/code> cifras distintas. Por  ejemplo,<\/p>\n<pre lang=\"text\">\n   take 6 (triangularesConCifras 1)   ==  [1,3,6,55,66,666]\n   take 6 (triangularesConCifras 2)   ==  [10,15,21,28,36,45]\n   take 6 (triangularesConCifras 3)   ==  [105,120,136,153,190,210]\n   take 5 (triangularesConCifras 4)   ==  [1035,1275,1326,1378,1485]\n   take 2 (triangularesConCifras 10)  ==  [1062489753,1239845706]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (nub)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ntriangularesConCifras1 :: Int -> [Integer]\ntriangularesConCifras1 n =\n  [x | x <- triangulares1,\n       nCifras x == n]\n\n-- triangulares1 es la lista de los n\u00fameros triangulares. Por ejemplo,\n--    take 10 triangulares1 == [1,3,6,10,15,21,28,36,45,55]\ntriangulares1 :: [Integer]\ntriangulares1 = map triangular [1..]\n\ntriangular :: Integer -> Integer\ntriangular 1 = 1\ntriangular n = triangular (n-1) + n\n\n-- (nCifras x) es el n\u00famero de cifras distintas del n\u00famero x. Por\n-- ejemplo,\n--    nCifras 325275  ==  4\nnCifras :: Integer -> Int\nnCifras = length . nub . show\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ntriangularesConCifras2 :: Int -> [Integer]\ntriangularesConCifras2 n =\n  [x | x <- triangulares2,\n       nCifras x == n]\n\ntriangulares2 :: [Integer]\ntriangulares2 = [(n*(n+1)) `div` 2 | n <- [1..]]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ntriangularesConCifras3 :: Int -> [Integer]\ntriangularesConCifras3 n =\n  [x | x <- triangulares3,\n       nCifras x == n]\n\ntriangulares3 :: [Integer]\ntriangulares3 = 1 : [x+y | (x,y) <- zip [2..] triangulares3]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\ntriangularesConCifras4 :: Int -> [Integer]\ntriangularesConCifras4 n =\n  [x | x <- triangulares4,\n       nCifras x == n]\n\ntriangulares4 :: [Integer]\ntriangulares4 = 1 : zipWith (+) [2..] triangulares4\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\ntriangularesConCifras5 :: Int -> [Integer]\ntriangularesConCifras5 n =\n  [x | x <- triangulares5,\n       nCifras x == n]\n\ntriangulares5 :: [Integer]\ntriangulares5 = scanl (+) 1 [2..]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La 1\u00aa propiedad es\nprop_triangularesConCifras1 :: Bool\nprop_triangularesConCifras1 =\n  [take 2 (triangularesConCifras1 n) | n <- [1..7]] ==\n  [take 2 (triangularesConCifras2 n) | n <- [1..7]]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> prop_triangularesConCifras1\n--    True\n\n-- La 2\u00aa propiedad es\nprop_triangularesConCifras2 :: Int -> Bool\nprop_triangularesConCifras2 n =\n  all (== take 5 (triangularesConCifras2 n'))\n      [take 5 (triangularesConCifras3 n'),\n       take 5 (triangularesConCifras4 n'),\n       take 5 (triangularesConCifras5 n')]\n  where n' = 1 + n `mod` 9\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_triangularesConCifras\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> (triangularesConCifras1 3) !! 220\n--    5456556\n--    (2.48 secs, 1,228,690,120 bytes)\n--    \u03bb> (triangularesConCifras2 3) !! 220\n--    5456556\n--    (0.01 secs, 4,667,288 bytes)\n--\n--    \u03bb> (triangularesConCifras2 3) !! 600\n--    500010500055\n--    (1.76 secs, 1,659,299,872 bytes)\n--    \u03bb> (triangularesConCifras3 3) !! 600\n--    500010500055\n--    (1.67 secs, 1,603,298,648 bytes)\n--    \u03bb> (triangularesConCifras4 3) !! 600\n--    500010500055\n--    (1.20 secs, 1,507,298,248 bytes)\n--    \u03bb> (triangularesConCifras5 3) !! 600\n--    500010500055\n--    (1.15 secs, 1,507,298,256 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Triangulares_con_cifras.hs\">GitHub<\/a>.<\/p>\n<p>La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n<p><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/_Ic-384xp2I\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Enumeraci\u00f3n de \u00e1rboles binarios<\/h3>\n<p>Los \u00e1rboles binarios se pueden representar mediante el tipo Arbol definido por<\/p>\n<pre lang=\"text\">\n   data Arbol a = H a\n                | N (Arbol a) a (Arbol a)\n      deriving Show\n<\/pre>\n<p>Por ejemplo, el \u00e1rbol<\/p>\n<pre lang=\"text\">\n        \"B\"\n        \/ \\\n       \/   \\\n      \/     \\\n    \"B\"     \"A\"\n    \/ \\     \/ \\\n  \"A\" \"B\" \"C\" \"C\"\n<\/pre>\n<p>se puede definir por<\/p>\n<pre lang=\"text\">\n   ej1 :: Arbol String\n   ej1 = N (N (H \"A\") \"B\" (H \"B\")) \"B\" (N (H \"C\") \"A\" (H \"C\"))\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   enumeraArbol :: Arbol t -> Arbol Int\n<\/pre>\n<p>tal que (enumeraArbol a) es el \u00e1rbol obtenido numerando las hojas y los nodos de a desde la hoja izquierda hasta la ra\u00edz. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> enumeraArbol ej1\n   N (N (H 0) 1 (H 2)) 3 (N (H 4) 5 (H 6))\n<\/pre>\n<p>Gr\u00e1ficamente,<\/p>\n<pre lang=\"text\">\n         3\n        \/ \\\n       \/   \\\n      \/     \\\n     1       5\n    \/ \\     \/ \\\n   0   2   4   6\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck (Arbitrary, Gen, arbitrary, quickCheck, sized)\nimport Control.Monad.State (State, evalState, get, put)\n\ndata Arbol a = H a\n             | N (Arbol a) a (Arbol a)\n  deriving (Show, Eq)\n\nej1 :: Arbol String\nej1 = N (N (H \"A\") \"B\" (H \"B\")) \"B\" (N (H \"C\") \"A\" (H \"C\"))\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nenumeraArbol1 :: Arbol t -> Arbol Int\nenumeraArbol1 a = fst (aux a 0)\n  where aux :: Arbol t -> Int -> (Arbol Int, Int)\n        aux (H _) n     = (H n, n+1)\n        aux (N i _ d) n = (N i' n1 d', n2)\n          where (i', n1) = aux i n\n                (d', n2) = aux d (n1+1)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nenumeraArbol2 :: Arbol t -> Arbol Int\nenumeraArbol2 a = evalState (aux a) 0\n  where aux :: Arbol t -> State Int (Arbol Int)\n        aux (H _)     = H <$> contador\n        aux (N i _ d) = do\n          i' <- aux i\n          n1 <- contador\n          d' <- aux d\n          return (N i' n1 d')\n\ncontador :: State Int Int\ncontador = do\n  n <- get\n  put (n+1)\n  return n\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nenumeraArbol3 :: Arbol t -> Arbol Int\nenumeraArbol3 a = evalState (aux a) 0\n  where aux :: Arbol t -> State Int (Arbol Int)\n        aux (H _)     = H <$> contador\n        aux (N i _ d) = N <$> aux i <*> contador <*> aux d\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- (arbolArbitrario n) genera un \u00e1rbol aleatorio de orden n. Por\n-- ejemplo,\n--    \u03bb> generate (arbolArbitrario 3 :: Gen (Arbol Int))\n--    N (N (H 19) 0 (H (-27))) 21 (N (H 2) 17 (H 26))\narbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)\narbolArbitrario n\n  | n <= 0    = H <$> arbitrary\n  | otherwise = N <$> subarbol <*> arbitrary <*> subarbol\n  where subarbol = arbolArbitrario (n `div` 2)\n\n-- Arbol es una subclase de Arbitrary.\ninstance Arbitrary a => Arbitrary (Arbol a) where\n  arbitrary = sized arbolArbitrario\n\n-- La propiedad es\nprop_enumeraArbol :: Arbol Int -> Bool\nprop_enumeraArbol a =\n  all (== enumeraArbol1 a)\n      [enumeraArbol2 a,\n       enumeraArbol3 a]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_enumeraArbol\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Enumera_arbol.hs\">GitHub<\/a>.<\/p>\n<p>La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n<p><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/JbLEKUZ2E2M\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Elementos de una matriz con alg\u00fan vecino menor<\/h3>\n<p>Las matrices pueden representarse mediante tablas cuyos \u00edndices son pares de n\u00fameros naturales. Su tipo se define por<\/p>\n<pre lang=\"text\">\n   type Matriz = Array (Int,Int) Int\n<\/pre>\n<p>Por ejemplo, la matriz<\/p>\n<pre lang=\"text\">\n   |9 4 6 5|\n   |8 1 7 3|\n   |4 2 5 4|\n<\/pre>\n<p>se define por<\/p>\n<pre lang=\"text\">\n   ej :: Matriz\n   ej = listArray ((1,1),(3,4)) [9,4,6,5,8,1,7,3,4,2,5,4]\n<\/pre>\n<p>Los vecinos de un elemento son los que est\u00e1n a un paso en la misma fila, columna o diagonal. Por ejemplo, en la matriz anterior, el 1 tiene 8 vecinos (el 9, 4, 6, 8, 7, 4, 2 y 5) pero el 9 s\u00f3lo tiene 3 vecinos (el 4, 8 y 1).<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   algunoMenor :: Matriz -> [Int]\n<\/pre>\n<p>tal que <code>(algunoMenor p)<\/code> es la lista de los elementos de <code>p<\/code> que tienen alg\u00fan vecino menor que \u00e9l. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   algunoMenor ej == [9,4,6,5,8,7,4,2,5,4]\n<\/pre>\n<p>pues s\u00f3lo el 1 y el 3 no tienen ning\u00fan vecino menor en la matriz.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Array (Array, (!), bounds, indices, inRange, listArray)\nimport Test.QuickCheck (Arbitrary, Gen, arbitrary, chooseInt, quickCheck,\n                        vectorOf)\n\ntype Matriz = Array (Int,Int) Int\n\nej :: Matriz\nej = listArray ((1,1),(3,4)) [9,4,6,5,8,1,7,3,4,2,5,4]\n\ntype Pos = (Int,Int)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nalgunoMenor1 :: Matriz -> [Int]\nalgunoMenor1 a =\n  [a!p| p <- indices a,\n        any (< a!p) (vecinos1 a p)]\n\n-- (vecinos q p) es la lista de los vecinos en la matriz a de la\n-- posici\u00f3n p. Por ejemplo,\n--    vecinos1 ej (2,2)  ==  [9,4,6,8,7,4,2,5]\n--    vecinos1 ej (1,1)  ==  [4,8,1]\nvecinos1 :: Matriz -> Pos -> [Int]\nvecinos1 a p =\n  [a!p' | p' <- posicionesVecinos1 a p]\n\n-- (posicionesVecinos a p) es la lista de las posiciones de los\n-- vecino de p en la matriz a. Por ejemplo,\n--    \u03bb> posicionesVecinos1 3 3 (2,2)\n--    [(1,1),(1,2),(1,3),(2,1),(2,3),(3,1),(3,2),(3,3)]\n--    \u03bb> posicionesVecinos1 3 3 (1,1)\n--    [(1,2),(2,1),(2,2)]\nposicionesVecinos1 :: Matriz -> Pos -> [Pos]\nposicionesVecinos1 a (i,j) =\n  [(i+di,j+dj) | (di,dj) <- [(-1,-1),(-1,0),(-1,1),\n                             ( 0,-1),       ( 0,1),\n                             ( 1,-1),( 1,0),( 1,1)],\n                 inRange (bounds a) (i+di,j+dj)]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nalgunoMenor2 :: Matriz -> [Int]\nalgunoMenor2 a =\n  [a!p | p <- indices a,\n         any (<a!p) (vecinos2 p)]\n  where\n    vecinos2 p =\n      [a!p' | p' <- posicionesVecinos2 p]\n    posicionesVecinos2 (i,j) =\n      [(i+di,j+dj) | (di,dj) <- [(-1,-1),(-1,0),(-1,1),\n                                 ( 0,-1),       ( 0,1),\n                                 ( 1,-1),( 1,0),( 1,1)],\n                     inRange (bounds a) (i+di,j+dj)]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nalgunoMenor3 :: Matriz -> [Int]\nalgunoMenor3 a =\n  [a!p | p <- indices a,\n         any (<a!p) (vecinos3 p)]\n  where\n    vecinos3 p =\n      [a!p' | p' <- posicionesVecinos3 p]\n    posicionesVecinos3 (i,j) =\n      [(i',j') | i' <- [i-1..i+1],\n                 j' <- [j-1..j+1],\n                 (i',j') \/= (i,j),\n                 inRange (bounds a) (i',j')]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nalgunoMenor4 :: Matriz -> [Int]\nalgunoMenor4 a =\n  [a!p | p <- indices a,\n         any (<a!p) (vecinos4 p)]\n  where\n    vecinos4 p =\n      [a!p' | p' <- posicionesVecinos4 p]\n    posicionesVecinos4 (i,j) =\n      [(i',j') | i' <- [max 1 (i-1)..min m (i+1)],\n                 j' <- [max 1 (j-1)..min n (j+1)],\n                 (i',j') \/= (i,j)]\n      where (_,(m,n)) = bounds a\n\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nalgunoMenor5 :: Matriz -> [Int]\nalgunoMenor5 a =\n  [a!p | p <- indices a,\n         any (<a!p) (vecinos5 p)]\n  where\n    vecinos5 p =\n      [a!p' | p' <- posicionesVecinos5 p]\n    posicionesVecinos5 (i,j) =\n      [(i-1,j-1) | i > 1, j > 1] ++\n      [(i-1,j)   | i > 1]        ++\n      [(i-1,j+1) | i > 1, j < n] ++\n      [(i,j-1)   | j > 1]        ++\n      [(i,j+1)   | j < n]        ++\n      [(i+1,j-1) | i < m, j > 1] ++\n      [(i+1,j)   | i < m]        ++\n      [(i+1,j+1) | i < m, j < n]\n      where (_,(m,n)) = bounds a\n\n-- ---------------------------------------------------------------------\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\nnewtype Matriz2 = M Matriz\n  deriving Show\n\n-- Generador de matrices arbitrarias. Por ejemplo,\n--    \u03bb> generate matrizArbitraria\n--    M (array ((1,1),(3,4))\n--             [((1,1),18),((1,2),6), ((1,3),-23),((1,4),-13),\n--              ((2,1),-2),((2,2),22),((2,3),-25),((2,4),-5),\n--              ((3,1),2), ((3,2),16),((3,3),-15),((3,4),7)])\nmatrizArbitraria :: Gen Matriz2\nmatrizArbitraria = do\n  m  <- chooseInt (1,10)\n  n  <- chooseInt (1,10)\n  xs <- vectorOf (m*n) arbitrary\n  return (M (listArray ((1,1),(m,n)) xs))\n\n-- Matriz es una subclase de Arbitrary.\ninstance Arbitrary Matriz2 where\n  arbitrary = matrizArbitraria\n\n-- La propiedad es\nprop_algunoMenor :: Matriz2 -> Bool\nprop_algunoMenor (M p) =\n  all (== algunoMenor1 p)\n      [algunoMenor2 p,\n       algunoMenor3 p,\n       algunoMenor4 p,\n       algunoMenor5 p]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_algunoMenor\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> maximum (algunoMenor1 (listArray ((1,1),(600,800)) [0..]))\n--    479999\n--    (2.20 secs, 1,350,075,240 bytes)\n--    \u03bb> maximum (algunoMenor2 (listArray ((1,1),(600,800)) [0..]))\n--    479999\n--    (2.24 secs, 1,373,139,968 bytes)\n--    \u03bb> maximum (algunoMenor3 (listArray ((1,1),(600,800)) [0..]))\n--    479999\n--    (2.08 secs, 1,200,734,112 bytes)\n--    \u03bb> maximum (algunoMenor4 (listArray ((1,1),(600,800)) [0..]))\n--    479999\n--    (2.76 secs, 1,287,653,136 bytes)\n--    \u03bb> maximum (algunoMenor5 (listArray ((1,1),(600,800)) [0..]))\n--    479999\n--    (1.67 secs, 953,937,600 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Algun_vecino_menor.hs\">GitHub<\/a>.<\/p>\n<p>La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n<p><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/ZILfrx75FyM\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Reiteraci\u00f3n de una funci\u00f3n<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   reiteracion :: (a -> a) -> Int -> a -> a\n   <\/pre>\n<p>tal que <code>(reiteracion f n x)<\/code> es el resultado de aplicar <code>n<\/code> veces la funci\u00f3n <code>f<\/code> a <code>x<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   reiteracion (+1) 10 5  ==  15\n   reiteracion (+5) 10 0  ==  50\n   reiteracion (*2)  4 1  ==  16\n   reiteracion (5:)  4 [] ==  [5,5,5,5]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck (Fun (..), Positive (..), quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nreiteracion1 :: (a -> a) -> Int -> a -> a\nreiteracion1 _ 0 x = x\nreiteracion1 f n x = f (reiteracion1 f (n-1) x)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nreiteracion2 :: (a -> a) -> Int -> a -> a\nreiteracion2 _ 0 = id\nreiteracion2 f n = f . reiteracion2 f (n-1)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nreiteracion3 :: (a -> a) -> Int -> a -> a\nreiteracion3 _ 0 = id\nreiteracion3 f n\n  | even n    = reiteracion3 (f . f) (n `div` 2)\n  | otherwise = f . reiteracion3 (f . f) (n `div` 2)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nreiteracion4 :: (a -> a) -> Int -> a -> a\nreiteracion4 f n x = reiteraciones f x !! n\n\nreiteraciones :: (a -> a) -> a -> [a]\nreiteraciones f x = x : reiteraciones f (f x)\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nreiteracion5 :: (a -> a) -> Int -> a -> a\nreiteracion5 f n x = (iterate f x) !! n\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\n-- Se puede eliminar los argumentos de la definici\u00f3n anterior como sigue:\n--    reiteracion4 f n x = iterate f x !! n\n--    reiteracion4 f n x = ((!!) (iterate f x)) n\n--    reiteracion4 f n x = (((!!) . (iterate f)) x) n\n--    reiteracion4 f n x = ((!!) . (iterate f)) x n\n--    reiteracion4 f n x = flip ((!!) . (iterate f)) n x\n--    reiteracion4 f = flip ((!!) . (iterate f))\n--    reiteracion4 f = flip (((!!) .) (iterate f))\n--    reiteracion4 f = flip (((!!) .) . iterate) f\n--    reiteracion4 f = (flip . ((!!) .) . iterate) f\n--    reiteracion4   = flip . ((!!) .) . iterate\n\nreiteracion6 :: (a -> a) -> Int -> a -> a\nreiteracion6 = flip . ((!!) .) . iterate\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_reiteracion :: Fun Int Int -> Positive Int -> Int -> Bool\nprop_reiteracion (Fun _ f) (Positive n) x =\n  all (== reiteracion1 f n x)\n      [reiteracion2 f n x,\n       reiteracion3 f n x,\n       reiteracion4 f n x,\n       reiteracion5 f n x,\n       reiteracion6 f n x]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_reiteracion\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> reiteracion1 (+1) (10^7) 0\n--    10000000\n--    (5.09 secs, 2,505,392,792 bytes)\n--    \u03bb> reiteracion2 (+1) (10^7) 0\n--    10000000\n--    (5.45 secs, 2,896,899,728 bytes)\n--    \u03bb> reiteracion3 (+1) (10^7) 0\n--    10000000\n--    (2.14 secs, 816,909,416 bytes)\n--    \u03bb> reiteracion4 (+1) (10^7) 0\n--    10000000\n--    (4.24 secs, 1,696,899,816 bytes)\n--    \u03bb> reiteracion5 (+1) (10^7) 0\n--    10000000\n--    (2.53 secs, 1,376,899,800 bytes)\n--    \u03bb> reiteracion6 (+1) (10^7) 0\n--    10000000\n--    (2.34 secs, 1,376,899,984 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Reiteracion_de_funciones.hs\">GitHub<\/a>.<\/p>\n<p>La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n<p><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/1Kig_ipFIu0\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. Trenzado de listas 2. N\u00fameros triangulares con n cifras distintas 3. Enumeraci\u00f3n de \u00e1rboles binarios 4. Elementos de una matriz con alg\u00fan vecino menor 5. Reiteraci\u00f3n de una funci\u00f3n A continuaci\u00f3n se muestran las soluciones.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[337],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7719"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=7719"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7719\/revisions"}],"predecessor-version":[{"id":7720,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7719\/revisions\/7720"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7719"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7719"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7719"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}