Inicial – Página 8

Suma de conjuntos de polinomios

PorJosé A. Alonso 25-febrero-20151-mayo-2016

Los conjuntos de polinomios se pueden representar por listas de listas de la misma longitud. Por ejemplo, los polinomios 3x²+5x+9, 10x³+9 y 8x³+5x²+x-1 se pueden representar por las listas [0,3,5,9], [10,0,0,9] y [8,5,1,-1].

Definir la función

   sumaPolinomios :: Num a => [[a]] -> [a]

1	sumaPolinomios :: Num a => [[a]] -> [a]

tal que (sumaPolinomios ps) es la suma de los polinomios ps. Por ejemplo,

   ghci> sumaPolinomios1 [[0,3,5,9],[10,0,0,9],[8,5,1,-1]]
   [18,8,6,17]
   ghci> sumaPolinomios6 (replicate 1000000 (replicate 3 1))
   [1000000,1000000,1000000]

ghci> sumaPolinomios1 [[0,3,5,9],[10,0,0,9],[8,5,1,-1]]

[18,8,6,17]

ghci> sumaPolinomios6 (replicate 1000000 (replicate 3 1))

[1000000,1000000,1000000]

Soluciones

import Data.List (transpose)
import Data.Array ((!),accumArray,elems,listArray)

-- 1ª definición (por recursión):
sumaPolinomios1 :: Num a => [[a]] -> [a]
sumaPolinomios1 []          = []
sumaPolinomios1 [xs]        = xs
sumaPolinomios1 (xs:ys:zss) = suma xs (sumaPolinomios1 (ys:zss))

-- (suma xs ys) es la suma de los vectores xs e ys. Por ejemplo,
--    suma [4,7,3] [1,2,5]  == [5,9,8]
suma :: Num a => [a] -> [a] -> [a]
suma [] []         = []
suma (x:xs) (y:ys) = x+y : suma xs ys

-- 2ª definición (por recursión con zipWith): 
sumaPolinomios2 :: Num a => [[a]] -> [a]
sumaPolinomios2 []       = []
sumaPolinomios2 [xs]     = xs
sumaPolinomios2 (xs:xss) = zipWith (+) xs (sumaPolinomios2 xss)

-- 3ª definición (por plegado)
sumaPolinomios3 :: Num a => [[a]] -> [a]
sumaPolinomios3 = foldr1 (zipWith (+))

-- 4ª definición (por comprensión con transpose):
sumaPolinomios4 :: Num a => [[a]] -> [a]
sumaPolinomios4 xss = [sum xs | xs <- transpose xss]

-- 5ª definición (con map y transpose):
sumaPolinomios5 :: Num a => [[a]] -> [a]
sumaPolinomios5 = map sum . transpose 

-- 6ª definición (con array)
sumaPolinomios6 :: Num a => [[a]] -> [a]
sumaPolinomios6 xss = [sum [p!(i,j) | i <- [1..m]] | j <- [1..n]] 
    where m = length xss
          n = length (head xss)
          p = listArray ((1,1),(m,n)) (concat xss) 

-- 7ª definición (con accumArray)
sumaPolinomios7 :: Num a => [[a]] -> [a]
sumaPolinomios7 xss = 
    elems $ accumArray (+) 0 (1,n) (concat [zip [1..] xs | xs <- xss])
    where n = length (head xss)

-- Comparación de eficiencia
--    ghci> sumaPolinomios1 (replicate 300000 (replicate 5 1))
--    [300000,300000,300000,300000,300000]
--    (3.94 secs, 354713532 bytes)
--    
--    ghci> sumaPolinomios2 (replicate 300000 (replicate 5 1))
--    [300000,300000,300000,300000,300000]
--    (2.08 secs, 185506908 bytes)
--    
--    ghci> sumaPolinomios3 (replicate 300000 (replicate 5 1))
--    [300000,300000,300000,300000,300000]
--    (1.48 secs, 167026728 bytes)
--    
--    ghci> sumaPolinomios4 (replicate 300000 (replicate 5 1))
--    [300000,300000,300000,300000,300000]
--    (1.08 secs, 148564752 bytes)
--    
--    ghci> sumaPolinomios5 (replicate 300000 (replicate 5 1))
--    [300000,300000,300000,300000,300000]
--    (1.02 secs, 148062764 bytes)
--    
--    ghci> sumaPolinomios6 (replicate 300000 (replicate 5 1))
--    [300000,300000,300000,300000,300000]
--    (3.17 secs, 463756028 bytes)
--    
--    ghci> sumaPolinomios7 (replicate 300000 (replicate 5 1))
--    [300000,300000,300000,300000,300000]
--    (1.50 secs, 291699548 bytes)

import Data.List (transpose)

import Data.Array ((!),accumArray,elems,listArray)

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

sumaPolinomios1 :: Num a => [[a]] -> [a]

sumaPolinomios1 [] = []

sumaPolinomios1 [xs] = xs

sumaPolinomios1 (xs:ys:zss) = suma xs (sumaPolinomios1 (ys:zss))

-- (suma xs ys) es la suma de los vectores xs e ys. Por ejemplo,

-- suma [4,7,3] [1,2,5] == [5,9,8]

suma :: Num a => [a] -> [a] -> [a]

suma [] [] = []

suma (x:xs) (y:ys) = x+y : suma xs ys

-- 2ª definición (por recursión con zipWith):

sumaPolinomios2 :: Num a => [[a]] -> [a]

sumaPolinomios2 [] = []

sumaPolinomios2 [xs] = xs

sumaPolinomios2 (xs:xss) = zipWith (+) xs (sumaPolinomios2 xss)

-- 3ª definición (por plegado)

sumaPolinomios3 :: Num a => [[a]] -> [a]

sumaPolinomios3 = foldr1 (zipWith (+))

-- 4ª definición (por comprensión con transpose):

sumaPolinomios4 :: Num a => [[a]] -> [a]

sumaPolinomios4 xss = [sum xs | xs <- transpose xss]

-- 5ª definición (con map y transpose):

sumaPolinomios5 :: Num a => [[a]] -> [a]

sumaPolinomios5 = map sum . transpose

-- 6ª definición (con array)

sumaPolinomios6 :: Num a => [[a]] -> [a]

sumaPolinomios6 xss = [sum [p!(i,j) | i <- [1..m]] | j <- [1..n]]

where m = length xss

n = length (head xss)

p = listArray ((1,1),(m,n)) (concat xss)

-- 7ª definición (con accumArray)

sumaPolinomios7 :: Num a => [[a]] -> [a]

sumaPolinomios7 xss =

elems $ accumArray (+) 0 (1,n) (concat [zip [1..] xs | xs <- xss])

where n = length (head xss)

-- Comparación de eficiencia

-- ghci> sumaPolinomios1 (replicate 300000 (replicate 5 1))

-- [300000,300000,300000,300000,300000]

-- (3.94 secs, 354713532 bytes)

-- ghci> sumaPolinomios2 (replicate 300000 (replicate 5 1))

-- [300000,300000,300000,300000,300000]

-- (2.08 secs, 185506908 bytes)

-- ghci> sumaPolinomios3 (replicate 300000 (replicate 5 1))

-- [300000,300000,300000,300000,300000]

-- (1.48 secs, 167026728 bytes)

-- ghci> sumaPolinomios4 (replicate 300000 (replicate 5 1))

-- [300000,300000,300000,300000,300000]

-- (1.08 secs, 148564752 bytes)

-- ghci> sumaPolinomios5 (replicate 300000 (replicate 5 1))

-- [300000,300000,300000,300000,300000]

-- (1.02 secs, 148062764 bytes)

-- ghci> sumaPolinomios6 (replicate 300000 (replicate 5 1))

-- [300000,300000,300000,300000,300000]

-- (3.17 secs, 463756028 bytes)

-- ghci> sumaPolinomios7 (replicate 300000 (replicate 5 1))

-- [300000,300000,300000,300000,300000]

-- (1.50 secs, 291699548 bytes)

Mínimo número de cambios para igualar una lista

PorJosé A. Alonso 23-febrero-201525-abril-2021

Definir la función

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

1	nMinimoCambios :: Ord a => [a] -> Int

tal que (nMinimoCambios xs) es el menor número de elementos de xs que hay que cambiar para que todos sean iguales. Por ejemplo,

   nMinimoCambios [3,5,3,7,9,6]      ==  4
   nMinimoCambios [3,5,3,7,3,3]      ==  2
   nMinimoCambios "Salamanca"        ==  5
   nMinimoCambios (4 : [1..500000])  ==  499999

nMinimoCambios [3,5,3,7,9,6] == 4

nMinimoCambios [3,5,3,7,3,3] == 2

nMinimoCambios "Salamanca" == 5

nMinimoCambios (4 : [1..500000]) == 499999

En el primer ejemplo, los elementos que hay que cambiar son 5, 7, 9 y 6.

Soluciones

import Data.List (group, nub, sort)

-- 1ª definición
-- =============

nMinimoCambios1 :: Ord a => [a] -> Int
nMinimoCambios1 xs = 
    length xs - fst (last (sort (frecuencias xs)))

-- (frecuencias xs) es la lista de los pares de los elementos de xs y el
-- número de veces que ocurren en xs. Por ejemplo,
--    frecuencias [3,5,3,7,9,6]  ==  [(2,3),(1,5),(1,7),(1,9),(1,6)]
--    frecuencias [3,5,3,7,5,5]  ==  [(2,3),(3,5),(1,7)]
frecuencias :: Ord a => [a] -> [(Int,a)]
frecuencias xs = [(cuenta x xs,x) | x <- nub xs]

-- (cuenta x ys) es el número de veces que ocurre x en ys. Por ejemplo,
--    cuenta 3 [3,5,3,7,9,6]  ==  2
cuenta :: Ord a => a -> [a] -> Int
cuenta x ys = length [y | y <- ys, y == x]

-- 2ª definición
-- =============

nMinimoCambios2 :: Ord a => [a] -> Int
nMinimoCambios2 xs = 
    length xs - fst (last (sort (frecuencias2 xs)))

-- (frecuencias2 xs) es la lista de los pares de los elementos de xs y el
-- número de veces que ocurren en xs. Por ejemplo,
--    frecuencias2 [3,5,3,7,9,6]  ==  [(2,3),(1,5),(1,7),(1,9),(1,6)]
--    frecuencias2 [3,5,3,7,5,5]  ==  [(2,3),(3,5),(1,7)]
frecuencias2 :: Ord a  => [a] -> [(Int,a)]
frecuencias2 xs = 
    [(1 + length ys, y) | (y:ys) <- group (sort xs)] 

-- 3ª definición
-- =============

nMinimoCambios3 :: Ord a => [a] -> Int
nMinimoCambios3 xs = sum ys - maximum ys
    where ys = [length ys | ys <- group (sort xs)]

import Data.List (group, nub, sort)

-- 1ª definición

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

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

nMinimoCambios1 xs =

length xs - fst (last (sort (frecuencias xs)))

-- (frecuencias xs) es la lista de los pares de los elementos de xs y el

-- número de veces que ocurren en xs. Por ejemplo,

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

-- frecuencias [3,5,3,7,5,5] == [(2,3),(3,5),(1,7)]

frecuencias :: Ord a => [a] -> [(Int,a)]

frecuencias xs = [(cuenta x xs,x) | x <- nub xs]

-- (cuenta x ys) es el número de veces que ocurre x en ys. Por ejemplo,

-- cuenta 3 [3,5,3,7,9,6] == 2

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

cuenta x ys = length [y | y <- ys, y == x]

-- 2ª definición

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

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

nMinimoCambios2 xs =

length xs - fst (last (sort (frecuencias2 xs)))

-- (frecuencias2 xs) es la lista de los pares de los elementos de xs y el

-- número de veces que ocurren en xs. Por ejemplo,

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

-- frecuencias2 [3,5,3,7,5,5] == [(2,3),(3,5),(1,7)]

frecuencias2 :: Ord a => [a] -> [(Int,a)]

frecuencias2 xs =

[(1 + length ys, y) | (y:ys) <- group (sort xs)]

-- 3ª definición

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

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

nMinimoCambios3 xs = sum ys - maximum ys

where ys = [length ys | ys <- group (sort xs)]

Segmentos de longitud dada

PorJosé A. Alonso 10-febrero-20151-mayo-2016

Definir la función

   segmentos :: Int -> [a] -> [[a]]

1	segmentos :: Int -> [a] -> [[a]]

tal que (segmentos n xs) es la lista de los segmentos de longitud n de la lista xs. Por ejemplo,

   segmentos 3 [1..5]  ==  [[1,2,3],[2,3,4],[3,4,5]]

1	segmentos 3 [1..5] == [[1,2,3],[2,3,4],[3,4,5]]

