Menu Close

Etiqueta: Recursión

Definición por recursión

Reiteración de una función

Enunciado

-- Definir la función 
--    reiteracion :: Int -> (a -> a) -> a -> a
-- tal que (reiteracion n f x) es el resultado de aplicar n veces la
-- función f a x. Por ejemplo,
--    reiteracion 10 (+1) 5  ==  15
--    reiteracion 10 (+5) 0  ==  50
--    reiteracion  4 (*2) 1  ==  16
--    reiteracion1 4 (5:) [] ==  [5,5,5,5]
-- 
-- Comprobar con QuickCheck que se verifican las siguientes propiedades
--    reiteracion 10 (+1) x  == 10 + x 
--    reiteracion 10 (+x) 0  == 10 * x 
--    reiteracion 10 (x:) [] == replicate 10 x

Soluciones

-- 1ª definición (por recursión):
reiteracion1 :: Int -> (a -> a) -> a -> a
reiteracion1 0 f x = x
reiteracion1 n f x = f (reiteracion1 (n-1) f x)
 
-- 2ª definición (por recursión sin el 3ª argumento):
reiteracion2 :: Int -> (a -> a) -> a -> a
reiteracion2 0 f = id
reiteracion2 n f = f . reiteracion2 (n-1) f
 
-- 3ª definición (con iterate):
reiteracion3 :: Int -> (a -> a) -> a -> a
reiteracion3 n f x = (iterate f x) !! n

Enumeración de árboles binarios

Enunciado

-- Los árboles binarios se pueden representar mediante el tipo Arbol
-- definido por  
--    data Arbol a = H a 
--                 | N a (Arbol a) (Arbol a)
--                 deriving Show
-- Por ejemplo, el árbol
--         "B"
--         / \ 
--        /   \
--       /     \
--     "B"     "A"
--     / \     / \
--   "A" "B" "C" "C" 
-- se puede definir por 
--    ej1 :: Arbol String
--    ej1 = N "B" (N "B" (H "A") (H "B")) (N "A" (H "C") (H "C"))
--
-- Definir la función
--    enumeraArbol :: Arbol t -> Arbol Int
-- tal que (enumeraArbol a) es el árbol obtenido numerando las hojas y
-- los nodos de a desde la hoja izquierda hasta la raíz. Por ejemplo,
--    ghci> enumeraArbol ej1
--    N 6 (N 2 (H 0) (H 1)) (N 5 (H 3) (H 4))
-- Gráficamente, 
--          6 
--         / \ 
--        /   \
--       /     \
--      2       5 
--     / \     / \
--    0   1   3   4

Solución

data Arbol a = H a 
             | N a (Arbol a) (Arbol a)
             deriving Show
 
ej1 :: Arbol String
ej1 = N "B" (N "B" (H "A") (H "B")) (N "A" (H "C") (H "C"))
 
enumeraArbol :: Arbol t -> Arbol Int
enumeraArbol a = fst (aux a 0)
    where aux :: Arbol a -> Int -> (Arbol Int,Int)
          aux (H _) n     = (H n, n+1)
          aux (N x i d) n = (N n2 i1 d1, 1+n2)
                            where (i1, n1) = aux i n
                                  (d1, n2) = aux d n1

Trenzado de listas

Enunciado

-- Definir la función 
--    trenza :: [a] -> [a] -> [a]
-- tal que (trenza xs ys) es la lista obtenida intercalando los
-- elementos de xs e ys. Por ejemplo,
--    trenza [5,1] [2,7,4]             ==  [5,2,1,7]
--    trenza [5,1,7] [2..]             ==  [5,2,1,3,7,4]
--    trenza [2..] [5,1,7]             ==  [2,5,3,1,4,7]
--    take 8 (trenza [2,4..] [1,5..])  ==  [2,1,4,5,6,9,8,13]

Soluciones

-- 1ª definición (por comprensión):
trenza1 :: [a] -> [a] -> [a]
trenza1 xs ys = concat [[x,y] | (x,y) <- zip xs ys]
 
-- 2ª definición (por zipWith):
trenza2 :: [a] -> [a] -> [a]
trenza2 xs ys = concat (zipWith par xs ys)
    where par x y = [x,y]
 
