PFH: La semana en Exercitium (21 de enero de 2023)

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:

1. Expresiones aritméticas reducibles
2. Máximos valores de una expresión aritmética
3. Valor de expresiones aritméticas generales
4. Valor de una expresión vectorial
5. El tipo abstracto de datos de las pilas

A continuación se muestran las soluciones.

1. Expresiones aritméticas reducibles

Las expresiones aritméticas con variables pueden representarse usando el siguiente tipo de datos

   data Expr = C Int
             | V Char
             | S Expr Expr
             | P Expr Expr

data Expr = C Int

| V Char

| S Expr Expr

| P Expr Expr

Por ejemplo, la expresión 2·(a+5) se representa por

   P (C 2) (S (V 'a') (C 5))

1	P (C 2) (S (V 'a') (C 5))

Definir la función

   reducible :: Expr -> Bool

1	reducible :: Expr -> Bool

tal que reducible a se verifica si a es una expresión reducible; es decir, contiene una operación en la que los dos operandos son números. Por ejemplo,

   reducible (S (C 3) (C 4))             == True
   reducible (S (C 3) (V 'x'))           == False
   reducible (S (C 3) (P (C 4) (C 5)))   == True
   reducible (S (V 'x') (P (C 4) (C 5))) == True
   reducible (S (C 3) (P (V 'x') (C 5))) == False
   reducible (C 3)                       == False
   reducible (V 'x')                     == False

reducible (S (C 3) (C 4)) == True

reducible (S (C 3) (V 'x')) == False

reducible (S (C 3) (P (C 4) (C 5))) == True

reducible (S (V 'x') (P (C 4) (C 5))) == True

reducible (S (C 3) (P (V 'x') (C 5))) == False

reducible (C 3) == False

reducible (V 'x') == False

Soluciones

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

Soluciones en Haskell

data Expr = C Int
          | V Char
          | S Expr Expr
          | P Expr Expr

reducible :: Expr -> Bool
reducible (C _)           = False
reducible (V _)           = False
reducible (S (C _) (C _)) = True
reducible (S a b)         = reducible a || reducible b
reducible (P (C _) (C _)) = True
reducible (P a b)         = reducible a || reducible b

data Expr = C Int

| V Char

| S Expr Expr

| P Expr Expr

reducible :: Expr -> Bool

reducible (C _) = False

reducible (V _) = False

reducible (S (C _) (C _)) = True

reducible (S a b) = reducible a || reducible b

reducible (P (C _) (C _)) = True

reducible (P a b) = reducible a || reducible b

Soluciones en Python

from dataclasses import dataclass


@dataclass
class Expr:
    pass

@dataclass
class C(Expr):
    x: int

@dataclass
class V(Expr):
    x: str

@dataclass
class S(Expr):
    x: Expr
    y: Expr

@dataclass
class P(Expr):
    x: Expr
    y: Expr

def reducible(e: Expr) -> bool:
    match e:
        case C(_):
            return False
        case V(_):
            return False
        case S(C(_), C(_)):
            return True
        case S(a, b):
            return reducible(a) or reducible(b)
        case P(C(_), C(_)):
            return True
        case P(a, b):
            return reducible(a) or reducible(b)
    assert False

from dataclasses import dataclass

@dataclass

class Expr:

pass

@dataclass

class C(Expr):

x: int

@dataclass

class V(Expr):

x: str

@dataclass

class S(Expr):

x: Expr

y: Expr

@dataclass

class P(Expr):

x: Expr

y: Expr

def reducible(e: Expr) -> bool:

match e:

case C(_):

return False

case V(_):

return False

case S(C(_), C(_)):

return True

case S(a, b):

return reducible(a) or reducible(b)

case P(C(_), C(_)):

return True

case P(a, b):

return reducible(a) or reducible(b)

assert False

2. Máximos valores de una expresión aritmética