Soluciones

import Data.List (tails)

-- 1ª definición (por recursión)
segmentos1 :: Int -> [a] -> [[a]]
segmentos1 n xs 
    | length xs < n = []
    | otherwise     = take n xs : segmentos1 n (tail xs)
                  
-- 2ª definición (con tails):
segmentos2 :: Int -> [a] -> [[a]]
segmentos2 n xs = 
    takeWhile (\ys -> length ys == n) (map (take n) (tails xs))

-- 3ª definición:
segmentos3 :: Int -> [a] -> [[a]]
segmentos3 n xs = 
    take (length xs - n + 1) (map (take n) (tails xs))

--    ghci> length (segmentos1 3 [1..30000])
--    29998
--    (2.99 secs, 13998816 bytes)
--    
--    ghci> length (segmentos2 3 [1..30000])
--    29998
--    (0.05 secs, 16941304 bytes)
--    
--    ghci> length (segmentos3 3 [1..30000])
--    29998
--    (0.04 secs, 10375520 bytes)
--    
--    ghci> length (segmentos2 3 [1..1000000])
--    999998
--    (0.70 secs, 498098336 bytes)
--    
--    ghci> length (segmentos3 3 [1..1000000])
--    999998
--    (0.24 secs, 273979304 bytes)

import Data.List (tails)

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

segmentos1 :: Int -> [a] -> [[a]]

segmentos1 n xs

| length xs < n = []

| otherwise = take n xs : segmentos1 n (tail xs)

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

segmentos2 :: Int -> [a] -> [[a]]

segmentos2 n xs =

takeWhile (\ys -> length ys == n) (map (take n) (tails xs))

-- 3ª definición:

segmentos3 :: Int -> [a] -> [[a]]

segmentos3 n xs =

take (length xs - n + 1) (map (take n) (tails xs))

-- ghci> length (segmentos1 3 [1..30000])

-- 29998

-- (2.99 secs, 13998816 bytes)

-- ghci> length (segmentos2 3 [1..30000])

-- 29998

-- (0.05 secs, 16941304 bytes)

-- ghci> length (segmentos3 3 [1..30000])

-- 29998

-- (0.04 secs, 10375520 bytes)

-- ghci> length (segmentos2 3 [1..1000000])

-- 999998

-- (0.70 secs, 498098336 bytes)

-- ghci> length (segmentos3 3 [1..1000000])

-- 999998

-- (0.24 secs, 273979304 bytes)

Menor número triangular con más de n divisores

PorJosé A. Alonso 6-febrero-201525-abril-2021

La sucesión de los números triangulares se obtiene sumando los números naturales.

Así, el 7º número triangular es

   1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

1	1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

Los primeros 10 números triangulares son

   1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

1	1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Los divisores de los primeros 7 números triangulares son:

    1: 1
    3: 1,3
    6: 1,2,3,6
   10: 1,2,5,10
   15: 1,3,5,15
   21: 1,3,7,21
   28: 1,2,4,7,14,28

1: 1

3: 1,3

6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21

28: 1,2,4,7,14,28

Como se puede observar, 28 es el menor número triangular con más de 5 divisores.

Definir la función

   menorTriangularConAlMenosNDivisores :: Int -> Integer

1	menorTriangularConAlMenosNDivisores :: Int -> Integer

tal que (menorTriangularConAlMenosNDivisores n) es el menor número triangular que tiene al menos n divisores. Por ejemplo,

   menorTriangularConAlMenosNDivisores 5    ==  28
   menorTriangularConAlMenosNDivisores 50   ==  25200
   menorTriangularConAlMenosNDivisores 500  ==  76576500

menorTriangularConAlMenosNDivisores 5 == 28

menorTriangularConAlMenosNDivisores 50 == 25200

menorTriangularConAlMenosNDivisores 500 == 76576500

Soluciones

import Data.List (group)
import Data.Numbers.Primes (primes,primeFactors)

-- 1ª definición
-- =============

menorTriangularConAlMenosNDivisores1 :: Int -> Integer
menorTriangularConAlMenosNDivisores1 n = 
    head [x | x <- triangulares, nDivisores x >= n]

-- triangulares es la sucesión de los números triangulares. Por ejemplo,
--    take 10 triangulares  ==  [1,3,6,10,15,21,28,36,45,55]
triangulares :: [Integer]
triangulares = scanl (+) 1 [2..]

-- (nDivisores x) es el número de divisores de x. Por ejemplo,
--    nDivisores 28  ==  6
nDivisores :: Integer -> Int
nDivisores x = 
    1 + length [y | y <- [1..x `div` 2], mod x y == 0]

-- 2ª solución
-- ===========

menorTriangularConAlMenosNDivisores2 :: Int -> Integer
menorTriangularConAlMenosNDivisores2 n = 
    head [x | x <- triangulares, nDivisores2 x >= n]

-- (nDivisores2 x) es el número de divisores de x. Por ejemplo,
--    nDivisores2 28  ==  6
nDivisores2 :: Integer -> Int
nDivisores2 n = product [1 + length xs | xs <- group (factoresPrimos n)]    

-- (factoresPrimos n) es la lista de los factores primos de n. Por
-- ejemplo, 
--    factoresPrimos 28  ==  [2,2,7]
factoresPrimos :: Integer -> [Integer]
factoresPrimos n = aux n primos
    where aux n (p:ps) 
              | p*p > n        = [n]
              | n `mod` p == 0 = p : aux (n `div` p) (p:ps)
              | otherwise      = aux n ps

-- primos es la lista de los números primos. Por ejemplo,
--    take 10 primos  ==  [2,3,5,7,11,13,17,19,23,29]
primos :: [Integer]
primos = 2 : filter ((==1) . length . factoresPrimos) [3,5..]

-- 3ª solución (usando primes)
-- ===========================

menorTriangularConAlMenosNDivisores3 :: Int -> Integer
menorTriangularConAlMenosNDivisores3 n = 
    head [x | x <- triangulares, nDivisores3 x >= n]

-- (nDivisores3 x) es el número de divisores de x. Por ejemplo,
--    nDivisores3 28  ==  6
nDivisores3 :: Integer -> Int
nDivisores3 n = product [1 + length xs | xs <- group (factoresPrimos3 n)]    

-- (factoresPrimos3 n) es la lista de los factores primos de n. Por
-- ejemplo, 
--    factoresPrimos3 28  ==  [2,2,7]
factoresPrimos3 n = aux n primes
  where
    aux n (p:ps) 
        | p*p > n        = [n]
        | n `mod` p == 0 = p : aux (n `div` p) (p:ps)
        | otherwise      = aux n ps

-- 4ª solución (usando primeFactors)
-- =================================

menorTriangularConAlMenosNDivisores4 :: Int -> Integer
menorTriangularConAlMenosNDivisores4 n = 
    head [x | x <- triangulares, nDivisores4 x >= n]

-- (nDivisores4 x) es el número de divisores de x. Por ejemplo,
--    nDivisores4 28  ==  6
nDivisores4 :: Integer -> Int
nDivisores4 n = product [1 + length xs | xs <- group (primeFactors n)]    

-- ---------------------------------------------------------------------
-- § Comparación de eficiencia                                        --
-- ---------------------------------------------------------------------

-- La comparación es
--    ghci> menorTriangularConAlMenosNDivisores1 50
--    25200
--    (1.25 secs, 200236512 bytes)
--    
--    ghci> menorTriangularConAlMenosNDivisores2 50
--    25200
--    (0.02 secs, 4199904 bytes)
--    
--    ghci> menorTriangularConAlMenosNDivisores3 50
--    25200
--    (0.03 secs, 6265128 bytes)
--    
--    ghci> menorTriangularConAlMenosNDivisores4 50
--    25200
--    (0.01 secs, 5753048 bytes)

100

101

102

import Data.List (group)

import Data.Numbers.Primes (primes,primeFactors)

-- 1ª definición

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

menorTriangularConAlMenosNDivisores1 :: Int -> Integer

menorTriangularConAlMenosNDivisores1 n =

head [x | x <- triangulares, nDivisores x >= n]

-- triangulares es la sucesión de los números triangulares. Por ejemplo,

-- take 10 triangulares == [1,3,6,10,15,21,28,36,45,55]

triangulares :: [Integer]

triangulares = scanl (+) 1 [2..]

-- (nDivisores x) es el número de divisores de x. Por ejemplo,

-- nDivisores 28 == 6

nDivisores :: Integer -> Int

nDivisores x =

1 + length [y | y <- [1..x `div` 2], mod x y == 0]

-- 2ª solución

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

menorTriangularConAlMenosNDivisores2 :: Int -> Integer

menorTriangularConAlMenosNDivisores2 n =

head [x | x <- triangulares, nDivisores2 x >= n]

-- (nDivisores2 x) es el número de divisores de x. Por ejemplo,

-- nDivisores2 28 == 6

nDivisores2 :: Integer -> Int

nDivisores2 n = product [1 + length xs | xs <- group (factoresPrimos n)]

-- (factoresPrimos n) es la lista de los factores primos de n. Por

-- ejemplo,

-- factoresPrimos 28 == [2,2,7]

factoresPrimos :: Integer -> [Integer]

factoresPrimos n = aux n primos

where aux n (p:ps)

| p*p > n = [n]

| n `mod` p == 0 = p : aux (n `div` p) (p:ps)

| otherwise = aux n ps

-- primos es la lista de los números primos. Por ejemplo,

-- take 10 primos == [2,3,5,7,11,13,17,19,23,29]

primos :: [Integer]

primos = 2 : filter ((==1) . length . factoresPrimos) [3,5..]

-- 3ª solución (usando primes)

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

menorTriangularConAlMenosNDivisores3 :: Int -> Integer

menorTriangularConAlMenosNDivisores3 n =

head [x | x <- triangulares, nDivisores3 x >= n]

-- (nDivisores3 x) es el número de divisores de x. Por ejemplo,

-- nDivisores3 28 == 6

nDivisores3 :: Integer -> Int

nDivisores3 n = product [1 + length xs | xs <- group (factoresPrimos3 n)]

-- (factoresPrimos3 n) es la lista de los factores primos de n. Por

-- ejemplo,

-- factoresPrimos3 28 == [2,2,7]

factoresPrimos3 n = aux n primes

where

aux n (p:ps)

| p*p > n = [n]

| n `mod` p == 0 = p : aux (n `div` p) (p:ps)

| otherwise = aux n ps

-- 4ª solución (usando primeFactors)

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

menorTriangularConAlMenosNDivisores4 :: Int -> Integer

menorTriangularConAlMenosNDivisores4 n =

head [x | x <- triangulares, nDivisores4 x >= n]

-- (nDivisores4 x) es el número de divisores de x. Por ejemplo,

-- nDivisores4 28 == 6

nDivisores4 :: Integer -> Int

nDivisores4 n = product [1 + length xs | xs <- group (primeFactors n)]

-- ---------------------------------------------------------------------

-- § Comparación de eficiencia --

-- ---------------------------------------------------------------------

-- La comparación es

-- ghci> menorTriangularConAlMenosNDivisores1 50

-- 25200

-- (1.25 secs, 200236512 bytes)

-- ghci> menorTriangularConAlMenosNDivisores2 50

-- 25200

-- (0.02 secs, 4199904 bytes)

-- ghci> menorTriangularConAlMenosNDivisores3 50

-- 25200

-- (0.03 secs, 6265128 bytes)

-- ghci> menorTriangularConAlMenosNDivisores4 50

-- 25200

-- (0.01 secs, 5753048 bytes)

Siguiente elemento en una lista

PorJosé A. Alonso 2-febrero-201526-marzo-2022

Definir la función

   siguiente :: Eq a => a -> [a] -> Maybe a

1	siguiente :: Eq a => a -> [a] -> Maybe a

tal que (siguiente x ys) es justo el elemento siguiente a la primera ocurrencia de x en ys o Nothing si x no pertenece a ys. Por ejemplo,

   siguiente 5 [3,5,2,5,7]                       ==  Just 2
   siguiente 9 [3,5,2,5,7]                       ==  Nothing
   siguiente 'd' "afdegdb"                       ==  Just 'e'
   siguiente "todo" ["En","todo","la","medida"]  ==  Just "la"
   siguiente "nada" ["En","todo","la","medida"]  ==  Nothing
   siguiente 999999 [1..1000000]                 ==  Just 1000000
   siguiente 1000000 [1..1000000]                ==  Nothing

siguiente 5 [3,5,2,5,7] == Just 2

siguiente 9 [3,5,2,5,7] == Nothing

siguiente 'd' "afdegdb" == Just 'e'

siguiente "todo" ["En","todo","la","medida"] == Just "la"

siguiente "nada" ["En","todo","la","medida"] == Nothing

