Menu Close

Ejercicios sobre definiciones con unfoldr

La siguiente relación de ejercicios (elaborada para I1M) presenta una colección de funciones que se pueden definir usando unfoldr.

-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------
 
import Data.List (unfoldr)
import Test.QuickCheck
 
-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir, usando unfoldr, la función
--    rango :: Int -> Int -> [Int]
-- tal que (rango n m) es la lista de los números entre n y m, ambos
-- inclusive. Por ejemplo,
--    rango 2 9  ==  [2,3,4,5,6,7,8,9]
-- ---------------------------------------------------------------------
 
rango :: Int -> Int -> [Int]
rango n m = unfoldr f n
    where f x | x > m     = Nothing
              | otherwise = Just (x,x+1)
 
-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir, usando unfoldr, la función
--    grupos 3 [1..11]  ==  [[1,2,3],[4,5,6],[7,8,9],[10,11]]
-- tal que (grupos xs) es la lista obtenida agrupando en listas de
-- longitud n (salvo, posiblemente la última que puede tener menos
-- elementos) los elementos de xs. Por ejemplo,
--    grupos 3 [1..10]  ==  [[1,2,3],[4,5,6],[7,8,9],[10]]
-- ---------------------------------------------------------------------
 
grupos :: Int -> [a] -> [[a]]
grupos n = unfoldr f 
    where f [] = Nothing
          f xs = Just (take n xs, drop n xs)
 
-- ---------------------------------------------------------------------
-- Ejercicio 3. Redefinir, usando unfoldr, la función map. Por ejemplo,
--    map' (*2) [1..7]  ==  [2,4,6,8,10,12,14]
-- ---------------------------------------------------------------------
 
map' :: (a -> b) -> [a] -> [b]
map' f = unfoldr g
    where g []     = Nothing
          g (x:xs) = Just (f x, xs)
 
-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir, usando unfoldr, la función
--    enBase :: Int -> Int -> [Int]
-- tal que (enBase b n) es la lista de los dígitos de n en base b (en
-- orden inverso). Por ejemplo,
--    enBase 2 13  ==  [1,0,1,1]
--    enBase 3 13  ==  [1,1,1]
-- ---------------------------------------------------------------------
 
enBase :: Int -> Int -> [Int]
enBase b n = unfoldr f n
    where f 0 = Nothing
          f x = Just (x `rem` b, x `div` b)
 
-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir, usando unfoldr, la función
--    diagonal :: [[a]] -> [a]
-- tal que (diagonal xss) es la diagonal principal de la matriz xss. Por
-- ejemplo, 
--    diagonal [[1,3,2,7],[4,6,5,9],[2,5,0,3,7]]  ==  [1,6,0]
-- ---------------------------------------------------------------------
 
diagonal :: [[a]] -> [a]
diagonal xss = unfoldr f xss 
    where f []          = Nothing
          f ((x:_):xss) = Just (x, map tail xss)  
 
-- ---------------------------------------------------------------------
-- Ejercicio 6. Definir, usando unfoldr, la función
--    traspuesta :: [[a]] -> [[a]]
-- tal que (traspuesta xs) es la traspuesta de la matriz xss. Por
-- ejemplo, 
--    traspuesta [[1,3,7],[4,6,9],[2,5,0]]  ==  [[1,4,2],[3,6,5],[7,9,0]]
-- ---------------------------------------------------------------------
 
traspuesta :: [[a]] -> [[a]]
traspuesta xss = unfoldr f xss
    where f ([]:_) = Nothing
          f xss    = Just (map head xss, map tail xss)
 
-- ---------------------------------------------------------------------
-- Ejercicio 7. Comprobar con QuickCheck que 
--    unfoldr f xs == xs
-- donde f es la función definida por
--    f []     = Nothing
--    f (x:xs) = Just (x,xs)
-- ---------------------------------------------------------------------
 
-- La propiedad es
prop_unfoldr :: [Int] -> Bool
prop_unfoldr xs =
    unfoldr f xs == xs
    where f []     = Nothing
          f (x:xs) = Just (x,xs)
 
-- La comprobación es
--    ghci> quickCheck prop_unfoldr
--    +++ OK, passed 100 tests.
 
