Tema 14: El tipo abstracto de datos de las pilas

Índice

1. Tipos abstractos de datos (TAD)
2. Especificación del TAD de las pilas
- 2.1. Signatura del TAD pilas
- 2.2. Propiedades del TAD de las pilas
3. Implementaciones del TAD de las pilas
- 3.1. Las pilas como tipos de datos algebraicos
- 3.2. Las pilas como listas
4. Comprobación de las implementaciones con QuickCheck
5. Material complementario
6. Referencias

1. Tipos abstractos de datos (TAD)

La abstracción es un mecanismo para comprender problemas que involucran una gran cantidad de detalles.
Aspectos de la abstracción:
- Destacar los detalles relevantes.
- Ocultar los detalles irrelevantes.
Un tipo abstracto de datos (TAD) es una colección de valores y *operaciones que se definen mediante una especificación que es independiente de cualquier representación.
Un TAD es una abstracción:
- Se destacan los detalles (normalmente pocos) de la especificación (el qué).
- Se ocultan los detalles (normalmente numerosos) de la implementación (el cómo).
Analogía con las estructuras algebraicas.

2. Especificación del TAD de las pilas

2.1. Signatura del TAD pilas

2.1.1. Descripción informal de las pilas

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.
La pilas también se llaman estructuras LIFO (del inglés Last In First Out), debido a que el último elemento en entrar será el primero en salir.
Analogía con las pilas de platos.

2.1.2. Signatura del TAD de las pilas

Signatura:

vacia    :: Pila a
apila    :: a -> Pila a -> Pila a
cima     :: Pila a -> a
desapila :: Pila a -> Pila a
esVacia  :: Pila a -> Bool

Descripción:
- vacia es la pila vacía.
- (apila x p) es la pila obtenida añadiendo x al principio de p.
- (cima p) es la cima de la pila p.
- (desapila p) es la pila obtenida suprimiendo la cima de p.
- (esVacia p) se verifica si p es la pila vacía.

2.2. Propiedades del TAD de las pilas

cima (apila x p) == x
desapila (apila x p) == p
esVacia vacia
not (esVacia (apila x p))

3. Implementaciones del TAD de las pilas

3.1. Las pilas como tipos de datos algebraicos

Cabecera del módulo:

module Tema_14.PilaConTipoDeDatoAlgebraico
  (Pila,
   vacia,      -- Pila a
   apila,      -- a -> Pila a -> Pila a
   cima,       -- Pila a -> a
   desapila,   -- Pila a -> Pila a
   esVacia,    -- Pila a -> Bool
   escribePila -- Show a => Pila a -> String
  ) where

Tipo de dato algebraico de las pilas.

data Pila a = Vacia
            | P a (Pila a)
  deriving Eq

Procedimiento de escritura de pilas.

-- (escribePila p) es la cadena correspondiente a la pila p. Por
-- ejemplo,
--    escribePila (apila 1 (apila 2 (apila 3 vacia))) == "1|2|3|-"
escribePila :: Show a => Pila a -> String
escribePila Vacia   = "-"
escribePila (P x s) = show x ++ "|" ++ escribePila s

-- Procedimiento de escritura de pilas.
instance Show a => Show (Pila a) where
  show = escribePila

Ejemplo de pila: La pila obtenida apilando el 3, a continuación el 2 y finalmente el 1 se define por
```
λ> apila 1 (apila 2 (apila 3 vacia))
1|2|3|-
```
vacia es la pila vacía. Por ejemplo,
```
λ> vacia
-
```
Su definición es
```
vacia :: Pila a
vacia = Vacia
```

(apila x p) es la pila obtenida añadiedo x encima de la pila p. Por ejemplo,

λ> apila 4 (apila 1 (apila 2 (apila 3 vacia)))
4|1|2|3|-

Su definición es

apila :: a -> Pila a -> Pila a
apila x p = P x p

(cima p) es la cima de la pila p. Por ejemplo,

cima (apila 1 (apila 2 (apila 3 vacia)))  ==  1

Su definición es

cima :: Pila a -> a
cima Vacia   = error "cima: pila vacia"
cima (P x _) =  x

(desapila p) es la pila obtenida suprimiendo la cima de la pila p. Por ejemplo,

λ> desapila (apila 1 (apila 2 (apila 3 vacia)))
2|3|-

Su definición es

desapila :: Pila a -> Pila a
desapila Vacia   = error "desapila: pila vacia"
desapila (P _ p) = p

(esVacia p) se verifica si p es la pila vacía. Por ejemplo,

esVacia (apila 1 (apila 2 (apila 3 vacia)))     ==  False
esVacia vacia  ==  True

Su definición es

esVacia :: Pila a -> Bool
esVacia Vacia = True
esVacia _     = False

3.2. Las pilas como listas

Cabecera del módulo