Las expresiones aritméticas generales se pueden definir usando el siguiente tipo de datos

   data Expr = C Int
             | X
             | S Expr Expr
             | R Expr Expr
             | P Expr Expr
             | E Expr Int
     deriving (Eq, Show)

data Expr = C Int

| X

| S Expr Expr

| R Expr Expr

| P Expr Expr

| E Expr Int

deriving (Eq, Show)

Por ejemplo, la expresión

   3*x - (x+2)^7

1	3*x - (x+2)^7

se puede definir por

   R (P (C 3) X) (E (S X (C 2)) 7)

1	R (P (C 3) X) (E (S X (C 2)) 7)

Definir la función

   maximo :: Expr -> [Int] -> (Int,[Int])

1	maximo :: Expr -> [Int] -> (Int,[Int])

tal que maximo e xs es el par formado por el máximo valor de la expresión e para los puntos de xs y en qué puntos alcanza el máximo. Por ejemplo,

   λ> maximo (E (S (C 10) (P (R (C 1) X) X)) 2) [-3..3]
   (100,[0,1])

1 2	λ> maximo (E (S (C 10) (P (R (C 1) X) X)) 2) [-3..3] (100,[0,1])

Soluciones

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

Soluciones en Haskell

data Expr = C Int
          | X
          | S Expr Expr
          | R Expr Expr
          | P Expr Expr
          | E Expr Int
  deriving (Eq, Show)

maximo :: Expr -> [Int] -> (Int,[Int])
maximo e ns = (m,[n | n <- ns, valor e n == m])
  where m = maximum [valor e n | n <- ns]

valor :: Expr -> Int -> Int
valor (C x) _     = x
valor X     n     = n
valor (S e1 e2) n = valor e1 n + valor e2 n
valor (R e1 e2) n = valor e1 n - valor e2 n
valor (P e1 e2) n = valor e1 n * valor e2 n
valor (E e1 m1) n = valor e1 n ^ m1

data Expr = C Int

| X

| S Expr Expr

| R Expr Expr

| P Expr Expr

| E Expr Int

deriving (Eq, Show)

maximo :: Expr -> [Int] -> (Int,[Int])

maximo e ns = (m,[n | n <- ns, valor e n == m])

where m = maximum [valor e n | n <- ns]

valor :: Expr -> Int -> Int

valor (C x) _ = x

valor X n = n

valor (S e1 e2) n = valor e1 n + valor e2 n

valor (R e1 e2) n = valor e1 n - valor e2 n

valor (P e1 e2) n = valor e1 n * valor e2 n

valor (E e1 m1) n = valor e1 n ^ m1

Soluciones en Python

from dataclasses import dataclass


@dataclass
class Expr:
    pass

@dataclass
class C(Expr):
    x: int

@dataclass
class X(Expr):
    pass

@dataclass
class S(Expr):
    x: Expr
    y: Expr

@dataclass
class R(Expr):
    x: Expr
    y: Expr

@dataclass
class P(Expr):
    x: Expr
    y: Expr

@dataclass
class E(Expr):
    x: Expr
    y: int

def valor(e: Expr, n: int) -> int:
    match e:
        case C(a):
            return a
        case X():
            return n
        case S(e1, e2):
            return valor(e1, n) + valor(e2, n)
        case R(e1, e2):
            return valor(e1, n) - valor(e2, n)
        case P(e1, e2):
            return valor(e1, n) * valor(e2, n)
        case E(e1, m):
            return valor(e1, n) ** m
    assert False

def maximo(e: Expr, ns: list[int]) -> tuple[int, list[int]]:
    m = max((valor(e, n) for n in ns))
    return (m, [n for n in ns if valor(e, n) == m])

from dataclasses import dataclass

@dataclass

class Expr:

pass

@dataclass

class C(Expr):

x: int

@dataclass

class X(Expr):

pass

@dataclass

class S(Expr):

x: Expr

y: Expr

@dataclass

class R(Expr):

x: Expr

y: Expr

@dataclass

class P(Expr):

x: Expr

y: Expr

@dataclass

class E(Expr):

