Utilizando el tipo abstracto de datos de las pilas, definir las funciones
subPila :: Eq a => Pila a -> Pila a -> Bool
tal que subPila p1 p2 se verifica si p1 es una subpila de p2. Por ejemplo,
λ> ej1 = apila 2 (apila 3 vacia) λ> ej2 = apila 7 (apila 2 (apila 3 (apila 5 vacia))) λ> ej3 = apila 2 (apila 7 (apila 3 (apila 5 vacia))) λ> subPila ej1 ej2 True λ> subPila ej1 ej3 False
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
prefijoPila :: Eq a => Pila a -> Pila a -> Bool
tal que prefijoPila p1 p2 se verifica si la pila p1 es justamente un prefijo de la pila p2. Por ejemplo,
λ> ej1 = apila 4 (apila 2 vacia) λ> ej2 = apila 4 (apila 2 (apila 5 vacia)) λ> ej3 = apila 5 (apila 4 (apila 2 vacia)) λ> prefijoPila ej1 ej2 True λ> prefijoPila ej1 ej3 False
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
contenidaPila :: Eq a => Pila a -> Pila a -> Bool
tal que contenidaPila p1 p2 se verifica si todos los elementos de de la pila p1 son elementos de la pila p2. Por ejemplo,
λ> ej1 = apila 3 (apila 2 vacia) λ> ej2 = apila 3 (apila 4 vacia) λ> ej3 = apila 5 (apila 2 (apila 3 vacia)) λ> contenidaPila ej1 ej3 True λ> contenidaPila ej2 ej3 False
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
pertenecePila :: Eq a => a -> Pila a -> Bool
tal que pertenecePila x p se verifica si x es un elemento de la pila p. Por ejemplo,
pertenecePila 2 (apila 5 (apila 2 (apila 3 vacia))) == True pertenecePila 4 (apila 5 (apila 2 (apila 3 vacia))) == False
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
mapPila :: (a -> a) -> Pila a -> Pila a
tal que mapPila f p es la pila formada con las imágenes por f de los elementos de pila p, en el mismo orden. Por ejemplo,
λ> mapPila (+1) (apila 5 (apila 2 (apila 7 vacia))) 6 | 3 | 8
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
filtraPila :: (a -> Bool) -> Pila a -> Pila a
tal que filtraPila p q es la pila obtenida con los elementos de pila q que verifican el predicado p, en el mismo orden. Por ejemplo,
λ> ejPila = apila 6 (apila 3 (apila 1 (apila 4 vacia))) λ> ejPila 6 | 3 | 1 | 4 λ> filtraPila even ejPila 6 | 4 λ> filtraPila odd ejPila 3 | 1
Utilizando el tipo abstracto de datos de las pilas, definir las funciones
listaApila :: [a] -> Pila a pilaALista :: Pila a -> [a]
tales que
listaApila xs es la pila formada por los elementos de xs. Por ejemplo,λ> listaApila [3, 2, 5] 5 | 2 | 3 ~~~ + `pilaALista p` es la lista formada por los elementos de la lista `p`. Por ejemplo, ~~~haskell λ> pilaAlista (apila 5 (apila 2 (apila 3 vacia))) [3, 2, 5]
Comprobar con QuickCheck que ambas funciones son inversa; es decir,
pilaAlista (listaApila xs) == xs listaApila (pilaAlista p) == p
Una pila es una estructura de datos, caracterizada por ser una secuencia de elementos en la que las operaciones de inserción y extracción se realizan por el mismo extremo.
Las operaciones que definen a tipo abstracto de datos (TAD) de las pilas (cuyos elementos son del tipo a) son las siguientes:
vacia :: Pila a apila :: a -> Pila a -> Pila a cima :: Pila a -> a desapila :: Pila a -> Pila a esVacia :: Pila a -> Bool
tales que
Las operaciones tienen que verificar las siguientes propiedades:
Se consideran las expresiones vectoriales formadas por un vector, la suma de dos expresiones vectoriales o el producto de un entero por una expresión vectorial. El siguiente tipo de dato define las expresiones vectoriales
data ExpV = Vec Int Int | Sum ExpV ExpV | Mul Int ExpV deriving Show
Definir la función
valorEV :: ExpV -> (Int,Int)
tal que valorEV e es el valorEV de la expresión vectorial e. Por ejemplo,
valorEV (Vec 1 2) == (1,2) valorEV (Sum (Vec 1 2) (Vec 3 4)) == (4,6) valorEV (Mul 2 (Vec 3 4)) == (6,8) valorEV (Mul 2 (Sum (Vec 1 2 ) (Vec 3 4))) == (8,12) valorEV (Sum (Mul 2 (Vec 1 2)) (Mul 2 (Vec 3 4))) == (8,12)
Las operaciones de suma, resta y multiplicación se pueden representar mediante el siguiente tipo de datos
data Op = S | R | M
La expresiones aritméticas con dichas operaciones se pueden representar mediante el siguiente tipo de dato algebraico
data Expr = C Int | A Op Expr Expr
Por ejemplo, la expresión
(7-3)+(2*5)
se representa por
A S (A R (C 7) (C 3)) (A M (C 2) (C 5))
Definir la función
valor :: Expr -> Int
tal que valor e es el valor de la expresión e. Por ejemplo,
valor (A S (A R (C 7) (C 3)) (A M (C 2) (C 5))) == 14 valor (A M (A R (C 7) (C 3)) (A S (C 2) (C 5))) == 28