siguiente 999999 [1..1000000] == Just 1000000

siguiente 1000000 [1..1000000] == Nothing

Soluciones

import Data.Maybe (listToMaybe) -- Para la 4ª solución

-- 1ª solución (por recursión):
siguiente1 :: Eq a => a -> [a] -> Maybe a
siguiente1 x (y1:y2:ys) | x == y1   = Just y2
                        | otherwise = siguiente1 x (y2:ys)
siguiente1 x _ = Nothing

-- 2ª solución (por comprensión):
siguiente2 :: Eq a => a -> [a] -> Maybe a
siguiente2 x ys 
    | null zs   = Nothing
    | otherwise = Just (snd (head zs))
    where zs = [(u,v) | (u,v) <- zip ys (tail ys), u == x]  

-- 3ª solución (con dropWhile)
siguiente3 :: Eq a => a -> [a] -> Maybe a
siguiente3 x = aux . drop 1 . dropWhile (/=x)
    where aux []    = Nothing
          aux (y:_) = Just y

-- 4ª solución (con dropWhile y listToMaybe):
siguiente4 :: Eq a => a -> [a] -> Maybe a
siguiente4 x = listToMaybe . drop 1 . dropWhile (/=x)

-- Nota: En la librería Data.Maybe está definida la función 
--    listToMaybe :: [a] -> Maybe a 
-- tal que (listToMaybe xs) es Nothing si la lista xs está vacía y es
-- justo el primer elemento, en caso contrario, Por ejemplo,
--    listToMaybe []       ==  Nothing
--    listToMaybe [3,2,5]  ==  Just 3

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    ghci> let n=10^6 in siguiente1 (n-1) [1..n]
--    Just 1000000
--    (1.34 secs, 277352616 bytes)
--    
--    ghci> let n=10^6 in siguiente2 (n-1) [1..n]
--    Just 1000000
--    (1.45 secs, 340836576 bytes)
--    
--    ghci> let n=10^6 in siguiente3 (n-1) [1..n]
--    Just 1000000
--    (0.26 secs, 84987544 bytes)
--    
--    ghci> let n=10^6 in siguiente4 (n-1) [1..n]
--    Just 1000000
--    (0.26 secs, 84987440 bytes)

import Data.Maybe (listToMaybe) -- Para la 4ª solución

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

siguiente1 :: Eq a => a -> [a] -> Maybe a

siguiente1 x (y1:y2:ys) | x == y1 = Just y2

| otherwise = siguiente1 x (y2:ys)

siguiente1 x _ = Nothing

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

siguiente2 :: Eq a => a -> [a] -> Maybe a

siguiente2 x ys

| null zs = Nothing

| otherwise = Just (snd (head zs))

where zs = [(u,v) | (u,v) <- zip ys (tail ys), u == x]

-- 3ª solución (con dropWhile)

siguiente3 :: Eq a => a -> [a] -> Maybe a

siguiente3 x = aux . drop 1 . dropWhile (/=x)

where aux [] = Nothing

aux (y:_) = Just y

-- 4ª solución (con dropWhile y listToMaybe):

siguiente4 :: Eq a => a -> [a] -> Maybe a

siguiente4 x = listToMaybe . drop 1 . dropWhile (/=x)

-- Nota: En la librería Data.Maybe está definida la función

-- listToMaybe :: [a] -> Maybe a

-- tal que (listToMaybe xs) es Nothing si la lista xs está vacía y es

-- justo el primer elemento, en caso contrario, Por ejemplo,

-- listToMaybe [] == Nothing

-- listToMaybe [3,2,5] == Just 3

-- Comparación de eficiencia

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

-- La comparación es

-- ghci> let n=10^6 in siguiente1 (n-1) [1..n]

-- Just 1000000

-- (1.34 secs, 277352616 bytes)

-- ghci> let n=10^6 in siguiente2 (n-1) [1..n]

-- Just 1000000

-- (1.45 secs, 340836576 bytes)

-- ghci> let n=10^6 in siguiente3 (n-1) [1..n]

-- Just 1000000

-- (0.26 secs, 84987544 bytes)

-- ghci> let n=10^6 in siguiente4 (n-1) [1..n]

-- Just 1000000

-- (0.26 secs, 84987440 bytes)

Posición del primer falso en un vector

PorJosé A. Alonso 29-enero-201526-marzo-2022

Excercitium

Definir la función

   posicion :: Array Int Bool -> Maybe Int

1	posicion :: Array Int Bool -> Maybe Int

tal que (posicion v) es la menor posición del vector de booleanos v cuyo valor es falso y es Nothing si todos los valores son verdaderos. Por ejemplo,

   posicion (listArray (0,4) [True,True,False,True,False]) == Just 2
   posicion (listArray (0,4) [i <= 2 | i <- [0..4]])       == Just 3
   posicion (listArray (0,4) [i <= 7 | i <- [0..4]])       == Nothing

posicion (listArray (0,4) [True,True,False,True,False]) == Just 2

posicion (listArray (0,4) [i <= 2 | i <- [0..4]]) == Just 3

posicion (listArray (0,4) [i <= 7 | i <- [0..4]]) == Nothing

Soluciones

import Data.Array 

-- 1ª definición:
posicion :: Array Int Bool -> Maybe Int
posicion v | p > n     = Nothing
           | otherwise = Just p
    where p = (length . takeWhile id . elems) v
          (_,n) = bounds v 

-- 2ª posición:
posicion2 :: Array Int Bool -> Maybe Int
posicion2 v | null xs   = Nothing
            | otherwise = Just (head xs)
    where xs = [i | i <- indices v, v!i]

import Data.Array

-- 1ª definición:

posicion :: Array Int Bool -> Maybe Int

posicion v | p > n = Nothing

| otherwise = Just p

where p = (length . takeWhile id . elems) v

(_,n) = bounds v

-- 2ª posición:

posicion2 :: Array Int Bool -> Maybe Int

posicion2 v | null xs = Nothing

| otherwise = Just (head xs)

where xs = [i | i <- indices v, v!i]

Números naturales separados por ceros

PorJosé A. Alonso 26-enero-201525-marzo-2022

Enunciado

Definir la sucesión

   naturales0 :: [Int]

1	naturales0 :: [Int]

cuyos elementos son los números naturales separados por 0. Por ejemplo,

   ghci> take 25 naturales0
   [0,0,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,0,10,0,11,0,12]

1 2	ghci> take 25 naturales0 [0,0,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9,0,10,0,11,0,12]

Comprobar con QuickCheck que el n-ésimo término de la sucesión es n*(1+(-1)^n)/4.

Nota. En la comprobación usar

   quickCheckWith (stdArgs {maxSize=7}) prop_naturales0

1	quickCheckWith (stdArgs {maxSize=7}) prop_naturales0

Soluciones

import Test.QuickCheck

naturales0 :: [Int]
naturales0 = concat [[n,0] | n <- [0..]]

-- La propiedad es
prop_naturales0 :: Int -> Property
prop_naturales0 n = 
    n >= 0  ==>  naturales0 !! n == n*(1+(-1)^n) `div` 4

-- La comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_naturales0
--    +++ OK, passed 100 tests.

import Test.QuickCheck

naturales0 :: [Int]

naturales0 = concat [[n,0] | n <- [0..]]

-- La propiedad es

prop_naturales0 :: Int -> Property

prop_naturales0 n =

n >= 0 ==> naturales0 !! n == n*(1+(-1)^n) `div` 4

-- La comprobación es

-- ghci> quickCheckWith (stdArgs {maxSize=7}) prop_naturales0

-- +++ OK, passed 100 tests.

Enumeración de los números enteros

PorJosé A. Alonso 23-enero-201525-marzo-2022

Exercitium

Definir la sucesión

   enteros :: [Int]

1	enteros :: [Int]

tal que sus elementos son los números enteros comenzando en el 0 e intercalando los positivos y los negativos. Por ejemplo,

   ghci> take 23 enteros
   [0,1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7,8,-8,9,-9,10,-10,11,-11]

1 2	ghci> take 23 enteros [0,1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7,8,-8,9,-9,10,-10,11,-11]

Comprobar con QuickCheck que el n-ésimo término de la sucesión es (1-(2n+1)(-1)^n)/4.

Nota. En la comprobación usar

   quickCheckWith (stdArgs {maxSize=7}) prop_enteros

1	quickCheckWith (stdArgs {maxSize=7}) prop_enteros

Soluciones

import Test.QuickCheck

enteros :: [Int]
enteros = 0 : concat [[n,-n] | n <- [1..]]

-- La propiedad es
prop_enteros :: Int -> Property
prop_enteros n = 
    n >= 0 ==> enteros !! n == (1-(2*n+1)*(-1)^n) `div` 4

-- La comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_enteros
--    +++ OK, passed 100 tests.

import Test.QuickCheck

enteros :: [Int]

enteros = 0 : concat [[n,-n] | n <- [1..]]

-- La propiedad es

prop_enteros :: Int -> Property

prop_enteros n =

n >= 0 ==> enteros !! n == (1-(2*n+1)*(-1)^n) `div` 4

-- La comprobación es

-- ghci> quickCheckWith (stdArgs {maxSize=7}) prop_enteros

-- +++ OK, passed 100 tests.

Suma de una lista de vectores

PorJosé A. Alonso 19-enero-201530-noviembre-2015

Definir la función

   sumaVec :: Num a => [[a]] -> [a]

1	sumaVec :: Num a => [[a]] -> [a]

tal que (sumaVec xss) es la suma de los vectores de xss. Por ejemplo,

   sumaVec [[4,7,3],[3,1,4],[2,2,5]]  ==  [9,10,12]
   sumaVec [[4,7],[3,3],[1,4],[2,5]]  ==  [10,19]

1 2	sumaVec [[4,7,3],[3,1,4],[2,2,5]] == [9,10,12] sumaVec [[4,7],[3,3],[1,4],[2,5]] == [10,19]

Soluciones

import Data.List (transpose)
import Data.Array (listArray,(!))

-- 1ª definición (por recursión):
sumaVec1 :: Num a => [[a]] -> [a]
sumaVec1 []          = []
sumaVec1 [xs]        = xs
sumaVec1 (xs:ys:zss) = suma xs (sumaVec1 (ys:zss))

-- (suma xs ys) es la suma de los vectores xs e ys. Por ejemplo,
--    suma [4,7,3] [1,2,5]  == [5,9,8]
suma :: Num a => [a] -> [a] -> [a]
suma [] []         = []
suma (x:xs) (y:ys) = x+y : suma xs ys

-- 2ª definición (por recursión con zipWith): 
sumaVec2 :: Num a => [[a]] -> [a]
sumaVec2 []       = []
sumaVec2 [xs]     = xs
sumaVec2 (xs:xss) = zipWith (+) xs (sumaVec2 xss)

-- 3ª definición (por plegado)
sumaVec3 :: Num a => [[a]] -> [a]
sumaVec3 = foldr1 (zipWith (+))

-- 4ª definición (con map y transpose):
sumaVec4 :: Num a => [[a]] -> [a]
sumaVec4 = map sum . transpose 

-- 5ª definición (con array)
-- =========================

sumaVec5 :: Num a => [[a]] -> [a]
sumaVec5 xss = [sum [p!(i,j) | i <- [1..m]] | j <- [1..n]] 
    where m = length xss
          n = length (head xss)
          p = listArray ((1,1),(m,n)) (concat xss)

import Data.List (transpose)

import Data.Array (listArray,(!))

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

sumaVec1 :: Num a => [[a]] -> [a]

sumaVec1 [] = []

sumaVec1 [xs] = xs

sumaVec1 (xs:ys:zss) = suma xs (sumaVec1 (ys:zss))

-- (suma xs ys) es la suma de los vectores xs e ys. Por ejemplo,

-- suma [4,7,3] [1,2,5] == [5,9,8]

suma :: Num a => [a] -> [a] -> [a]

suma [] [] = []

suma (x:xs) (y:ys) = x+y : suma xs ys

-- 2ª definición (por recursión con zipWith):

sumaVec2 :: Num a => [[a]] -> [a]

sumaVec2 [] = []

sumaVec2 [xs] = xs

sumaVec2 (xs:xss) = zipWith (+) xs (sumaVec2 xss)

-- 3ª definición (por plegado)

sumaVec3 :: Num a => [[a]] -> [a]

sumaVec3 = foldr1 (zipWith (+))

-- 4ª definición (con map y transpose):

sumaVec4 :: Num a => [[a]] -> [a]

sumaVec4 = map sum . transpose

-- 5ª definición (con array)

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

sumaVec5 :: Num a => [[a]] -> [a]

sumaVec5 xss = [sum [p!(i,j) | i <- [1..m]] | j <- [1..n]]

where m = length xss

n = length (head xss)

