El tipo abstracto de datos de las pilas en Haskell

En este artículo continúo la serie dedicada a los tipos de datos abstractos (TAD) en Haskell presentando el TAD de las pilas.

En artículos anteriores presenté los TAD de los polinomios y el de los conjuntos. En éste voy a presentar el TAD de las pilas y sus implementaciones en Haskell.

Al igual que hice en los anteriores TAD, usaré módulos, funciones de escritura y QuickCheck para conseguir la abstracción, independencia y certificación de los resultados de las implementaciones.

El contenido del resto del artículo es el siguiente: el TAD de las pilas, las implementaciones en Haskell mediante tipos algebraicos y mediante listas y la comprobación con QuickCheck de sus propiedades.

Pila.hs: El TAD de las pilas

module Pila (Pila,apilar,desapilar,cima,pilaVacia,esPilaVacia) where

-- El tipo de las pilas.
data Pila a = Undefined

-- pilaVacia es la pila vacía. 
pilaVacia :: Pila a
pilaVacia = undefined

-- (esPilaVacia p) se verifica si p es la pila vacía.
esPilaVacia :: Pila a -> Bool
esPilaVacia = undefined

-- (apilar x p) es la pila obtenida añadiéndole x encima de la pila
-- p.
apilar :: a -> Pila a -> Pila a
apilar = undefined

-- (desapilar p) es la pila obtenida suprimiendo la cima de la pila
-- p.
desapilar :: Pila a -> Pila a
desapilar = undefined

-- (cima p) es la cima de la pila p.
cima :: Pila a -> a
cima = undefined

module Pila (Pila,apilar,desapilar,cima,pilaVacia,esPilaVacia) where

-- El tipo de las pilas.

data Pila a = Undefined

-- pilaVacia es la pila vacía.

pilaVacia :: Pila a

pilaVacia = undefined

-- (esPilaVacia p) se verifica si p es la pila vacía.

esPilaVacia :: Pila a -> Bool

esPilaVacia = undefined

-- (apilar x p) es la pila obtenida añadiéndole x encima de la pila

-- p.

apilar :: a -> Pila a -> Pila a

apilar = undefined

-- (desapilar p) es la pila obtenida suprimiendo la cima de la pila

-- p.

desapilar :: Pila a -> Pila a

desapilar = undefined

-- (cima p) es la cima de la pila p.

cima :: Pila a -> a

cima = undefined

PilaConTipoDeDatoAlgebraico.hs: Implemetación de las pilas mediante tipos algebraicos

module PilaConTipoDeDatoAlgebraico 
    (Pila,apilar,desapilar,cima,pilaVacia,esPilaVacia) where

import qualified Pila

-- Tipo de dato algebraico de las pilas:
data Pila a = Vacia
            | P a (Pila a)
            deriving Eq

instance (Show a) => Show (Pila a) where
    showsPrec p Vacia cad   = showChar '-' cad
    showsPrec p (P x s) cad = shows x (showChar '|' (shows s cad))

-- Ejemplo de pila:
--    *Pila> p1
--    1|2|3|-
p1 = apilar 1 (apilar 2 (apilar 3 pilaVacia))

-- pilaVacia es la pila vacía. Por ejemplo,
--    > pilaVacia
--    -
pilaVacia :: Pila a
pilaVacia = Vacia

-- (esPilaVacia p) se verifica si p es la pila vacía. Por ejemplo,
--    esPilaVacia p1         ==  False
--    esPilaVacia pilaVacia  ==  True
esPilaVacia :: Pila a -> Bool
esPilaVacia Vacia = True
esPilaVacia _     = False

-- (apilar x p) es la pila obtenida añadiéndole x encima de la pila
-- p. Por ejemplo,
--    apilar 4 p1  =>  4|1|2|3|-
apilar :: a -> Pila a -> Pila a
apilar x p = P x p

-- (desapilar p) es la pila obtenida suprimiendo la cima de la pila
-- p. Por ejemplo,
--    desapilar p1  =>  2|3|-
desapilar :: Pila a -> Pila a
desapilar Vacia   = error "no se puede desapilar la pila vacia"
desapilar (P _ p) = p

-- (cima p) es la cima de la pila p. Por ejemplo,
--    cima p1  =>  1
cima :: Pila a -> a
cima Vacia   = error "la pila vacia no tiene cima"
cima (P x _) =  x

module PilaConTipoDeDatoAlgebraico

(Pila,apilar,desapilar,cima,pilaVacia,esPilaVacia) where

import qualified Pila

-- Tipo de dato algebraico de las pilas:

data Pila a = Vacia

| P a (Pila a)

deriving Eq

instance (Show a) => Show (Pila a) where

showsPrec p Vacia cad = showChar '-' cad

showsPrec p (P x s) cad = shows x (showChar '|' (shows s cad))

-- Ejemplo de pila:

-- *Pila> p1

