Menu Close

TAD de las pilas: Aplicación de una función a los elementos de una pila

José A. Alonso, ,

Utilizando el tipo abstracto de datos de las pilas, definir la función

   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

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)
import Transformaciones_pilas_listas (listaApila, pilaAlista)
import Test.QuickCheck.HigherOrder
 
-- 1ª solución
-- ===========
 
mapPila1 :: (a -> a) -> Pila a -> Pila a
mapPila1 f p
  | esVacia p = p
  | otherwise = apila (f cp) (mapPila1 f dp)
  where cp = cima p
        dp = desapila p
 
-- 2ª solución
-- ===========
 
-- Se usarán las funciones listaApila y pilaAlista del ejercicio
-- "Transformaciones entre pilas y listas" que se encuentra en
-- https://bit.ly/3ZHewQ8
 
mapPila2 :: (a -> a) -> Pila a -> Pila a
mapPila2 f p =
  listaApila (map f (pilaAlista p))
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_mapPila :: (Int -> Int) -> [Int] -> Bool
prop_mapPila f p =
  mapPila1 f q == mapPila2 f q
  where q = listaApila p
 
-- La comprobación es
--    λ> quickCheck' prop_mapPila
--    +++ OK, passed 100 tests.


Soluciones en Python

from copy import deepcopy
from typing import Callable, TypeVar
 
from hypothesis import given
 
from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,
                          vacia)
from src.transformaciones_pilas_listas import listaApila, pilaAlista
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def mapPila1(f: Callable[[A], A], p: Pila[A]) -> Pila[A]:
    if esVacia(p):
        return p
    cp = cima(p)
    dp = desapila(p)
    return apila(f(cp), mapPila1(f, dp))
 
# 2ª solución
# ===========
 
# Se usarán las funciones listaApila y pilaAlista del ejercicio
# "Transformaciones entre pilas y listas" que se encuentra en
# https://bit.ly/3ZHewQ8
 
def mapPila2(f: Callable[[A], A], p: Pila[A]) -> Pila[A]:
    return listaApila(list(map(f, pilaAlista(p))))
 
# 3ª solución
# ===========
 
def mapPila3Aux(f: Callable[[A], A], p: Pila[A]) -> Pila[A]:
    if p.esVacia():
        return p
    cp = p.cima()
    p.desapila()
    r = mapPila3Aux(f, p)
    r.apila(f(cp))
    return r
 
def mapPila3(f: Callable[[A], A], p: Pila[A]) -> Pila[A]:
    p1 = deepcopy(p)
    return mapPila3Aux(f, p1)
 
# 4ª solución
# ===========
 
def mapPila4Aux(f: Callable[[A], A], p: Pila[A]) -> Pila[A]:
    r: Pila[A] = Pila()
    while not p.esVacia():
        cp = p.cima()
        p.desapila()
        r.apila(f(cp))
    r1: Pila[A] = Pila()
    while not r.esVacia():
        r1.apila(r.cima())
        r.desapila()
    return r1
 
def mapPila4(f: Callable[[A], A], p: Pila[A]) -> Pila[A]:
    p1 = deepcopy(p)
    return mapPila4Aux(f, p1)
 
# Comprobación de equivalencia de las definiciones
# ================================================
 
# La propiedad es
@given(p=pilaAleatoria())
def test_mapPila(p: Pila[int]) -> None:
    r = mapPila1(lambda x: x + 1 == 0, p)
    assert mapPila2(lambda x: x + 1 == 0, p) == r
    assert mapPila3(lambda x: x + 1 == 0, p) == r
    assert mapPila4(lambda x: x + 1 == 0, p) == r
 
# La comprobación es
#    src> poetry run pytest -q mapPila.py
#    1 passed in 0.29s
Leer más →

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

José A. Alonso, ,

Utilizando el tipo abstracto de datos de las pilas, definir la función

   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

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)
import Transformaciones_pilas_listas (listaApila, pilaAlista)
import Test.QuickCheck.HigherOrder
 
-- 1ª solución
-- ===========
 
filtraPila1 :: (a -> Bool) -> Pila a -> Pila a
filtraPila1 p q
  | esVacia q = vacia
  | p cq      = apila cq (filtraPila1 p dq)
  | otherwise = filtraPila1 p dq
  where cq = cima q
        dq = desapila q
 
