Recursión

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!

Expresiones vectoriales

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

Enunciado

-- El siguiente tipo de dato define representa las expresiones
-- vectoriales formadas por un vector, la suma de dos expresiones
-- vectoriales o el producto de un entero por una expresión vectorial. 
--    data ExpV = Vec Int Int
--              | Sum ExpV ExpV
--              | Mul Int ExpV
--              deriving Show
-- 
-- Definir la función 
--    valor :: ExpV -> (Int,Int)
-- tal que (valor e) es el valor de la expresión vectorial c. Por
-- ejemplo, 
--    valor (Vec 1 2)                                  ==  (1,2)
--    valor (Sum (Vec 1 2 ) (Vec 3 4))                 ==  (4,6)
--    valor (Mul 2 (Vec 3 4))                          ==  (6,8)
--    valor (Mul 2 (Sum (Vec 1 2 ) (Vec 3 4)))         ==  (8,12)
--    valor (Sum (Mul 2 (Vec 1 2)) (Mul 2 (Vec 3 4)))  ==  (8,12)

-- El siguiente tipo de dato define representa las expresiones

-- vectoriales formadas por un vector, la suma de dos expresiones

-- vectoriales o el producto de un entero por una expresión vectorial.

-- data ExpV = Vec Int Int

-- | Sum ExpV ExpV

-- | Mul Int ExpV

-- deriving Show

-- Definir la función

-- valor :: ExpV -> (Int,Int)

-- tal que (valor e) es el valor de la expresión vectorial c. Por

-- ejemplo,

-- valor (Vec 1 2) == (1,2)

-- valor (Sum (Vec 1 2 ) (Vec 3 4)) == (4,6)

-- valor (Mul 2 (Vec 3 4)) == (6,8)

-- valor (Mul 2 (Sum (Vec 1 2 ) (Vec 3 4))) == (8,12)

-- valor (Sum (Mul 2 (Vec 1 2)) (Mul 2 (Vec 3 4))) == (8,12)

data ExpV = Vec Int Int
          | Sum ExpV ExpV
          | Mul Int ExpV
          deriving Show

-- 1ª solución
-- ===========
valor :: ExpV -> (Int,Int)
valor (Vec x y)   = (x,y)
valor (Sum e1 e2) = (x1+x2,y1+y2) where (x1,y1) = valor e1  
                                        (x2,y2) = valor e2  
valor (Mul n e)   = (n*x,n*y) where (x,y) = valor e  

-- 2ª solución
-- ===========
valor2 :: ExpV -> (Int,Int)
valor2 (Vec a b)   = (a, b)
valor2 (Sum e1 e2) = suma (valor2 e1) (valor2 e2)
valor2 (Mul n e1)  = multiplica n (valor2 e1)

suma :: (Int,Int) -> (Int,Int) -> (Int,Int)
suma (a,b) (c,d) = (a+c,b+d)

multiplica :: Int -> (Int, Int) -> (Int, Int)
multiplica n (a,b) = (n*a,n*b)

data ExpV = Vec Int Int

| Sum ExpV ExpV

| Mul Int ExpV

deriving Show

-- 1ª solución

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

valor :: ExpV -> (Int,Int)

valor (Vec x y) = (x,y)

valor (Sum e1 e2) = (x1+x2,y1+y2) where (x1,y1) = valor e1

(x2,y2) = valor e2

valor (Mul n e) = (n*x,n*y) where (x,y) = valor e

-- 2ª solución

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

valor2 :: ExpV -> (Int,Int)

valor2 (Vec a b) = (a, b)

valor2 (Sum e1 e2) = suma (valor2 e1) (valor2 e2)

valor2 (Mul n e1) = multiplica n (valor2 e1)

suma :: (Int,Int) -> (Int,Int) -> (Int,Int)

suma (a,b) (c,d) = (a+c,b+d)

multiplica :: Int -> (Int, Int) -> (Int, Int)

multiplica n (a,b) = (n*a,n*b)

Expresiones aritmética normalizadas

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

Enunciado

