Exercitium

Elemento más cercano que cumple una propiedad

PorJosé A. Alonso 9-julio-201426-marzo-2022

-- Definir la función
--    cercano :: (a -> Bool) -> Int -> [a] -> Maybe a
-- tal que (cercano p n xs) es el elemento de xs más cercano a n que
-- verifica la propiedad p. La búsqueda comienza en n y los elementos se
-- analizan en el siguiente orden: n, n+1, n-1, n+2, n-2,... Por ejemplo, 
--    cercano (`elem` "aeiou") 6 "Sevilla"     ==  Just 'a'
--    cercano (`elem` "aeiou") 1 "Sevilla"     ==  Just 'e'
--    cercano (`elem` "aeiou") 2 "Sevilla"     ==  Just 'i'
--    cercano (`elem` "aeiou") 5 "Sevilla"     ==  Just 'a'
--    cercano (`elem` "aeiou") 9 "Sevilla"     ==  Just 'a'
--    cercano (`elem` "aeiou") (-3) "Sevilla"  ==  Just 'e'
--    cercano (>100) 4 [200,1,150,2,4]         ==  Just 150
--    cercano even 5 [1,3..99]                 ==  Nothing

-- Definir la función

-- cercano :: (a -> Bool) -> Int -> [a] -> Maybe a

-- tal que (cercano p n xs) es el elemento de xs más cercano a n que

-- verifica la propiedad p. La búsqueda comienza en n y los elementos se

-- analizan en el siguiente orden: n, n+1, n-1, n+2, n-2,... Por ejemplo,

-- cercano (`elem` "aeiou") 6 "Sevilla" == Just 'a'

-- cercano (`elem` "aeiou") 1 "Sevilla" == Just 'e'

-- cercano (`elem` "aeiou") 2 "Sevilla" == Just 'i'

-- cercano (`elem` "aeiou") 5 "Sevilla" == Just 'a'

-- cercano (`elem` "aeiou") 9 "Sevilla" == Just 'a'

-- cercano (`elem` "aeiou") (-3) "Sevilla" == Just 'e'

-- cercano (>100) 4 [200,1,150,2,4] == Just 150

-- cercano even 5 [1,3..99] == Nothing

Soluciones

import Data.List

-- 1ª solución
-- ===========

cercano1 :: (a -> Bool) -> Int -> [a] -> Maybe a
cercano1 p n xs | null ys   = Nothing
                | otherwise = Just (head ys)
    where ys = filter p (ordenaPorCercanos xs n)

-- (ordenaPorCercanos xs n) es la lista de los elementos de xs que
-- ocupan las posiciones n, n+1, n-1, n+2, n-2... Por ejemplo, 
--    ordenaPorCercanos [0..9] 4     ==  [4,5,3,6,2,7,1,8,0,9]
--    ordenaPorCercanos [0..9] 7     ==  [7,8,6,9,5,4,3,2,1,0]
--    ordenaPorCercanos [0..9] 2     ==  [2,3,1,4,0,5,6,7,8,9]
--    ordenaPorCercanos [0..9] (-3)  ==  [0,1,2,3,4,5,6,7,8,9]
--    ordenaPorCercanos [0..9] 20    ==  [9,8,7,6,5,4,3,2,1,0]
ordenaPorCercanos :: [a] -> Int -> [a]
ordenaPorCercanos xs n 
    | n < 0          = xs
    | n >= length xs = reverse xs
    | otherwise      = z : intercala zs (reverse ys)
    where (ys,(z:zs)) = splitAt n xs

-- (intercala xs ys) es la lista obtenida intercalando los elementos de
-- las lista xs e ys. Por ejemplo,
--    intercala [1..4] [5..10]   ==  [1,5,2,6,3,7,4,8,9,10]
--    intercala [5..10] [1..4]   ==  [5,1,6,2,7,3,8,4,9,10]
intercala :: [a] -> [a] -> [a]
intercala [] ys = ys
intercala xs [] = xs
intercala (x:xs) (y:ys) = x : y : intercala xs ys