x: Expr

y: int

def valor(e: Expr, n: int) -> int:

match e:

case C(a):

return a

case X():

return n

case S(e1, e2):

return valor(e1, n) + valor(e2, n)

case R(e1, e2):

return valor(e1, n) - valor(e2, n)

case P(e1, e2):

return valor(e1, n) * valor(e2, n)

case E(e1, m):

return valor(e1, n) ** m

assert False

def maximo(e: Expr, ns: list[int]) -> tuple[int, list[int]]:

m = max((valor(e, n) for n in ns))

return (m, [n for n in ns if valor(e, n) == m])

3. Valor de expresiones aritméticas generales

Las operaciones de suma, resta y multiplicación se pueden representar mediante el siguiente tipo de datos

   data Op = S | R | M

1	data Op = S \| R \| M

La expresiones aritméticas con dichas operaciones se pueden representar mediante el siguiente tipo de dato algebraico

   data Expr = C Int
             | A Op Expr Expr

1 2	data Expr = C Int \| A Op Expr Expr

Por ejemplo, la expresión

   (7-3)+(2*5)

1	(7-3)+(2*5)

se representa por

   A S (A R (C 7) (C 3)) (A M (C 2) (C 5))

1	A S (A R (C 7) (C 3)) (A M (C 2) (C 5))

Definir la función

   valor :: Expr -> Int

1	valor :: Expr -> Int

tal que valor e es el valor de la expresión e. Por ejemplo,

   valor (A S (A R (C 7) (C 3)) (A M (C 2) (C 5)))  ==  14
   valor (A M (A R (C 7) (C 3)) (A S (C 2) (C 5)))  ==  28

1 2	valor (A S (A R (C 7) (C 3)) (A M (C 2) (C 5))) == 14 valor (A M (A R (C 7) (C 3)) (A S (C 2) (C 5))) == 28

Soluciones

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

Soluciones en Haskell

data Op = S | R | M

data Expr = C Int
          | A Op Expr Expr

-- 1ª solución
-- ===========

valor :: Expr -> Int
valor (C x)      = x
valor (A o e1 e2) = aplica o (valor e1) (valor e2)
  where aplica :: Op -> Int -> Int -> Int
        aplica S x y = x+y
        aplica R x y = x-y
        aplica M x y = x*y

-- 2ª solución
-- ===========

valor2 :: Expr -> Int
valor2 (C n)    = n
valor2 (A o x y) = sig o (valor2 x) (valor2 y)
  where sig :: Op -> Int -> Int -> Int
        sig S = (+)
        sig M = (*)
        sig R = (-)

data Op = S | R | M

data Expr = C Int

| A Op Expr Expr

-- 1ª solución

-- ===========

valor :: Expr -> Int

valor (C x) = x

valor (A o e1 e2) = aplica o (valor e1) (valor e2)

where aplica :: Op -> Int -> Int -> Int

aplica S x y = x+y

aplica R x y = x-y

aplica M x y = x*y

-- 2ª solución

-- ===========

valor2 :: Expr -> Int

valor2 (C n) = n

valor2 (A o x y) = sig o (valor2 x) (valor2 y)

where sig :: Op -> Int -> Int -> Int

sig S = (+)

sig M = (*)

sig R = (-)

Soluciones en Python

from dataclasses import dataclass
from enum import Enum

Op = Enum('Op', ['S', 'R', 'M'])

@dataclass
class Expr:
    pass

@dataclass
class C(Expr):
    x: int

@dataclass
class A(Expr):
    o: Op
    x: Expr
    y: Expr

def aplica(o: Op, x: int, y: int) -> int:
    match o:
        case Op.S:
            return x + y
        case Op.R:
            return x - y
        case Op.M:
            return x * y
    assert False

def valor(e: Expr) -> int:
    match e:
        case C(x):
            return x
        case A(o, e1, e2):
            return aplica(o, valor(e1), valor(e2))
    assert False

from dataclasses import dataclass

from enum import Enum