-- 2ª solución
-- ===========
 
-- Se usarán las funciones listaApila y pilaAlista del ejercicio
-- "Transformaciones entre pilas y listas" que se encuentra en
-- https://bit.ly/3ZHewQ8
 
filtraPila2 :: (a -> Bool) -> Pila a -> Pila a
filtraPila2 p q =
  listaApila (filter p (pilaAlista q))
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_filtraPila :: (Int -> Bool) -> [Int] -> Bool
prop_filtraPila p xs =
  filtraPila1 p q == filtraPila2 p q
  where q = listaApila xs
 
-- La comprobación es
--    λ> quickCheck' prop_filtraPila
--    +++ OK, passed 100 tests.


Soluciones en Python

from copy import deepcopy
from typing import Callable, TypeVar
 
from hypothesis import given
 
from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,
                          vacia)
from src.transformaciones_pilas_listas import listaApila, pilaAlista
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def filtraPila1(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:
    if esVacia(q):
        return q
    cq = cima(q)
    dq = desapila(q)
    r = filtraPila1(p, dq)
    if p(cq):
        return apila(cq, r)
    return r
 
# 2ª solución
# ===========
 
# Se usarán las funciones listaApila y pilaAlista del ejercicio
# "Transformaciones entre pilas y listas" que se encuentra en
# https://bit.ly/3ZHewQ8
 
def filtraPila2(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:
    return listaApila(list(filter(p, pilaAlista(q))))
 
# 3ª solución
# ===========
 
def filtraPila3Aux(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:
    if q.esVacia():
        return q
    cq = q.cima()
    q.desapila()
    r = filtraPila3Aux(p, q)
    if p(cq):
        r.apila(cq)
    return r
 
def filtraPila3(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:
    q1 = deepcopy(q)
    return filtraPila3Aux(p, q1)
 
# 4ª solución
# ===========
 
def filtraPila4Aux(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:
    r: Pila[A] = Pila()
    while not q.esVacia():
        cq = q.cima()
        q.desapila()
        if p(cq):
            r.apila(cq)
    r1: Pila[A] = Pila()
    while not r.esVacia():
        r1.apila(r.cima())
        r.desapila()
    return r1
 
def filtraPila4(p: Callable[[A], bool], q: Pila[A]) -> Pila[A]:
    q1 = deepcopy(q)
    return filtraPila4Aux(p, q1)
 
# Comprobación de equivalencia de las definiciones
# ================================================
 
# La propiedad es
@given(p=pilaAleatoria())
def test_filtraPila(p: Pila[int]) -> None:
    r = filtraPila1(lambda x: x % 2 == 0, p)
    assert filtraPila2(lambda x: x % 2 == 0, p) == r
    assert filtraPila3(lambda x: x % 2 == 0, p) == r
    assert filtraPila4(lambda x: x % 2 == 0, p) == r
 
# La comprobación es
#    src> poetry run pytest -q filtraPila.py
#    1 passed in 0.25s
Leer más →

TAD de las pilas: Transformaciones entre pilas y listas

José A. Alonso, ,

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 pila p. Por ejemplo,
     λ> 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

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

module Transformaciones_pilas_listas where
 
import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)
import Test.QuickCheck
 
-- 1ª definición de listaApila
-- ===========================
 
listaApila :: [a] -> Pila a
listaApila ys = aux (reverse ys)
  where aux []     = vacia
        aux (x:xs) = apila x (aux xs)
 
-- 2ª definición de listaApila
-- ===========================
 
listaApila2 :: [a] -> Pila a
listaApila2 = aux . reverse
  where aux [] = vacia
        aux (x:xs) = apila x (aux xs)
 
-- 3ª definición de listaApila
-- ===========================
 
listaApila3 :: [a] -> Pila a
listaApila3 = aux . reverse
  where aux = foldr apila vacia
 
-- 4ª definición de listaApila
-- ===========================
 
listaApila4 :: [a] -> Pila a
listaApila4 xs = foldr apila vacia (reverse xs)
 
-- 5ª definición de listaApila
-- ===========================
 
listaApila5 :: [a] -> Pila a
listaApila5 = foldr apila vacia . reverse
 
-- Comprobación de equivalencia de las definiciones de listaApila
-- ==============================================================
 
-- La propiedad es
prop_listaApila :: [Int] -> Bool
prop_listaApila xs =
  all (== listaApila xs)
      [listaApila2 xs,
       listaApila3 xs,
       listaApila4 xs,
       listaApila5 xs]
 
-- La comprobación es
--    λ> quickCheck prop_listaApila
--    +++ OK, passed 100 tests.
 
-- 1ª definición de pilaAlista
-- ===========================
 
pilaAlista :: Pila a -> [a]
pilaAlista p
  | esVacia p = []
  | otherwise = pilaAlista dp ++ [cp]
  where cp = cima p
        dp = desapila p
 
-- 2ª definición de pilaAlista
-- ===========================
 
pilaAlista2 :: Pila a -> [a]
pilaAlista2 = reverse . aux
  where aux p | esVacia p = []
              | otherwise = cp : aux dp
          where cp = cima p
                dp = desapila p
 
-- Comprobación de equivalencia de las definiciones de pilaAlista
-- ==============================================================
 
-- La propiedad es
prop_pilaAlista :: Pila Int -> Bool
prop_pilaAlista p =
  pilaAlista p == pilaAlista2 p
 
-- La comprobación es
--    λ> quickCheck prop_pilaAlista
--    +++ OK, passed 100 tests.
 
-- Comprobación de las propiedades
-- ===============================
 
-- La primera propiedad es
prop_1_listaApila :: [Int] -> Bool
prop_1_listaApila xs =
  pilaAlista (listaApila xs) == xs
 
-- La comprobación es
--    λ> quickCheck prop_1_listaApila
--    +++ OK, passed 100 tests.
 
-- La segunda propiedad es
prop_2_listaApila :: Pila Int -> Bool
prop_2_listaApila p =
  listaApila (pilaAlista p) == p
 
-- La comprobación es
--    λ> quickCheck prop_2_listaApila
--    +++ OK, passed 100 tests.


Soluciones en Python

from copy import deepcopy
from typing import TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,
                          vacia)
 
A = TypeVar('A')
 
# 1ª definición de listaApila
# ===========================
 
def listaApila(ys: list[A]) -> Pila[A]:
    def aux(xs: list[A]) -> Pila[A]:
        if not xs:
            return vacia()
        return apila(xs[0], aux(xs[1:]))
 
    return aux(list(reversed(ys)))
 
# 2ª solución de listaApila
# =========================
 
def listaApila2(xs: list[A]) -> Pila[A]:
    p: Pila[A] = Pila()
    for x in xs:
        p.apila(x)
    return p
 
# Comprobación de equivalencia de las definiciones de listaApila
# ==============================================================
 
# La propiedad es
@given(st.lists(st.integers()))
def test_listaApila(xs: list[int]) -> None:
    assert listaApila(xs) == listaApila2(xs)
 
# 1ª definición de pilaAlista
# ===========================
 
def pilaAlista(p: Pila[A]) -> list[A]:
    if esVacia(p):
        return []
    cp = cima(p)
    dp = desapila(p)
    return pilaAlista(dp) + [cp]
 
# 2ª definición de pilaAlista
# ===========================
 
def pilaAlista2Aux(p: Pila[A]) -> list[A]:
    if p.esVacia():
        return []
    cp = p.cima()
    p.desapila()
    return pilaAlista2Aux(p) + [cp]
 
def pilaAlista2(p: Pila[A]) -> list[A]:
    p1 = deepcopy(p)
    return pilaAlista2Aux(p1)
 
# 3ª definición de pilaAlista
# ===========================
 
def pilaAlista3Aux(p: Pila[A]) -> list[A]:
    r = []
    while not p.esVacia():
        r.append(p.cima())
        p.desapila()
    return r[::-1]
 
def pilaAlista3(p: Pila[A]) -> list[A]:
    p1 = deepcopy(p)
    return pilaAlista3Aux(p1)
 
# Comprobación de equivalencia de las definiciones de pilaAlista
# ==============================================================
 
@given(p=pilaAleatoria())
def test_pilaAlista(p: Pila[int]) -> None:
    assert pilaAlista(p) == pilaAlista2(p)
    assert pilaAlista(p) == pilaAlista3(p)
 
# Comprobación de las propiedades
# ===============================
 
# La primera propiedad es
@given(st.lists(st.integers()))
def test_1_listaApila(xs: list[int]) -> None:
    assert pilaAlista(listaApila(xs)) == xs
 
# La segunda propiedad es
@given(p=pilaAleatoria())
def test_2_listaApila(p: Pila[int]) -> None:
    assert listaApila(pilaAlista(p)) == p
 
# La comprobación es
#      src> poetry run pytest -v transformaciones_pilas_listas.py
#      test_listaApila PASSED
#      test_pilaAlista PASSED
#      test_1_listaApila PASSED
#      test_2_listaApila PASSED
Leer más →

El tipo abstracto de datos de las pilas

José A. Alonso, ,

1. El tipo abstracto de datos 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.

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

  • 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.

Las operaciones tienen que verificar las siguientes propiedades:

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

2. Las pilas en Haskell

2.1. El tipo abstracto de datos de las pilas en Haskell

El TAD de las pilas se encuentra en el módulo Pila.hs cuyo contenido es el siguiente:

module TAD.Pila
  (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
 
import TAD.PilaConListas
-- import TAD.PilaConSucesiones

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos dos una usando listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

2.2. Implementación de las pilas mediante listas

La implementación se encuentra en el módulo PilaConListas.hs cuyo contenido es el siguiente:

module TAD.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
 
import Test.QuickCheck
 
-- Representación de las pilas mediante listas.
newtype Pila a = P [a]
  deriving Eq
 
-- (escribePila p) es la cadena correspondiente a la pila p. Por
-- ejemplo,
--    escribePila (apila 5 (apila 2 (apila 3 vacia))) == "5 | 2 | 3"
escribePila :: Show a => Pila a -> String
escribePila (P [])     = "-"
escribePila (P [x])    = show x
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:
--    λ> 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 (apila 3 (apila 2 (apila 5 vacia)))
--    4 | 3 | 2 | 5
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 (apila 4 (apila 3 (apila 2 (apila 5 vacia))))
--    4
cima :: Pila a -> a
cima (P [])    = error "cima de la pila vacia"
cima (P (x:_)) = x
 
-- (desapila p) es la pila obtenida suprimiendo la cima de la pila
-- p. Por ejemplo,
--    λ> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))
--    3 | 2 | 5
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 (apila 1 (apila 2 (apila 3 vacia))) ==  False
--    esVacia vacia                               ==  True
esVacia :: Pila a -> Bool
esVacia (P xs) = null xs
 
-- 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|-
--    -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, Num a) => Gen (Pila a)
genPila = do
  xs <- listOf arbitrary
  return (foldr apila vacia xs)
 
-- El tipo pila es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Pila a) where
  arbitrary = genPila
 