-- 3ª definición (por zipWith y sin argumentos):
trenza3 :: [a] -> [a] -> [a]
trenza3 = (concat .) . zipWith par
    where par x y = [x,y]
 
-- 4ª definición (por recursión):
trenza4 :: [a] -> [a] -> [a]
trenza4 (x:xs) (y:ys) = x : y : trenza xs ys
trenza4 _      _      = []

Biparticiones de una lista

Enunciado

-- Definir la función
--    biparticiones :: [a] -> [([a],[a])]
-- tal que (biparticiones xs) es la lista de pares formados por un
-- prefijo de xs y el resto de xs. Por ejemplo,
--    ghci> biparticiones [3,2,5]
--    [([],[3,2,5]),([3],[2,5]),([3,2],[5]),([3,2,5],[])]
--    ghci> biparticiones "Roma"
--    [("","Roma"),("R","oma"),("Ro","ma"),("Rom","a"),("Roma","")]

Soluciones

import Data.List
 
-- 1ª definición (con splitAt):
biparticiones1 :: [a] -> [([a],[a])]
biparticiones1 xs = [splitAt i xs | i <- [0..length xs]]
 
-- 2ª definición (con inits y tails):
biparticiones2 :: [a] -> [([a],[a])]
biparticiones2 xs = zip (inits xs) (tails xs)
 
-- 3ª definición (por recursión):
biparticiones3 :: [a] -> [([a],[a])]
biparticiones3 [] = [([],[])] 
biparticiones3 (x:xs) = 
    ([],(x:xs)) : [(x:ys,zs) | (ys,zs) <- biparticiones3 xs]

Mayor producto de las ramas de un árbol

Enunciado

-- Los árboles se pueden representar mediante el siguiente tipo de datos
--    data Arbol a = N a [Arbol a]
--                   deriving Show
-- Por ejemplo, los árboles
--      1               3
--     / \             /|\ 
--    2   3           / | \
--        |          5  4  7
--        4          |     /\ 
--                   6    2  1
-- se representan por
--    ej1, ej2 :: Arbol Int
--    ej1 = N 1 [N 2 [],N 3 [N 4 []]]
--    ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]
-- 
-- Definir la función
--    mayorProducto :: (Ord a, Num a) => Arbol a -> a
-- tal que (mayorProducto a) es el mayor producto de las ramas del árbol
-- a. Por ejemplo,
--    ghci> mayorProducto (N 1 [N 2 [], N  3 []])
--    3
--    ghci> mayorProducto (N 1 [N 8 [], N  4 [N 3 []]])
--    12
--    ghci> mayorProducto (N 1 [N 2 [],N 3 [N 4 []]])
--    12
--    ghci> mayorProducto (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
--    90

Soluciones

data Arbol a = N a [Arbol a]
               deriving Show
 
-- 1º definición
mayorProducto1 :: (Ord a, Num a) => Arbol a -> a
mayorProducto1 (N x []) = x
mayorProducto1 (N x xs) = x * maximum [mayorProducto1 a | a <- xs]
 
-- Se puede usar map en lugar de comprensión:
mayorProducto1a :: (Ord a, Num a) => Arbol a -> a
mayorProducto1a (N x []) = x
mayorProducto1a (N x xs) = x * maximum (map mayorProducto1a xs)
 
-- 2ª definición
mayorProducto2 :: (Ord a, Num a) => Arbol a -> a
mayorProducto2 a = maximum [product xs | xs <- ramas a]
 
-- (ramas a) es la lista de las ramas del árbol a. Por ejemplo,
--    ghci> ramas (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
--    [[3,5,6],[3,4],[3,7,2],[3,7,1]]
ramas :: Arbol b -> [[b]]
ramas (N x []) = [[x]]
ramas (N x as) = [x : xs | a <- as, xs <- ramas a]
 
-- En la definición de mayorProducto2 se puede usar map en lugar de
-- comprensión. 
mayorProducto2a :: (Ord a, Num a) => Arbol a -> a
mayorProducto2a a = maximum (map product (ramas a))