Op = Enum('Op', ['S', 'R', 'M'])

@dataclass

class Expr:

pass

@dataclass

class C(Expr):

x: int

@dataclass

class A(Expr):

o: Op

x: Expr

y: Expr

def aplica(o: Op, x: int, y: int) -> int:

match o:

case Op.S:

return x + y

case Op.R:

return x - y

case Op.M:

return x * y

assert False

def valor(e: Expr) -> int:

match e:

case C(x):

return x

case A(o, e1, e2):

return aplica(o, valor(e1), valor(e2))

assert False

4. Valor de una expresión vectorial

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

data ExpV = Vec Int Int

| Sum ExpV ExpV

| Mul Int ExpV

deriving Show

Definir la función

   valorEV :: ExpV -> (Int,Int)

1	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)

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)

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

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

5. El tipo abstracto de datos de las pilas

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

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

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.

100

101

102

103

104

105

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.

100

101

102

103

104

105

106

107

108

109

110

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)

__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)

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()
   >>> print(p)
   -
   >>> p.apila(5)
   >>> p.apila(2)
   >>> p.apila(3)
   >>> p.apila(4)
   >>> print(p)
   4 | 3 | 2 | 5
   >>> p.cima()
   4
   >>> p.desapila()
   >>> print(p)
   3 | 2 | 5
   >>> p.esVacia()
   False
   >>> p = Pila()
   >>> p.esVacia()
   True

>>> p = Pila()

>>> print(p)

>>> p.apila(5)

>>> p.apila(2)

>>> p.apila(3)

>>> p.apila(4)

>>> print(p)

4 | 3 | 2 | 5

>>> p.cima()

>>> p.desapila()

>>> print(p)

3 | 2 | 5

>>> p.esVacia()

False

>>> p = Pila()

>>> p.esVacia()

True

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

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

>>> print(vacia())

>>> print(apila(4, apila(3, apila(2, apila(5, vacia())))))

4 | 3 | 2 | 5

>>> print(cima(apila(4, apila(3, apila(2, apila(5, vacia()))))))

>>> print(desapila(apila(4, apila(3, apila(2, apila(5, vacia()))))))

3 | 2 | 5

>>> print(esVacia(apila(4, apila(3, apila(2, apila(5, vacia()))))))

False