-- Propiedades
-- ===========
 
-- Las propiedades son
prop_pilas :: Int -> Pila Int -> Bool
prop_pilas x p =
  cima (apila x p) == x &&
  desapila (apila x p) == p &&
  esVacia vacia &&
  not (esVacia (apila x p))
 
-- La comprobación e:
--    λ> quickCheck prop_pilas
--    +++ OK, passed 100 tests.

2.3. Implementación de las pilas mediante sucesiones

La implementación (que usa la librería Data.Sequence) se encuentra en el módulo PilaConSucesiones.hs cuyo contenido es el siguiente:

module TAD.PilaConSucesiones
  (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
 
import Data.Sequence as S
import Test.QuickCheck
 
-- Representación de las pilas mediante sucesiones.
newtype Pila a = P (Seq a)
  deriving Eq
 
-- (escribePila p) es la cadena correspondiente a la pila p. Por
-- ejemplo,
--    escribePila (apila 5 (apila 2 (apila 3 vacia))) == "5 | 2 | 3"
escribePila :: Show a => Pila a -> String
escribePila (P xs) = case viewl xs of
    EmptyL   -> "-"
    x :< xs' -> case viewl xs' of
        EmptyL -> show x
        _      -> show x ++ " | " ++ escribePila (P xs')
 
-- Procedimiento de escritura de pilas.
instance Show a => Show (Pila a) where
  show = escribePila
 
-- Ejemplo de pila:
--    λ> apila 1 (apila 2 (apila 3 vacia))
--    1 | 2 | 3
 
-- vacia es la pila vacía. Por ejemplo,
--    λ> vacia
--    -
vacia   :: Pila a
vacia = P empty
 
-- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por
-- ejemplo,
--    λ> apila 4 (apila 3 (apila 2 (apila 5 vacia)))
--    5 | 2 | 3 | 4
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 (apila 4 (apila 3 (apila 2 (apila 5 vacia))))
--    4
cima :: Pila a -> a
cima (P xs) = case viewl xs of
  EmptyL -> error "cima de la pila vacia"
  x :< _ -> x
 
-- (desapila p) es la pila obtenida suprimiendo la cima de la pila
-- p. Por ejemplo,
--    λ> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))
--    3 | 2 | 5
desapila :: Pila a -> Pila a
desapila (P xs) = case viewl xs of
  EmptyL   -> error "desapila la pila vacia"
  _ :< xs' -> P xs'
 
