Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza:
introalg:taller07_3

Diferencias

Muestra las diferencias entre dos versiones de la página.

Enlace a la vista de comparación

Ambos lados, revisión anteriorRevisión previa
Próxima revisión		Revisión previa
introalg:taller07_3 [2007/04/20 18:25] – lauraintroalg:taller07_3 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
Línea 20: Línea 20:
  
 <code> <code>
-sucesion_inversa :: Int -> [Int] +sucesionInversa :: Int -> [Int] 
-sucesion_inversa n | n > 0  = n : sucesion (n-1) +sucesionInversa n | 0<=n = n : sucesionInversa (n-1) 
-                   | n <= 0 = [0]+                  | n<0  = []
 </code> </code>
  
-En esta función, si //n// es negativo o 0, se corta la recursividad, y además, para cualquier valor de //n//, sabemos que en algún momento vamos a llegar a un valor negativo o 0, ya que en cada aplicación del paso recursivo se decrementa el valor de n.+En esta función, si //n// es negativo, se corta la recursividad, y además, para cualquier valor de //n//, sabemos que en algún momento vamos a llegar a un valor negativo, ya que en cada aplicación del paso recursivo se decrementa el valor de n. 
  
 ==== Definición de factorial ==== ==== Definición de factorial ====
Línea 34: Línea 35:
 factorial :: Int -> Int factorial :: Int -> Int
 factorial 0     = 1                     -- caso base factorial 0     = 1                     -- caso base
-factorial (n+1) = n * factorial (n-1)   -- caso inductivo+factorial (n+1) = (n+1) * factorial n   -- caso inductivo
 </code> </code>
  
Línea 54: Línea 55:
 3 * 2 * 1 * factorial (1-1) 3 * 2 * 1 * factorial (1-1)
 = {álgebra} = {álgebra}
-3 * 2 * 1 * factorial ()+3 * 2 * 1 * factorial (0)
 = {factorial 0 = 1} = {factorial 0 = 1}
 3 * 2 * 1 * 1 3 * 2 * 1 * 1
Línea 60: Línea 61:
 6 6
 </code> </code>
 +
  
 ==== Definición de Sucesión de Fibonacci ==== ==== Definición de Sucesión de Fibonacci ====
Línea 66: Línea 68:
  
 <code> <code>
-fib n = fib (n-1) + fib (n-2)+fib (n+2) = fib (n+1) + fib n
 </code> </code>
  
-Una particularidad de la Sucesión de Fibonacci es que es **doblemente recursiva**, ya que se llama dos veces a sí misma en cada paso, y no tiene un caso base, sino dos: fib(0) = 0 y fib(1) = 1. +Una particularidad de la Sucesión de Fibonacci es que es **doblemente recursiva**, ya que se llama dos veces a sí misma en cada paso, y no tiene un caso base, sino dos: fib 0 = 0 y fib 1 = 1. 
  
 ===== Recursividad en listas ===== ===== Recursividad en listas =====
Línea 102: Línea 104:
 [False,True,True,True,False] [False,True,True,True,False]
 </code> </code>
 +
 +
 +
 +
  
 ==== Aplicar (Map) ==== ==== Aplicar (Map) ====
Línea 111: Línea 117:
 <code> <code>
   duplicar :: [Int] -> [Int]   duplicar :: [Int] -> [Int]
-  duplicar [] = []               +  duplicar []     = []
   duplicar (x:xs) = 2*x : xs        duplicar (x:xs) = 2*x : xs     
 </code> </code>
  
-En este caso, la función no se llama a sí misma, así que sólo se aplicaría a la cabeza de la lista, y no a todo el resto.+Probamos la función y obtenemos 
 + 
 +  Main> duplicar [] 
 +  [] 
 +  Main> duplicar [10] 
 +  [20] 
 +  Main> duplicar [10,20] 
 +  [20,20] 
 +  Main> duplicar [10,20,30] 
 +  [20,20,30] 
 + 
 +En este caso, la función **no se llama a sí misma**, así que sólo se aplicaría a la cabeza de la lista, y no a todo el resto. 
 +Corregimos este error.
  
 <code> <code>
   duplicar :: [Int] -> [Int]   duplicar :: [Int] -> [Int]