-- 1|2|3|-

p1 = apilar 1 (apilar 2 (apilar 3 pilaVacia))

-- pilaVacia es la pila vacía. Por ejemplo,

-- > pilaVacia

-- -

pilaVacia :: Pila a

pilaVacia = Vacia

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

-- esPilaVacia p1 == False

-- esPilaVacia pilaVacia == True

esPilaVacia :: Pila a -> Bool

esPilaVacia Vacia = True

esPilaVacia _ = False

-- (apilar x p) es la pila obtenida añadiéndole x encima de la pila

-- p. Por ejemplo,

-- apilar 4 p1 => 4|1|2|3|-

apilar :: a -> Pila a -> Pila a

apilar x p = P x p

-- (desapilar p) es la pila obtenida suprimiendo la cima de la pila

-- p. Por ejemplo,

-- desapilar p1 => 2|3|-

desapilar :: Pila a -> Pila a

desapilar Vacia = error "no se puede desapilar la pila vacia"

desapilar (P _ p) = p

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

-- cima p1 => 1

cima :: Pila a -> a

cima Vacia = error "la pila vacia no tiene cima"

cima (P x _) = x

PilaConListas.hs: Implemetación de las pilas mediante listas

module PilaConListas
    (Pila,apilar,desapilar,cima,pilaVacia,esPilaVacia) where

import qualified Pila

-- Pilas como listas
newtype Pila a = P [a]
     deriving Eq

-- Escritura de las pilas.
instance (Show a) => Show (Pila a) where
    showsPrec p (P [])     cad = showChar '-' cad
    showsPrec p (P (x:xs)) cad
        = shows x (showChar '|' (shows (P xs) cad))

-- Ejemplo de pila:
--    > p1
--    1|2|3|-
p1 = apilar 1 (apilar 2 (apilar 3 pilaVacia))

-- pilaVacia es la pila vacía. Por ejemplo,
--    > pilaVacia
--    -
pilaVacia :: Pila a
pilaVacia = P []

-- (esPilaVacia p) se verifica si p es la pila vacía. Por ejemplo,
--    esPilaVacia p1         ==  False
--    esPilaVacia pilaVacia  ==  True
esPilaVacia :: Pila a -> Bool
esPilaVacia (P []) = True
esPilaVacia (P _ ) = False

-- (apilar x p) es la pila obtenida añadiéndole x encima de la pila
-- p. Por ejemplo,
--    apilar 4 p1  =>  4|1|2|3|-
apilar :: a -> Pila a -> Pila a
apilar x (P xs) = P (x:xs)

-- (desapilar p) es la pila obtenida suprimiendo la cima de la pila
-- p. Por ejemplo,
--    desapilar p1  =>  2|3|-
desapilar :: Pila a -> Pila a
desapilar (P [])     = error "desapilar from an empty stack"
desapilar (P (_:xs)) = P  xs

-- (cima p) es la cima de la pila p. Por ejemplo,
--    cima p1  ==  1
cima :: Pila a -> a
cima (P [])    = error "cima from an empty stack"
cima (P (x:_)) = x

module PilaConListas

(Pila,apilar,desapilar,cima,pilaVacia,esPilaVacia) where

import qualified Pila

-- Pilas como listas

newtype Pila a = P [a]

deriving Eq

-- Escritura de las pilas.

instance (Show a) => Show (Pila a) where

showsPrec p (P []) cad = showChar '-' cad

showsPrec p (P (x:xs)) cad

= shows x (showChar '|' (shows (P xs) cad))

-- Ejemplo de pila:

-- > p1

-- 1|2|3|-

p1 = apilar 1 (apilar 2 (apilar 3 pilaVacia))

-- pilaVacia es la pila vacía. Por ejemplo,

-- > pilaVacia

-- -

pilaVacia :: Pila a

pilaVacia = P []

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

-- esPilaVacia p1 == False

-- esPilaVacia pilaVacia == True

esPilaVacia :: Pila a -> Bool

esPilaVacia (P []) = True

esPilaVacia (P _ ) = False

-- (apilar x p) es la pila obtenida añadiéndole x encima de la pila

-- p. Por ejemplo,

-- apilar 4 p1 => 4|1|2|3|-

apilar :: a -> Pila a -> Pila a

apilar x (P xs) = P (x:xs)

-- (desapilar p) es la pila obtenida suprimiendo la cima de la pila

-- p. Por ejemplo,

-- desapilar p1 => 2|3|-

desapilar :: Pila a -> Pila a

desapilar (P []) = error "desapilar from an empty stack"

desapilar (P (_:xs)) = P xs

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

-- cima p1 == 1

cima :: Pila a -> a

cima (P []) = error "cima from an empty stack"

cima (P (x:_)) = x

PilaPropiedades.hs: Propiedades de las pilas

import PilaConTipoDeDatoAlgebraico
-- import PilaConListas
import Test.QuickCheck