-- El siguiente tipo de dato representa expresiones construidas con
-- variables, sumas y productos
--    data Expr = V String
--              | S Expr Expr
--              | P Expr Expr
-- Por ejemplo, x*(y+z) se representa por (P (V "x") (S (V "y") (V "z"))) 
-- 
-- Una expresión es un término si es un producto de variables. Por
-- ejemplo, x*(y*z) es un término pero x+(y*z) ni x*(y+z) lo son.
--
-- Una expresión está en forma normal si es una suma de términos. Por
-- ejemplo, x*(y*z) y x+(y*z) está en forma normal; pero x*(y+z) y
-- (x+y)*(x+z) no lo están. 
-- 
-- Definir las funciones 
--    esTermino, esNormal :: Expr -> Bool
-- tales que
-- + (esTermino a) se verifica si a es un término. Por ejemplo,
--      esTermino (V "x")                                    == True
--      esTermino (P (V "x") (P (V "y") (V "z")))            == True
--      esTermino (P (V "x") (S (V "y") (V "z")))            == False
--      esTermino (S (V "x") (P (V "y") (V "z")))            == False
-- + (esNormal a) se verifica si a está en forma normal. Por ejemplo,
--      esNormal (V "x")                                     == True
--      esNormal (P (V "x") (P (V "y") (V "z")))             == True
--      esNormal (S (V "x") (P (V "y") (V "z")))             == True
--      esNormal (P (V "x") (S (V "y") (V "z")))             == False
--      esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False

-- El siguiente tipo de dato representa expresiones construidas con

-- variables, sumas y productos

-- data Expr = V String

-- | S Expr Expr

-- | P Expr Expr

-- Por ejemplo, x*(y+z) se representa por (P (V "x") (S (V "y") (V "z")))

-- Una expresión es un término si es un producto de variables. Por

-- ejemplo, x*(y*z) es un término pero x+(y*z) ni x*(y+z) lo son.

-- Una expresión está en forma normal si es una suma de términos. Por

-- ejemplo, x*(y*z) y x+(y*z) está en forma normal; pero x*(y+z) y

-- (x+y)*(x+z) no lo están.

-- Definir las funciones

-- esTermino, esNormal :: Expr -> Bool

-- tales que

-- + (esTermino a) se verifica si a es un término. Por ejemplo,

-- esTermino (V "x") == True

-- esTermino (P (V "x") (P (V "y") (V "z"))) == True

-- esTermino (P (V "x") (S (V "y") (V "z"))) == False

-- esTermino (S (V "x") (P (V "y") (V "z"))) == False

-- + (esNormal a) se verifica si a está en forma normal. Por ejemplo,

-- esNormal (V "x") == True

-- esNormal (P (V "x") (P (V "y") (V "z"))) == True

-- esNormal (S (V "x") (P (V "y") (V "z"))) == True

-- esNormal (P (V "x") (S (V "y") (V "z"))) == False

-- esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False

Soluciones

data Expr = V String
          | S Expr Expr
          | P Expr Expr

esTermino :: Expr -> Bool
esTermino (V _)   = True
esTermino (S _ _) = False
esTermino (P a b) = esTermino a && esTermino b

esNormal :: Expr -> Bool
esNormal (S a b) = esNormal a && esNormal b
esNormal a       = esTermino a

data Expr = V String

| S Expr Expr

| P Expr Expr

esTermino :: Expr -> Bool

esTermino (V _) = True

esTermino (S _ _) = False

esTermino (P a b) = esTermino a && esTermino b

esNormal :: Expr -> Bool

esNormal (S a b) = esNormal a && esNormal b

esNormal a = esTermino a

Particiones de longitud fija

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

Enunciado

-- Definir la función 
--    particionesFijas :: Int -> Int -> [[Int]]
-- tal que (particionesFijas n k) es la lista de listas de k números
-- naturales no crecientes cuya suma es n. Por ejemplo,
--    ghci> particionesFijas 8 3
--    [[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]]

-- Definir la función

-- particionesFijas :: Int -> Int -> [[Int]]

-- tal que (particionesFijas n k) es la lista de listas de k números

-- naturales no crecientes cuya suma es n. Por ejemplo,

-- ghci> particionesFijas 8 3

-- [[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]]

Soluciones

-- 1ª definición
particionesFijas :: Int -> Int -> [[Int]]
particionesFijas n 1 = [[n]]
particionesFijas n k 
    | k < 1     = []
    | otherwise = [x:y:ys | x <- [1..n-1], 
                            (y:ys) <- particionesFijas (n-x) (k-1),
                            x >= y]

-- 2ª definición
particionesFijas2 :: Int -> Int -> [[Int]]
particionesFijas2 n k
    | k <= 0    = []
    | k == 1    = [[n]]
    | k == n    = [replicate k 1]
    | k > n     = []
    | otherwise = [xs ++ [1] | xs <- particionesFijas2 (n-1) (k-1)] ++
                  [[x+1 | x <- xs] | xs <- particionesFijas2 (n-k) k]

