1. Haskell. Escribe una función que permita determinar si una cadena de caracteres está bien
balanceada o equilibrada en lo que se refiere a los paréntesis, corchetes y llaves que contiene. El
resto de caracteres no interesan. Por ejemplo la cadena “v(hg(jij)hags{ss[dd]dd})” está
balanceada pero no así la cadena “ff(h([sds)sds]ss)hags”.
Para ello, se utilizará una pila en la que cada vez que aparezca un signo de apertura, se
introduce en la pila y cada vez que aparece un signo de cierre se extrae la cima de la pila y se
comprueba que corresponde al signo de apertura correspondiente. Si al finalizar de recorrer la
cadena la pila está vacía entonces la expresión está equilibrada.
module WellBalanced where
import DataStructures.Stack.LinearStack
wellBalanced :: String -> Bool
wellBalanced xs = wellBalanced' xs S.empty
wellBalanced' :: String -> Stack Char -> Bool
wellBalanced' [] s = isEmpty s
wellBalanced' (x:xs) s ...
*WellBalanced > wellBalanced "vv(hg(jij)hags{ss[dd]dd})"
True
module WellBalanced where
import DataStructures.Stack.LinearStack
wellBalanced :: String -> Bool
wellBalanced xs = wellBalanced' xs empty
wellBalanced' :: String -> Stack Char -> Bool
wellBalanced' [] s = True
wellBalanced' (x:xs) s
| isOpen x = wellBalanced' xs (push x s)
| isClosed x = if (match (top s) x) then wellBalanced' xs (pop s) else wellBalanced' (xs) s
| otherwise = wellBalanced' (xs) s
isOpen x = elem x "([{"
isClosed x = elem x ")]}"
match '(' ')' = True
match '[' ']' = True
match '{' '}' = True
match _ _ = False
11. Haskell. Un saco (o multiconjunto) es parecido a un conjunto salvo que un elemento puede estar
incluido varias veces. Por ejemplo, {‘b’, ‘a’, ‘d’, ‘d’, ‘a’, ‘c’ , b’, ‘a’} es un saco que
incluye tres ocurrencias del carácter ‘a’ , dos ocurrencias del ‘b’, una del ‘c’ y dos del ‘d’.
a) Implementa sacos en Haskell usando el siguiente tipo de datos:
data Bag a = Empty | Node a Int (Bag a)
de forma que en cada nodo aparece, además del saco restante, cada elemento junto con
su contador de ocurrencias, o sea, el número de veces que aparece. Para agilizar
las operaciones de inserción y borrado en un Bag, interesa que los nodos estén ordenados
atendiendo al orden de los elementos a incluir. Además, no deben aparecer elementos con
contador nulo (o negativo). Por ejemplo, el saco anterior se representa por:
Node ‘a’ 3 (Node ‘b’ 2 (Node ‘c’ 1 (Node ‘d’ 2 Empty)))
La implementación debe incluir las siguientes funciones:
empty :: Bag a -- Devuelve un saco vacío
isEmpty :: Bag a -> Bool -- Comprueba si un saco está vacío
insert :: (Ord a) => a -> Bag a -> Bag a --Inserta una nueva ocurrencia
occurrences :: (Ord a) => a -> Bag a -> Int -- Devuelve el número de
-- ocurrencias de un elemento en un saco (0 si el elemento no está) -}
delete :: (Ord a) => a -> Bag a -> Bag a -- Borra una ocurrencia de un
-- elemento de un saco. Devuelve el mismo saco si el elemento no estaba incluido
b) Proporciona una especificación de Bag definiendo sus axiomas para las diferentes
operaciones y comprueba la implementación realizada con QuickCheck. Para ello,
incluye en el módulo la siguiente instancia para generar sacos aleatorios:
instance (Ord a, Arbitrary a) => Arbitrary (Bag a) where arbitrary = do
xs <- listOf arbitrary return (foldr insert empty xs)
c) Añade al módulo las siguientes funciones para manipular sacos: unión, intersección,
diferencia y una función que determine si un saco está contenido en otro. Estas
funciones son semejantes a las de los conjuntos pero teniendo en cuenta las
ocurrencias de cada elemento.
d) Analiza la complejidad de las diferentes operaciones y justifica las ventajas de
mantener los elementos ordenados.
module Bag
( Bag
, empty
, isEmpty
, insert
, delete
, occurrences
) where
import Test.QuickCheck
----------------
--- a)
----------------
data Bag a = Empty | Node a Int (Bag a) deriving Eq --Node tiene 3 argumentos: a, n (entero) y la bolsa
-- no deben aparecer nodos con el contador a cero.
-- es decir, los eliminamos
-- mantenemos los objetos ordenados
-- imponemos una relación de orden al tipo base.
-- esto permitirá comparar dos sacos: igualdad, pertenencia, etc.
empty :: Bag a
empty = Empty
isEmpty :: Bag a -> Bool
isEmpty Empty = True
isEmpty (Node a n s) = False
--'a' -> Empty
--'c' -> Nodo 'a' 1 Empty
--'a' -> Nodo 'a' 1 (Nodo 'c' 1 Empty)
--'c' -> Nodo 'a' 1 (Nodo 'c' 2 Empty)
-- Nodo 'a' 2 (Nodo 'c' 2 Empty)
--Las bolsas se expresan: Nodo 'a' 3 (Nodo 'c' 5 (Nodo 'd' 1 Empty) = 'a' aparece 3 veces, 'c' 5 veces y 'd' 1 vez
-- (a 3):((c 5):((d 2) : [ ])) = ':' es nodo y [ ] es Empty
insert :: (Ord a) => a -> Bag a -> Bag a
-- Inserta una nueva ocurrencia en un saco
-- pedimos Ord para mantener el orden
insert x Empty = Node x 1 Empty
insert x (Node y oy s) | x < y = Node x 1 (Node y oy s)
| x == y = Node y (oy+1) s
| x > y = Node y oy (insert x s)
occurrences :: (Ord a) => a -> Bag a -> Int
-- Devuelve el número de ocurrencias de un elemento en un saco
-- 0 si el elemento no está
occurrences x Empty = 0
occurrences x (Node y oy s) | x ==y = oy
| x < y = 0
| x > y = occurrences x s
delete :: (Ord a) => a -> Bag a -> Bag a
-- Borra una ocurrencia de un elemento de un saco.
-- Devuelve el mismo saco si el elemento no estaba incluido
delete x Empty = Empty
delete x (Node y oy s) | x == y = Node y (oy-1) s
| x < y = Node y oy s
| x > y = Node y oy (delete x s)
instance (Show a) => Show (Bag a) where
show s = "Bag { " ++ show' s
where
show' Empty = "}"
show' (Node x ox s) = muestra x ox ++ show' s
muestra x 0 = ""
muestra x ox = show x ++ ' ':muestra x (ox-1)
----------------
--- b) Proporcionar una especificación de sacos definiendo sus axiomas
-- para las diferentes operaciones y comprobar la implementación
-- realizada con QuickCheck.
----------------
instance (Ord a, Arbitrary a) => Arbitrary (Bag a) where
arbitrary = do
xs <- listOf arbitrary
return (foldr insert empty xs)
-- Sobre insertar
ax1 x y s = insert x(insert y s) == insert y(insert x s)
-- Sobre ocurrences
ax2 x = empty
ax3 x y s | x==y = occurrences x (insert y s) == 1 + occurrences x s
| x/=y = occurrences x (insert y s) == occurrences x s
-- Sobre delete
ax4 x = empty
ax5 x s = delete x (insert x s) == s
ax6 x y s = x /= y ==> (delete x (insert y s) == insert y (delete x s))
-- Sobre isEmpty
ax7 = isEmpty empty
ax8 x s = isEmpty (insert x s) == False
{- Si no tipificamos, solo genera pruebas con 'data () = ()'
*Bag> quickCheck ax6
*** Gave up! Passed only 0 tests.
*Bag> quickCheck (ax6 :: Char -> Char -> Bag Char -> Property)
+++ OK, passed 100 tests.
*Bag> quickCheck (ax6 (12::Integer))
+++ OK, passed 100 tests.
*Bag> quickCheck (ax6 'a')
+++ OK, passed 100 tests.
*Bag> quickCheck (ax5 'a')
+++ OK, passed 100 tests.
*Bag> quickCheck (ax5 True)
+++ OK, passed 100 tests.
-}
----------------
-- c) Añadir al módulo las siguientes funciones para manipular sacos:
-- unión, intersección, diferencia y una función que determine si un saco
-- está contenido en otro.
-- Estas funciones son semejantes a las de conjunto pero teniendo
-- en cuenta las ocurrencias de cada elemento.
----------------
union :: Ord a => Bag a -> Bag a -> Bag a
-- queda curioso la unión al estilo de merge
union s Empty = s
union Empty t = t
union (Node x ox s) (Node y oy t)
|x<y = (Node x ox (Node y oy (union s t)))
|x>y = (Node y oy (Node x ox (union s t)))
|x==y = Node x (ox + oy) (union s t)
intersection :: Ord a => Bag a -> Bag a -> Bag a
intersection s Empty = Empty
intersection Empty t = Empty
intersection (Node x ox s) (Node y oy t)
| x == y = Node x (ox+oy) (intersection s t)
| x < y = intersection s (Node y oy t)
| x > y = intersection (Node x ox s) t
difference :: Ord a => Bag a -> Bag a -> Bag a
difference s Empty = s
difference Empty t = Empty
difference (Node x ox s) (Node y oy t)
| x == y = difference s t
| x < y = Node x ox (difference s (Node y oy t))
| x > y = difference (Node x ox s) t
inBag :: Ord a => Bag a -> Bag a -> Bool
inBag Empty t = True
inBag t Empty = False
inBag (Node x ox s) (Node y oy t)
| x==y = inBag s t
| x < y = False
| x > y = inBag (Node x ox s) t
-- Ejercicio: Encontrar axiomas para estas operaciones
-- union
ax_union1 s t = union s t == union t s
-- quickCheck (ax_union1 saco1)
-- union e insert
ax_union2 x s t = union (insert x s) t == union (insert x t) s
-- quickCheck (ax_union2 3)
-- intersection
ax_intersection1 s t = intersection s t == intersection t s
-- intersection y delete
ax_intersection2 x s t = occurrences x s == occurrences x t ==>
intersection(delete x s) (delete x t) == intersection(delete x t)
(delete x s)
--
-- difference y empty
ax_difference1 s = difference s s == Empty
-- quickCheck (ax_difference1 :: Set Integer -> Bool)
-- difference, insert y empty
ax_difference3 x s = difference s (insert x s) == Empty
-- quickCheck (ax_difference3 :: Int -> Bag Int -> Bool)
-- difference e insert
ax_difference4 x s t = difference t (insert x s) == difference (insert x t) s
-- quickCheck (ax_difference4 :: Int -> Bag Int -> Bag Int -> Bool)
-- otra propiedad de los conjuntos que es falsa para Bag
-- difference y union
ax_difference2 s t u = difference (union s t) u == union (difference s u) (difference t u)
-- quickCheck (ax_difference2 :: Bag Int -> Bag Int -> Bag Int -> Bool)
-- ATENCION: falla la distributiva
ax_uni_inter1 s t u = intersection (union s t) u ==
union (intersection s u) (intersection t u)
-- *Bag> quickCheck (ax_uni_inter1)
-- *** Failed! Falsifiable (after 4 tests):
-- Bag { () () }
-- Bag { () }
-- Bag { () }
------------
-- d) Analizad la complejidad de las diferentes operaciones
-- y justificar las ventajas de mantener los elementos ordenados.
------------
--- Otras funciones
cardinal :: Ord a => Bag a -> Int
cardinal Empty = 0
cardinal (Node x ox s) = ox + cardinal s
foldBag :: ( a -> Int -> b -> b) -> b -> Bag a -> b
foldBag f z Empty = z
foldBag f z (Node x ox s) = f x ox (foldBag f z s)
elemBag y = foldBag esta False
where esta x ox b = x==y && b
sumBag = foldBag sum3 0
where sum3 x ox z = x*(fromIntegral ox) + z
cardinal' = foldBag (const (+) ) 0
-- Las ventajas de tener los elementos ordenados es que permite que se puede operar
--con las bolsas de una forma más rápida y además las funciones necesitan menos casos base.
--------------------------------------------------------------------------------
Demas ejercicios de las relaciones de otros años
--------------------------------------------------------------------------------
1. Consideremos la función:
dosVeces :: (Integer -> Integer) -> Integer -> Integer
dos Veces f x = f (f x)
a) ¿Cuál es el tipo de la función: fun = dosVeces (+1)?
fun :: Integer -> Integer
b) Escribe una λ-expresión equivalente a la función fun
fun’ :: Integer -> Integer
fun’ = λx -> x + 2
c) Escribe una sección equivalente a la función fun
fun'’ :: Integer -> Integer
fun’’ = (+2)
2. Escribe una función derivada que devuelva la derivada de una función de reales en reales
usando la aproximación:
Por ejemplo:
coseno :: Float -> Float
coseno= derivada sin
MAIN> derivada sqrt 1.0
> 0.499487 :: Float
MAIN> coseno 0.0
> 1.0 :: Float
¿Cuál es el tipo de la función derivada?
derivada :: (Float -> Float) -> Float -> Float
derivada f x = (f (x + epsilon) – f x) / épsilon
where
epsilon = 1e - 4
3. ¿Cuáles son los tipos polimórficos de las siguientes funciones?
swap (x, y) = (y, x) (a,b) -> (b,a)
const x y = x a -> b -> a
subst f g x = f x (g x) (a -> b -> c) -> (a -> b) -> a -> c
pair (f,g) x = (f x, g x) (a -> b, a -> c) -> a -> (b, c)
cross (f,g) (x,y) = (f x, g y) (a -> b, c -> d) -> (a, c) -> (b, d)
comp f g x = f (g x) (a -> b) -> (c -> a) -> c -> b
fix f = f (fix f) (a -> a) -> a
4. ¿Qué hace el siguiente operador?
infixr 0 >$>
(>$>) :: (a -> a) -> a -> a
f >$> x = f (f x)
Aplica la función dos veces
¿Por qué su tipo no es (>$>) :: (a -> b) -> a -> b?
La función f debe devolver un parámetro del mismo tipo que su parámetro de entrada
porque el resultado de aplicar la primera vez la función será el parámetro de entrada
en la segunda aplicación de la función
5. Define el operador (>$>) del ejercicio anterior usando la composición de funciones (.)
infixr 0 >$>
(>$>) :: (a->a) -> a -> a
(>$>) f = f . f
6. Consideremos el siguiente operador:
infixl 9 >.>f >.> g = λ x -> g (f x)
¿Cuál es su tipo polimórfico)
(a -> b) -> (b -> c) -> a -> c
¿Qué hace la siguiente función?
fun :: Integer -> Integer
fun = (+2) >.> (*2) >.> (+1)
Debido a la asociación a la izquierda del operador, sería como tener ((+2) >.>
(*2)) >.> (+1). Dado un número natural, primero le suma 2, luego lo multiplica por 2, y
luego le suma 1.
7. La función predefinida reverse invierte el orden de los elementos de una lista. Por ejemplo
MAIN> reverse [1,2,3]
[3,2,1] :: Integer
Defínela y da su tipo polimórfico. ¿Cuál es el tipo de la función palíndromo xs = (reverse xs ==
xs)?
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
palíndromo :: [a] -> Bool
palíndromo xs = (reverse xs == xs)
8. ¿Cuál es el tipo polimórfico de la función twice?
twice f x = f (f x)
twice :: (a -> a) -> a -> a
¿Cuál es el valor de cada una de las siguintes expresiones?
twice (+1) 0 2
twice twice (+1) 0 4
Demostración:
twice (+1) 0 -- f = (+1) ; x = 0
=> definición de twice
(+1) ( (+1) 0 )
=> definición de la función (+1) (la más interna, pues es la única aplicable)
(+1) 1
=> definición de la función (+1)
2
twice twice (+1) 0 -- f = twice (+1) ; x = 0
=> definición de twice (en el rédex más externo)
twice (+1) (twice (+1) 0)
=> definición de twice (en el twice más interno)
twice (+1) ( (+1) ( (+1) 0 ))
=> definición de la función (+1) (la más interna, pues es la única aplicable)
twice (+1) ( (+1) 1 )
=> definición de la función (+1) (la más interna, pues es la única aplicable)
twice (+1) 2
=> definición de la función twice
(+1) ( (+1) 2 )
=> definición de la función (+1) (la más interna, pues es la única aplicable)
(+1) 3
=> definición de la función (+1)
4
9 La función predefinida zip empareja dos listas. Por ejemplo
? zip [1, 2, 3] [4, 5, 6]
[(1, 4), (2, 5), (3, 6)] :: [(Integer , Integer )]
? zip [1, 2, 3] [True, False]
[(1,True), (2, False)] :: [(Integer ,Bool )]
? zip [True, False] [1, 2, 3]
[(True, 1), (False, 2)] :: [(Bool , Integer )]
Defínela y da su tipo polimórfico
zip :: [a] -> [b] -> [(a,b)]
zip' (x:xs) (y:ys) = (x,y) : zip' xs ys
zip' _ _ = []
10. ¿Cuál es el tipo de las siguientes expresiones (en caso de que sean correctas)?
not . even Int -> Bool (Bool -> Bool) -> (Int -> Bool)
even . not Incorrecto, ya que la función not produce un Booleano y
la función even necesita como entrada un número
chr . ord Char -> Char (Int -> Char) -> (Char -> Int)
ord . chr Int -> Int (Char -> Int) -> (Int -> Char)
ord . chr . (+1) Int -> Int (Char -> Int) -> ( (Int -> Char) -> (Int -> Int) )
map not [Bool] -> [Bool]
map (λ x -> not x ) [Bool] -> [Bool]
map (not . even) [Int] -> [Bool]
map not [True, False] [Bool]
map ord [Char] -> [Int]
map (+1) [a] -> [a], donde a es un número
map (map (+1)) [[a]] -> [[a]], donde a es un número
map (++[1]) [[a]] -> [[a]]
map (1 :) [[a]] -> [[a]]
Cuál es el valor de la expresión map (map (+1)) [[1, 2, 3], [10, 11]]?
[[2,3,4], [10,11]]
map (map (+1)) ([1,2,3] : [[10,11]]) = map (+1) [1,2,3] : map (map (+1)) [[10,11]]
Primera parte:
map (+1) [1,2,3] = [2,3,4]
Segunda parte:
map (map (+1)) ([10,11] : []) = map (+1) [10,11] : map (map (+1)) []
Primera parte:
map (+1) [10,11] = [11,12]
Segunda parte:
map (map (+1)) [] = []
Uniendo todo, resulta:
[2,3,4] : [11.12] : [] = [[2,3,4], [11,12]]
No hay comentarios:
Publicar un comentario