p = listArray ((1,1),(m,n)) (concat xss)

Conjuntos de puntos enteros en regiones rectangulares

PorJosé A. Alonso 14-enero-201526-abril-2015

Los puntos de una cuadrícula se puede representar mediante pares de números enteros

   type Punto = (Int,Int)

1	type Punto = (Int,Int)

y las regiones rectangulares mediante el siguiente tipo de dato

   data Region = Rectangulo Punto  Punto 
               | Union      Region Region
               | Diferencia Region Region
               deriving (Eq, Show)

data Region = Rectangulo Punto Punto

| Union Region Region

| Diferencia Region Region

deriving (Eq, Show)

donde

(Rectangulo p1 p2) es la región formada por un rectángulo cuyo vértice superior izquierdo es p1 y su vértice inferior derecho es p2.
(Union r1 r2) es la región cuyos puntos pertenecen a alguna de las regiones r1 y r2.
(Diferencia r1 r2) es la región cuyos puntos pertenecen a la región r1 pero no pertenecen a la r2.

Definir la función

   puntos :: Region -> [Punto]

1	puntos :: Region -> [Punto]

tal que (puntos r) es la lista de puntos de la región r. Por ejemplo, usando las regiones definidas por

   r0021, r3051, r4162 :: Region
   r0021 = Rectangulo (0,0) (2,1)
   r3051 = Rectangulo (3,0) (5,1)
   r4162 = Rectangulo (4,1) (6,2)

r0021, r3051, r4162 :: Region

r0021 = Rectangulo (0,0) (2,1)

r3051 = Rectangulo (3,0) (5,1)

r4162 = Rectangulo (4,1) (6,2)

se tiene

   ghci> puntos r0021
   [(0,0),(0,1),(1,0),(1,1),(2,0),(2,1)]
   ghci> puntos r3051
   [(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)]
   ghci> puntos r4162
   [(4,1),(4,2),(5,1),(5,2),(6,1),(6,2)]
   ghci> puntos (Union r0021 r3051)
   [(0,0),(0,1),(1,0),(1,1),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)]
   ghci> puntos (Diferencia r3051 r4162)
   [(3,0),(3,1),(4,0),(5,0)]
   ghci> puntos (Union (Diferencia r3051 r4162) r4162)
   [(3,0),(3,1),(4,0),(5,0),(4,1),(4,2),(5,1),(5,2),(6,1),(6,2)]

ghci> puntos r0021

[(0,0),(0,1),(1,0),(1,1),(2,0),(2,1)]

ghci> puntos r3051

[(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)]

ghci> puntos r4162

[(4,1),(4,2),(5,1),(5,2),(6,1),(6,2)]

ghci> puntos (Union r0021 r3051)

[(0,0),(0,1),(1,0),(1,1),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(5,0),(5,1)]

ghci> puntos (Diferencia r3051 r4162)

[(3,0),(3,1),(4,0),(5,0)]

ghci> puntos (Union (Diferencia r3051 r4162) r4162)

[(3,0),(3,1),(4,0),(5,0),(4,1),(4,2),(5,1),(5,2),(6,1),(6,2)]

Comprobar con QuickCheck, usando la función enRegion definida en el ejercicio [Puntos en regiones rectangulares](Puntos en regiones rectangulares) que (enRegion p r) es equivalente a (p elem puntos r).

Nota: Escribir las soluciones usando la siguiente plantilla que contiene un generador de regiones

import Test.QuickCheck
import Control.Monad

type Punto = (Int,Int)

data Region = Rectangulo Punto  Punto
            | Union      Region Region
            | Diferencia Region Region
            deriving (Eq, Show)

r0021, r3051, r4162 :: Region
r0021 = Rectangulo (0,0) (2,1)
r3051 = Rectangulo (3,0) (5,1)
r4162 = Rectangulo (4,1) (6,2)

puntos :: Region -> [Punto]
puntos = undefined

-- La propiedad es
prop_puntos :: Punto -> Region -> Bool
prop_puntos p r = undefined

-- La comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_puntos
--    +++ OK, passed 100 tests.

enRegion :: Punto -> Region -> Bool
enRegion (x,y) (Rectangulo (x1,y1) (x2,y2)) =
    x1 <= x && x <= x2 && y1 <= y && y <= y2
enRegion p (Union r1 r2)      = enRegion p r1 || enRegion p r2
enRegion p (Diferencia r1 r2) = enRegion p r1 && not (enRegion p r2)

-- Generador de regiones:
instance Arbitrary Region where
    arbitrary = sized arb where
        arb 0         = liftM2 Rectangulo arbitrary arbitrary
        arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary,
                               liftM2 Union sub sub, 
                               liftM2 Diferencia sub sub] 
              where sub = arb (n `div` 2)

import Test.QuickCheck

import Control.Monad

type Punto = (Int,Int)

data Region = Rectangulo Punto Punto

| Union Region Region

| Diferencia Region Region

deriving (Eq, Show)

r0021, r3051, r4162 :: Region

r0021 = Rectangulo (0,0) (2,1)

r3051 = Rectangulo (3,0) (5,1)

r4162 = Rectangulo (4,1) (6,2)

puntos :: Region -> [Punto]

puntos = undefined

-- La propiedad es

prop_puntos :: Punto -> Region -> Bool

prop_puntos p r = undefined

-- La comprobación es

-- ghci> quickCheckWith (stdArgs {maxSize=7}) prop_puntos

-- +++ OK, passed 100 tests.

enRegion :: Punto -> Region -> Bool

enRegion (x,y) (Rectangulo (x1,y1) (x2,y2)) =

x1 <= x && x <= x2 && y1 <= y && y <= y2

enRegion p (Union r1 r2) = enRegion p r1 || enRegion p r2

enRegion p (Diferencia r1 r2) = enRegion p r1 && not (enRegion p r2)

-- Generador de regiones:

instance Arbitrary Region where

arbitrary = sized arb where

arb 0 = liftM2 Rectangulo arbitrary arbitrary

arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary,

liftM2 Union sub sub,

liftM2 Diferencia sub sub]

where sub = arb (n `div` 2)

Soluciones

import Data.List 
import Test.QuickCheck
import Control.Monad

type Punto = (Int,Int)

data Region = Rectangulo Punto  Punto
            | Union      Region Region
            | Diferencia Region Region
            deriving (Eq, Show)

r0021, r3051, r4162 :: Region
r0021 = Rectangulo (0,0) (2,1)
r3051 = Rectangulo (3,0) (5,1)
r4162 = Rectangulo (4,1) (6,2)

puntos :: Region -> [Punto]
puntos (Rectangulo (x1,y1) (x2,y2)) = 
    [(x,y) | x <- [x1..x2], y <- [y1..y2]]
puntos (Union r1 r2)      = puntos r1 `union` puntos r2
puntos (Diferencia r1 r2) = puntos r1 \\ puntos r2

-- La propiedad es
prop_puntos :: Punto -> Region -> Bool
prop_puntos p r =
    enRegion p r == (p `elem` puntos r)

-- La comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_puntos
--    +++ OK, passed 100 tests.

enRegion :: Punto -> Region -> Bool
enRegion (x,y) (Rectangulo (x1,y1) (x2,y2)) =
    x1 <= x && x <= x2 && y1 <= y && y <= y2
enRegion p (Union r1 r2)      = enRegion p r1 || enRegion p r2
enRegion p (Diferencia r1 r2) = enRegion p r1 && not (enRegion p r2)

-- Generador de regiones:
instance Arbitrary Region where
    arbitrary = sized arb where
        arb 0         = liftM2 Rectangulo arbitrary arbitrary
        arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary,
                               liftM2 Union sub sub, 
                               liftM2 Diferencia sub sub] 
              where sub = arb (n `div` 2)

import Data.List

import Test.QuickCheck

import Control.Monad

type Punto = (Int,Int)

data Region = Rectangulo Punto Punto

| Union Region Region

| Diferencia Region Region

deriving (Eq, Show)

r0021, r3051, r4162 :: Region

r0021 = Rectangulo (0,0) (2,1)

r3051 = Rectangulo (3,0) (5,1)

r4162 = Rectangulo (4,1) (6,2)

puntos :: Region -> [Punto]

puntos (Rectangulo (x1,y1) (x2,y2)) =

[(x,y) | x <- [x1..x2], y <- [y1..y2]]

puntos (Union r1 r2) = puntos r1 `union` puntos r2

puntos (Diferencia r1 r2) = puntos r1 \\ puntos r2

-- La propiedad es

prop_puntos :: Punto -> Region -> Bool

prop_puntos p r =

enRegion p r == (p `elem` puntos r)

-- La comprobación es

-- ghci> quickCheckWith (stdArgs {maxSize=7}) prop_puntos

-- +++ OK, passed 100 tests.

enRegion :: Punto -> Region -> Bool

enRegion (x,y) (Rectangulo (x1,y1) (x2,y2)) =

x1 <= x && x <= x2 && y1 <= y && y <= y2

enRegion p (Union r1 r2) = enRegion p r1 || enRegion p r2

enRegion p (Diferencia r1 r2) = enRegion p r1 && not (enRegion p r2)

-- Generador de regiones:

instance Arbitrary Region where

arbitrary = sized arb where

arb 0 = liftM2 Rectangulo arbitrary arbitrary

arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary,

liftM2 Union sub sub,

liftM2 Diferencia sub sub]

where sub = arb (n `div` 2)

Listas disjuntas

PorJosé A. Alonso 12-enero-201526-abril-2015

Definir la función

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

1	disjuntas :: Ord a => [a] -> [a] -> Bool

tal que (disjuntas xs ys) se verifica si las listas ordenadas crecientemente xs e ys son disjuntas. Por ejemplo,

   disjuntas [2,5]   [1,4,7]                  ==  True
   disjuntas [2,5,7] [1,4,7]                  ==  False
   disjuntas [1..1000000] [3000000..4000000]  ==  True

disjuntas [2,5] [1,4,7] == True

disjuntas [2,5,7] [1,4,7] == False

disjuntas [1..1000000] [3000000..4000000] == True

Soluciones

disjuntas :: Ord a => [a] -> [a] -> Bool
disjuntas xs [] = True
disjuntas [] ys = True
disjuntas xs1@(x:xs) ys1@(y:ys)
    | x < y  = disjuntas xs ys1
    | x == y = False
    | x > y  = disjuntas xs1 ys

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

disjuntas xs [] = True

disjuntas [] ys = True

disjuntas xs1@(x:xs) ys1@(y:ys)

| x < y = disjuntas xs ys1

| x == y = False

| x > y = disjuntas xs1 ys

Dos cuadrados encajados

PorJosé A. Alonso 5-enero-201512-enero-2015

Enunciado

Definir la función

   dosCuadrados :: Picture

1	dosCuadrados :: Picture

que dibuje dos cuadrados encajados como se muestra en la siguiente figura

Nota: Escribir las soluciones usando la siguiente plantilla

import Graphics.Gloss
    
main :: IO ()
main = display (InWindow "Dibujo" (500,300) (20,20)) white dosCuadrados
    
dosCuadrados :: Picture
dosCuadrados = undefined

import Graphics.Gloss

main :: IO ()

main = display (InWindow "Dibujo" (500,300) (20,20)) white dosCuadrados

dosCuadrados :: Picture

dosCuadrados = undefined

Soluciones

import Graphics.Gloss
    
main :: IO ()
main = display (InWindow "Dibujo" (500,300) (20,20)) white dosCuadrados
    
dosCuadrados :: Picture
dosCuadrados = pictures [cuadrado,
                         scale r r $ rotate 45 $ cuadrado]
    where cuadrado = rectangleWire 200 200
          r        = 1 / sqrt 2

import Graphics.Gloss

main :: IO ()

main = display (InWindow "Dibujo" (500,300) (20,20)) white dosCuadrados

dosCuadrados :: Picture

dosCuadrados = pictures [cuadrado,

scale r r $ rotate 45 $ cuadrado]

where cuadrado = rectangleWire 200 200

r = 1 / sqrt 2

Período de una lista

PorJosé A. Alonso 31-diciembre-201425-abril-2021

El período de una lista xs es la lista más corta ys tal que xs se puede obtener concatenando varias veces la lista ys. Por ejemplo, el período «abababab» es «ab» ya que «abababab» se obtiene repitiendo tres veces la lista «ab».

Definir la función

   periodo :: Eq a => [a] -> [a]

1	periodo :: Eq a => [a] -> [a]

tal que (periodo xs) es el período de xs. Por ejemplo,

   periodo "ababab"      ==  "ab"
   periodo "buenobueno"  ==  "bueno"
   periodo "oooooo"      ==  "o"
   periodo "sevilla"     ==  "sevilla"

periodo "ababab" == "ab"