-  duplicar [] = []               +  duplicar []     = []               
   duplicar (x:xs) = 2*x : duplicar (x:xs)        duplicar (x:xs) = 2*x : duplicar (x:xs)     
 </code> </code>
 +
 +Probamos de nuevo la definición y obtenemos
 +
 +  Main> duplicar []
 +  []
 +  Main> duplicar [10]
 +  [20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20 ...
  
 En este caso, el caso recursivo no modifica su condición de aplicación, así que nunca va a llegar al caso base y por lo tanto caerá en un bucle infinito. En este caso, el caso recursivo no modifica su condición de aplicación, así que nunca va a llegar al caso base y por lo tanto caerá en un bucle infinito.
Línea 129: Línea 154:
 <code> <code>
   duplicar :: [Int] -> [Int]   duplicar :: [Int] -> [Int]
-  duplicar [] = []                        -- caso base+  duplicar []     = []                    -- caso base
   duplicar (x:xs) = 2*x : duplicar xs     -- caso inductivo   duplicar (x:xs) = 2*x : duplicar xs     -- caso inductivo
 </code> </code>
 +
 +La probamos.
 +
 +  Main> duplicar [10,20]
 +  [20,40]
 +  Main> duplicar [10,20,30]
 +  [20,40,60]
 +  Main> duplicar [1..10]
 +  [2,4,6,8,10,12,14,16,18,20]
 +  Main> duplicar [0..10]
 +  [0,2,4,6,8,10,12,14,16,18,20]
 +
  
 Notar que en las funciones de tipo "map" toman siempre a una lista como argumento y devuelven una lista como resultado; la lista de resultado se obtiene de **concatenar** el resultado de aplicar una función dada a cada uno de los elementos de la lista argumento. Notar que en las funciones de tipo "map" toman siempre a una lista como argumento y devuelven una lista como resultado; la lista de resultado se obtiene de **concatenar** el resultado de aplicar una función dada a cada uno de los elementos de la lista argumento.
 +
 +
 +
  
 ==== Acumular (Fold) ==== ==== Acumular (Fold) ====
Línea 141: Línea 181:
 <code> <code>
   sumatoria :: [Int] -> Int   sumatoria :: [Int] -> Int
-  sumatoria [] = 0+  sumatoria []     = 0
   sumatoria (x:xs) = x + sumatoria xs   sumatoria (x:xs) = x + sumatoria xs
 </code> </code>
  
 Notar que en las funciones de tipo "fold" toman una lista como argumento. El resultado se obtiene de **acumular** los resultados de aplicar una función dada a cada uno de los elementos de la lista argumento. La forma en como se acumulan los resultados depende de cada función: en la función //sumatoria// se suman, en la función //productoria// se multiplican, etc. Notar que en las funciones de tipo "fold" toman una lista como argumento. El resultado se obtiene de **acumular** los resultados de aplicar una función dada a cada uno de los elementos de la lista argumento. La forma en como se acumulan los resultados depende de cada función: en la función //sumatoria// se suman, en la función //productoria// se multiplican, etc.
 +
 +Probamos en algunos valores de entrada.
 +
 +  Main> sumatoria []
 +  0
 +  Main> sumatoria [0]
 +  0
 +  Main> sumatoria [0,0]
 +  0
 +  Main> sumatoria [1..3]
 +  6
 +  Main> sumatoria [1..10]
 +  55
 +  Main> sumatoria [1..10000]
 +  50005000
  
 ==== Seleccionar (Filter) ==== ==== Seleccionar (Filter) ====
Línea 159: Línea 214:
  
 Notar que en las funciones de tipo "filter" toman una lista como argumento y devuelven una lista como resultado. La lista de resultado se obtiene de concatenar los elementos de la lista de argumento que devuelven un valor especificado para una función dada (típicamente, los elementos que devuelven True para un predicado). Notar que en las funciones de tipo "filter" toman una lista como argumento y devuelven una lista como resultado. La lista de resultado se obtiene de concatenar los elementos de la lista de argumento que devuelven un valor especificado para una función dada (típicamente, los elementos que devuelven True para un predicado).
 +
 +Veamos como funciona.
 +
 +  Main> empiezaM ["marta", "liliana", "esther", "mario"]
 +  ["marta","mario"]
 +  Main> empiezaM ["Merceditas", "Tabaré"]
 +  []
 +
 +==== Múltiples casos base ====
 +
 +Recordemos que el número de casos base depende del problema concreto que estemos tratando. En la Sucesión de Fibonacci, encontramos dos casos base: fib 0 = 1 y fib 1 = 1. En la mayor parte de casos con listas tenemos un solo caso base, el de la lista vacía [], pero para algunos problemas podemos necesitar 2 o más casos base. Veamos por ejemplo la función //emparejar.xs//, //emparejar : [String] -> [(String,String)]//, que pone en parejas los elementos de una lista de strings que representen, por ejemplo, los nombres de los chicos de una clase, y nos devuelve una forma de agruparlos en parejas para, por ejemplo, distribuirlos en los asientos de un colectivo.
 +
 +<code>
 +emparejar :: [String] -> [(String,String)]
 +emparejar (x:y:xs) = (x,y) : emparejar xs
 +emparejar [x]      = [(x,x)]
 +emparejar []       = []
 +</code>
 +
 +Veamos cómo funciona.
 +
 +  Main> emparejar ["Pepa","Lola","Juan","Pili","Pedro"]
 +  [("Pepa","Lola"),("Juan","Pili"),("Pedro","Pedro")]
 +
  
 ===== Ejercicios ===== ===== Ejercicios =====
Línea 164: Línea 243:
 === Aplicar === === Aplicar ===
  
-   * Definir la función //veintePorCiento.xs//, //veintePorCiento : [Int] -> [Float]// que dada una lista de enteros devuelve una lista con el 20% de cada elemento de la lista.+   * Definir la función //veintePorCiento.xs//, //veintePorCiento : [Float] -> [Float]// que dada una lista de números  devuelve una lista con el 20% de cada elemento de la lista.
  
   probar con [345,20,46,0], [] y [3].   probar con [345,20,46,0], [] y [3].
  
-   * Generalizar la función //veintePorCiento// definiendo //porCiento.n.xs//, //porCiento : Int -> [Int] -> [Float]// que dado un número //n// y una lista, devuelve el //n// por ciento de cada uno de los elementos de la lista. Ejemplo: //porCiento 10 [200,87,6] = [20,8.7,0.6]//+   * Generalizar la función //veintePorCiento// definiendo //porCiento.n.xs//, //porCiento : Int -> [Float] -> [Float]// que dado un número //n// y una lista, devuelve el //n// por ciento de cada uno de los elementos de la lista. Ejemplo: //porCiento 10 [200,87,6] = [20,8.7,0.6]//. Puede ser útil la función ''fromIntegral'' que transforma un ''Int'' en ''Float''.
  
    * Generalizar la función //duplicar// definiendo //multiplicar.n.xs//, //multiplicar : Int -> [Int] -> [Int]// que dada un número //n// y una lista, multiplica cada uno de los elementos por //n//. Ejemplo: //multiplicar.3.[3,0,-2] = [9,0,-6]//.    * Generalizar la función //duplicar// definiendo //multiplicar.n.xs//, //multiplicar : Int -> [Int] -> [Int]// que dada un número //n// y una lista, multiplica cada uno de los elementos por //n//. Ejemplo: //multiplicar.3.[3,0,-2] = [9,0,-6]//.
Línea 197: Línea 276:
 === Miscelánea === === Miscelánea ===
  
-   * Escribir la función que calcula la Sucesión de Fibonacci, //fib.n//, //fib : Int -> Int//, que se define así: //fib(n) = fib(n-1) + fib(n-2)//.+   * Escribir la función que calcula la Sucesión de Fibonacci, //fib.n//, //fib : Int -> Int//, que se define así: //fib (n+2) = fib (n+1) + fib n//.
  
   probar con 4, 3, 2, 1 y 0.   probar con 4, 3, 2, 1 y 0.
Línea 205: Línea 284:
   probar con [(1,1)], [] y [(2,1),(1,2)].   probar con [(1,1)], [] y [(2,1),(1,2)].
  
-   * Definir la función //todos0y1.xs//, //todos0y1 : [Int] -> Bool// que dada una lista devuelve //True// si ésta consiste sólo de 0s y 1s.+   * Definir la función //todos0y1.xs//, //todos0y1 : [Int] -> Bool// que dada una lista devuelve //True// si ésta consiste sólo de 0s y 1s. Ayuda: para construir el Booleano del resultado no pueden usar el constructor de listas ":", sino que tienen que usar algún operador que dé como resultado un Booleano.
  
   probar con [0], [], [1], [0,0,0,0], [0,1,0,1], [1,2,3], ['a','b','c']   probar con [0], [], [1], [0,0,0,0], [0,1,0,1], [1,2,3], ['a','b','c']
Línea 212: Línea 291:
  
   probar con [], [0,0,0,0], [1,2,3,4], [0] y [1,5,7,0,9]   probar con [], [0,0,0,0], [1,2,3,4], [0] y [1,5,7,0,9]
 +
 +   * Definir la función //repetir.n.x//, //repetir : Int -> a -> [a]// que dado un elemento lo repite n veces, dando como resultado una lista que contiene las repeticiones.
 +
 +  probar con 8 y "bobo", 0 y 33 y 4 y [].
  
    * Definir la función //esMultiploLista.n.xs//, //esMultiploLista : Int -> [Int] -> [Bool]// que dado un entero //n// y una lista de enteros //xs// devuelve una lista de booleanos que indica si //n// es múltiplo de cada uno de los elementos de la lista //xs//. Ejemplo: //esMultiploLista.6.[2,3,5] = [True,True,False]//. Otro ejemplo: //esMultiploLista.18.[4,2,3,6,8] = [False,True,True,True,False]//.    * Definir la función //esMultiploLista.n.xs//, //esMultiploLista : Int -> [Int] -> [Bool]// que dado un entero //n// y una lista de enteros //xs// devuelve una lista de booleanos que indica si //n// es múltiplo de cada uno de los elementos de la lista //xs//. Ejemplo: //esMultiploLista.6.[2,3,5] = [True,True,False]//. Otro ejemplo: //esMultiploLista.18.[4,2,3,6,8] = [False,True,True,True,False]//.
introalg/taller07_3.1177093521.txt.gz · Última modificación: 2018/08/10 03:03 (editor externo)