Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza:
introalg:taller08_5

Diferencias

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

Enlace a la vista de comparación

Próxima revisión		Revisión previa
introalg:taller08_5 [2008/05/27 02:09] – creado lauraintroalg:taller08_5 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
Línea 15: Línea 15:
 ==== Divide y Vencerás ==== ==== Divide y Vencerás ====
  
-Veamos la función //longitud//----La función //longitud// viene ya definida en el preámbulo como //length//, pero acá la vamos a volver a definir para ver cómo funciona----, que cuenta cuántos elementos tiene una lista. Podríamos definirla así:+Veamos la función //longitud//((La función //longitud// viene ya definida en el preámbulo como //length//, pero acá la vamos a volver a definir para ver cómo funciona.)), que cuenta cuántos elementos tiene una lista. Podríamos definirla así:
  
   longitud :: [a] -> Int   longitud :: [a] -> Int
   longitud xs = foldr (+) 0 xs   longitud xs = foldr (+) 0 xs
  
-Pero esta función no anda! ¿por qué? porque el operador //+// requiere que sus argumentos sean números, y la declaración de tipos de //cuentaCuantosCumplen// no nos garantiza que la lista sea de números. Por lo tanto, habrá que garantizarlo de alguna forma: convirtiendo los elementos de la lista a números. Y además, no sólo queremos convertirlos a números, queremos convertirlos de forma que se cuente 1 por cada elemento de la lista, así que vamos a tener que convertir todos los elementos en 1. Sabemos todo esto, pero cómo lo hacemos?+Pero esta función no anda! ¿por qué? porque el operador //+// requiere que sus argumentos sean números, y la declaración de tipos de //longitud// no nos garantiza que la lista sea de números. Por lo tanto, habrá que garantizarlo de alguna forma: convirtiendo los elementos de la lista a números. Y además, no sólo queremos convertirlos a números, queremos convertirlos de forma que se cuente 1 por cada elemento de la lista, así que vamos a tener que convertir todos los elementos en 1. Sabemos todo esto, pero cómo lo hacemos?
  
 Para darnos cuenta de qué funciones hay que combinar y cómo hay que hacerlo, podemos pensar intuitivamente en lo que hay que hacer para resolver la tarea que se propone en la función, paso a paso. En primer lugar, habrá que convertir todos los elementos de la lista en 1, en segundo lugar, habrá que sumar todos esos 1 para llegar a un número que será el total de elementos. Para darnos cuenta de qué funciones hay que combinar y cómo hay que hacerlo, podemos pensar intuitivamente en lo que hay que hacer para resolver la tarea que se propone en la función, paso a paso. En primer lugar, habrá que convertir todos los elementos de la lista en 1, en segundo lugar, habrá que sumar todos esos 1 para llegar a un número que será el total de elementos.
Línea 27: Línea 27:
  
   sea1 :: a -> Int   sea1 :: a -> Int
-  sea1 = 1+  sea1 x = 1
  
 Ahora lo que tenemos que hacer es aplicar esta función a nuestra lista, mediante la función que generaliza la aplicación, //aplica// (o //map// si usamos la que viene definida en el preámbulo): Ahora lo que tenemos que hacer es aplicar esta función a nuestra lista, mediante la función que generaliza la aplicación, //aplica// (o //map// si usamos la que viene definida en el preámbulo):
Línea 37: Línea 37:
  
   longitud :: [a] -> Int   longitud :: [a] -> Int
 +  longitud xs = foldr (+) 0 (convierte1 xs)
 +
 +o bien, reemplazando //convierte1// por su definición:
 +
   longitud xs = foldr (+) 0 (map sea1 xs)   longitud xs = foldr (+) 0 (map sea1 xs)
  
Línea 46: Línea 50:
   filtraCuantosCumplen p xs = filter p xs   filtraCuantosCumplen p xs = filter p xs
  
-Esta función //filtraCuantos// nos devolverá una lista que contiene únicamente los elementos de la lista original que cumplen con el predicado //p//. Ahora necesitamos contar cuántos son estos elementos. Para eso podemos aplicar la función //longitud// que hemos visto arriba, o volver a definirla:+Esta función //filtraCuantosCumplen// nos devolverá una lista que contiene únicamente los elementos de la lista original que cumplen con el predicado //p//. Ahora necesitamos contar cuántos son estos elementos. Para eso podemos aplicar la función //longitud// que hemos visto arriba, o volver a definirla:
  
-  cuentaCuantosCumplen :: [a] -> Int +  cuenta :: [a] -> Int 
-  cuentaCuantosCumplen xs = foldr (+) 0 (map sea1 xs)+  cuenta xs = foldr (+) 0 (map sea1 xs)
  
 La función //cuantosCumplen// combinará estas dos funciones para obtener su resultado: La función //cuantosCumplen// combinará estas dos funciones para obtener su resultado:
  
   cuantosCumplen :: (a -> Bool) -> [a] -> Int   cuantosCumplen :: (a -> Bool) -> [a] -> Int
-  cuantosCumplen p xs = cuentaCuantosCumplen ( filtraCuantosCumplen xs ) +  cuantosCumplen p xs = cuenta ( filtraCuantosCumplen p xs )
- +
-esto también se puede escribir así, en Haskell: +
- +
-  cuantosCumplen p xs = cuentaCuantosCumplen . filtraCuantosCumplen xs+
  
 O también lo podemos escribir así: O también lo podemos escribir así:
Línea 122: Línea 122:
  
 Para practicar el tratamiento de casos complejos, recomendamos los ejercicios de la clase anterior, que copiamos en la sección de ejercicios. Para practicar el tratamiento de casos complejos, recomendamos los ejercicios de la clase anterior, que copiamos en la sección de ejercicios.
 +
  
  
Línea 156: Línea 157:
   encuentraEstafador :: [Int] -> [Int] -> [Int]   encuentraEstafador :: [Int] -> [Int] -> [Int]
   encuentraEstafador [] _      = []   encuentraEstafador [] _      = []
-  encuentraEstafador (x:xs) ys | existe (==x) ys = x : encuentraEstafador xs ys+  encuentraEstafador (x:xs) ys | existe x ys = x : encuentraEstafador xs ys
                                | otherwise       =     encuentraEstafador xs ys                                | otherwise       =     encuentraEstafador xs ys
  
 Esta versión es poco eficiente porque para cada elemento de la primera lista tenemos que recorrer toda la segunda lista. Sin embargo, si suponemos que las listas están ordenadas, podríamos aprovechar este hecho para recorrerlas a ambas de forma más eficiente. Esta versión es poco eficiente porque para cada elemento de la primera lista tenemos que recorrer toda la segunda lista. Sin embargo, si suponemos que las listas están ordenadas, podríamos aprovechar este hecho para recorrerlas a ambas de forma más eficiente.
  
-====Ejercicios====+=====Ejercicios=====
  
 ===Ejercicios de funciones complejas=== ===Ejercicios de funciones complejas===
introalg/taller08_5.1211854196.txt.gz · Última modificación: 2018/08/10 03:03 (editor externo)