{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " Tema 6: Funciones recursivas\n", " \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, 2 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-06.ipynb).\n", "+ Se desactiva el [corrector estilo de Haskell](https://github.com/gibiansky/IHaskell/wiki#opt-no-lint)." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ ":opt no-lint" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Librerías auxiliares**\n", "\n", "+ En este tema se usarán la siguiente librería:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "import Data.Char" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Recursión numérica\n", "\n", "**Recursión numérica: El factorial**\n", "\n", "+ La función factorial:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "factorial :: Integer -> Integer\n", "factorial 0 = 1\n", "factorial n = n * factorial (n-1)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "factorial 3" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "factorial 100" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Cálculo:\n", "\n", "```sesion\n", "factorial 3\n", "= 3 * (factorial 2)\n", "= 3 * (2 * (factorial 1))\n", "= 3 * (2 * (1 * (factorial 0)))\n", "= 3 * (2 * (1 * 1))\n", "= 3 * (2 * 1)\n", "= 3 * 2\n", "= 6\n", "```\n", "\n", "**Recursión numérica: El producto**\n", "\n", "+ Definición recursiva del producto:" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "por :: Int -> Int -> Int\n", "m `por` 0 = 0\n", "m `por` n = m + (m `por` (n-1))" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "3 `por` 2" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "por 3 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Cálculo:\n", "\n", "```sesion\n", "3 `por` 2\n", "= 3 + (3 `por` 1)\n", "= 3 + (3 + (3 `por` 0))\n", "= 3 + (3 + 0)\n", "= 3 + 3\n", "= 6\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Recusión sobre lista\n", "\n", "**Recursión sobre listas: La función `product`**\n", "\n", "+ Producto de una lista de números:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "producto :: Num a => [a] -> a\n", "producto [] = 1\n", "producto (n:ns) = n * producto ns" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "70" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "product [7,5,2]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Cálculo:\n", "\n", "```sesion\n", "producto [7,5,2]\n", "= 7 * (producto [5,2])\n", "= 7 * (5 * (producto [2]))\n", "= 7 * (5 * (2 * (producto [])))\n", "= 7 * (5 * (2 * 1))\n", "= 7 * (5 * 2)\n", "= 7 * 10\n", "= 70\n", "```\n", "\n", "* Nota. La función `producto`es equivalente a la predefinida \n", "`product`\n", "\n", "**Recursión sobre listas: La función `length`**\n", "\n", "+ Longitud de una lista:" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "longitud :: [a] -> Int\n", "longitud [] = 0\n", "longitud (_:xs) = 1 + longitud xs" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "longitud [2,3,5]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Cálculo:\n", "\n", "```sesion\n", "longitud [2,3,5]\n", "= 1 + (longitud [3,5])\n", "= 1 + (1 + (longitud [5]))\n", "= 1 + (1 + (1 + (longitud [])))\n", "= 1 + (1 + (1 + 0))\n", "= 1 + (1 + 1)\n", "= 1 + 2\n", "= 3\n", "```\n", "\n", "* Nota. La función `longitud`es equivalente a la predefinida \n", "`length`\n", "\n", "**Recursión sobre listas: La función `reverse`**\n", "\n", "+ Inversa de una lista:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "inversa :: [a] -> [a]\n", "inversa [] = []\n", "inversa (x:xs) = inversa xs ++ [x]" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[3,5,2]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "inversa [2,5,3]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Cálculo:\n", "\n", "```sesion\n", "inversa [2,5,3]\n", "= (inversa [5,3]) ++ [2]\n", "= ((inversa [3]) ++ [5]) ++ [2]\n", "= (((inversa []) ++ [3]) ++ [5]) ++ [2]\n", "= (([] ++ [3]) ++ [5]) ++ [2]\n", "= ([3] ++ [5]) ++ [2]\n", "= [3,5] ++ [2]\n", "= [3,5,2]\n", "```\n", "\n", "* Nota. La función `inversa`es equivalente a la predefinida \n", "`reverse`\n", "\n", "**Recursión sobre listas: `++`**\n", "\n", "+ Concatenación de listas:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "(++) :: [a] -> [a] -> [a]\n", "[] ++ ys = ys\n", "(x:xs) ++ ys = x : (xs ++ ys)" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1,3,5,2,4]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "[1,3,5] ++ [2,4]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Cálculo:\n", "\n", "```sesion\n", "[1,3,5] ++ [2,4]\n", "= 1:([3,5] ++ [2,4])\n", "= 1:(3:([5] ++ [2,4]))\n", "= 1:(3:(5:([] ++ [2,4])))\n", "= 1:(3:(5:[2,4]))\n", "= 1:(3:[5,2,4])\n", "= 1:[3,5,2,4]\n", "= [1,3,5,2,4]\n", "```\n", "\n", "**Recursión sobre listas: Inserción ordenada**\n", "\n", "+ `(inserta e xs)` inserta el elemento `e` en la lista `xs` delante del primer\n", " elemento de `xs` mayor o igual que `e`. Por ejemplo,\n", "\n", "```sesion\n", "inserta 5 [2,4,7,3,6,8,10] == [2,4,5,7,3,6,8,10]\n", "```" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "inserta :: Ord a => a -> [a] -> [a]\n", "inserta e [] = [e]\n", "inserta e (x:xs) | e <= x = e : (x:xs)\n", " | otherwise = x : inserta e xs" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1,3,4,5,7]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "inserta 4 [1,3,5,7]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Cálculo:\n", "\n", "```sesion\n", "inserta 4 [1,3,5,7]\n", "= 1:(inserta 4 [3,5,7])\n", "= 1:(3:(inserta 4 [5,7]))\n", "= 1:(3:(4:(5:[7])))\n", "= 1:(3:(4:[5,7]))\n", "= [1,3,4,5,7]\n", "```\n", "\n", "**Recursión sobre listas: Ordenación por inserción**\n", "\n", "+ `(ordena_por_insercion xs)` es la lista `xs` ordenada mediante inserción, Por\n", " ejemplo,\n", "\n", "```sesion\n", "ordena_por_insercion [2,4,3,6,3] == [2,3,3,4,6]\n", "```" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [], "source": [ "ordena_por_insercion :: Ord a => [a] -> [a]\n", "ordena_por_insercion [] = []\n", "ordena_por_insercion (x:xs) =\n", " inserta x (ordena_por_insercion xs)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[6,7,9]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ordena_por_insercion [7,9,6]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Cálculo:\n", "\n", "```sesion\n", " ordena_por_insercion [7,9,6] =\n", "= inserta 7 (inserta 9 (inserta 6 []))\n", "= inserta 7 (inserta 9 [6])\n", "= inserta 7 [6,9]\n", "= [6,7,9]\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Recursión sobre varios argumentos\n", "\n", "**Recursión sobre varios argumentos: La función `zip`**\n", "\n", "+ Emparejamiento de elementos (la función `zip`):" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "zip' :: [a] -> [b] -> [(a, b)]\n", "zip' [] _ = []\n", "zip' _ [] = []\n", "zip' (x:xs) (y:ys) = (x,y) : zip' xs ys" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(1,2),(3,4),(5,6)]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "zip' [1,3,5] [2,4,6,8]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Cálculo:\n", "\n", "```sesion\n", "zip' [1,3,5] [2,4,6,8]\n", "= (1,2) : (zip' [3,5] [4,6,8])\n", "= (1,2) : ((3,4) : (zip' [5] [6,8]))\n", "= (1,2) : ((3,4) : ((5,6) : (zip' [] [8])))\n", "= (1,2) : ((3,4) : ((5,6) : []))\n", "= [(1,2),(3,4),(5,6)]\n", "```\n", "\n", "* Nota. La función `zip'`es equivalente a la predefinida \n", "`zip`\n", "\n", "**Recursión sobre varios argumentos: La función `drop`**\n", "\n", "+ Eliminación de elementos iniciales:" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [], "source": [ "drop' :: Int -> [a] -> [a]\n", "drop' 0 xs = xs\n", "drop' n [] = []\n", "drop' n (x:xs) = drop' (n-1) xs" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[9,4]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "drop' 2 [5,7,9,4]" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "drop' 5 [1,4]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Cálculo:\n", "\n", "```sesion\n", "drop' 2 [5,7,9,4] \n", "= drop' 1 [7,9,4] \n", "= drop' 0 [9,4] \n", "= [9,4] \n", "\n", "drop' 5 [1,4]\n", "= drop' 4 [4]\n", "= drop' 1 []\n", "= []\n", "``` " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Recursión múltiple\n", "\n", "**Recursión múltiple: La función de Fibonacci**\n", "\n", "+ La sucesión de Fibonacci es: 0,1,1,2,3,5,8,13,21,\\dots. Sus dos primeros\n", " términos son 0 y 1 y los restantes se obtienen sumando los dos anteriores.\n", "\n", "+ `(fibonacci n)` es el `n`-ésimo término de la sucesión de Fibonacci. Por\n", " ejemplo,\n", "\n", "```sesion\n", "fibonacci 8 == 21\n", "```" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [], "source": [ "fibonacci :: Int -> Int\n", "fibonacci 0 = 0\n", "fibonacci 1 = 1\n", "fibonacci n = fibonacci (n-2) + fibonacci (n-1)" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "21" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "fibonacci 8" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Recursión múltiple: Ordenación rápida**\n", "\n", "+ Algoritmo de ordenación rápida:" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [], "source": [ "ordena :: (Ord a) => [a] -> [a]\n", "ordena [] = []\n", "ordena (x:xs) =\n", " (ordena menores) ++ [x] ++ (ordena mayores)\n", " where menores = [a | a <- xs, a <= x]\n", " mayores = [b | b <- xs, b > x]" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[2,3,5]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ordena [3,2,5]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Recursión mutua\n", "===============\n", "\n", "**Recursión mutua: Par e impar**\n", "\n", "+ Par e impar por recursión mutua:" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [], "source": [ "par :: Int -> Bool\n", "par 0 = True\n", "par n = impar (n-1)\n", "\n", "impar :: Int -> Bool\n", "impar 0 = False\n", "impar n = par (n-1)" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "impar 3" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "par 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Cálculo:\n", "\n", "```sesion\n", "impar 3 \n", "= par 2 \n", "= impar 1 \n", "= par 0 \n", "= True \n", "\n", "par 3\n", "= impar 2\n", "= par 1\n", "= impar 0\n", "= False\n", "```\n", "\n", "**Recursión mutua: Posiciones pares e impares**\n", "\n", "+ `(pares xs)` son los elementos de `xs` que ocupan posiciones pares.\n", "\n", "+ `(impares xs)` son los elementos de `xs` que ocupan posiciones impares." ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [], "source": [ "pares :: [a] -> [a]\n", "pares [] = []\n", "pares (x:xs) = x : impares xs\n", "\n", "impares :: [a] -> [a]\n", "impares [] = []\n", "impares (_:xs) = pares xs" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1,5]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "pares [1,3,5,7]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Cálculo:\n", "```sesion\n", "pares [1,3,5,7]\n", "= 1:(impares [3,5,7])\n", "= 1:(pares [5,7])\n", "= 1:(5:(impares [7]))\n", "= 1:(5:[])\n", "= [1,5]\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Heurísticas para las definiciones recursivas\n", "\n", "**Aplicación del método: La función `producto`**\n", "\n", "+ Paso 1: Definir el tipo:\n", "\n", "```haskell\n", "producto :: [Int] -> Int\n", "```\n", "\n", "+ Paso 2: Enumerar los casos:\n", "\n", "```haskell\n", "producto :: [Int] -> Int\n", "producto [] =\n", "producto (n:ns) =\n", "```\n", "\n", "+ Paso 3: Definir los casos simples:\n", "\n", "```haskell\n", "producto :: [Int] -> Int\n", "producto [] = 1\n", "producto (n:ns) =\n", "```\n", "\n", "+ Paso 4: Definir los otros casos:\n", "\n", "```haskell\n", "producto :: [Int] -> Int\n", "producto [] = 1\n", "producto (n:ns) = n * producto ns\n", "```\n", "+ Paso 5: Generalizar y simplificar:\n", "\n", "```haskell\n", "producto :: Num a => [a] -> a\n", "producto [] = 1\n", "producto (n:ns) = n * producto ns\n", "```\n", "\n", "**Aplicación del método: La función `drop`**\n", "\n", "+ Paso 1: Definir el tipo:\n", "\n", "```haskell\n", "drop :: Int -> [a] -> [a]\n", "```\n", "\n", "+ Paso 2: Enumerar los casos:\n", "\n", "```haskell\n", "drop :: Int -> [a] -> [a]\n", "drop 0 [] =\n", "drop 0 (x:xs) =\n", "drop n [] =\n", "drop n (x:xs) =\n", "```\n", "\n", "+ Paso 3: Definir los casos simples:\n", "\n", "```haskell\n", "drop :: Int -> [a] -> [a]\n", "drop 0 [] = []\n", "drop 0 (x:xs) = x:xs\n", "drop n [] = []\n", "drop n (x:xs) =\n", "```\n", "\n", "+ Paso 4: Definir los otros casos:\n", "\n", "```haskell\n", "drop :: Int -> [a] -> [a]\n", "drop 0 [] = []\n", "drop 0 (x:xs) = x:xs\n", "drop n [] = []\n", "drop n (x:xs) = drop n xs\n", "```\n", "\n", "+ Paso 5: Generalizar y simplificar:\n", "\n", "```haskell\n", "drop :: Integral b => b -> [a] -> [a]\n", "drop 0 xs = xs\n", "drop n [] = []\n", "drop n (_:xs) = drop n xs\n", "```\n", "\n", "**Aplicación del método: La función `init`**\n", "\n", "+ `init` elimina el último elemento de una lista no vacía.\n", "\n", "+ Paso 1: Definir el tipo:\n", "\n", "```haskell\n", "init :: [a] -> [a]\n", "```\n", "\n", "+ Paso 2: Enumerar los casos:\n", "\n", "```haskell\n", "init :: [a] -> [a]\n", "init (x:xs) =\n", "```\n", "\n", "+ Paso 3: Definir los casos simples:\n", "\n", "```haskell\n", "init :: [a] -> [a]\n", "init (x:xs) | null xs = []\n", " | otherwise =\n", "```\n", "\n", "+ Paso 4: Definir los otros casos:\n", "\n", "```haskell\n", "init :: [a] -> [a]\n", "init (x:xs) | null xs = []\n", " | otherwise = x : init xs\n", "```\n", "\n", "+ Paso 5: Generalizar y simplificar:\n", "\n", "```haskell\n", "init :: [a] -> [a]\n", "init [_] = []\n", "init (x:xs) = x : init xs\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Bibliografía\n", "\n", "+ R. Bird. *Introducción a la programación funcional con Haskell*. Prentice Hall, 2000.\n", " + Cap. 3: Números.\n", " + Cap. 4: Listas.\n", "\n", "+ G. Hutton. *Programming in Haskell*. Cambridge University Press, 2007.\n", " + Cap. 6: Recursive functions.\n", "\n", "+ B. O'Sullivan, D. Stewart y J. Goerzen. *Real World Haskell*. O'Reilly, 2008.\n", " + Cap. 2: Types and Functions.\n", "\n", "+ B.C. Ruiz, F. Gutiérrez, P. Guerrero y J.E. Gallardo. *Razonando con\n", " Haskell*. Thompson, 2004.\n", " + Cap. 2: Introducción a Haskell.\n", " + Cap. 6: Programación con listas.\n", "\n", "+ S. Thompson. *Haskell: The Craft of Functional Programming*, Second\n", " Edition. Addison-Wesley, 1999.\n", " + Cap. 4: Designing and writing programs." ] } ], "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 }