{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"font-size:2em; color:blue\">\n",
    "    Tema 14: El TAD de las pilas\n",
    "</span>  \n",
    "\n",
    "----------\n",
    "\n",
    "[José A. Alonso](https://www.cs.us.es/~jalonso)  \n",
    "[Departamento de Ciencias de la Computación e I.A.](https://www.cs.us.es)  \n",
    "[Universidad de Sevilla](http://www.us.es)  \n",
    "Sevilla, 10 de agosto de 2019"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __Notas:__ \n",
    "+ La versión interactiva de este tema se encuentra en [Binder](https://mybinder.org/v2/gh/jaalonso/Temas_interactivos_de_PF_con_Haskell/master?urlpath=lab/tree/temas/Tema-14.ipynb).\n",
    "+ Se desactiva el [corrector estilo de Haskell](https://github.com/gibiansky/IHaskell/wiki#opt-no-lint) en Jupyter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    ":opt no-lint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tipos abstractos de datos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Abstracción y tipos abstractos de datos\n",
    "\n",
    "**Abstracción y tipos abstractos de datos**\n",
    "\n",
    "+ La *abstracción* es un mecanismo para comprender problemas que involucran una\n",
    "  gran cantidad de detalles.\n",
    "\n",
    "+ Aspectos de la abstracción:\n",
    "    + *Destacar* los detalles relevantes.\n",
    "    + *Ocultar* los detalles irrelevantes.\n",
    "\n",
    "+ Un *tipo abstracto de datos* (TAD) es una colección de *valores y\n",
    "  *operaciones* que se definen mediante una *especificación* que es independiente\n",
    "  de cualquier *representación*.\n",
    "\n",
    "+  Un TAD es una abstracción:\n",
    "    + Se destacan los detalles (normalmente pocos) de la especificación (*el\n",
    "      qué*).\n",
    "    + Se ocultan los detalles (normalmente numerosos) de la implementación (*el\n",
    "      cómo*).\n",
    "\n",
    "+ Analogía con las *estructuras algebraicas*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Especificación del TAD de las pilas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Signatura del TAD pilas\n",
    "\n",
    "**Descripción informal de las pilas**\n",
    "\n",
    "+ Una *pila* es una estructura de datos, caracterizada por ser una secuencia de\n",
    "  elementos en la que las operaciones de inserción y extracción se realizan por\n",
    "  el mismo extremo.\n",
    "\n",
    "+ La pilas también se llaman estructuras LIFO (del inglés Last In First\n",
    "  Out), debido a que el último elemento en entrar será el primero en salir.  \n",
    "\n",
    "+ Analogía con las pilas de platos.\n",
    "\n",
    "\n",
    "**Signatura del TAD de las pilas**\n",
    "\n",
    "+ Signatura:\n",
    "\n",
    "```sesion\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",
    "```\n",
    "\n",
    "+ Descripción:\n",
    "    + `vacia` es la pila vacía.\n",
    "    + `(apila x p)` es la pila obtenida añadiendo `x` al principio de `p`.\n",
    "    + `(cima p)` es la cima de la pila `p`.\n",
    "    + `(desapila p)` es la pila obtenida suprimiendo la cima de `p`.\n",
    "    + `(esVacia p)` se verifica si `p` es la pila vacía."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Propiedades del TAD de las pilas\n",
    "\n",
    "**Propiedades de las pilas**\n",
    "\n",
    "+ `cima (apila x p) == x`\n",
    "\n",
    "+ `desapila (apila x p) == p`\n",
    "\n",
    "+ `esVacia vacia`\n",
    "\n",
    "+ `not (esVacia (apila x p))`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementaciones del TAD de las pilas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Las pilas como tipos de datos algebraicos\n",
    "\n",
    "Está en el fichero [PilaConTipoDeDatoAlgebraico.hs](codigos/PilaConTipoDeDatoAlgebraico.hs)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "module PilaConTipoDeDatoAlgebraico \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",
    "    ) where\n",
    "\n",
    "-- Tipo de dato algebraico de las pilas:\n",
    "data Pila a = Vacia\n",
    "            | P a (Pila a)\n",
    "              deriving Eq\n",
    "\n",
    "-- Procedimiento de escritura de pilas.\n",
    "instance (Show a) => Show (Pila a) where\n",
    "  showsPrec _ Vacia cad   = showChar '-' cad\n",
    "  showsPrec _ (P x s) cad = shows x (showChar '|' (shows s cad))\n",
    "\n",
    "-- Ejemplo de pila:\n",
    "--    ghci> p1\n",
    "--    1|2|3|-\n",
    "p1 :: Pila Int\n",
    "p1 = apila 1 (apila 2 (apila 3 vacia))\n",
    "\n",
    "-- vacia es la pila vacía. Por ejemplo,\n",
    "--    ghci> vacia\n",
    "--    -\n",
    "vacia :: Pila a\n",
    "vacia = Vacia\n",
    "\n",
    "-- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por\n",
    "-- ejemplo, \n",
    "--    apila 4 p1  =>  4|1|2|3|-\n",
    "apila :: a -> Pila a -> Pila a\n",
    "apila x p = P x p\n",
    "\n",
    "-- (cima p) es la cima de la pila p. Por ejemplo,\n",
    "--    cima p1  ==  1\n",
    "cima :: Pila a -> a\n",
    "cima Vacia   = error \"la pila vacia no tiene cima\"\n",
    "cima (P x _) =  x\n",
    "\n",
    "-- (desapila p) es la pila obtenida suprimiendo la cima de la pila\n",
    "-- p. Por ejemplo,\n",
    "--    desapila p1  =>  2|3|-\n",
    "desapila :: Pila a -> Pila a\n",
    "desapila Vacia   = error \"no se puede desapila la pila vacia\"\n",
    "desapila (P _ p) = p\n",
    "\n",
    "-- (esVacia p) se verifica si p es la pila vacía. Por ejemplo,\n",
    "--    esVacia p1         ==  False\n",
    "--    esVacia vacia  ==  True\n",
    "esVacia :: Pila a -> Bool\n",
    "esVacia Vacia = True\n",
    "esVacia _     = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Ejemplos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1 = apila 1 (apila 2 (apila 3 vacia))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1|2|3|-"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "p1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "vacia"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4|1|2|3|-"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "apila 4 p1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cima p1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2|3|-"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "desapila p1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "esVacia p1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "esVacia vacia"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Se borra la primera implementación"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    ":m - PilaConTipoDeDatoAlgebraico"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Las pilas como listas\n",
    "\n",
    "Está en el fichero [PilaConListas.hs](codigos/PilaConListas.hs)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "module 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",
    "    ) where\n",
    "\n",
    "-- Representación de las pilas mediante listas.\n",
    "newtype Pila a = P [a]\n",
    "    deriving Eq\n",
    "\n",
    "-- Procedimiento de escritura de pilas.\n",
    "instance (Show a) => Show (Pila a) where\n",
    "  showsPrec _ (P [])     cad = showChar '-' cad\n",
    "  showsPrec _ (P (x:xs)) cad =\n",
    "    shows x (showChar '|' (shows (P xs) cad))\n",
    "\n",
    "-- Ejemplo de pila:\n",
    "--    > p1\n",
    "--    1|2|3|-\n",
    "p1 :: Pila Integer\n",
    "p1 = apila 1 (apila 2 (apila 3 vacia))\n",
    "\n",
    "-- vacia es la pila vacía. Por ejemplo,\n",
    "--    > vacia\n",
    "--    -\n",
    "vacia   :: Pila a\n",
    "vacia = P []\n",
    "\n",
    "-- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por\n",
    "-- ejemplo, \n",
    "--    apila 4 p1  =>  4|1|2|3|-\n",
    "apila :: a -> Pila a -> Pila a\n",
    "apila x (P xs) = P (x:xs)\n",
    "\n",
    "-- (cima p) es la cima de la pila p. Por ejemplo,\n",
    "--    cima p1  ==  1\n",
    "cima :: Pila a -> a\n",
    "cima (P [])    = error \"cima de la pila vacia\"\n",
    "cima (P (x:_)) = x\n",
    "\n",
    "-- (desapila p) es la pila obtenida suprimiendo la cima de la pila\n",
    "-- p. Por ejemplo, \n",
    "--    desapila p1  =>  2|3|-\n",
    "desapila :: Pila a -> Pila a\n",
    "desapila (P [])     = error \"desapila la pila vacia\"\n",
    "desapila (P (_:xs)) = P  xs\n",
    "\n",
    "-- (esVacia p) se verifica si p es la pila vacía. Por ejemplo,\n",
    "--    esVacia p1     ==  False\n",
    "--    esVacia vacia  ==  True\n",
    "esVacia :: Pila a -> Bool\n",
    "esVacia (P xs) = null xs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Ejemplos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1 = apila 1 (apila 2 (apila 3 vacia))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1|2|3|-"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "p1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "vacia"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4|1|2|3|-"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "apila 4 p1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "cima p1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2|3|-"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "desapila p1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "esVacia p1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "esVacia vacia"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ Se borra la segunda implementación"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    ":m - PilaConListas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Comprobación de las implementaciones con QuickCheck\n",
    "\n",
    "En el fichero [PilaPropiedades.hs](codigos/PilaPropiedades.hs)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "module PilaPropiedades where\n",
    "\n",
    "-- Hay que elegir una implementación del TAD pilas.\n",
    "import PilaConTipoDeDatoAlgebraico\n",
    "-- import PilaConListas\n",
    "\n",
    "import Test.QuickCheck\n",
    "\n",
    "-- ---------------------------------------------------------------------\n",
    "-- Generador de pilas                                          --\n",
    "-- ---------------------------------------------------------------------\n",
    "\n",
    "-- genPila es un generador de pilas. Por ejemplo,\n",
    "--    ghci> 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|-\n",
    "genPila :: (Arbitrary a, Num a) => Gen (Pila a)\n",
    "genPila = do\n",
    "  xs <- listOf arbitrary\n",
    "  return (foldr apila vacia xs)\n",
    "  \n",
    "-- El tipo pila es una instancia del arbitrario. \n",
    "instance (Arbitrary a, Num a) => Arbitrary (Pila a) where\n",
    "  arbitrary = genPila\n",
    "\n",
    "-- ---------------------------------------------------------------------\n",
    "-- Propiedades\n",
    "-- ---------------------------------------------------------------------\n",
    "\n",
    "-- Propiedad. La cima de la pila que resulta de apilar x en una pila p\n",
    "-- es x.\n",
    "prop_cima_apila :: Int -> Pila Int -> Bool\n",
    "prop_cima_apila x p = \n",
    "  cima (apila x p) == x\n",
    "\n",
    "-- Comprobación.\n",
    "--    > quickCheck prop_cima_apila\n",
    "--    +++ OK, passed 100 tests.\n",
    "\n",
    "-- Propiedad. La pila que resulta de desapilar después de apilar\n",
    "-- cualquier elemento es la pila inicial.\n",
    "prop_desapila_apila :: Int -> Pila Int -> Bool\n",
    "prop_desapila_apila x p = \n",
    "  desapila (apila x p) == p\n",
    "\n",
    "-- Comprobación.\n",
    "--    > quickCheck prop_desapila_apila\n",
    "--    +++ OK, passed 100 tests.\n",
    "\n",
    "-- Propiedad. La pila vacía está vacía.\n",
    "prop_vacia_esta_vacia :: Bool\n",
    "prop_vacia_esta_vacia = esVacia vacia\n",
    "\n",
    "-- Comprobación.\n",
    "--    > quickCheck prop_vacia_esta_vacia\n",
    "--    +++ OK, passed 100 tests.\n",
    "\n",
    "-- Propiedad. La pila que resulta de apilar un elemento en un pila\n",
    "-- cualquiera no es vacía.\n",
    "prop_apila_no_es_vacia :: Int -> Pila Int -> Bool\n",
    "prop_apila_no_es_vacia x p = not (esVacia (apila x p))\n",
    "\n",
    "-- Comprobación.\n",
    "--    > quickCheck prop_apila_no_es_vacia\n",
    "--    +++ OK, passed 100 tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "+++ OK, passed 100 tests."
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "+++ OK, passed 100 tests."
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "+++ OK, passed 1 test."
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "+++ OK, passed 100 tests."
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import Test.QuickCheck\n",
    "quickCheck prop_cima_apila\n",
    "quickCheck prop_desapila_apila\n",
    "quickCheck prop_vacia_esta_vacia\n",
    "quickCheck prop_apila_no_es_vacia"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> **Nota** Se borran los ficheros de los módulos usados"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": []
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    ":! rm -f *.hs *.hi *.o *.dyn_*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Referencias\n",
    "\n",
    "+ F. Rabhi y G. Lapalme\n",
    "  [Algorithms: A functional programming approach](http://bit.ly/1mWBqiI)\n",
    "    + Cap. 5.2. Stacks\n",
    "+ WikiBooks, [Haskell](Algorithms: A functional programming approach)\n",
    "    + [Data structures primer](http://bit.ly/1mWAQRY)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  },
  "language_info": {
   "codemirror_mode": "ihaskell",
   "file_extension": ".hs",
   "name": "haskell",
   "pygments_lexer": "Haskell",
   "version": "8.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}