-- (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
esVacia :: Pila a -> Bool
esVacia (P xs) = S.null xs
 
-- 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|-
--    -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, Num a) => Gen (Pila a)
genPila = do
  xs <- listOf arbitrary
  return (foldr apila vacia xs)
 
-- El tipo pila es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Pila a) where
  arbitrary = genPila
 
-- Propiedades
-- ===========
 
-- Las propiedades son
prop_pilas :: Int -> Pila Int -> Bool
prop_pilas x p =
  cima (apila x p) == x &&
  desapila (apila x p) == p &&
  esVacia vacia &&
  not (esVacia (apila x p))
 
-- La comprobación e:
--    λ> quickCheck prop_pilas
--    +++ OK, passed 100 tests.

3. Las pilas en Python

3.1. El tipo abstracto de las pilas en Python

La implementación se encuentra en el módulo pila.py cuyo contenido es el siguiente:

__all__ = [
    'Pila',
    'vacia',
    'apila',
    'esVacia',
    'cima',
    'desapila',
    'pilaAleatoria'
]
from src.TAD.pilaConListas import (Pila, vacia, apila, esVacia, cima,
                                   desapila, pilaAleatoria)
# from src.TAD.pilaConDeque import (Pila, vacia, apila, esVacia, cima,
#                                   desapila, pilaAleatoria)

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos dos una usando listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