>>> print(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 __str__(self) -> str:
        if len(self._elementos) == 0:
            return '-'
        cadena = ''
        for x in self._elementos[:-1]:
            cadena = cadena + str(x) + ' | '
        return cadena + str(self._elementos[-1])

    def apila(self, x: A) -> None:
        self._elementos.insert(0, x)

    def esVacia(self) -> bool:
        return len(self._elementos) == 0

    def cima(self) -> A:
        return self._elementos[0]

    def desapila(self) -> None:
        self._elementos.pop(0)

# Funciones del tipo de las listas
# ================================

def vacia() -> Pila[A]:
    p: Pila[A] = Pila()
    return p

def apila(x: A, p: Pila[A]) -> Pila[A]:
    aux = deepcopy(p)
    aux.apila(x)
    return aux

def esVacia(p: Pila[A]) -> bool:
    return p.esVacia()

def cima(p: Pila[A]) -> A:
    return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:
    aux = deepcopy(p)
    aux.desapila()
    return aux

# Generador de pilas
# ==================

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:
    def _build_pila(elementos: list[int]) -> Pila[int]:
        pila: Pila[int] = vacia()
        for x in elementos:
            pila = apila(x, pila)
        return pila
    return st.builds(_build_pila, 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 pilaConListas.py
#    1 passed in 0.25s

__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 __str__(self) -> str:

if len(self._elementos) == 0:

return '-'

cadena = ''

for x in self._elementos[:-1]:

cadena = cadena + str(x) + ' | '

return cadena + str(self._elementos[-1])

def apila(self, x: A) -> None:

self._elementos.insert(0, x)

def esVacia(self) -> bool:

return len(self._elementos) == 0

def cima(self) -> A:

return self._elementos[0]

def desapila(self) -> None:

self._elementos.pop(0)

# Funciones del tipo de las listas

# ================================

def vacia() -> Pila[A]:

p: Pila[A] = Pila()

return p

def apila(x: A, p: Pila[A]) -> Pila[A]:

aux = deepcopy(p)

aux.apila(x)

return aux

def esVacia(p: Pila[A]) -> bool:

return p.esVacia()

def cima(p: Pila[A]) -> A:

return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:

aux = deepcopy(p)

aux.desapila()

return aux

# Generador de pilas

# ==================

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:

def _build_pila(elementos: list[int]) -> Pila[int]:

pila: Pila[int] = vacia()

for x in elementos:

pila = apila(x, pila)

return pila

return st.builds(_build_pila, 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 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 __str__(self) -> str:
        if len(self._elementos) == 0:
            return '-'
        cadena = ''
        for x in self._elementos:
            cadena = cadena + str(x) + ' | '
        return cadena[:-3]

    def apila(self, x: A) -> None:
        self._elementos.appendleft(x)

    def esVacia(self) -> bool:
        return len(self._elementos) == 0

    def cima(self) -> A:
        return self._elementos[0]

    def desapila(self) -> None:
        self._elementos.popleft()

# Funciones del tipo de las listas
# ================================

def vacia() -> Pila[A]:
    p: Pila[A] = Pila()
    return p

def apila(x: A, p: Pila[A]) -> Pila[A]:
    _aux = deepcopy(p)
    _aux.apila(x)
    return _aux

def esVacia(p: Pila[A]) -> bool:
    return p.esVacia()

def cima(p: Pila[A]) -> A:
    return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:
    _aux = deepcopy(p)
    _aux.desapila()
    return _aux

# Generador de pilas
# ==================

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:
    def _build_pila(elementos: list[int]) -> Pila[int]:
        pila: Pila[int] = vacia()
        for x in elementos:
            pila = apila(x, pila)
        return pila
    return st.builds(_build_pila, 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

__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 __str__(self) -> str:

if len(self._elementos) == 0:

return '-'

cadena = ''

for x in self._elementos:

cadena = cadena + str(x) + ' | '

return cadena[:-3]

def apila(self, x: A) -> None:

self._elementos.appendleft(x)

def esVacia(self) -> bool:

return len(self._elementos) == 0

def cima(self) -> A:

return self._elementos[0]

def desapila(self) -> None:

self._elementos.popleft()

# Funciones del tipo de las listas

# ================================

def vacia() -> Pila[A]:

p: Pila[A] = Pila()

return p

def apila(x: A, p: Pila[A]) -> Pila[A]:

_aux = deepcopy(p)

_aux.apila(x)

return _aux

def esVacia(p: Pila[A]) -> bool:

return p.esVacia()

def cima(p: Pila[A]) -> A:

return p.cima()

def desapila(p: Pila[A]) -> Pila[A]:

_aux = deepcopy(p)

_aux.desapila()

return _aux

# Generador de pilas

# ==================

def pilaAleatoria() -> st.SearchStrategy[Pila[int]]:

def _build_pila(elementos: list[int]) -> Pila[int]:

pila: Pila[int] = vacia()

for x in elementos:

pila = apila(x, pila)

return pila

return st.builds(_build_pila, 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

1. Expresiones aritméticas reducibles

2. Máximos valores de una expresión aritmética

3. Valor de expresiones aritméticas generales

4. Valor de una expresión vectorial

5. El tipo abstracto de datos de las pilas

1. El tipo abstracto de datos de las pilas

2. Las pilas en Haskell

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

2.2. Implementación de las pilas mediante listas

2.3. Implementación de las pilas mediante sucesiones

3. Las pilas en Python

3.1. El tipo abstracto de las pilas en Python

3.2. Implementación de las pilas mediante listas

3.3. Implementación de las pilas mediante deque

Se puede imprimir o compartir con