Diferencias

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

--- introalg:taller08_6 [2008/06/03 02:24] – creado laura
+++ introalg:taller08_6 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
@@ Línea 1: / Línea 1: @@
 ====== Clase 6 ======
-===== Optimización de cómputo =====
+===== Mejorando al eficiencia (optimización de cómputo) =====
+Vimos que hay diferentes formas de definir una misma función. Estas distintas definiciones pueden resultar muy distintas en eficiencia. Vamos a ver algunas estrategias para mejorar la eficiencia de las funciones.
 ==== Siendo verdaderamente recursivos en dos argumentos ====
@@ Línea 36: / Línea 38: @@
 ==== Explotando el absorbente ====
+Otra forma de optimizar el cómputo es cortando la recursión en el momento en que el resultado queda determinado y no puede ser cambiado en ninguna iteración posterior de la función, independientemente de los valores que la función encuentre. Eso pasa típicamente cuando se encuentra el valor absorbente del operador que estemos usando.
+Recordemos que el absorbente es el contrario exacto del neutro: para una determinada operación binaria, aplicar la operación a cualquier valor y el absorbente devuelve siempre el absorbente.
+Veamos un ejemplo con la función //existe//. Cuando la habíamos definido con recursión clásica, la definimos así:
+  existe :: Eq a => a -> [a] -> Bool
+  existe a [] = False
+  existe a (x:xs) = x == a || existe a xs
+o bien, usando foldr:
+  existe' :: Eq a => a -> [a] -> Bool
+  existe' a xs = foldr (||) False (map (igual a) xs)
+    where
+      igual :: Eq a => a -> a -> Bool
+      igual x y = x == y
+Sin embargo, hay una forma más eficiente de definirla:
+  existe'' :: Eq a => a -> [a] -> Bool
+  existe'' a [] = False
+  existe'' a (x:xs) | (x == a) == True  = True
+                    | (x == a) == False = existe'' a xs
+De esta forma, la recursión se corta en dos casos: cuando llegamos al final, en que se devuelve el neutro (//False//) o cuando encontramos al absorbente (//True//). En el caso recursivo no se acumula ningún resultado, aunque esta función es un acumulador, ya que sabemos de antemano que sólo puede haber dos resultados: el neutro o el absorbente, y tenemos definidos los casos en que nos va a devolver el uno o el otro.
+Podemos aplicar esta estrategia de optimización para los casos de acumuladores con un absorbente: la multiplicación, el paratodo (que es un //&&// generalizado).
+En el caso concreto de Haskell, este tipo de optimización no es especialmente eficiente, por la forma como funciona Haskell, sin embargo, esta estrategia dá muy buena optimización para otros lenguajes.
 ===== Tipos definidos por el usuario =====
-Main> :t (==)
+Para este apartado vamos a usar las filminas de [[http://www.lcc.uma.es/~pacog/|Paco Gutiérrez]] sobre [[http://www.lcc.uma.es/~pacog/apuntes/pd/cap04.pdf|definiciones de tipo]] y [[http://www.lcc.uma.es/~pacog/apuntes/pd/cap05.pdf|el sistema de clases de Haskell]].
-(==) :: Eq a ⇒ a → a → Bool
-Main> :t (+)
+===== Ejercicios de repaso =====
-(+) :: Num a ⇒ a → a → a
+==== Recursión en dos argumentos ====
+* Definir la función //segmentoInicial :: Int -> [a] -> [a]//, que dado un natural //n// y una lista //[a]//, devuelve los //n// primeros elementos de la lista.
+* Definir la función //subsegmento :: Int -> Int -> [a] -> [a]//, que dados dos naturales //i// y //j//, devuelve el segmento de la lista que se encuentra entre las posiciones //i// y //j// de la lista, ambos inclusive. Para ello, usar la función //segmentoInicial// y una modificación de la función //nesimo//.
+* Definir la función //combina :: Ord a => [a] -> [a] -> [a]//, que dadas dos listas nos devuelve una lista que combina las dos anteriores con sus elementos ordenados de menor a mayor. Implementen diferentes estrategias para obtener los elementos ordenados: ordenar las listas de antemano y después combinarlas (en una estrategia similar a //encuentraEstafador''//), ordenar la lista resultante, o comprobar si están ordenadas.
+* Definir la función //eliminaDuplicados :: [a] -> [a]//, que elimina los elementos duplicados de una lista.
+* Definir la función //fusiona :: Ord a => [a] -> [a] -> [a]//, que dadas dos listas nos devuelve una lista que combina las dos anteriores con sus elementos ordenados de menor a mayor, sin duplicados.
+* Definir la función //esPalindromo :: [a] -> Bool//, que dada una lista nos dice si es un palíndromo, es decir, si es igual leída de izquierda a derecha que de derecha a izquierda.
+* Definir la función //divideEnDos :: Int -> [a] -> ([a],[a])//, que divide una lista en dos, donde la longitud de la primera viene dada por el primer argumento de la función.