periodo "buenobueno" == "bueno"

periodo "oooooo" == "o"

periodo "sevilla" == "sevilla"

Soluciones

periodo :: Eq a => [a] -> [a]
periodo xs = take n xs
    where l = length xs
          n = head [m | m <- divisores l, 
                        concat (replicate (l `div` m) (take m xs)) == xs]

-- (divisores n) es la lista de los divisores de n. Por ejemplo,
--    divisores 96  ==  [1,2,3,4,6,8,12,16,24,32,48,96]
divisores :: Int -> [Int]
divisores n = [x | x <- [1..n], n `mod` x == 0]

periodo :: Eq a => [a] -> [a]

periodo xs = take n xs

where l = length xs

n = head [m | m <- divisores l,

concat (replicate (l `div` m) (take m xs)) == xs]

-- (divisores n) es la lista de los divisores de n. Por ejemplo,

-- divisores 96 == [1,2,3,4,6,8,12,16,24,32,48,96]

divisores :: Int -> [Int]

divisores n = [x | x <- [1..n], n `mod` x == 0]

La función suelo

PorJosé A. Alonso 30-diciembre-201426-abril-2015

La función suelo asigna a cada número real el número entero más próximo por defecto; es decir, el mayor número entero igual o menor que ese número real. Por ejemplo, al -2.4 le asigna el -3 y al 1.7 el 1.

Haskell tiene una implementación de la función suelo llamada floor. El objetivo de este ejercicio es redefinir dicha función; es decir, definir (sin usar floor, round ni ceiling) la función

   suelo :: Float -> Integer

1	suelo :: Float -> Integer

tal que (suelo x) es el suelo de x. Por ejemplo,

   suelo (-2.7)  ==  -3
   suelo (-2.4)  ==  -3
   suelo (-2)    ==  -2
   suelo 0       ==   0
   suelo 2       ==   2
   suelo 2.4     ==   2
   suelo 2.7     ==   2

suelo (-2.7) == -3

suelo (-2.4) == -3

suelo (-2) == -2

suelo 0 == 0

suelo 2 == 2

suelo 2.4 == 2

suelo 2.7 == 2

Comprobar con QuickCheck que las funciones suelo y floor son equivalentes.

Soluciones

import Test.QuickCheck

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

suelo1 :: Float -> Integer
suelo1 x | x < 0     = head [m | m <- [-1,-2..], fromIntegral m <= x] 
         | otherwise = head [m | m <- [1..], x < fromIntegral m] - 1

-- 2ª definición (con until)
-- =========================

suelo2 :: Float -> Integer
suelo2 x | x < 0     = until (`menorI` x) (subtract 1) (-1)
         | otherwise = until (x `menor`) (+1) 1 - 1
         where menorI m x = fromIntegral m <= x
               menor  x m = x < fromIntegral m

-- 3ª definición (con until sin auxiliares):
suelo3 :: Float -> Integer
suelo3 x | x < 0     = until ((<=x) . fromIntegral) (subtract 1) (-1)
         | otherwise = until ((x<)  . fromIntegral) (+1) 1 - 1

-- 4ª definición (con show, read y takeWhile):
suelo4 :: Float -> Integer
suelo4 x | r < 0     = n-1 
         | otherwise = n
    where n = read (takeWhile (/='.') (show x))
          r = x - fromIntegral n
   
-- 5ª definición (con properFraction):
suelo5 :: Float -> Integer
suelo5 x = if r < 0 then n-1 else n
    where (n,r) = properFraction x

-- 6ª definición (por búsqueda binaria):
suelo6 :: Float -> Integer
suelo6 x = fst (until unitario (mejora x) (acota x))
    where inferior x     = until (`menorI` x) (*2) (-1)
          superior x     = until (x `menor`) (*2) 1
          menorI m x     = fromIntegral m <= x
          menor  x m     = x < fromIntegral m
          acota x        = (inferior x, superior x)
          mejora x (m,n) = if p `menorI` x then (p,n) else (m,p)
                           where p =(m+n) `div` 2
          unitario (m,n) = (m+1 == n)

-- La propiedad es
prop_suelo x =
    suelo1 x == y &&
    suelo2 x == y &&
    suelo3 x == y &&
    suelo4 x == y &&
    suelo5 x == y &&
    suelo6 x == y
    where y = floor x

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

import Test.QuickCheck

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

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

suelo1 :: Float -> Integer

suelo1 x | x < 0 = head [m | m <- [-1,-2..], fromIntegral m <= x]

| otherwise = head [m | m <- [1..], x < fromIntegral m] - 1

-- 2ª definición (con until)

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

suelo2 :: Float -> Integer

suelo2 x | x < 0 = until (`menorI` x) (subtract 1) (-1)

| otherwise = until (x `menor`) (+1) 1 - 1

where menorI m x = fromIntegral m <= x

menor x m = x < fromIntegral m

-- 3ª definición (con until sin auxiliares):

suelo3 :: Float -> Integer

suelo3 x | x < 0 = until ((<=x) . fromIntegral) (subtract 1) (-1)

| otherwise = until ((x<) . fromIntegral) (+1) 1 - 1

-- 4ª definición (con show, read y takeWhile):

suelo4 :: Float -> Integer

suelo4 x | r < 0 = n-1

| otherwise = n

where n = read (takeWhile (/='.') (show x))

r = x - fromIntegral n

-- 5ª definición (con properFraction):

suelo5 :: Float -> Integer

suelo5 x = if r < 0 then n-1 else n

where (n,r) = properFraction x

-- 6ª definición (por búsqueda binaria):

suelo6 :: Float -> Integer

suelo6 x = fst (until unitario (mejora x) (acota x))

where inferior x = until (`menorI` x) (*2) (-1)

superior x = until (x `menor`) (*2) 1

menorI m x = fromIntegral m <= x

menor x m = x < fromIntegral m

acota x = (inferior x, superior x)

mejora x (m,n) = if p `menorI` x then (p,n) else (m,p)

where p =(m+n) `div` 2

unitario (m,n) = (m+1 == n)

-- La propiedad es

prop_suelo x =

suelo1 x == y &&

suelo2 x == y &&

suelo3 x == y &&

suelo4 x == y &&

suelo5 x == y &&

suelo6 x == y

where y = floor x

-- La comprobación es

-- ghci> quickCheck prop_suelo

-- +++ OK, passed 100 tests.

Elementos más frecuentes

PorJosé A. Alonso 26-diciembre-201414-enero-2015

Definir la función

   masFrecuentes :: Ord a => Int -> [a] -> [(Int,a)]

1	masFrecuentes :: Ord a => Int -> [a] -> [(Int,a)]

tal que (masFrecuentes n xs) es la lista de los pares formados por los elementos de xs que aparecen más veces junto con el número de veces que aparecen. Por ejemplo,

   ghci> masFrecuentes 2 "trianera"
   [(2,'r'),(2,'a')]
   ghci> masFrecuentes 2 "interdisciplinariedad"
   [(5,'i'),(3,'d')]
   ghci> masFrecuentes 3 (show (product [1..10000]))
   [(5803,'0'),(3416,'2'),(3341,'4')]

ghci> masFrecuentes 2 "trianera"

[(2,'r'),(2,'a')]

ghci> masFrecuentes 2 "interdisciplinariedad"

[(5,'i'),(3,'d')]

ghci> masFrecuentes 3 (show (product [1..10000]))

[(5803,'0'),(3416,'2'),(3341,'4')]

Soluciones

import Data.List (group, sort)

masFrecuentes :: Ord a => Int -> [a] -> [(Int,a)]
masFrecuentes n = take n . reverse . sort . cuenta . group . sort
    where cuenta xss = [(length xs,head xs) | xs <- xss]

import Data.List (group, sort)

masFrecuentes :: Ord a => Int -> [a] -> [(Int,a)]

masFrecuentes n = take n . reverse . sort . cuenta . group . sort

where cuenta xss = [(length xs,head xs) | xs <- xss]

Desemparejamiento de listas

PorJosé A. Alonso 23-diciembre-201430-diciembre-2014

Definir la función

   desemparejada :: [(a,b)] -> ([a],[b])

1	desemparejada :: [(a,b)] -> ([a],[b])

tal que (desemparejada ps) es el par de lista (xs,ys) tal que al emparejar (con zip) xs e ys devuelve ps. Por ejemplo,

   ghci> desemparejada [(3,'l'),(2,'u'),(5,'i'),(9,'s')]
   ([3,2,5,9],"luis")

1 2	ghci> desemparejada [(3,'l'),(2,'u'),(5,'i'),(9,'s')] ([3,2,5,9],"luis")

Comprobar con QuickCheck que

desemparejada es equivalente a la función predefinida unzip.
si el valor de (desemparejada ps) es (xs,ys), entonces (zip xs ys) es igual a ps.

Soluciones

import Test.QuickCheck

-- 1ª definición (por comprensión):
desemparejada1 :: [(a,b)] -> ([a],[b])
desemparejada1 ps = ([x | (x,_) <- ps], [y | (_,y) <- ps])

-- 2ª definición (con map):
desemparejada2 :: [(a,b)] -> ([a],[b])
desemparejada2 ps = (map fst ps, map snd ps)

-- 3ª definición (por recursión):
desemparejada3 :: [(a,b)] -> ([a],[b])
desemparejada3 []         = ([],[])
desemparejada3 ((x,y):ps) = (x:xs,y:ys)
    where (xs,ys) = desemparejada3 ps 

-- 4ª definición (por plegado):
desemparejada4 :: [(a,b)] -> ([a],[b])
desemparejada4 = foldr f ([],[])
    where f (x,y) (xs,ys) = (x:xs, y:ys)

-- 5ª definición (por plegado por la izquierda):
desemparejada5 :: [(a,b)] -> ([a],[b])
desemparejada5 ps = (reverse us, reverse vs)
    where (us,vs) = foldl f ([],[]) ps
          f (xs,ys) (x,y) = (x:xs,y:ys)

-- Comparación de eficiencia-
--    ghci> let ps = zip [1..10^7] [1..10^7]
--    
--    ghci> length (fst (desemparejada1 ps))
--    10000000
--    (3.67 secs, 360441524 bytes)
--    
--    ghci> length (fst (desemparejada2 ps))
--    10000000
--    (0.38 secs, 440476764 bytes)
--    
--    ghci> length (fst (desemparejada3 ps))
--    10000000
--    (14.11 secs, 2160188668 bytes)
--    
--    ghci> length (fst (desemparejada4 ps))
--    10000000
--    (19.08 secs, 1658689692 bytes)
--    
--    ghci> length (fst (desemparejada5 ps))
--    10000000
--    (20.98 secs, 1610061796 bytes)

-- En lo que sigue, usaremos la  2º definición
desemparejada :: [(a,b)] -> ([a],[b])
desemparejada = desemparejada2

-- La primera propiedad es
prop_desemparejada_1 :: (Eq a, Eq b) => [(a,b)] -> Bool
prop_desemparejada_1 ps =
    desemparejada ps == unzip ps

-- Su comprobación es
--    ghci> quickCheck prop_desemparejada_1
--    +++ OK, passed 100 tests.

-- La segunda propiedad es
prop_desemparejada_2 :: (Eq a, Eq b) => [(a,b)] -> Bool
prop_desemparejada_2 ps = zip xs ys == ps
    where (xs,ys) = desemparejada ps

-- Su comprobación es
--    ghci> quickCheck prop_desemparejada_2
--    +++ OK, passed 100 tests.

import Test.QuickCheck

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

desemparejada1 :: [(a,b)] -> ([a],[b])

desemparejada1 ps = ([x | (x,_) <- ps], [y | (_,y) <- ps])

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

desemparejada2 :: [(a,b)] -> ([a],[b])

desemparejada2 ps = (map fst ps, map snd ps)

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

desemparejada3 :: [(a,b)] -> ([a],[b])

desemparejada3 [] = ([],[])

desemparejada3 ((x,y):ps) = (x:xs,y:ys)

where (xs,ys) = desemparejada3 ps

-- 4ª definición (por plegado):

desemparejada4 :: [(a,b)] -> ([a],[b])

desemparejada4 = foldr f ([],[])

where f (x,y) (xs,ys) = (x:xs, y:ys)

-- 5ª definición (por plegado por la izquierda):

desemparejada5 :: [(a,b)] -> ([a],[b])

desemparejada5 ps = (reverse us, reverse vs)

where (us,vs) = foldl f ([],[]) ps

f (xs,ys) (x,y) = (x:xs,y:ys)

-- Comparación de eficiencia-

-- ghci> let ps = zip [1..10^7] [1..10^7]

-- ghci> length (fst (desemparejada1 ps))

-- 10000000

-- (3.67 secs, 360441524 bytes)

-- ghci> length (fst (desemparejada2 ps))

