Utilizando el tipo abstracto de datos de las pilas, definir la función
ordenaInserPila :: Ord a => Pila a -> Pila a
tal que ordenaInserPila p es la pila obtenida ordenando por inserción los los elementos de la pila p. Por ejemplo,
λ> ordenaInserPila (apila 4 (apila 1 (apila 3 vacia))) 1 | 3 | 4
Comprobar con QuickCheck que la pila (ordenaInserPila p) está ordenada.
Utilizando el tipo abstracto de datos de las pilas, definir la función
ordenadaPila :: Ord a => Pila a -> Bool
tal que ordenadaPila p se verifica si los elementos de la pila p están ordenados en orden creciente. Por ejemplo,
ordenadaPila (apila 1 (apila 5 (apila 6 vacia))) == True ordenadaPila (apila 1 (apila 0 (apila 6 vacia))) == False
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: