Ir al contenido principal

TAD de las pilas - Ordenación de pilas por inserción

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.

Leer más…

TAD de las pilas - Reconocimiento de subpilas

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

Leer más…

TAD de las pilas - Reconocimiento de prefijos de pilas

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

Leer más…

TAD de las pilas - Inclusión de pilas

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

Leer más…

TAD de las pilas - Filtrado de pilas según una propiedad

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

Leer más…

TAD de las pilas - Transformaciones entre pilas y listas

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

Leer más…