-- 10000000

-- (0.38 secs, 440476764 bytes)

-- ghci> length (fst (desemparejada3 ps))

-- 10000000

-- (14.11 secs, 2160188668 bytes)

-- ghci> length (fst (desemparejada4 ps))

-- 10000000

-- (19.08 secs, 1658689692 bytes)

-- ghci> length (fst (desemparejada5 ps))

-- 10000000

-- (20.98 secs, 1610061796 bytes)

-- En lo que sigue, usaremos la 2º definición

desemparejada :: [(a,b)] -> ([a],[b])

desemparejada = desemparejada2

-- La primera propiedad es

prop_desemparejada_1 :: (Eq a, Eq b) => [(a,b)] -> Bool

prop_desemparejada_1 ps =

desemparejada ps == unzip ps

-- Su comprobación es

-- ghci> quickCheck prop_desemparejada_1

-- +++ OK, passed 100 tests.

-- La segunda propiedad es

prop_desemparejada_2 :: (Eq a, Eq b) => [(a,b)] -> Bool

prop_desemparejada_2 ps = zip xs ys == ps

where (xs,ys) = desemparejada ps

-- Su comprobación es

-- ghci> quickCheck prop_desemparejada_2

-- +++ OK, passed 100 tests.

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

Permutación de elementos consecutivos

PorJosé A. Alonso 15-diciembre-201417-marzo-2019

-- Definir la función
--    permutaConsecutivos :: [a] -> [a]
-- tal que (permutaConsecutivos xs) es la lista obtenida permutando los
-- elementos consecutivos de xs. Por ejemplo,
--    permutaConsecutivos [1..8]         ==  [2,1,4,3,6,5,8,7]
--    permutaConsecutivos [1..9]         ==  [2,1,4,3,6,5,8,7,9]
--    permutaConsecutivos "simplemente"  ==  "ispmelemtne"

-- Definir la función

-- permutaConsecutivos :: [a] -> [a]

-- tal que (permutaConsecutivos xs) es la lista obtenida permutando los

-- elementos consecutivos de xs. Por ejemplo,

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

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

-- permutaConsecutivos "simplemente" == "ispmelemtne"

Soluciones

permutaConsecutivos :: [a] -> [a]
permutaConsecutivos (x:y:zs) = y : x : permutaConsecutivos zs
permutaConsecutivos xs       = xs

permutaConsecutivos :: [a] -> [a]

permutaConsecutivos (x:y:zs) = y : x : permutaConsecutivos zs

permutaConsecutivos xs = xs

Números que sumados a su siguiente primo dan primos

PorJosé A. Alonso 11-diciembre-201425-marzo-2022

Introducción

La Enciclopedia electrónica de sucesiones de enteros (OEIS por sus siglas en inglés, de On-Line Encyclopedia of Integer Sequences) es una base de datos que registra sucesiones de números enteros. Está disponible libremente en Internet, en la dirección http://oeis.org.

La semana pasada Antonio Roldán añadió una nueva sucesión a la OEIS, la A249624 que sirve de base para el problema de hoy.

Enunciado

-- Definir la sucesión
--     a249624 :: [Integer]
-- tal que sus elementos son los números x tales que la suma de x y el
-- primo que le sigue es un número primo. Por ejemplo, 
--    ghci> take 20 a249624
--    [0,1,2,6,8,14,18,20,24,30,34,36,38,48,50,54,64,68,78,80]
-- 
-- El número 8 está en la sucesión porque su siguiente primo es 11 y
-- 8+11=19 es primo. El 12 no está en la sucesión porque su siguiente
-- primo es 13 y 12+13=25 no es primo.

-- Definir la sucesión

-- a249624 :: [Integer]

-- tal que sus elementos son los números x tales que la suma de x y el

-- primo que le sigue es un número primo. Por ejemplo,

-- ghci> take 20 a249624

-- [0,1,2,6,8,14,18,20,24,30,34,36,38,48,50,54,64,68,78,80]

-- El número 8 está en la sucesión porque su siguiente primo es 11 y

-- 8+11=19 es primo. El 12 no está en la sucesión porque su siguiente

-- primo es 13 y 12+13=25 no es primo.

Soluciones

import Data.Numbers.Primes (primes, isPrime)
import Data.List (genericReplicate)

-- 1ª definición
-- =============

a249624 :: [Integer]
a249624 = 0: 1: [x | x <- [2,4..], primo (x + siguientePrimo x)]

primo :: Integer -> Bool
primo x = [y | y <- [1..x], x `rem` y == 0] == [1,x]

siguientePrimo :: Integer -> Integer
siguientePrimo x = head [y | y <- [x+1..], primo y]

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

a249624b :: [Integer]
a249624b = 0 : 1 : 2: aux [2,4..] primos where
    aux (x:xs) (y:ys) 
        | y < x                = aux (x:xs) ys
        | (x+y) `pertenece` ys = x : aux xs (y:ys)
        | otherwise            = aux xs (y:ys)
    pertenece x ys = x == head (dropWhile (<x) ys)

primos :: [Integer]
primos = 2 : [x | x <- [3,5..], primo x]

-- 3ª definición (con la librería de primos)
-- =========================================

a249624c :: [Integer]
a249624c = 0: 1: [x | x <- [2,4..], isPrime (x + siguientePrimo3 x)]

siguientePrimo3 x = head [y | y <- [x+1..], isPrime y]

-- 4ª definición (por recursión con la librería de primos)
-- =======================================================

a249624d :: [Integer]
a249624d = 0 : 1 : 2: aux [2,4..] primes where
    aux (x:xs) (y:ys) 
        | y < x                = aux (x:xs) ys
        | (x+y) `pertenece` ys = x : aux xs (y:ys)
        | otherwise            = aux xs (y:ys)
    pertenece x ys = x == head (dropWhile (<x) ys)

-- 5ª definición
-- =============

a249624e :: [Integer]
a249624e = [a | q <- primes, 
                let p = siguientePrimo3 (q `div` 2),
                let a = q-p,
                siguientePrimo3 a == p]

-- 6ª definición
-- =============

a249624f :: [Integer]
a249624f = [x | (x,y) <- zip [0..] ps, isPrime (x+y)]
    where ps = 2:2:concat (zipWith f primes (tail primes))
          f p q = genericReplicate (q-p) q

-- 7ª definición
-- =============

a249624g :: [Integer]
a249624g = 0:1:(aux primes (tail primes) primes)
    where aux (x:xs) (y:ys) zs
              | null rs   = aux xs ys zs2
              | otherwise = [r-y | r <- rs] ++ (aux xs ys zs2)
              where a = x+y
                    b = 2*y-1
                    zs1 = takeWhile (<=b) zs
                    rs = [r | r <- [a..b], r `elem` zs1]
                    zs2 = dropWhile (<=b) zs

-- ---------------------------------------------------------------------
-- § Comparación de eficiencia                                        --
-- ---------------------------------------------------------------------

-- La comparación es
--    ghci> :set +s
--    
--    ghci> a249624 !! 700
--    5670
--    (12.72 secs, 1245938184 bytes)
--    
--    ghci> a249624b !! 700
--    5670
--    (8.01 secs, 764775268 bytes)
-- 
--    ghci> a249624c !! 700
--    5670
--    (0.22 secs, 108982640 bytes)
--    
--    ghci> a249624d !! 700
--    5670
--    (0.20 secs, 4707384 bytes)
--    
--    ghci> a249624e !! 700
--    5670
--    (0.17 secs, 77283064 bytes)
--    
--    ghci> a249624f !! 700
--    5670
--    (0.08 secs, 31684408 bytes)
--    
--    ghci> a249624g !! 700
--    5670
--    (0.03 secs, 4651576 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

import Data.Numbers.Primes (primes, isPrime)

import Data.List (genericReplicate)

-- 1ª definición

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

a249624 :: [Integer]

a249624 = 0: 1: [x | x <- [2,4..], primo (x + siguientePrimo x)]

primo :: Integer -> Bool

primo x = [y | y <- [1..x], x `rem` y == 0] == [1,x]

siguientePrimo :: Integer -> Integer

siguientePrimo x = head [y | y <- [x+1..], primo y]

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

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

a249624b :: [Integer]

a249624b = 0 : 1 : 2: aux [2,4..] primos where

aux (x:xs) (y:ys)

| y < x = aux (x:xs) ys

| (x+y) `pertenece` ys = x : aux xs (y:ys)

| otherwise = aux xs (y:ys)

pertenece x ys = x == head (dropWhile (<x) ys)

primos :: [Integer]

primos = 2 : [x | x <- [3,5..], primo x]

-- 3ª definición (con la librería de primos)

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

a249624c :: [Integer]

a249624c = 0: 1: [x | x <- [2,4..], isPrime (x + siguientePrimo3 x)]

siguientePrimo3 x = head [y | y <- [x+1..], isPrime y]

-- 4ª definición (por recursión con la librería de primos)

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

a249624d :: [Integer]

a249624d = 0 : 1 : 2: aux [2,4..] primes where

aux (x:xs) (y:ys)

| y < x = aux (x:xs) ys

| (x+y) `pertenece` ys = x : aux xs (y:ys)

| otherwise = aux xs (y:ys)

pertenece x ys = x == head (dropWhile (<x) ys)

-- 5ª definición

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

a249624e :: [Integer]

a249624e = [a | q <- primes,

let p = siguientePrimo3 (q `div` 2),

let a = q-p,

siguientePrimo3 a == p]

-- 6ª definición

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

a249624f :: [Integer]

a249624f = [x | (x,y) <- zip [0..] ps, isPrime (x+y)]

where ps = 2:2:concat (zipWith f primes (tail primes))

f p q = genericReplicate (q-p) q

-- 7ª definición

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

a249624g :: [Integer]

a249624g = 0:1:(aux primes (tail primes) primes)

where aux (x:xs) (y:ys) zs

| null rs = aux xs ys zs2

| otherwise = [r-y | r <- rs] ++ (aux xs ys zs2)

where a = x+y

b = 2*y-1

zs1 = takeWhile (<=b) zs

rs = [r | r <- [a..b], r `elem` zs1]

zs2 = dropWhile (<=b) zs

-- ---------------------------------------------------------------------

-- § Comparación de eficiencia --

-- ---------------------------------------------------------------------

-- La comparación es

-- ghci> :set +s

-- ghci> a249624 !! 700

-- 5670

-- (12.72 secs, 1245938184 bytes)

-- ghci> a249624b !! 700

-- 5670

-- (8.01 secs, 764775268 bytes)

-- ghci> a249624c !! 700

-- 5670

-- (0.22 secs, 108982640 bytes)

-- ghci> a249624d !! 700

-- 5670

-- (0.20 secs, 4707384 bytes)

-- ghci> a249624e !! 700

-- 5670

-- (0.17 secs, 77283064 bytes)

-- ghci> a249624f !! 700

-- 5670

-- (0.08 secs, 31684408 bytes)

-- ghci> a249624g !! 700

-- 5670

-- (0.03 secs, 4651576 bytes)

Búsqueda en lista de listas de pares

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

Enunciado

-- Definir la función
--    busca :: Eq a => a -> [[(a,b)]] -> [b]
-- tal que (busca x pss) es la lista de los segundos componentes de los
-- pares de la lista de listas de pares pss cuya primera componentes es
-- x. Por ejemplo,
--    busca 3 [[(3,4)],[(5,4),(3,2),(3,5)],[(4,1),(7,3)]] == [4,2,5]

-- Definir la función

-- busca :: Eq a => a -> [[(a,b)]] -> [b]

-- tal que (busca x pss) es la lista de los segundos componentes de los

-- pares de la lista de listas de pares pss cuya primera componentes es

-- x. Por ejemplo,

-- busca 3 [[(3,4)],[(5,4),(3,2),(3,5)],[(4,1),(7,3)]] == [4,2,5]

Soluciones

-- 1ª solución:
busca :: Eq a => a -> [[(a,b)]] -> [b]
busca x pss = [y | ps <- pss, (z,y) <- ps, z == x]  

-- 2ª solución:
busca2 :: Eq a => a -> [[(a,b)]] -> [b]
busca2 x pss = [y | (z,y) <- concat pss, z == x]

-- 1ª solución:

busca :: Eq a => a -> [[(a,b)]] -> [b]

busca x pss = [y | ps <- pss, (z,y) <- ps, z == x]

-- 2ª solución:

busca2 :: Eq a => a -> [[(a,b)]] -> [b]

busca2 x pss = [y | (z,y) <- concat pss, z == x]

Llanuras de longitud dada

PorJosé A. Alonso 4-diciembre-20141-mayo-2016

Enunciado

-- Una llanura de longitud n de una lista xs es una sublista de xs
-- formada por n elementos iguales.
--
-- Definir la función
--    llanuras :: Eq a => Int -> [a] -> [[a]]
-- tal que (llanuras n xs) es la lista de las llanuras de xs que tienen
-- n elementos como mínimo. Por ejemplo,
--    llanuras 3 "aabbbcddddffxffxx"  ==  ["bbb","dddd"]

-- Una llanura de longitud n de una lista xs es una sublista de xs

-- formada por n elementos iguales.

-- Definir la función

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

-- tal que (llanuras n xs) es la lista de las llanuras de xs que tienen

-- n elementos como mínimo. Por ejemplo,

-- llanuras 3 "aabbbcddddffxffxx" == ["bbb","dddd"]

Soluciones

import Data.List (group)
import Test.QuickCheck

-- 1ª definición (por comprensión):
llanuras :: Eq a => Int -> [a] -> [[a]]
llanuras n xs = [ys | ys <- group xs, length ys >= n] 

-- 2ª definición (por recursión con takeWhile y dropWhile):
llanuras2 :: Eq a => Int -> [a] -> [[a]]
llanuras2 _ [] = []
llanuras2 n xs@(x:_) 
    | length ys >= n = ys : llanuras2 n (dropWhile (x==) xs) 
    | otherwise      = llanuras2 n (dropWhile (x==) xs) 
    where ys = takeWhile (x==) xs

-- 3ª definición (por recursión con span):
llanuras3 :: Eq a => Int -> [a] -> [[a]]
llanuras3 _ [] = []
llanuras3 n xs@(x:_) 
    | length ys >= n = ys : llanuras3 n zs
    | otherwise      = llanuras3 n zs
    where (ys,zs) = span (x==) xs

-- 4ª definición (por recursión con span):
llanuras4 :: Eq a => Int -> [a] -> [[a]]
llanuras4 n = aux where
    aux [] = []
    aux xs@(x:_) | length ys >= n = ys : llanuras4 n zs
                 | otherwise      = llanuras4 n zs
                 where (ys,zs) = span (x==) xs

-- ---------------------------------------------------------------------
-- § Verificación                                                     --
-- ---------------------------------------------------------------------

-- Las definiciones son equivalentes
prop_equivalencia :: Int -> [Int] -> Bool
prop_equivalencia n xs =
    llanuras2 n xs == ys &&
    llanuras3 n xs == ys
    where ys = llanuras n xs

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

import Data.List (group)

import Test.QuickCheck

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

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

llanuras n xs = [ys | ys <- group xs, length ys >= n]

-- 2ª definición (por recursión con takeWhile y dropWhile):

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

llanuras2 _ [] = []

llanuras2 n xs@(x:_)

| length ys >= n = ys : llanuras2 n (dropWhile (x==) xs)

| otherwise = llanuras2 n (dropWhile (x==) xs)

where ys = takeWhile (x==) xs

-- 3ª definición (por recursión con span):

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

llanuras3 _ [] = []

llanuras3 n xs@(x:_)

| length ys >= n = ys : llanuras3 n zs

| otherwise = llanuras3 n zs

where (ys,zs) = span (x==) xs

-- 4ª definición (por recursión con span):

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

llanuras4 n = aux where

aux [] = []

aux xs@(x:_) | length ys >= n = ys : llanuras4 n zs

| otherwise = llanuras4 n zs

where (ys,zs) = span (x==) xs

-- ---------------------------------------------------------------------

-- § Verificación --

-- ---------------------------------------------------------------------

-- Las definiciones son equivalentes

prop_equivalencia :: Int -> [Int] -> Bool

prop_equivalencia n xs =

llanuras2 n xs == ys &&

llanuras3 n xs == ys

where ys = llanuras n xs

-- La comprobación es

-- ghci> quickCheck prop_equivalencia

-- +++ OK, passed 100 tests.

Referencias

Esté ejercicio está basado en el problema Llanura de números iguales con longitud igual a n propuesto Solveet!

Evaluación de árboles de expresiones aritméticas

PorJosé A. Alonso 27-noviembre-201425-abril-2021

Enunciado

-- Las expresiones aritméticas se pueden representar como árboles con
-- números en las hojas y operaciones en los nodos. Por ejemplo, la
-- expresión "9-2*4" se puede representar por el árbol
--      - 
--     / \
--    9   *
--       / \
--      2   4
-- 
-- Definiendo el tipo de dato Arbol por 
--    data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol
-- la representación del árbol anterior es
--    N (-) (H 9) (N (*) (H 2) (H 4))
--
-- Definir la función
--    valor :: Arbol -> Int
-- tal que (valor a) es el valor de la expresión aritmética
-- correspondiente al árbol a. Por ejemplo,
--    valor (N (-) (H 9) (N (*) (H 2) (H 4)))    ==  1
--    valor (N (+) (H 9) (N (*) (H 2) (H 4)))    ==  17
--    valor (N (+) (H 9) (N (div) (H 4) (H 2)))  ==  11
--    valor (N (+) (H 9) (N (max) (H 4) (H 2)))  ==  13

-- Las expresiones aritméticas se pueden representar como árboles con

-- números en las hojas y operaciones en los nodos. Por ejemplo, la

-- expresión "9-2*4" se puede representar por el árbol

-- -

-- / \

-- 9 *

-- / \

-- 2 4

-- Definiendo el tipo de dato Arbol por

-- data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol

-- la representación del árbol anterior es

-- N (-) (H 9) (N (*) (H 2) (H 4))

-- Definir la función

-- valor :: Arbol -> Int

-- tal que (valor a) es el valor de la expresión aritmética

-- correspondiente al árbol a. Por ejemplo,

-- valor (N (-) (H 9) (N (*) (H 2) (H 4))) == 1

-- valor (N (+) (H 9) (N (*) (H 2) (H 4))) == 17

-- valor (N (+) (H 9) (N (div) (H 4) (H 2))) == 11

-- valor (N (+) (H 9) (N (max) (H 4) (H 2))) == 13

Soluciones

data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol

valor :: Arbol -> Int
valor (H x)     = x
valor (N f i d) = f (valor i) (valor d)

data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol

valor :: Arbol -> Int

valor (H x) = x

valor (N f i d) = f (valor i) (valor d)

Aplicaciones alternativas

PorJosé A. Alonso 26-noviembre-201425-marzo-2022

Enunciado

-- Definir la función
--    alternativa :: (a -> b) -> (a -> b) -> [a] -> [b]
-- tal que (alternativa f g xs) es la lista obtenida aplicando
-- alternativamente las funciones f y g a los elementos de xs. Por
-- ejemplo, 
--    alternativa (+1)  (+10) [1,2,3,4]    ==  [2,12,4,14]
--    alternativa (+10) (*10) [1,2,3,4,5]  ==  [11,20,13,40,15]

-- Definir la función

-- alternativa :: (a -> b) -> (a -> b) -> [a] -> [b]

-- tal que (alternativa f g xs) es la lista obtenida aplicando

-- alternativamente las funciones f y g a los elementos de xs. Por

-- ejemplo,

-- alternativa (+1) (+10) [1,2,3,4] == [2,12,4,14]

-- alternativa (+10) (*10) [1,2,3,4,5] == [11,20,13,40,15]

Soluciones

[schedule expon=’2014-12-03′ expat=»06:00″]

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

[/schedule]

[schedule on=’2014-12-03′ at=»06:00″]

-- 1ª definición (por recursión):
alternativa1 :: (a -> b) -> (a -> b) -> [a] -> [b]
alternativa1 f g []     = []
alternativa1 f g (x:xs) = f x : alternativa1 g f xs

-- 2ª definición (por comprensión):
alternativa2 :: (a -> b) -> (a -> b) -> [a] -> [b]
alternativa2 f g xs = 
    [h x | (h,x) <- zip (cycle [f,g]) xs]

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

alternativa1 :: (a -> b) -> (a -> b) -> [a] -> [b]

alternativa1 f g [] = []

alternativa1 f g (x:xs) = f x : alternativa1 g f xs

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

alternativa2 :: (a -> b) -> (a -> b) -> [a] -> [b]

alternativa2 f g xs =

[h x | (h,x) <- zip (cycle [f,g]) xs]

[/schedule]

Repetición cíclica

PorJosé A. Alonso 25-noviembre-201425-marzo-2022

Enunciado

-- Definir la función
--    ciclica :: [a] -> [a]
-- tal que (ciclica xs) es la lista obtenida repitiendo cíclicamente los
-- elementos de xs. Por ejemplo,
--    take 10 (ciclica [3,5])    ==  [3,5,3,5,3,5,3,5,3,5]
--    take 10 (ciclica [3,5,7])  ==  [3,5,7,3,5,7,3,5,7,3]
--    take 10 (ciclica [3,5..])  ==  [3,5,7,9,11,13,15,17,19,1]
--    ciclica []                 ==  []
--
-- Comprobar con QuickCheck que la función ciclica es equivalente a la
-- predefinida cycle; es decir, para cualquier número entero n y
-- cualquier lista no vacía xs, se verifica que 
--    take n (ciclica xs) == take n (cycle xs)
-- 
-- Nota. Al hacer la comprobación limitar el tamaño de las pruebas como
-- se indica a continuación
--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_ciclica
--    +++ OK, passed 100 tests.

-- Definir la función

-- ciclica :: [a] -> [a]

-- tal que (ciclica xs) es la lista obtenida repitiendo cíclicamente los

-- elementos de xs. Por ejemplo,

-- take 10 (ciclica [3,5]) == [3,5,3,5,3,5,3,5,3,5]

-- take 10 (ciclica [3,5,7]) == [3,5,7,3,5,7,3,5,7,3]

-- take 10 (ciclica [3,5..]) == [3,5,7,9,11,13,15,17,19,1]

-- ciclica [] == []

-- Comprobar con QuickCheck que la función ciclica es equivalente a la

-- predefinida cycle; es decir, para cualquier número entero n y

-- cualquier lista no vacía xs, se verifica que

-- take n (ciclica xs) == take n (cycle xs)

-- Nota. Al hacer la comprobación limitar el tamaño de las pruebas como

-- se indica a continuación

-- ghci> quickCheckWith (stdArgs {maxSize=7}) prop_ciclica

-- +++ OK, passed 100 tests.

Soluciones

import Test.QuickCheck

-- 1ª definición
ciclica1 :: [a] -> [a]
ciclica1 [] = []
ciclica1 xs = xs ++ ciclica1 xs

-- 2ª definición
ciclica2 :: [a] -> [a]
ciclica2 [] = []
ciclica2 xs = ys where ys = xs ++ ys

-- Comprobación de eficiencia
--    ghci> last (take 10000000 (ciclica1 [1,2])) 
--    2
--    (3.69 secs, 1521758928 bytes)
--    
--    ghci> last (take 10000000 (ciclica2 [1,2])) 
--    2
--    (0.21 secs, 561468144 bytes)
-- La 2ª definición es más eficiente.

-- La propiedad es
prop_ciclica :: Int -> [Int] -> Property
prop_ciclica n xs =
    not (null xs) ==> 
    take n (ciclica2 xs) == take n (cycle xs)

-- La comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_ciclica
--    +++ OK, passed 100 tests.

import Test.QuickCheck

-- 1ª definición

ciclica1 :: [a] -> [a]

ciclica1 [] = []

ciclica1 xs = xs ++ ciclica1 xs

-- 2ª definición

ciclica2 :: [a] -> [a]

ciclica2 [] = []

ciclica2 xs = ys where ys = xs ++ ys

-- Comprobación de eficiencia

-- ghci> last (take 10000000 (ciclica1 [1,2]))

-- 2

-- (3.69 secs, 1521758928 bytes)

-- ghci> last (take 10000000 (ciclica2 [1,2]))

-- 2

-- (0.21 secs, 561468144 bytes)

-- La 2ª definición es más eficiente.

-- La propiedad es

prop_ciclica :: Int -> [Int] -> Property

prop_ciclica n xs =

not (null xs) ==>

take n (ciclica2 xs) == take n (cycle xs)

-- La comprobación es

-- ghci> quickCheckWith (stdArgs {maxSize=7}) prop_ciclica

-- +++ OK, passed 100 tests.

Elemento común en la menor posición

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

Enunciado

-- Definir la función
--    elemento :: Eq a => [a] -> [a] -> [a]
-- tal que (elemento xs ys) es la lista formada por el elemento común a
-- xs e ys con la menor posición. Por ejemplo.
--    elemento [3,7,6,9,8,0] [5,4,2,7,8,6,9]  ==  [7]
--    elemento [3,7,6,9] [9,5,6]              ==  [9]
--    elemento [5,3,6] [7,6,3]                ==  [3]
--    elemento [3,7,6,3,8,0] [5,4,9,1,4,2,1]  ==  []
--    elemento [2,3,5] [7,4]                  ==  []
--
-- Nota: Como se observa en el 3ª ejemplo, en el caso de que un elemento
-- x de xs pertenezca a ys y el elemento de ys en la misma posición que
-- x pertenezca a xs, se elige como el de menor posición el de xs.

-- Definir la función

-- elemento :: Eq a => [a] -> [a] -> [a]

-- tal que (elemento xs ys) es la lista formada por el elemento común a

-- xs e ys con la menor posición. Por ejemplo.

-- elemento [3,7,6,9,8,0] [5,4,2,7,8,6,9] == [7]

-- elemento [3,7,6,9] [9,5,6] == [9]

-- elemento [5,3,6] [7,6,3] == [3]

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

-- elemento [2,3,5] [7,4] == []

-- Nota: Como se observa en el 3ª ejemplo, en el caso de que un elemento

-- x de xs pertenezca a ys y el elemento de ys en la misma posición que

-- x pertenezca a xs, se elige como el de menor posición el de xs.

Soluciones

[schedule expon=’2014-12-01′ expat=»06:00″]

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

[/schedule]

[schedule on=’2014-12-01′ at=»06:00″]

import Test.QuickCheck

-- 1ª definición:
elemento1 :: Eq a => [a] -> [a] -> [a]
elemento1 p@(x:xs) q@(y:ys)
    | x `elem` q  = [x]
    | y `elem` xs = [y]
    | otherwise   = elemento1 xs ys
elemento1 _ _ = []

-- 2ª definición:
elemento2 :: Eq a => [a] -> [a] -> [a]
elemento2 [] _ = []
elemento2 (x:xs) ys
    | x `elem` ys = [x]
    | otherwise   = elemento2 ys xs

-- Propiedad de equivalencia de las definiciones
prop_elemento :: [Int] -> [Int] -> Bool
prop_elemento xs ys =
    elemento1 xs ys == elemento2 xs ys

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

import Test.QuickCheck

-- 1ª definición:

elemento1 :: Eq a => [a] -> [a] -> [a]

elemento1 p@(x:xs) q@(y:ys)

| x `elem` q = [x]

| y `elem` xs = [y]

| otherwise = elemento1 xs ys

elemento1 _ _ = []

-- 2ª definición:

elemento2 :: Eq a => [a] -> [a] -> [a]

elemento2 [] _ = []

elemento2 (x:xs) ys

| x `elem` ys = [x]

| otherwise = elemento2 ys xs

-- Propiedad de equivalencia de las definiciones

prop_elemento :: [Int] -> [Int] -> Bool

prop_elemento xs ys =

elemento1 xs ys == elemento2 xs ys

-- La comprobación es

-- ghci> quickCheck prop_elemento

-- +++ OK, passed 100 tests.

...

[/schedule]

Pequeño test de inteligencia

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

Enunciado

-- Recientemente se publicó en la Red un pequeño test de inteligencia
-- cuyo objetivo consistía en descubrir una función a partir de una
-- colección de ejemplos. Los ejemplos eran los siguientes
--    f 6  4 == 210
--    f 9  2 == 711
--    f 8  5 == 313
--    f 5  2 == 37
--    f 7  6 == 113
--    f 9  8 == 117
--    f 10 6 == 416
--    f 15 3 == 1218
--
-- Definir la función 
--    f :: Int -> Int -> Int
-- tal que f cubra los ejemplos anteriores y la definición de f sea lo
-- más corta posible (en número de palabras).

-- Recientemente se publicó en la Red un pequeño test de inteligencia

-- cuyo objetivo consistía en descubrir una función a partir de una

-- colección de ejemplos. Los ejemplos eran los siguientes

-- f 6 4 == 210

-- f 9 2 == 711

-- f 8 5 == 313

-- f 5 2 == 37

-- f 7 6 == 113

-- f 9 8 == 117

-- f 10 6 == 416

-- f 15 3 == 1218

-- Definir la función

-- f :: Int -> Int -> Int

-- tal que f cubra los ejemplos anteriores y la definición de f sea lo

-- más corta posible (en número de palabras).

Soluciones

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

Las soluciones se pueden escribir en los comentarios hasta el 25 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-25′ at=»06:00″]

