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
Las expresiones aritméticas generales se pueden definir usando el siguiente tipo de datos
data Expr = C Int | X | S Expr Expr | R Expr Expr | P Expr Expr | E Expr Int deriving (Eq, Show)
Por ejemplo, la expresión
3*x - (x+2)^7
se puede definir por
R (P (C 3) X) (E (S X (C 2)) 7)
Definir la función
maximo :: Expr -> [Int] -> (Int,[Int])
tal que maximo e xs es el par formado por el máximo valor de la expresión e para los puntos de xs y en qué puntos alcanza el máximo. Por ejemplo,
λ> maximo (E (S (C 10) (P (R (C 1) X) X)) 2) [-3..3] (100,[0,1])
Las expresiones aritméticas con variables pueden representarse usando el siguiente tipo de datos
data Expr = C Int | V Char | S Expr Expr | P Expr Expr
Por ejemplo, la expresión 2·(a+5) se representa por
P (C 2) (S (V 'a') (C 5))
Definir la función
reducible :: Expr -> Bool
tal que reducible a se verifica si a es una expresión reducible; es decir, contiene una operación en la que los dos operandos son números. Por ejemplo,
reducible (S (C 3) (C 4)) == True reducible (S (C 3) (V 'x')) == False reducible (S (C 3) (P (C 4) (C 5))) == True reducible (S (V 'x') (P (C 4) (C 5))) == True reducible (S (C 3) (P (V 'x') (C 5))) == False reducible (C 3) == False reducible (V 'x') == False
Las expresiones aritméticas con variables pueden representarse usando el siguiente tipo de datos
data Expr = C Int | V Char | S Expr Expr | P Expr Expr deriving (Eq, Show)
Por ejemplo, la expresión 2·(a+5) se representa por
P (C 2) (S (V 'a') (C 5))
Definir la función
sustitucion :: Expr -> [(Char, Int)] -> Expr
tal que sustitucion e s es la expresión obtenida sustituyendo las variables de la expresión e según se indica en la sustitución s. Por ejemplo,
λ> sustitucion (P (V 'z') (S (C 3) (V 'x'))) [('x',7),('z',9)] P (C 9) (S (C 3) (C 7)) λ> sustitucion (P (V 'z') (S (C 3) (V 'y'))) [('x',7),('z',9)] P (C 9) (S (C 3) (V 'y'))
Las expresiones aritméticas con variables pueden representarse usando el siguiente tipo de datos
data Expr = C Int | V Char | S Expr Expr | P Expr Expr
Por ejemplo, la expresión 2·(a+5) se representa por
P (C 2) (S (V 'a') (C 5))
Definir la función
sumas :: Expr -> Int
tal que sumas e es el número de sumas en la expresión e. Por ejemplo,
sumas (P (V 'z') (S (C 3) (V 'x'))) == 1 sumas (S (V 'z') (S (C 3) (V 'x'))) == 2 sumas (P (V 'z') (P (C 3) (V 'x'))) == 0
Las expresiones aritméticas con variables pueden representarse usando el siguiente tipo de datos
data Expr = C Int | V Char | S Expr Expr | P Expr Expr
Por ejemplo, la expresión 2·(a+5) se representa por
P (C 2) (S (V 'a') (C 5))
Definir la función
valor :: Expr -> [(Char,Int)] -> Int
tal que valor x e es el valor de la expresión x en el entorno e (es decir, el valor de la expresión donde las variables de x se sustituyen por los valores según se indican en el entorno e). Por ejemplo,
λ> valor (P (C 2) (S (V 'a') (V 'b'))) [('a',2),('b',5)] 14