{"id":7878,"date":"2023-01-21T07:24:55","date_gmt":"2023-01-21T06:24:55","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7878"},"modified":"2023-01-21T07:27:40","modified_gmt":"2023-01-21T06:27:40","slug":"21-ene-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/21-ene-23\/","title":{"rendered":"PFH: La semana en Exercitium (21 de enero de 2023)"},"content":{"rendered":"<p>Esta semana he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. Expresiones aritm\u00e9ticas reducibles<\/a><\/li>\n<li><a href=\"#ej2\">2. M\u00e1ximos valores de una expresi\u00f3n aritm\u00e9tica<\/a><\/li>\n<li><a href=\"#ej3\">3. Valor de expresiones aritm\u00e9ticas generales<\/a><\/li>\n<li><a href=\"#ej4\">4. Valor de una expresi\u00f3n vectorial<\/a><\/li>\n<li><a href=\"#ej5\">5. El tipo abstracto de datos de las pilas<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. Expresiones aritm\u00e9ticas reducibles<\/h3>\n<p>Las expresiones aritm\u00e9ticas con variables pueden representarse usando el siguiente tipo de datos<\/p>\n<pre lang=\"text\">\n   data Expr = C Int\n             | V Char\n             | S Expr Expr\n             | P Expr Expr\n<\/pre>\n<p>Por ejemplo, la expresi\u00f3n <code>2\u00b7(a+5)<\/code> se representa por<\/p>\n<pre lang=\"text\">\n   P (C 2) (S (V 'a') (C 5))\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   reducible :: Expr -> Bool\n<\/pre>\n<p>tal que <code>reducible a<\/code> se verifica si <code>a<\/code> es una expresi\u00f3n reducible; es decir, contiene una operaci\u00f3n en la que los dos operandos son n\u00fameros. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   reducible (S (C 3) (C 4))             == True\n   reducible (S (C 3) (V 'x'))           == False\n   reducible (S (C 3) (P (C 4) (C 5)))   == True\n   reducible (S (V 'x') (P (C 4) (C 5))) == True\n   reducible (S (C 3) (P (V 'x') (C 5))) == False\n   reducible (C 3)                       == False\n   reducible (V 'x')                     == False\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\ndata Expr = C Int\n          | V Char\n          | S Expr Expr\n          | P Expr Expr\n\nreducible :: Expr -> Bool\nreducible (C _)           = False\nreducible (V _)           = False\nreducible (S (C _) (C _)) = True\nreducible (S a b)         = reducible a || reducible b\nreducible (P (C _) (C _)) = True\nreducible (P a b)         = reducible a || reducible b\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom dataclasses import dataclass\n\n\n@dataclass\nclass Expr:\n    pass\n\n@dataclass\nclass C(Expr):\n    x: int\n\n@dataclass\nclass V(Expr):\n    x: str\n\n@dataclass\nclass S(Expr):\n    x: Expr\n    y: Expr\n\n@dataclass\nclass P(Expr):\n    x: Expr\n    y: Expr\n\ndef reducible(e: Expr) -> bool:\n    match e:\n        case C(_):\n            return False\n        case V(_):\n            return False\n        case S(C(_), C(_)):\n            return True\n        case S(a, b):\n            return reducible(a) or reducible(b)\n        case P(C(_), C(_)):\n            return True\n        case P(a, b):\n            return reducible(a) or reducible(b)\n    assert False\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. M\u00e1ximos valores de una expresi\u00f3n aritm\u00e9tica<\/h3>\n<p>Las expresiones aritm\u00e9ticas generales se pueden definir usando el siguiente tipo de datos<\/p>\n<pre lang=\"text\">\n   data Expr = C Int\n             | X\n             | S Expr Expr\n             | R Expr Expr\n             | P Expr Expr\n             | E Expr Int\n     deriving (Eq, Show)\n<\/pre>\n<p>Por ejemplo, la expresi\u00f3n<\/p>\n<pre lang=\"text\">\n   3*x - (x+2)^7\n<\/pre>\n<p>se puede definir por<\/p>\n<pre lang=\"text\">\n   R (P (C 3) X) (E (S X (C 2)) 7)\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   maximo :: Expr -> [Int] -> (Int,[Int])\n<\/pre>\n<p>tal que <code>maximo e xs<\/code> es el par formado por el m\u00e1ximo valor de la expresi\u00f3n <code>e<\/code> para los puntos de <code>xs<\/code> y en qu\u00e9 puntos alcanza el m\u00e1ximo. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> maximo (E (S (C 10) (P (R (C 1) X) X)) 2) [-3..3]\n   (100,[0,1])\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\ndata Expr = C Int\n          | X\n          | S Expr Expr\n          | R Expr Expr\n          | P Expr Expr\n          | E Expr Int\n  deriving (Eq, Show)\n\nmaximo :: Expr -> [Int] -> (Int,[Int])\nmaximo e ns = (m,[n | n <- ns, valor e n == m])\n  where m = maximum [valor e n | n <- ns]\n\nvalor :: Expr -> Int -> Int\nvalor (C x) _     = x\nvalor X     n     = n\nvalor (S e1 e2) n = valor e1 n + valor e2 n\nvalor (R e1 e2) n = valor e1 n - valor e2 n\nvalor (P e1 e2) n = valor e1 n * valor e2 n\nvalor (E e1 m1) n = valor e1 n ^ m1\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom dataclasses import dataclass\n\n\n@dataclass\nclass Expr:\n    pass\n\n@dataclass\nclass C(Expr):\n    x: int\n\n@dataclass\nclass X(Expr):\n    pass\n\n@dataclass\nclass S(Expr):\n    x: Expr\n    y: Expr\n\n@dataclass\nclass R(Expr):\n    x: Expr\n    y: Expr\n\n@dataclass\nclass P(Expr):\n    x: Expr\n    y: Expr\n\n@dataclass\nclass E(Expr):\n    x: Expr\n    y: int\n\ndef valor(e: Expr, n: int) -> int:\n    match e:\n        case C(a):\n            return a\n        case X():\n            return n\n        case S(e1, e2):\n            return valor(e1, n) + valor(e2, n)\n        case R(e1, e2):\n            return valor(e1, n) - valor(e2, n)\n        case P(e1, e2):\n            return valor(e1, n) * valor(e2, n)\n        case E(e1, m):\n            return valor(e1, n) ** m\n    assert False\n\ndef maximo(e: Expr, ns: list[int]) -> tuple[int, list[int]]:\n    m = max((valor(e, n) for n in ns))\n    return (m, [n for n in ns if valor(e, n) == m])\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Valor de expresiones aritm\u00e9ticas generales<\/h3>\n<p>Las operaciones de suma, resta y  multiplicaci\u00f3n se pueden representar mediante el siguiente tipo de datos<\/p>\n<pre lang=\"text\">\n   data Op = S | R | M\n<\/pre>\n<p>La expresiones aritm\u00e9ticas con dichas operaciones se pueden representar mediante el siguiente tipo de dato algebraico<\/p>\n<pre lang=\"text\">\n   data Expr = C Int\n             | A Op Expr Expr\n<\/pre>\n<p>Por ejemplo, la expresi\u00f3n<\/p>\n<pre lang=\"text\">\n   (7-3)+(2*5)\n<\/pre>\n<p>se representa por<\/p>\n<pre lang=\"text\">\n   A S (A R (C 7) (C 3)) (A M (C 2) (C 5))\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   valor :: Expr -> Int\n<\/pre>\n<p>tal que <code>valor e<\/code> es el valor de la expresi\u00f3n <code>e<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   valor (A S (A R (C 7) (C 3)) (A M (C 2) (C 5)))  ==  14\n   valor (A M (A R (C 7) (C 3)) (A S (C 2) (C 5)))  ==  28\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\ndata Op = S | R | M\n\ndata Expr = C Int\n          | A Op Expr Expr\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nvalor :: Expr -> Int\nvalor (C x)      = x\nvalor (A o e1 e2) = aplica o (valor e1) (valor e2)\n  where aplica :: Op -> Int -> Int -> Int\n        aplica S x y = x+y\n        aplica R x y = x-y\n        aplica M x y = x*y\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nvalor2 :: Expr -> Int\nvalor2 (C n)    = n\nvalor2 (A o x y) = sig o (valor2 x) (valor2 y)\n  where sig :: Op -> Int -> Int -> Int\n        sig S = (+)\n        sig M = (*)\n        sig R = (-)\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom dataclasses import dataclass\nfrom enum import Enum\n\nOp = Enum('Op', ['S', 'R', 'M'])\n\n@dataclass\nclass Expr:\n    pass\n\n@dataclass\nclass C(Expr):\n    x: int\n\n@dataclass\nclass A(Expr):\n    o: Op\n    x: Expr\n    y: Expr\n\ndef aplica(o: Op, x: int, y: int) -> int:\n    match o:\n        case Op.S:\n            return x + y\n        case Op.R:\n            return x - y\n        case Op.M:\n            return x * y\n    assert False\n\ndef valor(e: Expr) -> int:\n    match e:\n        case C(x):\n            return x\n        case A(o, e1, e2):\n            return aplica(o, valor(e1), valor(e2))\n    assert False\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Valor de una expresi\u00f3n vectorial<\/h3>\n<p>Se consideran las expresiones vectoriales formadas por un vector, la suma de dos expresiones vectoriales o el producto de un entero por una expresi\u00f3n vectorial. El siguiente tipo de dato define las expresiones vectoriales<\/p>\n<pre lang=\"text\">\n   data ExpV = Vec Int Int\n             | Sum ExpV ExpV\n             | Mul Int ExpV\n     deriving Show\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   valorEV :: ExpV -> (Int,Int)\n<\/pre>\n<p>tal que <code>valorEV e<\/code> es el valorEV de la expresi\u00f3n vectorial <code>e<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   valorEV (Vec 1 2)                                  ==  (1,2)\n   valorEV (Sum (Vec 1 2) (Vec 3 4))                  ==  (4,6)\n   valorEV (Mul 2 (Vec 3 4))                          ==  (6,8)\n   valorEV (Mul 2 (Sum (Vec 1 2 ) (Vec 3 4)))         ==  (8,12)\n   valorEV (Sum (Mul 2 (Vec 1 2)) (Mul 2 (Vec 3 4)))  ==  (8,12)\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\ndata ExpV = Vec Int Int\n          | Sum ExpV ExpV\n          | Mul Int ExpV\n  deriving Show\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nvalorEV1 :: ExpV -> (Int,Int)\nvalorEV1 (Vec x y)   = (x,y)\nvalorEV1 (Sum e1 e2) = (x1+x2,y1+y2)\n  where (x1,y1) = valorEV1 e1\n        (x2,y2) = valorEV1 e2\nvalorEV1 (Mul n e)   = (n*x,n*y)\n  where (x,y) = valorEV1 e\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nvalorEV2 :: ExpV -> (Int,Int)\nvalorEV2 (Vec a b)   = (a, b)\nvalorEV2 (Sum e1 e2) = suma (valorEV2 e1) (valorEV2 e2)\nvalorEV2 (Mul n e1)  = multiplica n (valorEV2 e1)\n\nsuma :: (Int,Int) -> (Int,Int) -> (Int,Int)\nsuma (a,b) (c,d) = (a+c,b+d)\n\nmultiplica :: Int -> (Int, Int) -> (Int, Int)\nmultiplica n (a,b) = (n*a,n*b)\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom dataclasses import dataclass\n\n\n@dataclass\nclass ExpV:\n    pass\n\n@dataclass\nclass Vec(ExpV):\n    x: int\n    y: int\n\n@dataclass\nclass Sum(ExpV):\n    x: ExpV\n    y: ExpV\n\n@dataclass\nclass Mul(ExpV):\n    x: int\n    y: ExpV\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef valorEV1(e: ExpV) -> tuple[int, int]:\n    match e:\n        case Vec(x, y):\n            return (x, y)\n        case Sum(e1, e2):\n            x1, y1 = valorEV1(e1)\n            x2, y2 = valorEV1(e2)\n            return (x1 + x2, y1 + y2)\n        case Mul(n, e):\n            x, y = valorEV1(e)\n            return (n * x, n * y)\n    assert False\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef suma(p: tuple[int, int], q: tuple[int, int]) -> tuple[int, int]:\n    a, b = p\n    c, d = q\n    return (a + c, b + d)\n\ndef multiplica(n: int, p: tuple[int, int]) -> tuple[int, int]:\n    a, b = p\n    return (n * a, n * b)\n\ndef valorEV2(e: ExpV) -> tuple[int, int]:\n    match e:\n        case Vec(x, y):\n            return (x, y)\n        case Sum(e1, e2):\n            return suma(valorEV2(e1), valorEV2(e2))\n        case Mul(n, e):\n            return multiplica(n, valorEV2(e))\n    assert False\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. El tipo abstracto de datos de las pilas<\/h3>\n<h4>1. El tipo abstracto de datos de las pilas<\/h4>\n<p>Una pila es una estructura de datos, caracterizada por ser una secuencia de elementos en la que las operaciones de inserci\u00f3n y extracci\u00f3n se realizan por el mismo extremo.<\/p>\n<p>Las operaciones que definen a tipo abstracto de datos (TAD) de las pilas (cuyos elementos son del tipo a) son las siguientes:<\/p>\n<pre lang=\"text\">\n   vacia    :: Pila a\n   apila    :: a -> Pila a -> Pila a\n   cima     :: Pila a -> a\n   desapila :: Pila a -> Pila a\n   esVacia  :: Pila a -> Bool\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>vacia es la pila vac\u00eda.<\/li>\n<li>(apila x p) es la pila obtenida a\u00f1adiendo x al principio de p.<\/li>\n<li>(cima p) es la cima de la pila p.<\/li>\n<li>(desapila p) es la pila obtenida suprimiendo la cima de p.<\/li>\n<li>(esVacia p) se verifica si p es la pila vac\u00eda.<\/li>\n<\/ul>\n<p>Las operaciones tienen que verificar las siguientes propiedades:<\/p>\n<ul>\n<li>cima(apila(x, p) == x<\/li>\n<li>desapila(apila(x, p)) == p<\/li>\n<li>esVacia(vacia)<\/li>\n<li>not esVacia(apila(x, p))<\/li>\n<\/ul>\n<h4>2. Las pilas en Haskell<\/h4>\n<h5>2.1. El tipo abstracto de datos de las pilas en Haskell<\/h5>\n<p>El TAD de las pilas se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3ZGUVzT\">Pila.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.Pila\n  (Pila,\n   vacia,      -- Pila a\n   apila,      -- a -> Pila a -> Pila a\n   cima,       -- Pila a -> a\n   desapila,   -- Pila a -> Pila a\n   esVacia,    -- Pila a -> Bool\n   escribePila -- Show a => Pila a -> String\n  ) where\n\nimport TAD.PilaConListas\n-- import TAD.PilaConSucesiones\n<\/pre>\n<p>Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos dos una usando listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descoment\u00e1ndola y comentando las otras.<\/p>\n<h5>2.2. Implementaci\u00f3n de las pilas mediante listas<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3HdYQwM\">PilaConListas.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.PilaConListas\n  (Pila,\n   vacia,      -- Pila a\n   apila,      -- a -> Pila a -> Pila a\n   cima,       -- Pila a -> a\n   desapila,   -- Pila a -> Pila a\n   esVacia,    -- Pila a -> Bool\n   escribePila -- Show a => Pila a -> String\n  ) where\n\nimport Test.QuickCheck\n\n-- Representaci\u00f3n de las pilas mediante listas.\nnewtype Pila a = P [a]\n  deriving Eq\n\n-- (escribePila p) es la cadena correspondiente a la pila p. Por\n-- ejemplo,\n--    escribePila (apila 5 (apila 2 (apila 3 vacia))) == \"5 | 2 | 3\"\nescribePila :: Show a => Pila a -> String\nescribePila (P [])     = \"-\"\nescribePila (P [x])    = show x\nescribePila (P (x:xs)) = show x ++ \" | \" ++ escribePila (P xs)\n\n-- Procedimiento de escritura de pilas.\ninstance Show a => Show (Pila a) where\n  show = escribePila\n\n-- Ejemplo de pila:\n--    \u03bb> apila 1 (apila 2 (apila 3 vacia))\n--    1 | 2 | 3\n\n-- vacia es la pila vac\u00eda. Por ejemplo,\n--    \u03bb> vacia\n--    -\nvacia   :: Pila a\nvacia = P []\n\n-- (apila x p) es la pila obtenida a\u00f1adiendo x encima de la pila p. Por\n-- ejemplo,\n--    \u03bb> apila 4 (apila 3 (apila 2 (apila 5 vacia)))\n--    4 | 3 | 2 | 5\napila :: a -> Pila a -> Pila a\napila x (P xs) = P (x:xs)\n\n-- (cima p) es la cima de la pila p. Por ejemplo,\n--    \u03bb> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia))))\n--    4\ncima :: Pila a -> a\ncima (P [])    = error \"cima de la pila vacia\"\ncima (P (x:_)) = x\n\n-- (desapila p) es la pila obtenida suprimiendo la cima de la pila\n-- p. Por ejemplo,\n--    \u03bb> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))\n--    3 | 2 | 5\ndesapila :: Pila a -> Pila a\ndesapila (P [])     = error \"desapila la pila vacia\"\ndesapila (P (_:xs)) = P  xs\n\n-- (esVacia p) se verifica si p es la pila vac\u00eda. Por ejemplo,\n--    esVacia (apila 1 (apila 2 (apila 3 vacia))) ==  False\n--    esVacia vacia                               ==  True\nesVacia :: Pila a -> Bool\nesVacia (P xs) = null xs\n\n-- Generador de pilas                                          --\n-- ==================\n\n-- genPila es un generador de pilas. Por ejemplo,\n--    \u03bb> sample genPila\n--    -\n--    0|0|-\n--    -\n--    -6|4|-3|3|0|-\n--    -\n--    9|5|-1|-3|0|-8|-5|-7|2|-\n--    -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-\n--    2|-14|-5|2|-\n--    5|9|-\n--    -1|-14|5|-\n--    6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-\ngenPila :: (Arbitrary a, Num a) => Gen (Pila a)\ngenPila = do\n  xs <- listOf arbitrary\n  return (foldr apila vacia xs)\n\n-- El tipo pila es una instancia del arbitrario.\ninstance (Arbitrary a, Num a) => Arbitrary (Pila a) where\n  arbitrary = genPila\n\n-- Propiedades\n-- ===========\n\n-- Las propiedades son\nprop_pilas :: Int -> Pila Int -> Bool\nprop_pilas x p =\n  cima (apila x p) == x &&\n  desapila (apila x p) == p &&\n  esVacia vacia &&\n  not (esVacia (apila x p))\n\n-- La comprobaci\u00f3n e:\n--    \u03bb> quickCheck prop_pilas\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h5>2.3. Implementaci\u00f3n de las pilas mediante sucesiones<\/h5>\n<p>La implementaci\u00f3n (que usa la librer\u00eda <a href=\"https:\/\/bit.ly\/3ZKMm71\">Data.Sequence<\/a>) se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3ZGVvO5\">PilaConSucesiones.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.PilaConSucesiones\n  (Pila,\n   vacia,      -- Pila a\n   apila,      -- a -> Pila a -> Pila a\n   cima,       -- Pila a -> a\n   desapila,   -- Pila a -> Pila a\n   esVacia,    -- Pila a -> Bool\n   escribePila -- Show a => Pila a -> String\n  ) where\n\nimport Data.Sequence as S\nimport Test.QuickCheck\n\n-- Representaci\u00f3n de las pilas mediante sucesiones.\nnewtype Pila a = P (Seq a)\n  deriving Eq\n\n-- (escribePila p) es la cadena correspondiente a la pila p. Por\n-- ejemplo,\n--    escribePila (apila 5 (apila 2 (apila 3 vacia))) == \"5 | 2 | 3\"\nescribePila :: Show a => Pila a -> String\nescribePila (P xs) = case viewl xs of\n    EmptyL   -> \"-\"\n    x :< xs' -> case viewl xs' of\n        EmptyL -> show x\n        _      -> show x ++ \" | \" ++ escribePila (P xs')\n\n-- Procedimiento de escritura de pilas.\ninstance Show a => Show (Pila a) where\n  show = escribePila\n\n-- Ejemplo de pila:\n--    \u03bb> apila 1 (apila 2 (apila 3 vacia))\n--    1 | 2 | 3\n\n-- vacia es la pila vac\u00eda. Por ejemplo,\n--    \u03bb> vacia\n--    -\nvacia   :: Pila a\nvacia = P empty\n\n-- (apila x p) es la pila obtenida a\u00f1adiendo x encima de la pila p. Por\n-- ejemplo,\n--    \u03bb> apila 4 (apila 3 (apila 2 (apila 5 vacia)))\n--    5 | 2 | 3 | 4\napila :: a -> Pila a -> Pila a\napila x (P xs) = P (x <| xs)\n\n-- (cima p) es la cima de la pila p. Por ejemplo,\n--    \u03bb> cima (apila 4 (apila 3 (apila 2 (apila 5 vacia))))\n--    4\ncima :: Pila a -> a\ncima (P xs) = case viewl xs of\n  EmptyL -> error \"cima de la pila vacia\"\n  x :< _ -> x\n\n-- (desapila p) es la pila obtenida suprimiendo la cima de la pila\n-- p. Por ejemplo,\n--    \u03bb> desapila (apila 4 (apila 3 (apila 2 (apila 5 vacia))))\n--    3 | 2 | 5\ndesapila :: Pila a -> Pila a\ndesapila (P xs) = case viewl xs of\n  EmptyL   -> error \"desapila la pila vacia\"\n  _ :< xs' -> P xs'\n\n-- (esVacia p) se verifica si p es la pila vac\u00eda. Por ejemplo,\n--    esVacia (apila 1 (apila 2 (apila 3 vacia))) ==  False\n--    esVacia vacia                               ==  True\nesVacia :: Pila a -> Bool\nesVacia (P xs) = S.null xs\n\n-- Generador de pilas                                          --\n-- ==================\n\n-- genPila es un generador de pilas. Por ejemplo,\n--    \u03bb> sample genPila\n--    -\n--    0|0|-\n--    -\n--    -6|4|-3|3|0|-\n--    -\n--    9|5|-1|-3|0|-8|-5|-7|2|-\n--    -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-\n--    2|-14|-5|2|-\n--    5|9|-\n--    -1|-14|5|-\n--    6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-\ngenPila :: (Arbitrary a, Num a) => Gen (Pila a)\ngenPila = do\n  xs <- listOf arbitrary\n  return (foldr apila vacia xs)\n\n-- El tipo pila es una instancia del arbitrario.\ninstance (Arbitrary a, Num a) => Arbitrary (Pila a) where\n  arbitrary = genPila\n\n-- Propiedades\n-- ===========\n\n-- Las propiedades son\nprop_pilas :: Int -> Pila Int -> Bool\nprop_pilas x p =\n  cima (apila x p) == x &&\n  desapila (apila x p) == p &&\n  esVacia vacia &&\n  not (esVacia (apila x p))\n\n-- La comprobaci\u00f3n e:\n--    \u03bb> quickCheck prop_pilas\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>3. Las pilas en Python<\/h4>\n<h5>3.1. El tipo abstracto de las pilas en Python<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3iHZyJm\">pila.py<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"python\">\n__all__ = [\n    'Pila',\n    'vacia',\n    'apila',\n    'esVacia',\n    'cima',\n    'desapila',\n    'pilaAleatoria'\n]\nfrom src.TAD.pilaConListas import (Pila, vacia, apila, esVacia, cima,\n                                   desapila, pilaAleatoria)\n# from src.TAD.pilaConDeque import (Pila, vacia, apila, esVacia, cima,\n#                                   desapila, pilaAleatoria)\n<\/pre>\n<p>Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos dos una usando listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descoment\u00e1ndola y comentando las otras.<\/p>\n<h5>3.2. Implementaci\u00f3n de las pilas mediante listas<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3VVt8by\">pilaConListas.py<\/a> en el que se define la clase Pila con los siguientes m\u00e9todos:<\/p>\n<ul>\n<li>apila(x) a\u00f1ade x al principio de la pila.<\/li>\n<li>cima() devuelve la cima de la pila.<\/li>\n<li>desapila() elimina la cima de la pila.<\/li>\n<li>esVacia() se verifica si la pila es vac\u00eda.<\/li>\n<\/ul>\n<p>Por ejemplo,<\/p>\n<pre lang=\"text\">\n   >>> p = Pila()\n   >>> print(p)\n   -\n   >>> p.apila(5)\n   >>> p.apila(2)\n   >>> p.apila(3)\n   >>> p.apila(4)\n   >>> print(p)\n   4 | 3 | 2 | 5\n   >>> p.cima()\n   4\n   >>> p.desapila()\n   >>> print(p)\n   3 | 2 | 5\n   >>> p.esVacia()\n   False\n   >>> p = Pila()\n   >>> p.esVacia()\n   True\n<\/pre>\n<p>Adem\u00e1s se definen las correspondientes funciones. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   >>> print(vacia())\n   -\n   >>> print(apila(4, apila(3, apila(2, apila(5, vacia())))))\n   4 | 3 | 2 | 5\n   >>> print(cima(apila(4, apila(3, apila(2, apila(5, vacia()))))))\n   4\n   >>> print(desapila(apila(4, apila(3, apila(2, apila(5, vacia()))))))\n   3 | 2 | 5\n   >>> print(esVacia(apila(4, apila(3, apila(2, apila(5, vacia()))))))\n   False\n   >>> print(esVacia(vacia()))\n   True\n<\/pre>\n<p>Finalmente, se define un generador aleatorio de pilas y se comprueba que las pilas cumplen las propiedades de su especificaci\u00f3n.<\/p>\n<pre lang=\"python\">\n__all__ = [\n    'Pila',\n    'vacia',\n    'apila',\n    'esVacia',\n    'cima',\n    'desapila',\n    'pilaAleatoria'\n]\n\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A')\n\n# Clase de las pilas mediante Listas\n# ==================================\n\n@dataclass\nclass Pila(Generic[A]):\n    _elementos: list[A] = field(default_factory=list)\n\n    def __str__(self) -> str:\n        if len(self._elementos) == 0:\n            return '-'\n        cadena = ''\n        for x in self._elementos[:-1]:\n            cadena = cadena + str(x) + ' | '\n        return cadena + str(self._elementos[-1])\n\n    def apila(self, x: A) -> None:\n        self._elementos.insert(0, x)\n\n    def esVacia(self) -> bool:\n        return len(self._elementos) == 0\n\n    def cima(self) -> A:\n        return self._elementos[0]\n\n    def desapila(self) -> None:\n        self._elementos.pop(0)\n\n# Funciones del tipo de las listas\n# ================================\n\ndef vacia() -> Pila[A]:\n    p: Pila[A] = Pila()\n    return p\n\ndef apila(x: A, p: Pila[A]) -> Pila[A]:\n    aux = deepcopy(p)\n    aux.apila(x)\n    return aux\n\ndef esVacia(p: Pila[A]) -> bool:\n    return p.esVacia()\n\ndef cima(p: Pila[A]) -> A:\n    return p.cima()\n\ndef desapila(p: Pila[A]) -> Pila[A]:\n    aux = deepcopy(p)\n    aux.desapila()\n    return aux\n\n# Generador de pilas\n# ==================\n\ndef pilaAleatoria() -> st.SearchStrategy[Pila[int]]:\n    def _build_pila(elementos: list[int]) -> Pila[int]:\n        pila: Pila[int] = vacia()\n        for x in elementos:\n            pila = apila(x, pila)\n        return pila\n    return st.builds(_build_pila, st.lists(st.integers()))\n\n# Comprobaci\u00f3n de las propiedades de las pilas\n# ============================================\n\n# Las propiedades son\n@given(p=pilaAleatoria(), x=st.integers())\ndef test_pila(p: Pila[int], x: int) -> None:\n    assert cima(apila(x, p)) == x\n    assert desapila(apila(x, p)) == p\n    assert esVacia(vacia())\n    assert not esVacia(apila(x, p))\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q pilaConListas.py\n#    1 passed in 0.25s\n<\/pre>\n<h5>3.3. Implementaci\u00f3n de las pilas mediante deque<\/h5>\n<p>La implementaci\u00f3n (que usa la librer\u00eda <a href=\"https:\/\/bit.ly\/3CYKWw6\">deque<\/a>) se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3iQIwsg\">pilaConDeque.py<\/a> y su contenido es el siguiente:<\/p>\n<pre lang=\"python\">\n__all__ = [\n    'Pila',\n    'vacia',\n    'apila',\n    'esVacia',\n    'cima',\n    'desapila',\n    'pilaAleatoria'\n]\n\nfrom collections import deque\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A')\n\n# Clase de las pilas mediante Listas\n# ==================================\n\n@dataclass\nclass Pila(Generic[A]):\n    _elementos: deque[A] = field(default_factory=deque)\n\n    def __str__(self) -> str:\n        if len(self._elementos) == 0:\n            return '-'\n        cadena = ''\n        for x in self._elementos:\n            cadena = cadena + str(x) + ' | '\n        return cadena[:-3]\n\n    def apila(self, x: A) -> None:\n        self._elementos.appendleft(x)\n\n    def esVacia(self) -> bool:\n        return len(self._elementos) == 0\n\n    def cima(self) -> A:\n        return self._elementos[0]\n\n    def desapila(self) -> None:\n        self._elementos.popleft()\n\n# Funciones del tipo de las listas\n# ================================\n\ndef vacia() -> Pila[A]:\n    p: Pila[A] = Pila()\n    return p\n\ndef apila(x: A, p: Pila[A]) -> Pila[A]:\n    _aux = deepcopy(p)\n    _aux.apila(x)\n    return _aux\n\ndef esVacia(p: Pila[A]) -> bool:\n    return p.esVacia()\n\ndef cima(p: Pila[A]) -> A:\n    return p.cima()\n\ndef desapila(p: Pila[A]) -> Pila[A]:\n    _aux = deepcopy(p)\n    _aux.desapila()\n    return _aux\n\n# Generador de pilas\n# ==================\n\ndef pilaAleatoria() -> st.SearchStrategy[Pila[int]]:\n    def _build_pila(elementos: list[int]) -> Pila[int]:\n        pila: Pila[int] = vacia()\n        for x in elementos:\n            pila = apila(x, pila)\n        return pila\n    return st.builds(_build_pila, st.lists(st.integers()))\n\n# Comprobaci\u00f3n de las propiedades de las pilas\n# ============================================\n\n# Las propiedades son\n@given(p=pilaAleatoria(), x=st.integers())\ndef test_pila(p: Pila[int], x: int) -> None:\n    assert cima(apila(x, p)) == x\n    assert desapila(apila(x, p)) == p\n    assert esVacia(vacia())\n    assert not esVacia(apila(x, p))\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q pilaConQueue.py\n#    1 passed in 0.25s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. Expresiones aritm\u00e9ticas reducibles 2. M\u00e1ximos valores de una expresi\u00f3n aritm\u00e9tica 3. Valor de expresiones aritm\u00e9ticas generales 4. Valor de una expresi\u00f3n vectorial 5. El tipo abstracto de datos de las pilas A continuaci\u00f3n se muestran las soluciones.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[337],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7878"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=7878"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7878\/revisions"}],"predecessor-version":[{"id":7880,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7878\/revisions\/7880"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7878"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7878"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7878"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}