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 19:34] – Ejemplo de duplicar cuando no decrementa su parámetro nicolaswintroalg:taller07_3 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
Línea 35: 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 68: Línea 68:
  
 <code> <code>
-fib n = fib (n-1) + fib (n-2)+fib (n+2) = fib (n+1) + fib n
 </code> </code>
  
Línea 104: Línea 104:
 [False,True,True,True,False] [False,True,True,True,False]
 </code> </code>
 +
 +
  
  
Línea 144: Línea 146:
   []   []
   Main> duplicar [10]   Main> duplicar [10]
-  [20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20+  [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 155: Línea 157:
   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 164: 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 182: 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 187: 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 220: 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 228: 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 235: 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.1177097684.txt.gz · Última modificación: 2018/08/10 03:03 (editor externo)