-- 2ª solución (usando find)
-- =========================

cercano2 :: (a -> Bool) -> Int -> [a] -> Maybe a
cercano2 p n xs = find p (ordenaPorCercanos xs n)

import Data.List

-- 1ª solución

-- ===========

cercano1 :: (a -> Bool) -> Int -> [a] -> Maybe a

cercano1 p n xs | null ys = Nothing

| otherwise = Just (head ys)

where ys = filter p (ordenaPorCercanos xs n)

-- (ordenaPorCercanos xs n) es la lista de los elementos de xs que

-- ocupan las posiciones n, n+1, n-1, n+2, n-2... Por ejemplo,

-- ordenaPorCercanos [0..9] 4 == [4,5,3,6,2,7,1,8,0,9]

-- ordenaPorCercanos [0..9] 7 == [7,8,6,9,5,4,3,2,1,0]

-- ordenaPorCercanos [0..9] 2 == [2,3,1,4,0,5,6,7,8,9]

-- ordenaPorCercanos [0..9] (-3) == [0,1,2,3,4,5,6,7,8,9]

-- ordenaPorCercanos [0..9] 20 == [9,8,7,6,5,4,3,2,1,0]

ordenaPorCercanos :: [a] -> Int -> [a]

ordenaPorCercanos xs n

| n < 0 = xs

| n >= length xs = reverse xs

| otherwise = z : intercala zs (reverse ys)

where (ys,(z:zs)) = splitAt n xs

-- (intercala xs ys) es la lista obtenida intercalando los elementos de

-- las lista xs e ys. Por ejemplo,

-- intercala [1..4] [5..10] == [1,5,2,6,3,7,4,8,9,10]

-- intercala [5..10] [1..4] == [5,1,6,2,7,3,8,4,9,10]

intercala :: [a] -> [a] -> [a]

intercala [] ys = ys

intercala xs [] = xs

intercala (x:xs) (y:ys) = x : y : intercala xs ys

-- 2ª solución (usando find)

-- =========================

cercano2 :: (a -> Bool) -> Int -> [a] -> Maybe a

cercano2 p n xs = find p (ordenaPorCercanos xs n)

Referencia

El ejercicio está basado en el problema del 12 de mayo de 1HaskellADay.

Ventana deslizante

PorJosé A. Alonso 7-julio-20141-mayo-2015

-- Definir la función
--    ventanas :: Int -> Int -> [a] -> [[a]]
-- tal que (ventanas x y zs) es la lista de ventanas de zs de tamaño x
-- y deslizamiento y; es decir listas de x elementos consecutivos de zs
-- (salvo, posiblemente, la última que puede ser menor) tales que la
-- diferencia de posiciones entre los primeros elementos de ventanas
-- consecutivas es y. Por ejemplo, 
--    ventanas 3 2 [5,1,9,2] == [[5,1,9],[9,2]]
--    ventanas 3 3 [5,1,9,2] == [[5,1,9],[2]]
--    ventanas 3 4 [5,1,9,2] == [[5,1,9]]
--    ventanas 4 1 [1..7]    == [[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6,7]]
--    ventanas 4 2 [1..7]    == [[1,2,3,4],[3,4,5,6],[5,6,7]]
--    ventanas 4 3 [1..7]    == [[1,2,3,4],[4,5,6,7]]
--    ventanas 4 4 [1..7]    == [[1,2,3,4],[5,6,7]]
--    ventanas 4 5 [1..7]    == [[1,2,3,4],[6,7]]
--    ventanas 4 6 [1..7]    == [[1,2,3,4],[7]]
--    ventanas 4 7 [1..7]    == [[1,2,3,4]]
--    ventanas 4 8 [1..7]    == [[1,2,3,4]]
--    ventanas 3 2 "abcdef"  == ["abc","cde","ef"]
--    ventanas 3 3 "abcdef"  == ["abc","def"]
--    ventanas 3 4 "abcdef"  == ["abc","ef"]
--    ventanas 3 5 "abcdef"  == ["abc","f"]
--    ventanas 3 6 "abcdef"  == ["abc"]
--    ventanas 3 7 "abcdef"  == ["abc"]
--    ventanas 1 5 "abcdef"  == ["a","f"]