3.2. Implementación de las pilas mediante listas

La implementación se encuentra en el módulo pilaConListas.py en el que se define la clase Pila con los siguientes métodos:

  • apila(x) añade x al principio de la pila.
  • cima() devuelve la cima de la pila.
  • desapila() elimina la cima de la pila.
  • esVacia() se verifica si la pila es vacía.

Por ejemplo,

   >>> p = Pila()
   >>> p
   -
   >>> p.apila(5)
   >>> p.apila(2)
   >>> p.apila(3)
   >>> p.apila(4)
   >>> p
   4 | 3 | 2 | 5
   >>> p.cima()
   4
   >>> p.desapila()
   >>> p
   3 | 2 | 5
   >>> p.esVacia()
   False
   >>> p = Pila()
   >>> p.esVacia()
   True

Además se definen las correspondientes funciones. Por ejemplo,

   >>> vacia()
   -
   >>> apila(4, apila(3, apila(2, apila(5, vacia()))))
   4 | 3 | 2 | 5
   >>> cima(apila(4, apila(3, apila(2, apila(5, vacia())))))
   4
   >>> desapila(apila(4, apila(3, apila(2, apila(5, vacia())))))
   3 | 2 | 5
   >>> esVacia(apila(4, apila(3, apila(2, apila(5, vacia())))))
   False
   >>> esVacia(vacia())
   True

Finalmente, se define un generador aleatorio de pilas y se comprueba que las pilas cumplen las propiedades de su especificación.

__all__ = [
    'Pila',
    'vacia',
    'apila',
    'esVacia',
    'cima',
    'desapila',
    'pilaAleatoria'
]
 
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
A = TypeVar('A')
 
# Clase de las pilas mediante Listas
# ==================================
 
