{"id":7890,"date":"2023-02-11T08:22:41","date_gmt":"2023-02-11T07:22:41","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7890"},"modified":"2023-02-11T08:25:24","modified_gmt":"2023-02-11T07:25:24","slug":"11-feb-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/11-feb-23\/","title":{"rendered":"PFH: La semana en Exercitium (11 de febrero 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. TAD de las pilas: M\u00e1ximo elemento de una pila<\/a><\/li>\n<li><a href=\"#ej2\">2. El tipo abstracto de datos de las colas<\/a><\/li>\n<li><a href=\"#ej3\">3. TAD de las colas: Transformaciones entre colas y listas<\/a><\/li>\n<li><a href=\"#ej4\">4. TAD de las colas: \u00daltimo elemento<\/a><\/li>\n<li><a href=\"#ej5\">5. TAD de las colas: Longitud de una cola<\/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. TAD de las pilas: M\u00e1ximo elemento de una pila<\/h3>\n<p>Utilizando el <a href=\"https:\/\/bit.ly\/3GTToyK\">tipo abstracto de datos de las pilas<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   maxPila :: Ord a => Pila a -> a\n<\/pre>\n<p>tal que <code>maxPila p<\/code> sea el mayor de los elementos de la pila <code>p<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> maxPila (apila 3 (apila 5 (apila 1 vacia)))\n   5\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\">\nimport TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)\nimport Transformaciones_pilas_listas (pilaAlista)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmaxPila1 :: Ord a => Pila a -> a\nmaxPila1 p\n  | esVacia dp = cp\n  | otherwise  = max cp (maxPila1 dp)\n  where cp = cima p\n        dp = desapila p\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- Se usar\u00e1 la funci\u00f3n pilaAlista del ejercicio\n-- \"Transformaciones entre pilas y listas\" que se encuentra en\n-- https:\/\/bit.ly\/3ZHewQ8\n\nmaxPila2 :: Ord a => Pila a -> a\nmaxPila2 =\n  maximum . pilaAlista\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_maxPila :: Pila Int -> Property\nprop_maxPila p =\n  not (esVacia p) ==> maxPila1 p == maxPila2 p\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_maxPila\n--    +++ OK, passed 100 tests; 17 discarded.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom copy import deepcopy\nfrom typing import TypeVar\n\nfrom hypothesis import assume, given\n\nfrom src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,\n                          vacia)\nfrom src.transformaciones_pilas_listas import pilaAlista\n\nA = TypeVar('A', int, float, str)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef maxPila1(p: Pila[A]) -> A:\n    cp = cima(p)\n    dp = desapila(p)\n    if esVacia(dp):\n        return cp\n    return max(cp, maxPila1(dp))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# Se usar\u00e1 la funci\u00f3n pilaAlista del ejercicio\n# \"Transformaciones entre pilas y listas\" que se encuentra en\n# https:\/\/bit.ly\/3ZHewQ8\n\ndef maxPila2(p: Pila[A]) -> A:\n    return max(pilaAlista(p))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef maxPila3Aux(p: Pila[A]) -> A:\n    cp = p.cima()\n    p.desapila()\n    if esVacia(p):\n        return cp\n    return max(cp, maxPila3Aux(p))\n\ndef maxPila3(p: Pila[A]) -> A:\n    q = deepcopy(p)\n    return maxPila3Aux(q)\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef maxPila4Aux(p: Pila[A]) -> A:\n    r = p.cima()\n    while not esVacia(p):\n        cp = p.cima()\n        if cp > r:\n            r = cp\n        p.desapila()\n    return r\n\ndef maxPila4(p: Pila[A]) -> A:\n    q = deepcopy(p)\n    return maxPila4Aux(q)\n\n# Comprobaci\u00f3n de equivalencia de las definiciones\n# ================================================\n\n# La propiedad es\n@given(p=pilaAleatoria())\ndef test_maxPila(p: Pila[int]) -> None:\n    assume(not esVacia(p))\n    r = maxPila1(p)\n    assert maxPila2(p) == r\n    assert maxPila3(p) == r\n    assert maxPila4(p) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q maxPila.py\n#    1 passed in 0.25s\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. El tipo abstracto de datos de las colas<\/h3>\n<h4>2.1. El tipo abstracto de datos de las colas<\/h4>\n<p>Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operaci\u00f3n de inserci\u00f3n se realiza por un extremo (el posterior o final) y la operaci\u00f3n de extracci\u00f3n por el otro (el anterior o frente).<\/p>\n<p>Las operaciones que definen a tipo abstracto de datos (TAD) de las colas (cuyos elementos son del tipo a) son las siguientes:<\/p>\n<pre lang=\"text\">\n   vacia   :: Cola a\n   inserta :: a -> Cola a -> Cola a\n   primero :: Cola a -> a\n   resto   :: Cola a -> Cola a\n   esVacia :: Cola a -> Bool\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>vacia es la cola vac\u00eda.<\/li>\n<li>(inserta x c) es la cola obtenida a\u00f1adiendo x al final de c.<\/li>\n<li>(primero c) es el primero de la cola c.<\/li>\n<li>(resto c) es la cola obtenida eliminando el primero de c.<\/li>\n<li>(esVacia c) se verifica si c es la cola vac\u00eda.<\/li>\n<\/ul>\n<p>Las operaciones tienen que verificar las siguientes propiedades:<\/p>\n<ul>\n<li>primero (inserta x vacia) == x<\/li>\n<li>Si c es una cola no vac\u00eda, entonces primero (inserta x c) == primero c,<\/li>\n<li>resto (inserta x vacia) == vacia<\/li>\n<li>Si c es una cola no vac\u00eda, entonces resto (inserta x c) == inserta x (resto c)<\/li>\n<li>esVacia vacia<\/li>\n<li>not (esVacia (inserta x c))<\/li>\n<\/ul>\n<h4>2.2. Las colas en Haskell<\/h4>\n<h5>2.2.1. El tipo abstracto de datos de las colas en Haskell<\/h5>\n<p>El TAD de las colas se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3kBlh60\">Cola.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.Cola\n  (Cola,\n   vacia,      -- Cola a\n   inserta,    -- a -> Cola a -> Cola a\n   primero,    -- Cola a -> a\n   resto,      -- Cola a -> Cola a\n   esVacia,    -- Cola a -> Bool\n  ) where\n\nimport TAD.ColaConListas\n-- import TAD.ColaConDosListas\n-- import TAD.ColaConSucesiones\n<\/pre>\n<p>Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos tres: una usando listas, otra usando pares de listas y otra usando sucesiones. Hay que elegir la que se desee utilizar, descoment\u00e1ndola y comentando las otras.<\/p>\n<h5>2.2.2. Implementaci\u00f3n de las colas mediante listas<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3HdYQwM\">ColaConListas.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\n{-# LANGUAGE FlexibleInstances #-}\n{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}\n\nmodule TAD.ColaConListas\n  (Cola,\n   vacia,   -- Cola a\n   inserta, -- a -> Cola a -> Cola a\n   primero, -- Cola a -> a\n   resto,   -- Cola a -> Cola a\n   esVacia, -- Cola a -> Bool\n  ) where\n\nimport Test.QuickCheck\n\n-- Colas como listas:\nnewtype Cola a = C [a]\n  deriving Eq\n\n-- (escribeCola c) es la cadena correspondiente a la cola c. Por\n-- ejemplo,\n--    escribeCola (inserta 5 (inserta 2 (inserta 3 vacia))) == \"3 | 2 | 5\"\nescribeCola :: Show a => Cola a -> String\nescribeCola (C [])     = \"-\"\nescribeCola (C [x])    = show x\nescribeCola (C (x:xs)) = show x ++ \" | \" ++ escribeCola (C xs)\n\n-- Procedimiento de escritura de colas.\ninstance Show a => Show (Cola a) where\n  show = escribeCola\n\n-- Ejemplo de cola:\n--    \u03bb> inserta 5 (inserta 2 (inserta 3 vacia))\n--    3 | 2 | 5\n\n-- vacia es la cola vac\u00eda. Por ejemplo,\n--    \u03bb> vacia\n--    -\nvacia :: Cola a\nvacia = C []\n\n-- (inserta x c) es la cola obtenida a\u00f1adiendo x al final de la cola\n-- c. Por ejemplo,\n--    \u03bb> ej = inserta 2 (inserta 3 vacia)\n--    \u03bb> ej\n--    3 | 2\n--    \u03bb> inserta 5 ej\n--    3 | 2 | 5\ninserta :: a -> Cola a -> Cola a\ninserta x (C c) = C (c ++ [x])\n\n-- (primero c) es el primer elemento de la cola c. Por ejemplo,\n--    \u03bb> primero (inserta 5 (inserta 2 (inserta 3 vacia)))\n--    3\nprimero :: Cola a -> a\nprimero (C [])    = error \"primero: cola vacia\"\nprimero (C (x:_)) = x\n\n-- (resto c) es la cola obtenida eliminando el primer elemento de la\n-- cola c. Por ejemplo,\n--    \u03bb> resto (inserta 5 (inserta 2 (inserta 3 vacia)))\n--    2 | 5\nresto :: Cola a -> Cola a\nresto (C (_:xs)) = C xs\nresto (C [])     = error \"resto: cola vacia\"\n\n-- (esVacia c) se verifica si c es la cola vac\u00eda. Por ejemplo,\n--    esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False\n--    esVacia vacia  == True\nesVacia :: Cola a -> Bool\nesVacia (C xs)  = null xs\n\n-- Generador de colas                                          --\n-- ==================\n\n-- genCola es un generador de colas de enteros. Por ejemplo,\n--    \u03bb> sample genCola\n--    -\n--    -\n--    -3 | 2\n--    6 | 0 | 1\n--    -5 | 0 | -5 | 0 | -4\n--    2 | 9 | -6 | 9 | 0 | -1\n--    -\n--    11 | -5 | 5\n--    -\n--    16 | 6 | 15 | -3 | -9\n--    11 | 6 | 15 | 13 | 20 | -7 | 11 | -5 | 13\ngenCola :: (Arbitrary a, Num a) => Gen (Cola a)\ngenCola = do\n  xs <- listOf arbitrary\n  return (foldr inserta vacia xs)\n\n-- El tipo pila es una instancia del arbitrario.\ninstance (Arbitrary a, Num a) => Arbitrary (Cola a) where\n  arbitrary = genCola\n\n-- Propiedades de las colas\n-- ========================\n\n-- Las propiedades son\nprop_colas1 :: Int -> Cola Int -> Bool\nprop_colas1 x c =\n  primero (inserta x vacia) == x &&\n  resto (inserta x vacia) == vacia &&\n  esVacia vacia &&\n  not (esVacia (inserta x c))\n\nprop_colas2 :: Int -> Cola Int -> Property\nprop_colas2 x c =\n  not (esVacia c) ==>\n  primero (inserta x c) == primero c &&\n  resto (inserta x c) == inserta x (resto c)\n\n-- La comprobaci\u00f3n es:\n--    \u03bb> quickCheck prop_colas1\n--    +++ OK, passed 100 tests.\n--    \u03bb> quickCheck prop_colas2\n--    +++ OK, passed 100 tests; 3 discarded.\n<\/pre>\n<h5>2.2.3. Implementaci\u00f3n de las colas mediante pares de listas<\/h5>\n<p>En esta implementaci\u00f3n, una cola c se representa mediante un par de listas (xs,ys) de modo que los elementos de c son, en ese orden, los elementos de la lista xs++(reverse ys).<\/p>\n<p>Al dividir la lista en dos parte e invertir la segunda de ellas, esperamos hacer m\u00e1s eficiente las operaciones sobre las colas.<\/p>\n<p>Impondremos tambi\u00e9n una restricci\u00f3n adicional sobre la representaci\u00f3n: las colas ser\u00e1n representadas mediante pares (xs,ys) tales que si xs es vac\u00eda, entonces ys ser\u00e1 tambi\u00e9n vac\u00eda. Esta restricci\u00f3n ha de ser conservada por los programas que crean colas.<\/p>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3QTM6P6\">ColaConDosListas.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.ColaConDosListas\n  (Cola,\n   vacia,      -- Cola a\n   inserta,    -- a -> Cola a -> Cola a\n   primero,    -- Cola a -> a\n   resto,      -- Cola a -> Cola a\n   esVacia,    -- Cola a -> Bool\n  ) where\n\nimport Test.QuickCheck\n\n-- Las colas como pares listas.\nnewtype Cola a = C ([a],[a])\n\n-- (escribeCola p) es la cadena correspondiente a la cola p. Por\n-- ejemplo,\n--    \u03bb> escribeCola (inserta 5 (inserta 2 (inserta 3 vacia)))\n--    \"3 | 2 | 5\"\nescribeCola :: Show a => Cola a -> String\nescribeCola (C (xs,ys)) = aux (xs ++ reverse ys)\n  where aux []     = \"-\"\n        aux [z]    = show z\n        aux (z:zs) = show z ++ \" | \" ++ aux zs\n\n-- Procedimiento de escritura de colas.\ninstance Show a => Show (Cola a) where\n  show = escribeCola\n\n-- Ejemplo de cola:\n--    \u03bb> inserta 5 (inserta 2 (inserta 3 vacia))\n--    3 | 2 | 5\n\n-- vacia es la cola vac\u00eda. Por ejemplo,\n--    \u03bb>  vacia\n--    -\nvacia :: Cola a\nvacia  = C ([],[])\n\n-- (inserta x c) es la cola obtenida a\u00f1adiendo x al final de la cola\n-- c. Por ejemplo,\n--    \u03bb> inserta 5 (inserta 2 (inserta 3 vacia))\n--    3 | 2 | 5\ninserta :: a -> Cola a -> Cola a\ninserta y (C (xs,ys)) = C (normaliza (xs,y:ys))\n\n-- (normaliza p) es la cola obtenida al normalizar el par de listas\n-- p. Por ejemplo,\n--    normaliza ([],[2,5,3])   ==  ([3,5,2],[])\n--    normaliza ([4],[2,5,3])  ==  ([4],[2,5,3])\nnormaliza :: ([a],[a]) -> ([a],[a])\nnormaliza ([], ys) = (reverse ys, [])\nnormaliza p        = p\n\n-- (primero c) es el primer elemento de la cola c. Por ejemplo,\n--    \u03bb> primero (inserta 5 (inserta 2 (inserta 3 vacia)))\n--    3\nprimero  :: Cola a -> a\nprimero (C (x:_,_)) = x\nprimero _           = error \"primero: cola vacia\"\n\n-- (resto c) es la cola obtenida eliminando el primer elemento de la\n-- cola c. Por ejemplo,\n--    \u03bb> resto (inserta 5 (inserta 2 (inserta 3 vacia)))\n--    2 | 5\nresto  :: Cola a -> Cola a\nresto (C ([],[]))   = error \"resto: cola vacia\"\nresto (C (_:xs,ys)) = C (normaliza (xs,ys))\nresto (C ([],_:_))  = error \"Imposible\"\n\n-- (esVacia c) se verifica si c es la cola vac\u00eda. Por ejemplo,\n--    esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False\n--    esVacia vacia == True\nesVacia :: Cola a -> Bool\nesVacia (C (xs,_)) = null xs\n\n-- (valida c) se verifica si la cola c es v\u00e1lida; es decir, si\n-- su primer elemento es vac\u00edo entonces tambi\u00e9n lo es el segundo. Por\n-- ejemplo,\n--    valida (C ([2],[5]))  ==  True\n--    valida (C ([2],[]))   ==  True\n--    valida (C ([],[5]))   ==  False\nvalida :: Cola a -> Bool\nvalida (C (xs,ys)) = not (null xs) || null ys\n\n-- ---------------------------------------------------------------------\n-- Igualdad de colas                                                  --\n-- ---------------------------------------------------------------------\n\n-- (elementos c) es la lista de los elementos de la cola c en el orden de\n-- la cola. Por ejemplo,\n--    \u03bb> elementos (inserta 5 (inserta 2 (inserta 3 vacia)))\n--    [3,2,5]\nelementos :: Cola a -> [a]\nelementos (C (xs,ys)) = xs ++ reverse ys\n\n-- (igualColas c1 c2) se verifica si las colas c1 y c2 son iguales. Por\n-- ejemplo,\n--    igualColas (C ([3,2],[5,4,7])) (C ([3],[5,4,7,2]))   ==  True\n--    igualColas (C ([3,2],[5,4,7])) (C ([],[5,4,7,2,3]))  ==  False\nigualColas :: Eq a => Cola a -> Cola a -> Bool\nigualColas c1 c2 =\n  valida c1 &&\n  valida c2 &&\n  elementos c1 == elementos c2\n\ninstance Eq a => Eq (Cola a) where\n  (==) = igualColas\n\n-- Generador de colas                                          --\n-- ==================\n\n-- genCola es un generador de colas de enteros. Por ejemplo,\n--    \u03bb> sample genCola\n--    -\n--    -\n--    -3 | 2\n--    6 | 0 | 1\n--    -5 | 0 | -5 | 0 | -4\n--    2 | 9 | -6 | 9 | 0 | -1\n--    -\n--    11 | -5 | 5\n--    -\n--    16 | 6 | 15 | -3 | -9\n--    11 | 6 | 15 | 13 | 20 | -7 | 11 | -5 | 13\ngenCola :: (Arbitrary a, Num a) => Gen (Cola a)\ngenCola = do\n  xs <- listOf arbitrary\n  return (foldr inserta vacia xs)\n\n-- El tipo pila es una instancia del arbitrario.\ninstance (Arbitrary a, Num a) => Arbitrary (Cola a) where\n  arbitrary = genCola\n\n-- Propiedades de las colas\n-- ========================\n\n-- Las propiedades son\nprop_colas1 :: Int -> Cola Int -> Bool\nprop_colas1 x c =\n  primero (inserta x vacia) == x &&\n  resto (inserta x vacia) == vacia &&\n  esVacia vacia &&\n  not (esVacia (inserta x c))\n\nprop_colas2 :: Int -> Cola Int -> Property\nprop_colas2 x c =\n  not (esVacia c) ==>\n  primero (inserta x c) == primero c &&\n  resto (inserta x c) == inserta x (resto c)\n\n-- La comprobaci\u00f3n es:\n--    \u03bb> quickCheck prop_colas1\n--    +++ OK, passed 100 tests.\n--    \u03bb> quickCheck prop_colas2\n--    +++ OK, passed 100 tests; 3 discarded.\n<\/pre>\n<h5>2.2.4. Implementaci\u00f3n de las colas 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\/3WshC86\">ColaConSucesiones.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\n{-# LANGUAGE FlexibleInstances #-}\n{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}\n\nmodule TAD.ColaConSucesiones\n  (Cola,\n   vacia,   -- Cola a\n   inserta, -- a -> Cola a -> Cola a\n   primero, -- Cola a -> a\n   resto,   -- Cola a -> Cola a\n   esVacia, -- Cola a -> Bool\n  ) where\n\nimport Data.Sequence as S\nimport Test.QuickCheck\n\n-- Colas como sucesiones:\nnewtype Cola a = C (Seq a)\n  deriving Eq\n\n-- (escribeCola c) es la cadena correspondiente a la cola c. Por\n-- ejemplo,\n--    escribeCola (inserta 5 (inserta 2 (inserta 3 vacia))) == \"3 | 2 | 5\"\nescribeCola :: Show a => Cola a -> String\nescribeCola (C xs) = case viewl xs of\n    EmptyL   -> \"-\"\n    x :< xs' -> case viewl xs' of\n        EmptyL -> show x\n        _      -> show x ++ \" | \" ++ escribeCola (C xs')\n\n-- Procedimiento de escritura de colas.\ninstance Show a => Show (Cola a) where\n  show = escribeCola\n\n-- Ejemplo de cola:\n--    \u03bb> inserta 5 (inserta 2 (inserta 3 vacia))\n--    3 | 2 | 5\n\n-- vacia es la cola vac\u00eda. Por ejemplo,\n--    \u03bb> vacia\n--    C []\nvacia :: Cola a\nvacia = C empty\n\n-- (inserta x c) es la cola obtenida a\u00f1adiendo x al final de la cola\n-- c. Por ejemplo,\n--    \u03bb> ej = inserta 2 (inserta 3 vacia)\n--    \u03bb> ej\n--    3 | 2\n--    \u03bb> inserta 5 ej\n--    3 | 2 | 5\ninserta :: a -> Cola a -> Cola a\ninserta x (C xs) = C (xs |> x )\n\n-- (primero c) es el primer elemento de la cola c. Por ejemplo,\n--    \u03bb> primero (inserta 5 (inserta 2 (inserta 3 vacia)))\n--    3\nprimero :: Cola a -> a\nprimero (C xs) = case viewl xs of\n  EmptyL -> error \"primero de la pila vacia\"\n  x :< _ -> x\n\n-- (resto c) es la cola obtenida eliminando el primer elemento de la\n-- cola c. Por ejemplo,\n--    \u03bb> resto (inserta 5 (inserta 2 (inserta 3 vacia)))\n--    2 | 5\nresto :: Cola a -> Cola a\nresto (C xs) = case viewl xs of\n  EmptyL   -> error \"resto la pila vacia\"\n  _ :< xs' -> C xs'\n\n-- (esVacia c) se verifica si c es la cola vac\u00eda. Por ejemplo,\n--    esVacia (inserta 5 (inserta 2 (inserta 3 vacia))) == False\n--    esVacia vacia  == True\nesVacia :: Cola a -> Bool\nesVacia (C xs)  = S.null xs\n\n-- Generador de colas                                          --\n-- ==================\n\n-- genCola es un generador de colas de enteros. Por ejemplo,\n--    \u03bb> sample genCola\n--    -\n--    2 | -2\n--    0 | 0 | 0 | 4\n--    -\n--    2\n--    -1 | -6 | 9\n--    12 | -12 | -12 | 7 | -2 | -3 | 5 | -8 | -3 | -9 | -6\n--    -11 | -5 | -7 | -8 | -10 | 8 | -9 | -7 | 6 | -12 | 8 | -9 | -1\n--    -16 | -12\n--    -17 | -17 | 1 | 2 | -15 | -15 | -13 | 8 | 13 | -12 | 15\n--    -16 | -18\ngenCola :: (Arbitrary a, Num a) => Gen (Cola a)\ngenCola = do\n  xs <- listOf arbitrary\n  return (foldr inserta vacia xs)\n\n-- El tipo pila es una instancia del arbitrario.\ninstance (Arbitrary a, Num a) => Arbitrary (Cola a) where\n  arbitrary = genCola\n\n-- Propiedades de las colas\n-- ========================\n\n-- Las propiedades son\nprop_colas1 :: Int -> Cola Int -> Bool\nprop_colas1 x c =\n  primero (inserta x vacia) == x &&\n  resto (inserta x vacia) == vacia &&\n  esVacia vacia &&\n  not (esVacia (inserta x c))\n\nprop_colas2 :: Int -> Cola Int -> Property\nprop_colas2 x c =\n  not (esVacia c) ==>\n  primero (inserta x c) == primero c &&\n  resto (inserta x c) == inserta x (resto c)\n\n-- La comprobaci\u00f3n es:\n--    \u03bb> quickCheck prop_colas1\n--    +++ OK, passed 100 tests.\n--    \u03bb> quickCheck prop_colas2\n--    +++ OK, passed 100 tests; 9 discarded.\n<\/pre>\n<h4>2.3. Las colas en Python<\/h4>\n<h5>2.3.1. El tipo abstracto de las colas en Python<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3J5Hmnu\">cola.py<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"python\">\n__all__ = [\n    'Cola',\n    'vacia',\n    'inserta',\n    'primero',\n    'resto',\n    'esVacia',\n    'colaAleatoria'\n]\nfrom src.TAD.colaConListas import (Cola, colaAleatoria, esVacia, inserta,\n                                   primero, resto, vacia)\n# from src.TAD.colaConDosListas import (Cola, colaAleatoria, esVacia, inserta,\n#                                       primero, resto, vacia)\n# from src.TAD.colaConDeque import (Cola, vacia, inserta, primero, resto,\n#                                   esVacia, colaAleatoria)\n<\/pre>\n<p>Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos tres: una usando listas, otra usando pares de listas y otra usando deques. Hay que elegir la que se desee utilizar, descoment\u00e1ndola y comentando las otras.<\/p>\n<h5>2.3.2. Implementaci\u00f3n de las colas mediante listas<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3kxW4JT\">colaConListas.py<\/a> en el que se define la clase Cola con los siguientes m\u00e9todos:<\/p>\n<ul>\n<li>inserta(x) a\u00f1ade x al final de la cola.<\/li>\n<li>primero() es el primero de la cola.<\/li>\n<li>resto() elimina el primero de la cola.<\/li>\n<li>esVacia() se verifica si la cola es vac\u00eda.<\/li>\n<\/ul>\n<p>Por ejemplo,<\/p>\n<pre lang=\"text\">\n   >>> c = Cola()\n   >>> c\n   -\n   >>> c.inserta(5)\n   >>> c.inserta(2)\n   >>> c.inserta(3)\n   >>> c.inserta(4)\n   >>> c\n   5 | 2 | 3 | 4\n   >>> c.primero()\n   5\n   >>> c.resto()\n   >>> c\n   2 | 3 | 4\n   >>> c.esVacia()\n   False\n   >>> c = Cola()\n   >>> c.esVacia()\n   True\n<\/pre>\n<p>Adem\u00e1s se definen las correspondientes funciones. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   >>> vacia()\n   -\n   >>> inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))\n   5 | 2 | 3 | 4\n   >>> primero(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))\n   5\n   >>> resto(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))\n   2 | 3 | 4\n   >>> esVacia(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))\n   False\n   >>> esVacia(vacia())\n   True\n<\/pre>\n<p>Finalmente, se define un generador aleatorio de colas y se comprueba que las colas cumplen las propiedades de su especificaci\u00f3n.<\/p>\n<pre lang=\"python\">\n__all__ = [\n    'Cola',\n    'vacia',\n    'inserta',\n    'primero',\n    'resto',\n    'esVacia',\n    'colaAleatoria'\n]\n\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import assume, given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A')\n\n# Clase de las colas mediante listas\n# ==================================\n\n@dataclass\nclass Cola(Generic[A]):\n    _elementos: list[A] = field(default_factory=list)\n\n    def __repr__(self) -> str:\n        \"\"\"\n        Devuelve una cadena con los elementos de la cola separados por \" | \".\n        Si la cola est\u00e1 vac\u00eda, devuelve \"-\".\n        \"\"\"\n        if not self._elementos:\n            return '-'\n        return ' | '.join(str(x) for x in self._elementos)\n\n    def inserta(self, x: A) -> None:\n        \"\"\"\n        Inserta el elemento x al final de la cola.\n        \"\"\"\n        self._elementos.append(x)\n\n    def esVacia(self) -> bool:\n        \"\"\"\n        Comprueba si la cola est\u00e1 vac\u00eda.\n\n        Devuelve True si la cola est\u00e1 vac\u00eda, False en caso contrario.\n        \"\"\"\n        return not self._elementos\n\n    def primero(self) -> A:\n        \"\"\"\n        Devuelve el primer elemento de la cola.\n        \"\"\"\n        return self._elementos[0]\n\n    def resto(self) -> None:\n        \"\"\"\n        Elimina el primer elemento de la cola\n        \"\"\"\n        self._elementos.pop(0)\n\n# Funciones del tipo de las listas\n# ================================\n\ndef vacia() -> Cola[A]:\n    \"\"\"\n    Crea y devuelve una cola vac\u00eda de tipo A.\n    \"\"\"\n    c: Cola[A] = Cola()\n    return c\n\ndef inserta(x: A, c: Cola[A]) -> Cola[A]:\n    \"\"\"\n    Inserta un elemento x en la cola c y devuelve una nueva cola con\n    el elemento insertado.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.inserta(x)\n    return _aux\n\ndef esVacia(c: Cola[A]) -> bool:\n    \"\"\"\n    Devuelve True si la cola est\u00e1 vac\u00eda, False si no lo est\u00e1.\n    \"\"\"\n    return c.esVacia()\n\ndef primero(c: Cola[A]) -> A:\n    \"\"\"\n    Devuelve el primer elemento de la cola c.\n    \"\"\"\n    return c.primero()\n\ndef resto(c: Cola[A]) -> Cola[A]:\n    \"\"\"\n    Elimina el primer elemento de la cola c y devuelve una copia de la\n    cola resultante.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.resto()\n    return _aux\n\n# Generador de colas\n# ==================\n\ndef colaAleatoria() -> st.SearchStrategy[Cola[int]]:\n    \"\"\"\n    Genera una estrategia de b\u00fasqueda para generar colas de enteros de\n    forma aleatoria.\n\n    Utiliza la librer\u00eda Hypothesis para generar una lista de enteros y\n    luego se convierte en una instancia de la clase cola.\n    \"\"\"\n    return st.lists(st.integers()).map(Cola)\n\n# Comprobaci\u00f3n de las propiedades de las colas\n# ============================================\n\n# Las propiedades son\n@given(c=colaAleatoria(), x=st.integers())\ndef test_cola1(c: Cola[int], x: int) -> None:\n    assert primero(inserta(x, vacia())) == x\n    assert resto(inserta(x, vacia())) == vacia()\n    assert esVacia(vacia())\n    assert not esVacia(inserta(x, c))\n\n@given(c=colaAleatoria(), x=st.integers())\ndef test_cola2(c: Cola[int], x: int) -> None:\n    assume(not esVacia(c))\n    assert primero(inserta(x, c)) == primero(c)\n    assert resto(inserta(x, c)) == inserta(x, resto(c))\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q colaConListas.py\n#    1 passed in 0.24s\n<\/pre>\n<h5>2.3.3. Implementaci\u00f3n de las colas mediante pares de listas<\/h5>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3GYLwer\">colaConDosListas.py<\/a> cuyo contenido es<\/p>\n<pre lang=\"python\">\n__all__ = [\n    'Cola',\n    'vacia',\n    'inserta',\n    'primero',\n    'resto',\n    'esVacia',\n    'colaAleatoria'\n]\n\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom typing import Generic, TypeVar\n\nfrom hypothesis import assume, given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A')\n\n# Clase de las colas mediante listas\n# ==================================\n\n@dataclass\nclass Cola(Generic[A]):\n    _primera: list[A] = field(default_factory=list)\n    _segunda: list[A] = field(default_factory=list)\n\n    def _elementos(self) -> list[A]:\n        \"\"\"\n        Devuelve una lista con los elementos de la cola en orden.\n        \"\"\"\n        return self._primera + self._segunda[::-1]\n\n    def __repr__(self) -> str:\n        \"\"\"\n        Devuelve una cadena con los elementos de la cola separados por \" | \".\n        Si la cola est\u00e1 vac\u00eda, devuelve \"-\".\n        \"\"\"\n        elementos = self._elementos()\n        if not elementos:\n            return \"-\"\n        return \" | \".join(map(str, elementos))\n\n    def __eq__(self, c) -> bool:\n        \"\"\"\n        Comprueba si la cola actual es igual a otra cola.\n        Se considera que dos colas son iguales si tienen los mismos\n        elementos en el mismo orden.\n\n        Par\u00e1metro:\n        - c (Cola): La cola con la que se va a comparar.\n\n        Devuelve True si las dos colas son iguales, False en caso\n        contrario.\n        \"\"\"\n        return self._elementos() == c._elementos()\n\n    def inserta(self, y: A) -> None:\n        \"\"\"\n        Inserta el elemento y en la cola.\n        \"\"\"\n        xs = self._primera\n        ys = self._segunda\n        # Si no hay elementos en la primera lista, se inserta en la segunda\n        if not xs:\n            ys.insert(0, y)\n            # Se invierte la segunda lista y se asigna a la primera\n            self._primera = ys[::-1]\n            self._segunda = []\n        else:\n            # Si hay elementos en la primera lista, se inserta en la segunda\n            ys.insert(0, y)\n\n    def esVacia(self) -> bool:\n        \"\"\"\n        Devuelve si la cola est\u00e1 vac\u00eda.\n        \"\"\"\n        return not self._primera\n\n    def primero(self) -> A:\n        \"\"\"\n        Devuelve el primer elemento de la cola.\n        \"\"\"\n        return self._primera[0]\n\n    def resto(self) -> None:\n        \"\"\"\n        Elimina el primer elemento de la cola.\n        \"\"\"\n        xs = self._primera\n        ys = self._segunda\n        del xs[0]\n        if not xs:\n            self._primera = ys[::-1]\n            self._segunda = []\n\n# Funciones del tipo de las listas\n# ================================\n\ndef vacia() -> Cola[A]:\n    \"\"\"\n    Crea y devuelve una cola vac\u00eda de tipo A.\n    \"\"\"\n    c: Cola[A] = Cola()\n    return c\n\ndef inserta(x: A, c: Cola[A]) -> Cola[A]:\n    \"\"\"\n    Inserta un elemento x en la cola c y devuelve una nueva cola con\n    el elemento insertado.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.inserta(x)\n    return _aux\n\ndef esVacia(c: Cola[A]) -> bool:\n    \"\"\"\n    Devuelve True si la cola est\u00e1 vac\u00eda, False si no lo est\u00e1.\n    \"\"\"\n    return c.esVacia()\n\ndef primero(c: Cola[A]) -> A:\n    \"\"\"\n    Devuelve el primer elemento de la cola c.\n    \"\"\"\n    return c.primero()\n\ndef resto(c: Cola[A]) -> Cola[A]:\n    \"\"\"\n    Elimina el primer elemento de la cola c y devuelve una copia de la\n    cola resultante.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.resto()\n    return _aux\n\n# Generador de colas\n# ==================\n\ndef colaAleatoria() -> st.SearchStrategy[Cola[int]]:\n    \"\"\"\n    Genera una estrategia de b\u00fasqueda para generar colas de enteros de\n    forma aleatoria.\n\n    Utiliza la librer\u00eda Hypothesis para generar una lista de enteros y\n    luego se convierte en una instancia de la clase cola.\n    \"\"\"\n    return st.lists(st.integers()).map(Cola)\n\n# Comprobaci\u00f3n de las propiedades de las colas\n# ============================================\n\n# Las propiedades son\n@given(c=colaAleatoria(), x=st.integers())\ndef test_cola1(c: Cola[int], x: int) -> None:\n    assert primero(inserta(x, vacia())) == x\n    assert resto(inserta(x, vacia())) == vacia()\n    assert esVacia(vacia())\n    assert not esVacia(inserta(x, c))\n\n@given(c=colaAleatoria(), x=st.integers())\ndef test_cola2(c: Cola[int], x: int) -> None:\n    assume(not esVacia(c))\n    assert primero(inserta(x, c)) == primero(c)\n    assert resto(inserta(x, c)) == inserta(x, resto(c))\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q colaConListas.py\n#    2 passed in 0.40s\n<\/pre>\n<h5>2.3.4. Implementaci\u00f3n de las colas 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\">colaConDeque.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 __repr__(self) -> str:\n        \"\"\"\n        Devuelve una cadena con los elementos de la pila separados por \" | \".\n        Si la pila est\u00e1 vac\u00eda, devuelve \"-\".\n        \"\"\"\n        if len(self._elementos) == 0:\n            return '-'\n        return ' | '.join(str(x) for x in self._elementos)\n\n    def apila(self, x: A) -> None:\n        \"\"\"\n        Agrega el elemento x al inicio de la pila.\n        \"\"\"\n        self._elementos.appendleft(x)\n\n    def esVacia(self) -> bool:\n        \"\"\"\n        Verifica si la pila est\u00e1 vac\u00eda.\n\n        Devuelve True si la pila est\u00e1 vac\u00eda, False en caso contrario.\n        \"\"\"\n        return len(self._elementos) == 0\n\n    def cima(self) -> A:\n        \"\"\"\n        Devuelve el elemento en la cima de la pila.\n        \"\"\"\n        return self._elementos[0]\n\n    def desapila(self) -> None:\n        \"\"\"\n        Elimina el elemento en la cima de la pila.\n        \"\"\"\n        self._elementos.popleft()\n\n# Funciones del tipo de las listas\n# ================================\n\ndef vacia() -> Pila[A]:\n    \"\"\"\n    Crea y devuelve una pila vac\u00eda de tipo A.\n    \"\"\"\n    p: Pila[A] = Pila()\n    return p\n\ndef apila(x: A, p: Pila[A]) -> Pila[A]:\n    \"\"\"\n    A\u00f1ade un elemento x al tope de la pila p y devuelve una copia de la\n    pila modificada.\n    \"\"\"\n    _aux = deepcopy(p)\n    _aux.apila(x)\n    return _aux\n\ndef esVacia(p: Pila[A]) -> bool:\n    \"\"\"\n    Devuelve True si la pila est\u00e1 vac\u00eda, False si no lo est\u00e1.\n    \"\"\"\n    return p.esVacia()\n\ndef cima(p: Pila[A]) -> A:\n    \"\"\"\n    Devuelve el elemento en la cima de la pila p.\n    \"\"\"\n    return p.cima()\n\ndef desapila(p: Pila[A]) -> Pila[A]:\n    \"\"\"\n    Elimina el elemento en la cima de la pilla p y devuelve una copia de la\n    pila resultante.\n    \"\"\"\n    _aux = deepcopy(p)\n    _aux.desapila()\n    return _aux\n\n# Generador de pilas\n# ==================\n\ndef pilaAleatoria() -> st.SearchStrategy[Pila[int]]:\n    \"\"\"\n    Genera una estrategia de b\u00fasqueda para generar pilas de enteros de\n    forma aleatoria.\n\n    Utiliza la librer\u00eda Hypothesis para generar una lista de enteros y\n    luego se convierte en una instancia de la clase pila.\n    \"\"\"\n    def _creaPila(elementos: list[int]) -> Pila[int]:\n        pila: Pila[int] = vacia()\n        pila._elementos.extendleft(elementos)\n        return pila\n    return st.builds(_creaPila, 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<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. TAD de las colas: Transformaciones entre colas y listas<\/h3>\n<p>Utilizando el <a href=\"https:\/\/bit.ly\/3QWTsRL\">tipo abstracto de datos de las colas<\/a>, definir las funciones<\/p>\n<pre lang=\"text\">\n   listaAcola :: [a] -> Cola a\n   colaAlista :: Cola a -> [a]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>listaAcola xs<\/code> es la cola formada por los elementos de <code>xs<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> listaAcola [3, 2, 5]\n     3 | 2 | 5\n<\/pre>\n<ul>\n<li><code>colaAlista c<\/code> es la lista formada por los elementos de la cola <code>c<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> colaAlista (inserta 5 (inserta 2 (inserta 3 vacia)))\n     [3, 2, 5]\n<\/pre>\n<p>Comprobar con QuickCheck que ambas funciones son inversa; es decir,<\/p>\n<pre lang=\"text\">\n   colaAlista (listaAcola xs) = xs\n   listaAcola (colaAlista c)  = c\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\">\nimport TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto)\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n de listaAcola\n-- ===========================\n\nlistaAcola :: [a] -> Cola a\nlistaAcola ys = aux (reverse ys)\n  where aux []     = vacia\n        aux (x:xs) = inserta x (aux xs)\n\n-- 2\u00aa definici\u00f3n de listaAcola\n-- ===========================\n\nlistaAcola2 :: [a] -> Cola a\nlistaAcola2 = aux . reverse\n  where aux [] = vacia\n        aux (x:xs) = inserta x (aux xs)\n\n-- 3\u00aa definici\u00f3n de listaAcola\n-- ===========================\n\nlistaAcola3 :: [a] -> Cola a\nlistaAcola3 = aux . reverse\n  where aux = foldr inserta vacia\n\n-- 4\u00aa definici\u00f3n de listaAcola\n-- ===========================\n\nlistaAcola4 :: [a] -> Cola a\nlistaAcola4 xs = foldr inserta vacia (reverse xs)\n\n-- 5\u00aa definici\u00f3n de listaAcola\n-- ===========================\n\nlistaAcola5 :: [a] -> Cola a\nlistaAcola5 = foldr inserta vacia . reverse\n\n-- Comprobaci\u00f3n de equivalencia de las definiciones de listaAcola\n-- ==============================================================\n\n-- La propiedad es\nprop_listaAcola :: [Int] -> Bool\nprop_listaAcola xs =\n  all (== listaAcola xs)\n      [listaAcola2 xs,\n       listaAcola3 xs,\n       listaAcola4 xs,\n       listaAcola5 xs]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_listaAcola\n--    +++ OK, passed 100 tests.\n\n-- Definici\u00f3n de colaAlista\n-- ========================\n\ncolaAlista :: Cola a -> [a]\ncolaAlista c\n  | esVacia c = []\n  | otherwise = pc : colaAlista rc\n  where pc = primero c\n        rc = resto c\n\n-- Comprobaci\u00f3n de las propiedades\n-- ===============================\n\n-- La primera propiedad es\nprop_1_listaAcola :: [Int] -> Bool\nprop_1_listaAcola xs =\n  colaAlista (listaAcola xs) == xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_1_listaAcola\n--    +++ OK, passed 100 tests.\n\n-- La segunda propiedad es\nprop_2_listaAcola :: Cola Int -> Bool\nprop_2_listaAcola c =\n  listaAcola (colaAlista c) == c\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_2_listaAcola\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom copy import deepcopy\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.TAD.cola import (Cola, inserta, primero, resto, esVacia, vacia,\n                          colaAleatoria)\n\nA = TypeVar('A')\n\n# 1\u00aa definici\u00f3n de listaAcola\n# ===========================\n\ndef listaAcola(ys: list[A]) -> Cola[A]:\n    def aux(xs: list[A]) -> Cola[A]:\n        if not xs:\n            return vacia()\n        return inserta(xs[0], aux(xs[1:]))\n\n    return aux(list(reversed(ys)))\n\n# 2\u00aa soluci\u00f3n de listaAcola\n# =========================\n\ndef listaAcola2(xs: list[A]) -> Cola[A]:\n    p: Cola[A] = Cola()\n    for x in xs:\n        p.inserta(x)\n    return p\n\n# Comprobaci\u00f3n de equivalencia de las definiciones de listaAcola\n# ==============================================================\n\n# La propiedad es\n@given(st.lists(st.integers()))\ndef test_listaAcola(xs: list[int]) -> None:\n    assert listaAcola(xs) == listaAcola2(xs)\n\n# 1\u00aa definici\u00f3n de colaAlista\n# ===========================\n\ndef colaAlista(c: Cola[A]) -> list[A]:\n    if esVacia(c):\n        return []\n    pc = primero(c)\n    rc = resto(c)\n    return [pc] + colaAlista(rc)\n\n# 2\u00aa definici\u00f3n de colaAlista\n# ===========================\n\ndef colaAlista2Aux(c: Cola[A]) -> list[A]:\n    if c.esVacia():\n        return []\n    pc = c.primero()\n    c.resto()\n    return [pc] + colaAlista2Aux(c)\n\ndef colaAlista2(c: Cola[A]) -> list[A]:\n    c1 = deepcopy(c)\n    return colaAlista2Aux(c1)\n\n# 3\u00aa definici\u00f3n de colaAlista\n# ===========================\n\ndef colaAlista3Aux(c: Cola[A]) -> list[A]:\n    r = []\n    while not c.esVacia():\n        r.append(c.primero())\n        c.resto()\n    return r\n\ndef colaAlista3(c: Cola[A]) -> list[A]:\n    c1 = deepcopy(c)\n    return colaAlista3Aux(c1)\n\n# Comprobaci\u00f3n de equivalencia de las definiciones de colaAlista\n# ==============================================================\n\n@given(p=colaAleatoria())\ndef test_colaAlista(p: Cola[int]) -> None:\n    assert colaAlista(p) == colaAlista2(p)\n    assert colaAlista(p) == colaAlista3(p)\n\n# Comprobaci\u00f3n de las propiedades\n# ===============================\n\n# La primera propiedad es\n@given(st.lists(st.integers()))\ndef test_1_listaAcola(xs: list[int]) -> None:\n    assert colaAlista(listaAcola(xs)) == xs\n\n# La segunda propiedad es\n@given(c=colaAleatoria())\ndef test_2_listaAcola(c: Cola[int]) -> None:\n    assert listaAcola(colaAlista(c)) == c\n\n# La comprobaci\u00f3n es\n#      src> poetry run pytest -v transformaciones_colas_listas.py\n#      test_listaAcola PASSED\n#      test_colaAlista PASSED\n#      test_1_listaAcola PASSED\n#      test_2_listaAcola PASSED\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. TAD de las colas: \u00daltimo elemento<\/h3>\n<p>Utilizando el <a href=\"https:\/\/bit.ly\/3QWTsRL\">tipo abstracto de datos de las colas<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   ultimoCola :: Cola a -> a\n<\/pre>\n<p>tal que <code>ultimoCola c<\/code> es el \u00faltimo elemento de la cola <code>c<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   ultimoCola (inserta 3 (inserta 5 (inserta 2 vacia))) == 3\n   ultimoCola (inserta 2 vacia)                         == 2\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\">\nimport TAD.Cola (Cola, vacia, inserta, primero, resto, esVacia)\nimport Transformaciones_colas_listas (colaAlista)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nultimoCola :: Cola a -> a\nultimoCola c\n  | esVacia c  = error \"cola vacia\"\n  | esVacia rc = pc\n  | otherwise  = ultimoCola rc\n  where pc = primero c\n        rc = resto c\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- Se usar\u00e1n la funci\u00f3n colaAlista del ejercicio\n-- \"Transformaciones entre colas y listas\" que se encuentra en\n-- https:\/\/bit.ly\/3Xv0oIt\n\nultimoCola2 :: Cola a -> a\nultimoCola2 c\n  | esVacia c  = error \"cola vacia\"\n  | otherwise  = last (colaAlista c)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_ultimoCola :: Cola Int -> Property\nprop_ultimoCola c =\n  not (esVacia c) ==> ultimoCola c == ultimoCola2 c\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_ultimoCola\n--    +++ OK, passed 100 tests; 16 discarded.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom copy import deepcopy\nfrom typing import TypeVar\n\nfrom hypothesis import assume, given\n\nfrom src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero,\n                          resto, vacia)\nfrom src.transformaciones_colas_listas import colaAlista\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef ultimoCola(c: Cola[A]) -> A:\n    if esVacia(c):\n        raise ValueError(\"cola vacia\")\n    pc = primero(c)\n    rc = resto(c)\n    if esVacia(rc):\n        return pc\n    return ultimoCola(rc)\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef ultimoCola2Aux(c: Cola[A]) -> A:\n    if c.esVacia():\n        raise ValueError(\"cola vacia\")\n    pc = primero(c)\n    c.resto()\n    if c.esVacia():\n        return pc\n    return ultimoCola2(c)\n\ndef ultimoCola2(c: Cola[A]) -> A:\n    _c = deepcopy(c)\n    return ultimoCola2Aux(_c)\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef ultimoCola3(c: Cola[A]) -> A:\n    if esVacia(c):\n        raise ValueError(\"cola vacia\")\n    while not esVacia(resto(c)):\n        c = resto(c)\n    return primero(c)\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef ultimoCola4Aux(c: Cola[A]) -> A:\n    if c.esVacia():\n        raise ValueError(\"cola vacia\")\n    r = primero(c)\n    while not c.esVacia():\n        c.resto()\n        if not c.esVacia():\n            r = primero(c)\n    return r\n\ndef ultimoCola4(c: Cola[A]) -> A:\n    _c = deepcopy(c)\n    return ultimoCola4Aux(_c)\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\n# Se usar\u00e1n la funci\u00f3n colaAlista del ejercicio\n# \"Transformaciones entre colas y listas\" que se encuentra en\n# https:\/\/bit.ly\/3Xv0oIt\n\ndef ultimoCola5(c: Cola[A]) -> A:\n    if esVacia(c):\n        raise ValueError(\"cola vacia\")\n    return colaAlista(c)[-1]\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(c=colaAleatoria())\ndef test_ultimoCola(c: Cola[int]) -> None:\n    assume(not esVacia(c))\n    r = ultimoCola(c)\n    assert ultimoCola2(c) == r\n    assert ultimoCola3(c) == r\n    assert ultimoCola4(c) == r\n    assert ultimoCola5(c) == r\n\n# La comprobaci\u00f3n es\n#      src> poetry run pytest -q ultimoCola.py\n#      1 passed in 0.25s\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. TAD de las colas: Longitud de una cola<\/h3>\n<p>Utilizando el <a href=\"https:\/\/bit.ly\/3QWTsRL\">tipo abstracto de datos de las colas<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   longitudCola :: Cola a -> Int\n<\/pre>\n<p>tal que <code>longitudCola c<\/code> es el n\u00famero de elementos de la cola <code>c<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   longitudCola (inserta 4 (inserta 2 (inserta 5 vacia))) == 3\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\">\nimport TAD.Cola (Cola, vacia, inserta, resto, esVacia)\nimport Transformaciones_colas_listas (colaAlista)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nlongitudCola1 :: Cola a -> Int\nlongitudCola1 c\n  | esVacia c = 0\n  | otherwise = 1 + longitudCola1 rc\n  where rc = resto c\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nlongitudCola2 :: Cola a -> Int\nlongitudCola2 = length . colaAlista\n\n-- La funci\u00f3n colaAlista est\u00e1 definida en el ejercicio\n-- \"Transformaciones entre colas y listas\" que se encuentra en\n-- https:\/\/bit.ly\/3Xv0oIt\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_longitudCola :: Cola Int -> Bool\nprop_longitudCola c =\n  longitudCola1 c == longitudCola2 c\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_longitudCola\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom copy import deepcopy\nfrom typing import TypeVar\n\nfrom hypothesis import given\n\nfrom src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, resto,\n                          vacia)\nfrom src.transformaciones_colas_listas import colaAlista\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef longitudCola1(c: Cola[A]) -> int:\n    if esVacia(c):\n        return 0\n    return 1 + longitudCola1(resto(c))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef longitudCola2(c: Cola[A]) -> int:\n    return len(colaAlista(c))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef longitudCola3Aux(c: Cola[A]) -> int:\n    if c.esVacia():\n        return 0\n    c.resto()\n    return 1 + longitudCola3Aux(c)\n\ndef longitudCola3(c: Cola[A]) -> int:\n    _c = deepcopy(c)\n    return longitudCola3Aux(_c)\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef longitudCola4Aux(c: Cola[A]) -> int:\n    r = 0\n    while not esVacia(c):\n        r = r + 1\n        c = resto(c)\n    return r\n\ndef longitudCola4(c: Cola[A]) -> int:\n    _c = deepcopy(c)\n    return longitudCola4Aux(_c)\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef longitudCola5Aux(c: Cola[A]) -> int:\n    r = 0\n    while not c.esVacia():\n        r = r + 1\n        c.resto()\n    return r\n\ndef longitudCola5(c: Cola[A]) -> int:\n    _c = deepcopy(c)\n    return longitudCola5Aux(_c)\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(c=colaAleatoria())\ndef test_longitudCola_(c: Cola[int]) -> None:\n    r = longitudCola1(c)\n    assert longitudCola2(c) == r\n    assert longitudCola3(c) == r\n    assert longitudCola4(c) == r\n    assert longitudCola5(c) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q longitudCola.py\n#    1 passed in 0.28s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Esta semana he publicado en Exercitium las soluciones de los siguientes problemas: 1. TAD de las pilas: M\u00e1ximo elemento de una pila 2. El tipo abstracto de datos de las colas 3. TAD de las colas: Transformaciones entre colas y listas 4. TAD de las colas: \u00daltimo elemento 5. TAD de las colas: Longitud de&#8230;<\/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\/7890"}],"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=7890"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7890\/revisions"}],"predecessor-version":[{"id":7892,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7890\/revisions\/7892"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7890"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7890"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7890"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}