-- Comparación:
--    ghci> length (particionesFijas 800 3)
--    53333
--    (1.01 secs, 97696476 bytes)
--    
--    ghci> length (particionesFijas2 800 3)
--    53333
--    (4.52 secs, 693969028 bytes)

-- 1ª definición

particionesFijas :: Int -> Int -> [[Int]]

particionesFijas n 1 = [[n]]

particionesFijas n k

| k < 1 = []

| otherwise = [x:y:ys | x <- [1..n-1],

(y:ys) <- particionesFijas (n-x) (k-1),

x >= y]

-- 2ª definición

particionesFijas2 :: Int -> Int -> [[Int]]

particionesFijas2 n k

| k <= 0 = []

| k == 1 = [[n]]

| k == n = [replicate k 1]

| k > n = []

| otherwise = [xs ++ [1] | xs <- particionesFijas2 (n-1) (k-1)] ++

[[x+1 | x <- xs] | xs <- particionesFijas2 (n-k) k]

-- Comparación:

-- ghci> length (particionesFijas 800 3)

-- 53333

-- (1.01 secs, 97696476 bytes)

-- ghci> length (particionesFijas2 800 3)

-- 53333

-- (4.52 secs, 693969028 bytes)

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]

Cuantificadores sobre listas

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

Enunciado

-- Definir la función 
--    verificaP :: (a -> Bool) -> [[a]] -> Bool
-- tal que (verificaP p xs) se verifica si cada elemento de la lista xss
-- contiene algún elemento que cumple el predicado p. Por ejemplo,
--    verificaP odd [[1,3,4,2], [4,5], [9]] == True
--    verificaP odd [[1,3,4,2], [4,8], [9]] == False

-- Definir la función

-- verificaP :: (a -> Bool) -> [[a]] -> Bool

-- tal que (verificaP p xs) se verifica si cada elemento de la lista xss

-- contiene algún elemento que cumple el predicado p. Por ejemplo,

-- verificaP odd [[1,3,4,2], [4,5], [9]] == True

-- verificaP odd [[1,3,4,2], [4,8], [9]] == False

Soluciones

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

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

-- 1ª definición (por comprensión):
verificaP :: (a -> Bool) -> [[a]] -> Bool
verificaP p xss = and [any p xs | xs <- xss]

-- 2ª definición (por recursión):
verificaP2 :: (a -> Bool) -> [[a]] -> Bool
verificaP2 p []       = True
verificaP2 p (xs:xss) = any p xs && verificaP2 p xss

-- 3ª definición (por plegado):
verificaP3 :: (a -> Bool) -> [[a]] -> Bool
verificaP3 p = foldr ((&&) . any p) True

-- 4ª definición (con cuantificadores)
verificaP4 :: (a -> Bool) -> [[a]] -> Bool
verificaP4 p = all (any p)

-- 5ª definición (con cuantificadores y composición)
verificaP5 :: (a -> Bool) -> [[a]] -> Bool
verificaP5 = all . any

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

verificaP :: (a -> Bool) -> [[a]] -> Bool

verificaP p xss = and [any p xs | xs <- xss]

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

verificaP2 :: (a -> Bool) -> [[a]] -> Bool

verificaP2 p [] = True

verificaP2 p (xs:xss) = any p xs && verificaP2 p xss

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

verificaP3 :: (a -> Bool) -> [[a]] -> Bool

verificaP3 p = foldr ((&&) . any p) True

-- 4ª definición (con cuantificadores)

verificaP4 :: (a -> Bool) -> [[a]] -> Bool

verificaP4 p = all (any p)

-- 5ª definición (con cuantificadores y composición)

verificaP5 :: (a -> Bool) -> [[a]] -> Bool

verificaP5 = all . any

[/schedule]

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]

Expresiones vectoriales

Enunciado

Expresiones aritmética normalizadas

Enunciado

Soluciones

Particiones de longitud fija

Enunciado

Soluciones

Evaluación de árboles de expresiones aritméticas

Enunciado

Soluciones

Aplicaciones alternativas

Enunciado

Soluciones

Repetición cíclica

Enunciado

Soluciones

Elemento común en la menor posición

Enunciado

Soluciones

Cuantificadores sobre listas

Enunciado

Soluciones

Inversa a trozos

Enunciado

Soluciones

Entradas recientes

Buscar

Correo electrónico