module Tema_14.PilaConListas
  (Pila,
   vacia,      -- Pila a
   apila,      -- a -> Pila a -> Pila a
   cima,       -- Pila a -> a
   desapila,   -- Pila a -> Pila a
   esVacia,    -- Pila a -> Bool
   escribePila -- Show a => Pila a -> String
  ) where

Tipo de datos de las pilas:
```
newtype Pila a = P [a]
  deriving Eq
```

Procedimiento de escritura de pilas.

-- (escribePila p) es la cadena correspondiente a la pila p. Por
-- ejemplo,
--    escribePila (apila 1 (apila 2 (apila 3 vacia))) == "1|2|3|-"
escribePila :: Show a => Pila a -> String
escribePila (P [])     = "-"
escribePila (P (x:xs)) = show x ++ "|" ++ escribePila (P xs)

-- Procedimiento de escritura de pilas.
instance Show a => Show (Pila a) where
  show = escribePila

Ejemplo de pila: p1 es la pila obtenida anadiéndole los elementos 3, 2 y 1 a la pila vacía. Por ejemplo,
```
λ> apila 1 (apila 2 (apila 3 vacia))
1|2|3|-
```

vacia es la pila vacía. Por ejemplo,

λ> vacia
-

vacia   :: Pila a
vacia = P []

(apila x p) es la pila obtenida añadiendo x encima de la pila p. Por ejemplo,

λ> apila 4 p1
4|1|2|3|-

Su definición es

apila :: a -> Pila a -> Pila a
apila x (P xs) = P (x:xs)

(cima p) es la cima de la pila p. Por ejemplo,

cima p1  ==  1

Su definición es

cima :: Pila a -> a
cima (P (x:_)) = x
cima (P [])    = error "cima de la pila vacia"

(desapila p) es la pila obtenida suprimiendo la cima de la pila p. Por ejemplo,

λ> desapila p1
2|3|-

Su definición es

desapila :: Pila a -> Pila a
desapila (P [])     = error "desapila la pila vacia"
desapila (P (_:xs)) = P  xs

(esVacia p) se verifica si p es la pila vacía. Por ejemplo,

esVacia p1     ==  False
esVacia vacia  ==  True

Su definición es

esVacia :: Pila a -> Bool
esVacia (P xs) = null xs

4. Comprobación de las implementaciones con QuickCheck

4.1. Pragma y librerías auxiliares

Al principio del fichero se añade

{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}

Importación de la implementación de pilas que se desea comprobar.

import Tema-14.PilaConTipoDeDatoAlgebraico
-- import Tema-14.PilaConListas
-- import I1M.Pila

Importación de la librería de comprobación
```
import Test.QuickCheck
```

4.2. Generador de pilas

genPila es un generador de pilas. Por ejemplo,

λ> sample genPila
0|0|-
-6|4|-3|3|0|-
-
9|5|-1|-3|0|-8|-5|-7|2|-
...

Su definición es

genPila :: (Num a, Arbitrary a) => Gen (Pila a)
genPila = do
  xs <- listOf arbitrary
  return (foldr apila vacia xs)

instance (Arbitrary a, Num a) => Arbitrary (Pila a) where
  arbitrary = genPila

4.3. Especificación de las propiedades de las pilas

La cima de la pila que resulta de añadir x a la pila p es x.

prop_cima_apila :: Int -> Pila Int -> Bool
prop_cima_apila x p =
  cima (apila x p) == x

La pila que resulta de desapilar después de añadir cualquier elemento a una pila p es p.

prop_desapila_apila :: Int -> Pila Int -> Bool
prop_desapila_apila x p =
  desapila (apila x p) == p

La pila vacía está vacía.

prop_vacia_esta_vacia :: Bool
prop_vacia_esta_vacia =
  esVacia vacia

La pila que resulta de añadir un elemento en un pila cualquiera no es vacía.

prop_apila_no_es_vacia :: Int -> Pila Int -> Bool
prop_apila_no_es_vacia x p =
  not (esVacia (apila x p))

4.4. Comprobación de las propiedades

Para verificar todas las propiedades se escribe
```
return []
verifica = $quickCheckAll
```

Comprobación de las propiedades de las pilas

λ> verifica
=== prop_cima_apila from PilaPropiedades.hs:47 ===
+++ OK, passed 100 tests.

=== prop_desapila_apila from PilaPropiedades.hs:57 ===
+++ OK, passed 100 tests.

=== prop_vacia_esta_vacia from PilaPropiedades.hs:66 ===
+++ OK, passed 1 tests.

=== prop_apila_no_es_vacia from PilaPropiedades.hs:75 ===
+++ OK, passed 100 tests.

True

5. Material complementario

El código del tema se encuentra en este los siguientes enlaces

Este tema también se encuentra en los siguientes formatos:

Como transparencias en PDF.
Como libro interactivo en IHaskell sobre Jupyter.
Como vídeo de clase.

6. Referencias

F. Rabhi y G. Lapalme. Algorithms: A functional programming approach.
- Cap. 5.2. Stacks
WikiBooks, [Haskell](Algorithms: A functional programming approach)
- Data structures primer.