-- ---------------------------------------------------------------------
-- Generador de pilas                                          --
-- ---------------------------------------------------------------------

-- genPila es un generador de pilas. Por ejemplo,
--    *Main> sample genPila
--    -
--    0|0|-
--    -
--    -6|4|-3|3|0|-
--    -
--    9|5|-1|-3|0|-8|-5|-7|2|-
--    -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-
--    2|-14|-5|2|-
--    5|9|-
--    -1|-14|5|-
--    6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-
genPila :: Arbitrary a => Gen (Pila a)
genPila = do xs <- listOf arbitrary
             return (foldr apilar pilaVacia xs)
  
-- El tipo pila es una instancia del arbitrario. 
instance (Arbitrary a, Num a) => Arbitrary (Pila a) where
    arbitrary = genPila

-- ---------------------------------------------------------------------
-- Propiedades
-- ---------------------------------------------------------------------

-- Propiedad 1. La cima de la pila que resulta de apilar x en una pila p
-- es x 
--    > quickCheck propCimaApilar
--    +++ OK, passed 100 tests.
propCimaApilar x p = 
    cima (apilar x p) == x

-- Propiedad 2. La pila que resulta de desapilar después de apilar
-- cualquier elemento es la pila inicial.
--    > quickCheck propDesapilarApilar
--    +++ OK, passed 100 tests.
propDesapilarApilar x p = 
    desapilar (apilar x p) == p

-- Propiedad 3. La pila vacía está vacía.
--    > quickCheck propVaciaEsvacia
--    +++ OK, passed 100 tests.
propVaciaEsvacia = esPilaVacia pilaVacia

-- Propiedad 4. La pila que resulta de apilar un elemento en un pila
-- cualquiera no es vacía.
--    > quickCheck propApilarNoEsvacia
--    +++ OK, passed 100 tests.
propApilarNoEsvacia x p = not (esPilaVacia (apilar x p))

-- todasPropiedades verifica toada las propiedades anteriores.
--    *Main> quickCheck todasPropiedades
--    +++ OK, passed 100 tests.
todasPropiedades x p =
    propCimaApilar x p &&
    propDesapilarApilar x p &&
    propVaciaEsvacia &&
    propApilarNoEsvacia x p

import PilaConTipoDeDatoAlgebraico

-- import PilaConListas

import Test.QuickCheck

-- ---------------------------------------------------------------------

-- Generador de pilas --

-- ---------------------------------------------------------------------

-- genPila es un generador de pilas. Por ejemplo,

-- *Main> sample genPila

-- -

-- 0|0|-

-- -

-- -6|4|-3|3|0|-

-- -

-- 9|5|-1|-3|0|-8|-5|-7|2|-

-- -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-

-- 2|-14|-5|2|-

-- 5|9|-

-- -1|-14|5|-

-- 6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-

genPila :: Arbitrary a => Gen (Pila a)

genPila = do xs <- listOf arbitrary

return (foldr apilar pilaVacia xs)

-- El tipo pila es una instancia del arbitrario.

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

arbitrary = genPila

-- ---------------------------------------------------------------------

-- Propiedades

-- ---------------------------------------------------------------------

-- Propiedad 1. La cima de la pila que resulta de apilar x en una pila p

-- es x

-- > quickCheck propCimaApilar

-- +++ OK, passed 100 tests.

propCimaApilar x p =

cima (apilar x p) == x

-- Propiedad 2. La pila que resulta de desapilar después de apilar

-- cualquier elemento es la pila inicial.

-- > quickCheck propDesapilarApilar

-- +++ OK, passed 100 tests.

propDesapilarApilar x p =

desapilar (apilar x p) == p

-- Propiedad 3. La pila vacía está vacía.

-- > quickCheck propVaciaEsvacia

-- +++ OK, passed 100 tests.

propVaciaEsvacia = esPilaVacia pilaVacia

-- Propiedad 4. La pila que resulta de apilar un elemento en un pila

-- cualquiera no es vacía.

-- > quickCheck propApilarNoEsvacia

-- +++ OK, passed 100 tests.

propApilarNoEsvacia x p = not (esPilaVacia (apilar x p))

-- todasPropiedades verifica toada las propiedades anteriores.

-- *Main> quickCheck todasPropiedades

-- +++ OK, passed 100 tests.

todasPropiedades x p =

propCimaApilar x p &&

propDesapilarApilar x p &&

propVaciaEsvacia &&

propApilarNoEsvacia x p

El objetivo de la serie es la elaboración del tema de TAD del curso de Informática del Grado en Matemáticas.

Pila.hs: El TAD de las pilas

PilaConTipoDeDatoAlgebraico.hs: Implemetación de las pilas mediante tipos algebraicos

PilaConListas.hs: Implemetación de las pilas mediante listas

PilaPropiedades.hs: Propiedades de las pilas

Se puede imprimir o compartir con