-- Definir la función

-- ventanas :: Int -> Int -> [a] -> [[a]]

-- tal que (ventanas x y zs) es la lista de ventanas de zs de tamaño x

-- y deslizamiento y; es decir listas de x elementos consecutivos de zs

-- (salvo, posiblemente, la última que puede ser menor) tales que la

-- diferencia de posiciones entre los primeros elementos de ventanas

-- consecutivas es y. Por ejemplo,

-- ventanas 3 2 [5,1,9,2] == [[5,1,9],[9,2]]

-- ventanas 3 3 [5,1,9,2] == [[5,1,9],[2]]

-- ventanas 3 4 [5,1,9,2] == [[5,1,9]]

-- ventanas 4 1 [1..7] == [[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6,7]]

-- ventanas 4 2 [1..7] == [[1,2,3,4],[3,4,5,6],[5,6,7]]

-- ventanas 4 3 [1..7] == [[1,2,3,4],[4,5,6,7]]

-- ventanas 4 4 [1..7] == [[1,2,3,4],[5,6,7]]

-- ventanas 4 5 [1..7] == [[1,2,3,4],[6,7]]

-- ventanas 4 6 [1..7] == [[1,2,3,4],[7]]

-- ventanas 4 7 [1..7] == [[1,2,3,4]]

-- ventanas 4 8 [1..7] == [[1,2,3,4]]

-- ventanas 3 2 "abcdef" == ["abc","cde","ef"]

-- ventanas 3 3 "abcdef" == ["abc","def"]

-- ventanas 3 4 "abcdef" == ["abc","ef"]

-- ventanas 3 5 "abcdef" == ["abc","f"]

-- ventanas 3 6 "abcdef" == ["abc"]

-- ventanas 3 7 "abcdef" == ["abc"]

-- ventanas 1 5 "abcdef" == ["a","f"]

Soluciones

import Data.List

-- 1º definición (por recursión):
ventanas1 :: Int -> Int -> [a] -> [[a]]
ventanas1 _ _ [] = []
ventanas1 x y zs 
    | length zs <= x = [zs]
    | otherwise      = take x zs : ventanas1 x y (drop y zs)

-- 2ª definición (con unfold):
ventanas2 :: Int -> Int -> [a] -> [[a]]
ventanas2 x y = unfoldr aux
  where aux [] = Nothing
        aux xs = Just (ys,zs)
                 where (ys,us)        = splitAt x xs
                       zs | null us   = []
                          | otherwise = drop y xs

import Data.List

-- 1º definición (por recursión):

ventanas1 :: Int -> Int -> [a] -> [[a]]

ventanas1 _ _ [] = []

ventanas1 x y zs

| length zs <= x = [zs]

| otherwise = take x zs : ventanas1 x y (drop y zs)

-- 2ª definición (con unfold):

ventanas2 :: Int -> Int -> [a] -> [[a]]

ventanas2 x y = unfoldr aux

where aux [] = Nothing

aux xs = Just (ys,zs)

where (ys,us) = splitAt x xs

zs | null us = []

| otherwise = drop y xs

Referencia

El ejercicio está basado en el problema del 30 de abril de 2014 de 1HaskellADay.

Divide si todos son múltiplos

PorJosé A. Alonso 4-julio-201426-marzo-2022

Ejercicio. Definir la función

   divideSiTodosMultiplos :: Integral a => a -> [a] -> Maybe [a]

1	divideSiTodosMultiplos :: Integral a => a -> [a] -> Maybe [a]