@dataclass
class Pila(Generic[A]):
    _elementos: list[A] = field(default_factory=list)
 
    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos de la pila separados por " | ".
        Si la pila está vacía, devuelve "-".
        """
        if len(self._elementos) == 0:
            return '-'
        return " | ".join(str(x) for x in self._elementos)
 
    def apila(self, x: A) -> None:
        """
        Agrega el elemento x al inicio de la pila.
        """
        self._elementos.insert(0, x)
 
    def esVacia(self) -> bool:
        """
        Verifica si la pila está vacía.
 
        Devuelve True si la pila está vacía, False en caso contrario.
        """
        return not self._elementos
 
    def cima(self) -> A:
        """
        Devuelve el elemento en la cima de la pila.
        """
        return self._elementos[0]
 
    def desapila(self) -> None:
        """
        Elimina el elemento en la cima de la pila.
        """
        self._elementos.pop(0)
 
# Funciones del tipo de las listas
# ================================
 
def vacia() -> Pila[A]:
    """
    Crea y devuelve una pila vacía de tipo A.
    """
    p: Pila[A] = Pila()
    return p
 
def apila(x: A, p: Pila[A]) -> Pila[A]:
    """
    Añade un elemento x al tope de la pila p y devuelve una copia de la
    pila modificada.
    """
    aux = deepcopy(p)
    aux.apila(x)
    return aux
 
def esVacia(p: Pila[A]) -> bool:
    """
    Devuelve True si la pila está vacía, False si no lo está.
    """
    return p.esVacia()
 
def cima(p: Pila[A]) -> A:
    """
    Devuelve el elemento en la cima de la pila p.
    """
    return p.cima()
 
def desapila(p: Pila[A]) -> Pila[A]:
    """
    Elimina el elemento en la cima de la pilla p y devuelve una copia de la
    pila resultante.
    """
    aux = deepcopy(p)
    aux.desapila()
    return aux
 
# Generador de pilas
# ==================
 
def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:
    """
    Genera una estrategia de búsqueda para generar pilas de enteros de
    forma aleatoria.
 
    Utiliza la librería Hypothesis para generar una lista de enteros y
    luego se convierte en una instancia de la clase pila.
    """
    return st.lists(st.integers()).map(Pila)
 
# Comprobación de las propiedades de las pilas
# ============================================
 
# Las propiedades son
@given(p=pilaAleatoria(), x=st.integers())
def test_pila(p: Pila[int], x: int) -> None:
    assert cima(apila(x, p)) == x
    assert desapila(apila(x, p)) == p
    assert esVacia(vacia())
    assert not esVacia(apila(x, p))
 
# La comprobación es
#    > poetry run pytest -q pilaConListas.py
#    1 passed in 0.25s

3.3. Implementación de las pilas mediante deque

La implementación (que usa la librería deque) se encuentra en el módulo pilaConDeque.py y su contenido es el siguiente:

__all__ = [
    'Pila',
    'vacia',
    'apila',
    'esVacia',
    'cima',
    'desapila',
    'pilaAleatoria'
]
 
from collections import deque
from copy import deepcopy
from dataclasses import dataclass, field
from typing import Generic, TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
A = TypeVar('A')
 
# Clase de las pilas mediante listas
# ==================================
 
@dataclass
class Pila(Generic[A]):
    _elementos: deque[A] = field(default_factory=deque)
 
    def __repr__(self) -> str:
        """
        Devuelve una cadena con los elementos de la pila separados por " | ".
        Si la pila está vacía, devuelve "-".
        """
        if len(self._elementos) == 0:
            return '-'
        return ' | '.join(str(x) for x in self._elementos)
 
    def apila(self, x: A) -> None:
        """
        Agrega el elemento x al inicio de la pila.
        """
        self._elementos.appendleft(x)
 
    def esVacia(self) -> bool:
        """
        Verifica si la pila está vacía.
 
        Devuelve True si la pila está vacía, False en caso contrario.
        """
        return len(self._elementos) == 0
 
    def cima(self) -> A:
        """
        Devuelve el elemento en la cima de la pila.
        """
        return self._elementos[0]
 
    def desapila(self) -> None:
        """
        Elimina el elemento en la cima de la pila.
        """
        self._elementos.popleft()
 
# Funciones del tipo de las listas
# ================================
 
def vacia() -> Pila[A]:
    """
    Crea y devuelve una pila vacía de tipo A.
    """
    p: Pila[A] = Pila()
    return p
 
def apila(x: A, p: Pila[A]) -> Pila[A]:
    """
    Añade un elemento x al tope de la pila p y devuelve una copia de la
    pila modificada.
    """
    _aux = deepcopy(p)
    _aux.apila(x)
    return _aux
 
def esVacia(p: Pila[A]) -> bool:
    """
    Devuelve True si la pila está vacía, False si no lo está.
    """
    return p.esVacia()
 
def cima(p: Pila[A]) -> A:
    """
    Devuelve el elemento en la cima de la pila p.
    """
    return p.cima()
 
def desapila(p: Pila[A]) -> Pila[A]:
    """
    Elimina el elemento en la cima de la pilla p y devuelve una copia de la
    pila resultante.
    """
    _aux = deepcopy(p)
    _aux.desapila()
    return _aux
 
# Generador de pilas
# ==================
 
def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:
    """
    Genera una estrategia de búsqueda para generar pilas de enteros de
    forma aleatoria.
 
    Utiliza la librería Hypothesis para generar una lista de enteros y
    luego se convierte en una instancia de la clase pila.
    """
    def _creaPila(elementos: list[int]) -> Pila[int]:
        pila: Pila[int] = vacia()
        pila._elementos.extendleft(elementos)
        return pila
    return st.builds(_creaPila, st.lists(st.integers()))
 
# Comprobación de las propiedades de las pilas
# ============================================
 
# Las propiedades son
@given(p=pilaAleatoria(), x=st.integers())
def test_pila(p: Pila[int], x: int) -> None:
    assert cima(apila(x, p)) == x
    assert desapila(apila(x, p)) == p
    assert esVacia(vacia())
    assert not esVacia(apila(x, p))
 
# La comprobación es
#    > poetry run pytest -q pilaConQueue.py
#    1 passed in 0.25s
Leer más →

Valor de una expresión vectorial

José A. Alonso, ,

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)

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

data ExpV = Vec Int Int
          | Sum ExpV ExpV
          | Mul Int ExpV
  deriving Show
 
-- 1ª solución
-- ===========
 
valorEV1 :: ExpV -> (Int,Int)
valorEV1 (Vec x y)   = (x,y)
valorEV1 (Sum e1 e2) = (x1+x2,y1+y2)
  where (x1,y1) = valorEV1 e1
        (x2,y2) = valorEV1 e2
valorEV1 (Mul n e)   = (n*x,n*y)
  where (x,y) = valorEV1 e
 
-- 2ª solución
-- ===========
 
valorEV2 :: ExpV -> (Int,Int)
valorEV2 (Vec a b)   = (a, b)
valorEV2 (Sum e1 e2) = suma (valorEV2 e1) (valorEV2 e2)
valorEV2 (Mul n e1)  = multiplica n (valorEV2 e1)
 
suma :: (Int,Int) -> (Int,Int) -> (Int,Int)
suma (a,b) (c,d) = (a+c,b+d)
 
multiplica :: Int -> (Int, Int) -> (Int, Int)
multiplica n (a,b) = (n*a,n*b)


Soluciones en Python

from dataclasses import dataclass
 
 
@dataclass
class ExpV:
    pass
 
@dataclass
class Vec(ExpV):
    x: int
    y: int
 
@dataclass
class Sum(ExpV):
    x: ExpV
    y: ExpV
 
@dataclass
class Mul(ExpV):
    x: int
    y: ExpV
 
# 1ª solución
# ===========
 
def valorEV1(e: ExpV) -> tuple[int, int]:
    match e:
        case Vec(x, y):
            return (x, y)
        case Sum(e1, e2):
            x1, y1 = valorEV1(e1)
            x2, y2 = valorEV1(e2)
            return (x1 + x2, y1 + y2)
        case Mul(n, e):
            x, y = valorEV1(e)
            return (n * x, n * y)
    assert False
 
# 2ª solución
# ===========
 
def suma(p: tuple[int, int], q: tuple[int, int]) -> tuple[int, int]:
    a, b = p
    c, d = q
    return (a + c, b + d)
 
def multiplica(n: int, p: tuple[int, int]) -> tuple[int, int]:
    a, b = p
    return (n * a, n * b)
 
def valorEV2(e: ExpV) -> tuple[int, int]:
    match e:
        case Vec(x, y):
            return (x, y)
        case Sum(e1, e2):
            return suma(valorEV2(e1), valorEV2(e2))
        case Mul(n, e):
            return multiplica(n, valorEV2(e))
    assert False
Leer más →