drop

Representaciones de matrices

PorJosé A. Alonso 16-diciembre-201427-diciembre-2014

Enunciado

-- Las matrices se pueden representar de distintas formas. Por ejemplo,
-- la matriz
--    |7 5 6|
--    |1 9 4|
-- se puede representar como la terna
--    ([7,5,6,1,9,4],2,3)
-- (donde la primera componente es la lista de los elementos de la
-- matriz, la segunda es su número de filas y la tercera es su número de
-- columnas) y también se puede representar como una lista de listas
--    [[[7,5,6],[1,9,4]]
-- (donde cada elemento es una de las filas de la matriz).
-- 
-- Definir las funciones
--    ternaAlistas :: ([a],Int,Int) -> [[a]]
--    listasAterna :: [[a]] -> ([a],Int,Int) 
-- tales que ternaAlistas pase de la primera representación a la
-- segunda y listasAterna pase de la segunda a la primera. Por ejemplo, 
--    ternaAlistas ([7,5,6,1,9,4],2,3)  ==  [[7,5,6],[1,9,4]]
--    listasAterna [[7,5,6],[1,9,4]]    ==  ([7,5,6,1,9,4],2,3)
--    ternaAlistas ([7,5,6,1,9,4],3,2)  ==  [[7,5],[6,1],[9,4]]
--    listasAterna [[7,5],[6,1],[9,4]]  ==  ([7,5,6,1,9,4],3,2)

-- Las matrices se pueden representar de distintas formas. Por ejemplo,

-- la matriz

-- |7 5 6|

-- |1 9 4|

-- se puede representar como la terna

-- ([7,5,6,1,9,4],2,3)

-- (donde la primera componente es la lista de los elementos de la

-- matriz, la segunda es su número de filas y la tercera es su número de

-- columnas) y también se puede representar como una lista de listas

-- [[[7,5,6],[1,9,4]]

-- (donde cada elemento es una de las filas de la matriz).

-- Definir las funciones

-- ternaAlistas :: ([a],Int,Int) -> [[a]]

-- listasAterna :: [[a]] -> ([a],Int,Int)

-- tales que ternaAlistas pase de la primera representación a la

-- segunda y listasAterna pase de la segunda a la primera. Por ejemplo,

-- ternaAlistas ([7,5,6,1,9,4],2,3) == [[7,5,6],[1,9,4]]

-- listasAterna [[7,5,6],[1,9,4]] == ([7,5,6,1,9,4],2,3)

-- ternaAlistas ([7,5,6,1,9,4],3,2) == [[7,5],[6,1],[9,4]]

-- listasAterna [[7,5],[6,1],[9,4]] == ([7,5,6,1,9,4],3,2)

Soluciones

ternaAlistas :: ([a],Int,Int) -> [[a]]
ternaAlistas (xs,n,m) = aux xs
    where aux [] = []
          aux xs = take m xs : aux (drop m xs)

listasAterna :: [[a]] -> ([a],Int,Int) 
listasAterna xss = (concat xss, length xss, length (head xss))

ternaAlistas :: ([a],Int,Int) -> [[a]]

ternaAlistas (xs,n,m) = aux xs

where aux [] = []

aux xs = take m xs : aux (drop m xs)

listasAterna :: [[a]] -> ([a],Int,Int)

listasAterna xss = (concat xss, length xss, length (head xss))

Inversa a trozos

PorJosé A. Alonso 20-noviembre-201427-diciembre-2014

Enunciado

-- Definir la función 
--    inversa :: Int -> [a] -> [a]
-- tal que (inversa k xs) es la lista obtenida invirtiendo elementos de
-- xs, k elementos cada vez. Si el número de elementos de xs no es un
-- múltiplo de k, entonces los finales elementos de xs se dejen sin
-- invertir. Por ejemplo,
--    inversa 3 [1..11]  ==  [3,2,1,6,5,4,9,8,7,10,11]
--    inversa 4 [1..11]  ==  [4,3,2,1,8,7,6,5,9,10,11]
--
-- Comprobar con QuickCheck que la función inversa es involutiva; es
-- decir, para todo número k>0 y toda lista xs, se tiene que
-- (inversa k (inversa k xs)) es igual a xs

-- Definir la función

-- inversa :: Int -> [a] -> [a]

-- tal que (inversa k xs) es la lista obtenida invirtiendo elementos de

-- xs, k elementos cada vez. Si el número de elementos de xs no es un

-- múltiplo de k, entonces los finales elementos de xs se dejen sin

-- invertir. Por ejemplo,

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

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

-- Comprobar con QuickCheck que la función inversa es involutiva; es

-- decir, para todo número k>0 y toda lista xs, se tiene que

-- (inversa k (inversa k xs)) es igual a xs

Soluciones

[schedule expon=’2014-11-27′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 27 de noviembre.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2014-11-27′ at=»06:00″]

import Test.QuickCheck

-- 1ª definición
inversa1 :: Int -> [a] -> [a]
inversa1 k xs 
    | length xs < k = xs
    | otherwise     = reverse (take k xs) ++ inversa1 k (drop k xs) 

-- 2ª definición 
inversa2 :: Int -> [a] -> [a]
inversa2 k xs = aux xs (length xs) where
    aux xs n
        | n < k     = xs
        | otherwise = reverse (take k xs) ++ aux (drop k xs) (n-k)


-- La dos definiciones son equivalentes
prop_equivalencia ::Int -> [Int] -> Property
prop_equivalencia k xs =
    k > 0 ==> inversa1 k xs == inversa2 k xs

-- La comprobación es
--    ghci> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.

-- La segunda es más eficiente
--    ghci> :set +s 
--    
--    ghci> last (inversa1 3 [1..100000])
--    100000
--    (16.42 secs, 17576420 bytes)
--     
--    ghci> last (inversa2 3 [1..100000])
--    100000
--    (0.11 secs, 18171356 bytes)

-- La propiedad es 
prop_inversa :: Int -> [Int] -> Property
prop_inversa k xs =
    k > 0 ==> inversa2 k (inversa2 k xs) == xs

-- La comprobación es 
--    ghci> quickCheck prop_inversa
--    +++ OK, passed 100 tests.

import Test.QuickCheck

-- 1ª definición

inversa1 :: Int -> [a] -> [a]

inversa1 k xs

| length xs < k = xs

| otherwise = reverse (take k xs) ++ inversa1 k (drop k xs)

-- 2ª definición

inversa2 :: Int -> [a] -> [a]

inversa2 k xs = aux xs (length xs) where

aux xs n

| n < k = xs

| otherwise = reverse (take k xs) ++ aux (drop k xs) (n-k)

-- La dos definiciones son equivalentes

prop_equivalencia ::Int -> [Int] -> Property

prop_equivalencia k xs =

k > 0 ==> inversa1 k xs == inversa2 k xs

-- La comprobación es

-- ghci> quickCheck prop_equivalencia

-- +++ OK, passed 100 tests.

-- La segunda es más eficiente

-- ghci> :set +s

-- ghci> last (inversa1 3 [1..100000])

-- 100000

-- (16.42 secs, 17576420 bytes)

-- ghci> last (inversa2 3 [1..100000])

-- 100000

-- (0.11 secs, 18171356 bytes)

-- La propiedad es

prop_inversa :: Int -> [Int] -> Property

prop_inversa k xs =

k > 0 ==> inversa2 k (inversa2 k xs) == xs

-- La comprobación es

-- ghci> quickCheck prop_inversa

-- +++ OK, passed 100 tests.

[/schedule]

Mínimos locales

PorJosé A. Alonso 19-noviembre-201427-diciembre-2014

Enunciado

-- Un mínimo local de una lista es un elemento de la lista que es menor
-- que su predecesor y que su sucesor en la lista. Por ejemplo, 1 es un
-- mínimo local de [3,2,1,3,7,7,1,0,2] ya que es menor  que 2 (su
-- predecesor) y que 3 (su sucesor). 
-- 
-- Definir la función
--    minimosLocales :: Ord a => [a] -> [a]
-- tal que (minimosLocales xs) es la lista de los mínimos locales de la
-- lista xs. Por ejemplo,
--    minimosLocales [3,2,1,3,7,7,9,6,8]  ==  [1,6]
--    minimosLocales [1..100]             ==  []
--    minimosLocales "mqexvzat"           ==  "eva"

-- Un mínimo local de una lista es un elemento de la lista que es menor

-- que su predecesor y que su sucesor en la lista. Por ejemplo, 1 es un

-- mínimo local de [3,2,1,3,7,7,1,0,2] ya que es menor que 2 (su

-- predecesor) y que 3 (su sucesor).

-- Definir la función

-- minimosLocales :: Ord a => [a] -> [a]

-- tal que (minimosLocales xs) es la lista de los mínimos locales de la

-- lista xs. Por ejemplo,

-- minimosLocales [3,2,1,3,7,7,9,6,8] == [1,6]

-- minimosLocales [1..100] == []

-- minimosLocales "mqexvzat" == "eva"

Soluciones

[schedule expon=’2014-11-26′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 26 de noviembre.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2014-11-26′ at=»06:00″]

-- 1ª definición (por recursión):
minimosLocales1 :: Ord a => [a] -> [a]
minimosLocales1 (x:y:z:xs) | y < x && y < z = y : minimosLocales1 (z:xs)
                           | otherwise      = minimosLocales1 (y:z:xs)
minimosLocales1 _                           = []

-- 2ª definición (por comprensión):
minimosLocales2 :: Ord a => [a] -> [a]
minimosLocales2 xs = 
    [y | (x,y,z) <- zip3 xs (tail xs) (drop 2 xs), y < x, y < z]

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

minimosLocales1 :: Ord a => [a] -> [a]

minimosLocales1 (x:y:z:xs) | y < x && y < z = y : minimosLocales1 (z:xs)

| otherwise = minimosLocales1 (y:z:xs)

minimosLocales1 _ = []

-- 2ª definición (por comprensión):

minimosLocales2 :: Ord a => [a] -> [a]

minimosLocales2 xs =

[y | (x,y,z) <- zip3 xs (tail xs) (drop 2 xs), y < x, y < z]

[/schedule]

Extensión de un fichero

PorJosé A. Alonso 10-noviembre-20141-mayo-2016

Enunciado

-- La extensión de un fichero es la palabra a continuación del último
-- punto en el nombre del fichero. Por ejemplo, la extensión de
-- "documento.txt" es "txt" 
-- 
-- Definir la función
--    extension :: String -> String
-- tal que (extension cs) es la extensión del fichero cs. Por ejemplo,
--    extension "ejercicio.hs"       ==  "hs"
--    extension "documento.txt"      ==  "txt"
--    extension "documento.txt.pdf"  ==  "pdf"
--    extension "resumen"            ==  ""

-- La extensión de un fichero es la palabra a continuación del último

-- punto en el nombre del fichero. Por ejemplo, la extensión de

-- "documento.txt" es "txt"

-- Definir la función

-- extension :: String -> String

-- tal que (extension cs) es la extensión del fichero cs. Por ejemplo,

-- extension "ejercicio.hs" == "hs"

-- extension "documento.txt" == "txt"

-- extension "documento.txt.pdf" == "pdf"

-- extension "resumen" == ""

Soluciones

-- 1ª definición (por recursión):
extension1 :: String -> String
extension1 cs | elem '.' cs = reverse (aux (reverse cs))
              | otherwise   = ""
    where aux []       = []
          aux ('.':cs) = []
          aux (c:cs)   = c : aux cs

-- 2ª definición (con takeWhile):
extension2 :: String -> String
extension2 cs
    | notElem '.' cs = ""
    | otherwise      = reverse (takeWhile (/= '.') (reverse cs))

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

extension1 :: String -> String

extension1 cs | elem '.' cs = reverse (aux (reverse cs))

| otherwise = ""

where aux [] = []

aux ('.':cs) = []

aux (c:cs) = c : aux cs

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

extension2 :: String -> String

extension2 cs

| notElem '.' cs = ""

| otherwise = reverse (takeWhile (/= '.') (reverse cs))

Ordenada cíclicamente

PorJosé A. Alonso 12-junio-201421-abril-2022

Enunciado

-- Se dice que una sucesión x(1), ..., x(n) está ordenada cíclicamente
-- si existe un índice i tal que la sucesión  
--    x(i), x(i+1), ..., x(n), x(1), ..., x(i-1)
-- está ordenada crecientemente. 
-- 
-- Definir la función 
--    ordenadaCiclicamente :: Ord a => [a] -> Int
-- tal que (ordenadaCiclicamente xs) es el índice (empezando en 1) a
-- partir del cual está ordenada, si el la lista está ordenado cíclicamente
-- y 0 en caso contrario. Por ejemplo,
--    ordenadaCiclicamente [1,2,3,4]      ==  1  
--    ordenadaCiclicamente [5,8,2,3]      ==  3 
--    ordenadaCiclicamente [4,6,7,5,4,3]  ==  0 
--    ordenadaCiclicamente [1,0,1,2]      ==  0
--    ordenadaCiclicamente [0,2,0]        ==  3
--    ordenadaCiclicamente "cdeab"        ==  4

-- Se dice que una sucesión x(1), ..., x(n) está ordenada cíclicamente

-- si existe un índice i tal que la sucesión

-- x(i), x(i+1), ..., x(n), x(1), ..., x(i-1)

-- está ordenada crecientemente.

-- Definir la función

-- ordenadaCiclicamente :: Ord a => [a] -> Int

-- tal que (ordenadaCiclicamente xs) es el índice (empezando en 1) a

-- partir del cual está ordenada, si el la lista está ordenado cíclicamente

-- y 0 en caso contrario. Por ejemplo,

-- ordenadaCiclicamente [1,2,3,4] == 1

-- ordenadaCiclicamente [5,8,2,3] == 3

-- ordenadaCiclicamente [4,6,7,5,4,3] == 0

-- ordenadaCiclicamente [1,0,1,2] == 0

-- ordenadaCiclicamente [0,2,0] == 3

-- ordenadaCiclicamente "cdeab" == 4

Soluciones

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

ordenadaCiclicamente1 :: Ord a => [a] -> Int
ordenadaCiclicamente1 xs = 
    primero [n+1 | n <- [0..length xs-1], 
                   ordenada (drop n xs ++ take n xs)]
    where primero []     = 0
          primero (x:xs) = x

-- (ordenada xs) se verifica si la lista xs está ordenada
-- crecientemente. Por ejemplo,
--   ordenada "acd"   ==  True
--   ordenada "acdb"  ==  False
ordenada :: Ord a => [a] -> Bool 
ordenada (x:y:zs) = x <= y && ordenada (y:zs) 
ordenada _        = True 
 
-- 2ª definición (por recursión)
-- =============================

ordenadaCiclicamente2 :: Ord a => [a] -> Int
ordenadaCiclicamente2 xs = aux xs 1 (length xs)  
    where aux xs i k 
              | i > k       = 0 
              | ordenada xs = i 
              | otherwise   = aux (siguienteCiclo xs) (i+1) k 

-- (siguienteCiclo xs) es la lista obtenida añadiendo el primer elemento
-- de xs al final del resto de xs. Por ejemplo,
--   siguienteCiclo [3,2,5]  =>  [2,5,3]
siguienteCiclo [] = [] 
siguienteCiclo (x:xs) = xs ++ [x]

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

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

ordenadaCiclicamente1 :: Ord a => [a] -> Int

ordenadaCiclicamente1 xs =

primero [n+1 | n <- [0..length xs-1],

ordenada (drop n xs ++ take n xs)]

where primero [] = 0

primero (x:xs) = x

-- (ordenada xs) se verifica si la lista xs está ordenada

-- crecientemente. Por ejemplo,

-- ordenada "acd" == True

-- ordenada "acdb" == False

ordenada :: Ord a => [a] -> Bool

ordenada (x:y:zs) = x <= y && ordenada (y:zs)

ordenada _ = True

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

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

ordenadaCiclicamente2 :: Ord a => [a] -> Int

ordenadaCiclicamente2 xs = aux xs 1 (length xs)

where aux xs i k

| i > k = 0

| ordenada xs = i

| otherwise = aux (siguienteCiclo xs) (i+1) k

-- (siguienteCiclo xs) es la lista obtenida añadiendo el primer elemento

-- de xs al final del resto de xs. Por ejemplo,

-- siguienteCiclo [3,2,5] => [2,5,3]

siguienteCiclo [] = []

siguienteCiclo (x:xs) = xs ++ [x]

Representaciones de matrices

Enunciado

Soluciones

Inversa a trozos

Enunciado

Soluciones

Mínimos locales

Enunciado

Soluciones

Extensión de un fichero

Enunciado

Soluciones

Ordenada cíclicamente

Enunciado

Soluciones

Entradas recientes

Buscar

Correo electrónico