tal que (divideSiTodosMultiplos x ys) es justo la lista de los cocientes de los elementos de ys entre x si todos son múltiplos de x y Nothing en caso contrario. Por ejemplo,

   divideSiTodosMultiplos 2 [6,10,4]  ==  Just [3,5,2]
   divideSiTodosMultiplos 2 [6,10,5]  ==  Nothing

1 2	divideSiTodosMultiplos 2 [6,10,4] == Just [3,5,2] divideSiTodosMultiplos 2 [6,10,5] == Nothing

Soluciones

-- 1ª definición (por comprensión)
divideSiTodosMultiplos :: Integral a => a -> [a] -> Maybe [a]
divideSiTodosMultiplos x ys
    | todosMultiplos x ys = Just [y `div` x | y <- ys]
    | otherwise           = Nothing

-- (todosMultiplos x ys) se verifica si todos los elementos de ys son
-- múltiplos de x. Por ejemplo,
--    todosMultiplos 2 [6,10,4]  ==  True
--    todosMultiplos 2 [6,10,5]  ==  False
todosMultiplos :: Integral a => a -> [a] -> Bool
todosMultiplos x ys = and [y `mod` x == 0 | y <- ys]

-- 2ª definición (por recursión)
divideSiTodosMultiplos2 :: Integral a => a -> [a] -> Maybe [a]
divideSiTodosMultiplos2 _ [] = Just []
divideSiTodosMultiplos2 x (y:ys)
    | y `mod` x /= 0 = Nothing
    | aux == Nothing  = Nothing
    | otherwise       = Just ((y `div` x) : zs)
    where aux     = divideSiTodosMultiplos2 x ys
          Just zs = aux

-- 1ª definición (por comprensión)

divideSiTodosMultiplos :: Integral a => a -> [a] -> Maybe [a]

divideSiTodosMultiplos x ys

| todosMultiplos x ys = Just [y `div` x | y <- ys]

| otherwise = Nothing

-- (todosMultiplos x ys) se verifica si todos los elementos de ys son

-- múltiplos de x. Por ejemplo,

-- todosMultiplos 2 [6,10,4] == True

-- todosMultiplos 2 [6,10,5] == False

todosMultiplos :: Integral a => a -> [a] -> Bool

todosMultiplos x ys = and [y `mod` x == 0 | y <- ys]

-- 2ª definición (por recursión)

divideSiTodosMultiplos2 :: Integral a => a -> [a] -> Maybe [a]

divideSiTodosMultiplos2 _ [] = Just []

divideSiTodosMultiplos2 x (y:ys)

| y `mod` x /= 0 = Nothing

| aux == Nothing = Nothing

| otherwise = Just ((y `div` x) : zs)

where aux = divideSiTodosMultiplos2 x ys

Just zs = aux

Renombramiento de un árbol

PorJosé A. Alonso 3-julio-201427-diciembre-2014

-- 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
--         "C"
--         / \ 
--        /   \
--       /     \
--     "B"     "A"
--     / \     / \
--   "A" "B" "B" "C" 
-- se puede definir por 
--    ej1 :: Arbol String
--    ej1 = N "C" (N "B" (H "A") (H "B")) (N "A" (H "B") (H "C"))
--
-- Definir la función
--    renombraArbol :: Arbol t -> Arbol Int
-- tal que (renombraArbol a) es el árbol obtenido sustituyendo el valor
-- de los nodos y hojas por números tales que tengan el mismo valor si y
-- sólo si coincide su contenido. Por ejemplo,
--    ghci> renombraArbol ej1
--    N 2 (N 1 (H 0) (H 1)) (N 0 (H 1) (H 2))
-- Gráficamente, 
--          2 
--         / \ 
--        /   \
--       /     \
--      1       0 
--     / \     / \
--    0   1   1   2

-- 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

-- "C"

-- / \

-- "B" "A"

-- / \ / \

-- "A" "B" "B" "C"

-- se puede definir por

-- ej1 :: Arbol String

-- ej1 = N "C" (N "B" (H "A") (H "B")) (N "A" (H "B") (H "C"))