f1 :: Int -> Int -> Int
f1 x y = read (show (x-y) ++ show (x+y))

1 2	f1 :: Int -> Int -> Int f1 x y = read (show (x-y) ++ show (x+y))

[/schedule]

Repetición de elementos

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

Enunciado

-- Definir la función
--    repiteElementos :: Int -> [a] -> [a]
-- tal que (repiteElementos k xs) es la lista obtenida repitiendo cada
-- elemento de xs k veces. Por ejemplo,
--    repiteElementos 3 [5,2,7,4]  ==  [5,5,5,2,2,2,7,7,7,4,4,4]
--
-- Comprobar con QuickCheck que, para todo número natural k y toda lista
-- xs, el número de elementos de (repiteElementos k xs) es k veces el
-- número de elementos de xs.
--
-- Nota. Al hacer la comprobación limitar el tamaño de las pruebas como
-- se indica a continuación
--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_repiteElementos
--    +++ OK, passed 100 tests.

-- Definir la función

-- repiteElementos :: Int -> [a] -> [a]

-- tal que (repiteElementos k xs) es la lista obtenida repitiendo cada

-- elemento de xs k veces. Por ejemplo,

-- repiteElementos 3 [5,2,7,4] == [5,5,5,2,2,2,7,7,7,4,4,4]

-- Comprobar con QuickCheck que, para todo número natural k y toda lista

-- xs, el número de elementos de (repiteElementos k xs) es k veces el

-- número de elementos de xs.

-- Nota. Al hacer la comprobación limitar el tamaño de las pruebas como

-- se indica a continuación

-- ghci> quickCheckWith (stdArgs {maxSize=7}) prop_repiteElementos

-- +++ OK, passed 100 tests.

Soluciones

import Test.QuickCheck

-- 1ª definición (por comprensión):
repiteElementos1 :: Int -> [a] -> [a]
repiteElementos1 k xs = concat [replicate k x | x <- xs]

-- 2ª definición (con map)
repiteElementos2 :: Int -> [a] -> [a]
repiteElementos2 k xs = concat (map (replicate k) xs)

-- 3ª definición (con concatMap):
repiteElementos3 :: Int -> [a] -> [a]
repiteElementos3 k = concatMap (replicate k)

-- 4ª definición (por recursión):
repiteElementos4 :: Int -> [a] -> [a]
repiteElementos4 k [] = []
repiteElementos4 k (x:xs) = replicate k x ++ repiteElementos4 k xs

-- 5ª definición (por plegado):
repiteElementos5 :: Int -> [a] -> [a]
repiteElementos5 k = foldr ((++) . replicate k) []

-- Propiedad de equivalencia
prop_equivalencia :: Int -> [Int] -> Bool
prop_equivalencia k xs =
    repiteElementos2 k xs == ys &&
    repiteElementos3 k xs == ys &&
    repiteElementos4 k xs == ys &&
    repiteElementos5 k xs == ys 
    where ys = repiteElementos1 k xs

-- Su comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=10}) prop_equivalencia
--    +++ OK, passed 100 tests.

-- La propiedad es
prop_repiteElementos :: Int -> [Int] -> Property
prop_repiteElementos k xs =
    k >= 0 ==> length (repiteElementos1 k xs) == k * length xs 

-- La comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_repiteElementos
--    +++ OK, passed 100 tests.

import Test.QuickCheck

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

repiteElementos1 :: Int -> [a] -> [a]

repiteElementos1 k xs = concat [replicate k x | x <- xs]

-- 2ª definición (con map)

repiteElementos2 :: Int -> [a] -> [a]

repiteElementos2 k xs = concat (map (replicate k) xs)

-- 3ª definición (con concatMap):

repiteElementos3 :: Int -> [a] -> [a]

repiteElementos3 k = concatMap (replicate k)

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

repiteElementos4 :: Int -> [a] -> [a]

repiteElementos4 k [] = []

repiteElementos4 k (x:xs) = replicate k x ++ repiteElementos4 k xs

-- 5ª definición (por plegado):

repiteElementos5 :: Int -> [a] -> [a]

repiteElementos5 k = foldr ((++) . replicate k) []

-- Propiedad de equivalencia

prop_equivalencia :: Int -> [Int] -> Bool

prop_equivalencia k xs =

repiteElementos2 k xs == ys &&

repiteElementos3 k xs == ys &&

repiteElementos4 k xs == ys &&

repiteElementos5 k xs == ys

where ys = repiteElementos1 k xs

-- Su comprobación es

-- ghci> quickCheckWith (stdArgs {maxSize=10}) prop_equivalencia

-- +++ OK, passed 100 tests.

-- La propiedad es

prop_repiteElementos :: Int -> [Int] -> Property

prop_repiteElementos k xs =

k >= 0 ==> length (repiteElementos1 k xs) == k * length xs

-- La comprobación es

-- ghci> quickCheckWith (stdArgs {maxSize=7}) prop_repiteElementos

-- +++ OK, passed 100 tests.

Precio total

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

Enunciado

-- Una función de precio determina el precio de cada elemento; por
-- ejemplo,
--    precioCI :: String -> Int
--    precioCI "leche"       = 10
--    precioCI "mantequilla" = 18
--    precioCI "patatas"     = 22
--    precioCI "chocolate"   = 16
-- 
-- Definir la función
--    precioTotal :: (String -> Int) -> [String] -> Int
-- tal que (precioTotal f xs) es el precio total de los elementos de xs
-- respecto de la función de precio f. Por ejemplo,
--    precioTotal precioCI ["leche", "leche", "mantequilla"]  ==  38
--    precioTotal precioCI ["chocolate", "mantequilla"]       ==  34

-- Una función de precio determina el precio de cada elemento; por

-- ejemplo,

-- precioCI :: String -> Int

-- precioCI "leche" = 10

-- precioCI "mantequilla" = 18

-- precioCI "patatas" = 22

-- precioCI "chocolate" = 16

-- Definir la función

-- precioTotal :: (String -> Int) -> [String] -> Int

-- tal que (precioTotal f xs) es el precio total de los elementos de xs

-- respecto de la función de precio f. Por ejemplo,

-- precioTotal precioCI ["leche", "leche", "mantequilla"] == 38

-- precioTotal precioCI ["chocolate", "mantequilla"] == 34

Soluciones

-- 1ª solución (por comprensión):
precioTotal1 :: (String -> Int) -> [String] -> Int
precioTotal1 f xs = sum [precioCI x | x <- xs]

-- 2ª solución (por recursión):
precioTotal2 :: (String -> Int) -> [String] -> Int
precioTotal2 f []     = 0
precioTotal2 f (x:xs) = f x + precioTotal2 f xs

-- 3ª solución (por plegado)
precioTotal3 :: (String -> Int) -> [String] -> Int
precioTotal3 f = foldr g 0
    where g x y = f x + y

-- 4ª solución (por plegado y lambda)
precioTotal4 :: (String -> Int) -> [String] -> Int
precioTotal4 f = foldr (\x y -> f x + y) 0

-- 5ª solución (por plegado y composición)
precioTotal5 :: (String -> Int) -> [String] -> Int
precioTotal5 f = foldr ((+) . f) 0

-- 1ª solución (por comprensión):

precioTotal1 :: (String -> Int) -> [String] -> Int

precioTotal1 f xs = sum [precioCI x | x <- xs]

-- 2ª solución (por recursión):

precioTotal2 :: (String -> Int) -> [String] -> Int

precioTotal2 f [] = 0

precioTotal2 f (x:xs) = f x + precioTotal2 f xs

-- 3ª solución (por plegado)

precioTotal3 :: (String -> Int) -> [String] -> Int

precioTotal3 f = foldr g 0

where g x y = f x + y

-- 4ª solución (por plegado y lambda)

precioTotal4 :: (String -> Int) -> [String] -> Int

precioTotal4 f = foldr (\x y -> f x + y) 0

-- 5ª solución (por plegado y composición)

precioTotal5 :: (String -> Int) -> [String] -> Int

precioTotal5 f = foldr ((+) . f) 0

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

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Excercitium

Soluciones

Enunciado

Soluciones

Exercitium

Soluciones

Soluciones

Soluciones

Soluciones

Enunciado

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Enunciado

Soluciones

Soluciones

Introducción

Enunciado

Soluciones

Enunciado

Soluciones

Enunciado

Soluciones

Enunciado

Soluciones

Referencias

Enunciado

Soluciones

Enunciado

Soluciones

Enunciado

Soluciones

Enunciado

Soluciones

Enunciado

Soluciones

Enunciado

Soluciones

Enunciado

Soluciones

Enunciado

Soluciones

Entradas recientes

Buscar

Correo electrónico