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 |
Por ejemplo, la expresión 2·(a+5)
se representa por
P (C 2) (S (V 'a') (C 5)) |
Definir la función
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 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 |
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) |
Por ejemplo, la expresión
3*x - (x+2)^7 |
se puede definir por
R (P (C 3) X) (E (S X (C 2)) 7) |
Definir la función
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]) |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 |
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 |
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 |
Por ejemplo, la expresión
(7-3)+(2*5) |
se representa por
A S (A R (C 7) (C 3)) (A M (C 2) (C 5)) |
Definir la función
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 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 = (-) |
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 |
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.
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) |
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 |
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() >>> 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 |
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 |
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 |
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 |