-- Definir la función

-- renombraArbol :: Arbol t -> Arbol Int

-- tal que (renombraArbol a) es el árbol obtenido sustituyendo el valor

-- de los nodos y hojas por números tales que tengan el mismo valor si y

-- sólo si coincide su contenido. Por ejemplo,

-- ghci> renombraArbol ej1

-- N 2 (N 1 (H 0) (H 1)) (N 0 (H 1) (H 2))

-- Gráficamente,

-- 2

-- / \

-- 1 0

-- / \ / \

-- 0 1 1 2

Soluciones

import Data.List 

data Arbol a = H a
             | N a (Arbol a) (Arbol a) 
             deriving (Show, Eq)

ej1 :: Arbol String
ej1 = N "C" (N "B" (H "A") (H "B")) (N "A" (H "B") (H "C"))

renombraArbol :: Ord t => Arbol t -> Arbol Int
renombraArbol a = aux a
    where ys            = valores a
          aux (H x)     = H (posicion x ys)
          aux (N x i d) = N (posicion x ys) (aux i) (aux d) 

-- (valores a) es la lista de los valores en los nodos y las hojas del
-- árbol a. Por ejemplo,
--    valores ej1  ==  ["A","B","C"]
valores :: Ord a => Arbol a -> [a]
valores a = sort (nub (aux a))
    where aux (H x)     = [x]
          aux (N x i d) = x : (aux i ++ aux d)

-- (posicion x ys) es la posición de x en ys. Por ejemplo.
--    posicion 7 [5,3,7,8]  ==  2
posicion :: Eq a => a -> [a] -> Int
posicion x ys = head [n | (y,n) <- zip ys [0..], y == x]

import Data.List

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

ej1 :: Arbol String

ej1 = N "C" (N "B" (H "A") (H "B")) (N "A" (H "B") (H "C"))

renombraArbol :: Ord t => Arbol t -> Arbol Int

renombraArbol a = aux a

where ys = valores a

aux (H x) = H (posicion x ys)

aux (N x i d) = N (posicion x ys) (aux i) (aux d)

-- (valores a) es la lista de los valores en los nodos y las hojas del

-- árbol a. Por ejemplo,

-- valores ej1 == ["A","B","C"]

valores :: Ord a => Arbol a -> [a]

valores a = sort (nub (aux a))

where aux (H x) = [x]

aux (N x i d) = x : (aux i ++ aux d)

-- (posicion x ys) es la posición de x en ys. Por ejemplo.

-- posicion 7 [5,3,7,8] == 2

posicion :: Eq a => a -> [a] -> Int

posicion x ys = head [n | (y,n) <- zip ys [0..], y == x]

Empiezan con mayúscula

PorJosé A. Alonso 2-julio-201427-diciembre-2014

Enunciado

-- Ejercicio. Definir, por composición, la función
--    conMayuscula :: String -> Int
-- tal que (conMayuscula cs) es el número de palabras de cs que empiezan
-- con mayúscula. Por ejemplo.
--    conMayuscula "Juan vive en Sevilla o en Huelva"  ==  3

-- Ejercicio. Definir, por composición, la función

-- conMayuscula :: String -> Int

-- tal que (conMayuscula cs) es el número de palabras de cs que empiezan

-- con mayúscula. Por ejemplo.

-- conMayuscula "Juan vive en Sevilla o en Huelva" == 3

Soluciones

import Data.Char

conMayuscula :: String -> Int
conMayuscula = length . filter (isUpper . head) . words

import Data.Char

conMayuscula :: String -> Int

conMayuscula = length . filter (isUpper . head) . words

Elemento más cercano que cumple una propiedad

Soluciones

Referencia

Ventana deslizante

Soluciones

Referencia

Divide si todos son múltiplos

Soluciones

Renombramiento de un árbol

Soluciones

Empiezan con mayúscula

Enunciado

Soluciones

Entradas recientes

Buscar

Correo electrónico