-- ---------------------------------------------------------------------
-- Ejercicio 8. Redefinir, usando unfoldr, la función iterate. Por
-- ejemplo, 
--    take 10 (iterate' (+2) 0)  ==  [0,2,4,6,8,10,12,14,16,18]
-- ---------------------------------------------------------------------
 
iterate' :: (a -> a) -> a -> [a]
iterate' f = unfoldr (\x -> Just (x, f x)) 
 
-- ---------------------------------------------------------------------
-- Ejercicio 9. Redefinir, usando unfoldr, la función repeat. Por
-- ejemplo, 
--    take 5 (repeat' 3)  ==  [3,3,3,3,3]
-- ---------------------------------------------------------------------
 
repeat' :: a -> [a]
repeat' x = unfoldr (\y -> Just (y,y)) x 
 
-- ---------------------------------------------------------------------
-- Ejercicio 10. Redefinir, usando unfoldr, la función takeWhile. Por
-- ejemplo, 
--    takeWhile' (<7) [2,3,9,4,5]  ==  [2,3]
-- ---------------------------------------------------------------------
 
takeWhile' :: (a -> Bool) -> [a] -> [a]
takeWhile' p  = unfoldr f 
    where f [] = Nothing
          f (x:xs) | p x       = Just (x,xs)
                   | otherwise = Nothing
 
-- ---------------------------------------------------------------------
-- Ejercicio 11. Redefinir, usando unfoldr, la función init. Por
-- ejemplo, 
--    init' [3..9]  ==  [3,4,5,6,7,8]
-- ---------------------------------------------------------------------
 
init' :: [a] -> [a]
init' = unfoldr f
    where f (x:y:zs) = Just(x,y:zs)
          f _        = Nothing
 
-- ---------------------------------------------------------------------
-- Ejercicio 12. Redefinir, usando unfoldr, la función zip. Por
-- ejemplo, 
--    zip' [1..5] [6..9]  ==  [(1,6),(2,7),(3,8),(4,9)]
--    zip' [1..4] [5..9]  ==  [(1,5),(2,6),(3,7),(4,8)]
-- ---------------------------------------------------------------------
 
zip' :: [a] -> [b] -> [(a, b)]
zip' xs ys = unfoldr f (xs,ys)
    where f (x:xs,y:ys) = Just ((x,y),(xs,ys))
          f _           = Nothing
 
-- ---------------------------------------------------------------------
-- Ejercicio 13. Redefinir, usando unfoldr, la función zip. Por
-- ejemplo, 
--    zipWith (*) [1..4] [5..9]  ==  [5,12,21,32]
-- ---------------------------------------------------------------------
 
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' g xs ys = unfoldr f (xs,ys)
    where f (x:xs,y:ys) = Just (g x y,(xs,ys))
          f _           = Nothing
 
-- ---------------------------------------------------------------------
-- Ejercicio 14. Definir, con unfoldr, la función
--    factoriales :: [Integer]
-- tal que factoriales es la lista de los factoriales. Por ejemplo,
--    take 10 factoriales  ==  [1,1,2,6,24,120,720,5040,40320,362880]
-- ---------------------------------------------------------------------
 
factoriales :: [Integer]
factoriales = 1 : unfoldr f (1,1)
    where f (x,y) = Just (x*y,(x*y,y+1))
 
-- ---------------------------------------------------------------------
-- Ejercicio 15. Definir, usando unfoldr, la función
--    fibs :: [Integer]
-- tal que fibs es la sucesión de Fibonacci. Por ejemplo,
--    take 10 fibs  ==  [0,1,1,2,3,5,8,13,21,34]
-- ---------------------------------------------------------------------
 
fibs :: [Integer]
fibs = 0 : 1: unfoldr f (0,1)
    where f (a,b) = Just (a+b,(b,b+a))
 
-- ---------------------------------------------------------------------
-- Ejercicio 16. El triángulo de Pascal es un triángulo de números
--          1
--         1 1
--        1 2 1
--      1  3 3  1
--     1 4  6  4 1
--    1 5 10 10 5 1
--   ...............
-- construido de la siguiente forma
-- * la primera fila está formada por el número 1;
-- * las filas siguientes se construyen sumando los números adyacentes
--   de la fila superior y añadiendo un 1 al principio y al final de la
--   fila. 
-- 
-- Definir, usando unfoldr, la función
--    pascal :: [[Integer]]
-- tal que pascal es la lista de las líneas del triángulo de Pascal. Por
-- ejemplo, 
--    ghci> take 6 pascal
--    [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]
-- ---------------------------------------------------------------------
 
pascal :: [[Integer]]
pascal = unfoldr f [1]
    where f xs = Just (xs, zipWith (+) (0:xs) (xs++[0]))
 
-- ---------------------------------------------------------------------
-- El triángulo de Floyd, llamado así en honor a Robert Floyd, es un
-- triángulo rectángulo formado con números naturales. Para crear un
-- triángulo de Floyd, se comienza con un 1 en la esquina superior
-- izquierda, y se continúa escribiendo la secuencia de los números
-- naturales de manera que cada línea contenga un número más que la
-- anterior. Las 5 primeras líneas del triángulo de Floyd son
--     1
--     2   3
--     4   5   6
--     7   8   9  10
--    11  12  13  14  15
-- 
-- El triángulo de Floyd tiene varias propiedades matemáticas
-- interesantes. Los números del cateto de la parte izquierda forman la
-- secuencia de los números poligonales centrales, mientras que los de
-- la hipotenusa nos dan el conjunto de los números triangulares.
-- 
-- Definir, usando unfoldr, la función        
--    trianguloFloyd :: [[Integer]]
-- tal que trianguloFloyd es el triángulo de Floyd. Por ejemplo,
--    ghci> take 4 trianguloFloyd
--    [[1],
--     [2,3],
--     [4,5,6],
--     [7,8,9,10]]
-- ---------------------------------------------------------------------
 
trianguloFloyd :: [[Int]]
trianguloFloyd = unfoldr f [1]
    where f xs = Just (xs,[a..a+n])
                 where a = 1 + last xs
                       n = length xs
 
-- ---------------------------------------------------------------------
-- Ejercicio 17. Lo números triangulares se forman como sigue
--    *     *      * 
--         * *    * *
--               * * *
--    1     3      6
-- 
-- La sucesión de los números triangulares se obtiene sumando los
-- números naturales. Así, los 5 primeros números triangulares son
--     1 = 1
--     3 = 1+2
--     6 = 1+2+3
--    10 = 1+2+3+4
--    15 = 1+2+3+4+5
-- 
-- Definir, usando unfoldr, la función
--    triangulares :: [Integer]
-- tal que triangulares es la lista de los números triangulares. Por
-- ejemplo, 
--    take 10 triangulares  ==  [1,3,6,10,15,21,28,36,45,55]
-- ---------------------------------------------------------------------
 
triangulares :: [Integer]
triangulares = unfoldr f (0,1)
    where f (x,y) = Just (x+y,(x+y,y+1))
I1M, PeH