En "Funciones de Lista I" intencionalmente incluí solamente las funciones que no toman otra función como argumento. De las que usan otra funciòn hay dos casos muy importantes, que son el bloque de construcciòn básico de muchas funciones más complicadas.
La primera es el mapa, del que existe la forma más general fmap pero normalmente se usa simplemente map, que es la que opera sobre listas. La diferencia está en la declaración de tipo:
Prelude> :t fmap fmap :: (Functor f) => (a -> b) -> f a -> f b Prelude> :t map map :: (a -> b) -> [a] -> [b]
fmap pide que haya un "contenedor" f (que sea functor) en el que haya guardadas cosas de tipo 'a', les aplica a todas una función de tipo '(a -> b)', eso es, que recibe un argumento de tipo 'a' y el resultado es de tipo 'b', y construye otro contenedor del mismo tipo para guardar todos los resultados.
Que algo sea de tipo functor tiene varias propiedades algebraicas, pero la que importa aquí es que, si es un functor, entonces se le puede aplicar un mapa. Por supuesto, la lista es una especie de contenedor, y es functor.
Ejemplos (recordar: le aplica la misma función a todos los elementos en el contenedor):
-- Le suma 1 a todos los números entre 1 y 10 Prelude> map (+1) [1..10] [2,3,4,5,6,7,8,9,10,11] -- Hace una lista del código numérico de las letras en esa cadena Prelude> map fromEnum "hola mundo" [104,111,108,97,32,109,117,110,100,111]
La segunda forma son los pliegues, y los hay de muchos tipos; primero se dividen en fold y scan, siendo 'scan' una versiòn "con memoria" de 'fold'. Luego, en listas, o en otras estructuras en las que se identifique un orden, y que sean finitas al menos por un lado, los pliegues se pueden hacer "por la izquierda" o "por la derecha" (solamente del lado que sea finito, si es el caso).
Así como un mapa es la generalización funcional de
for elemento in lista: elemento = func (elemento)
el pliegue es la generalización de
for elemento in lista: resultado = func(resultado, elemento)
si es por un lado, o
for elemento in lista.reverse(): resultado = func(elemento, resultado)
si es por el otro. El primer caso se llama foldl y, el segundo, foldr. Es importante notar que 'foldl' recorre la lista de izquierda a derecha, y 'foldr' lo hace de derecha a izquierda (por eso el "reverse" en el pseudocódigo imperativo).
Ejemplos:
El primer argumento es una función que toma dos argumentos, el segundo es el valor inicial, y el tercero es la lista sobre la que se va a realizar el pliegue.
El 'foldl', aquí, lo que hace equivalente a:
resultado = 10 resultado = resultado/3 resultado = resultado/2 resultado = resultado/5
y 'foldr' es equivalente a:
resultado = 10 resultado = 5/resultado resultado = 2/resultado resultado = 3/resultado
Para ver, paso por paso, cuales son los resultados intermedios (la parte de "con memoria"), se emplean los scan equivalentes:
Prelude> scanl (/) 10 [3,2,5] [10.0,3.3333333333333335,1.6666666666666667,0.33333333333333337] Prelude> scanr (/) 10 [3,2,5] [0.75,4.0,0.5,10.0]
Los resultados del 'scanl' se leen de izquierda a derecha, y los del 'scanr' se leen de izquierda a derecha.
Los pliegues se emplean como base para varias funciones de la biblioteca estándar:
concat es equivalente a 'foldr (++) []':
Prelude> concat ["foo", "bar", "baz", "quux"] "foobarbazquux" Prelude> foldr (++) [] ["foo", "bar", "baz", "quux"] "foobarbazquux"
reverse es equivalente a 'foldl (flip (:)) []':
Como comentario, flip cambia el orden de los argumentos de una función; se emplea cuando se quiere crear una función aplicada parcialmente con el segundo argumento, no el primero. Hablaré de esto en más detalle en el tutorial apropiado. Ejemplo:
-- normal; divide 2 (el valor fijo) entre el argumento Prelude> ((/) 2) 10 0.2 -- con flip; divide el argumento entre 2 (el valor fijo) Prelude> ((flip (/)) 2) 10 5.0 Prelude> (:) 'a' ['b'] "ab" Prelude> (flip (:)) ['a'] 'b' "ba"
and y or están definidos como 'foldr (&&) True' y 'foldr (||) False', respectivamente.
Prelude> and [True, True, True] True Prelude> foldr (&&) True [True, True, True] True Prelude> or [True, False, False] True Prelude> foldr (||) False [True, False, False] True
sum y product producen la suma o el producto de todos los números en la lista. 'product' es una forma práctica de calcular el factorial.
Están definidos como 'fold + 0' y 'foldr * 1', respectivamente.
Prelude> sum [1..10] 55 Prelude> product [1..7] 5040 Prelude> foldl (+) 0 [1..10] 55 Prelude> foldl (*) 1 [1..7] 5040
maximum y minimum regresan el mayor y el menor valor en la lista; están definidos como 'foldl1 max' y 'foldl1 min', respectivamente.
Prelude> maximum [3, 5, 2, 8, 14, 6, 3] 14 Prelude> minimum [3, 5, 2, 8, 14, 6, 3] 2 Prelude> foldl1 max [3, 5, 2, 8, 14, 6, 3] 14 Prelude> foldl1 min [3, 5, 2, 8, 14, 6, 3] 2
foldl1 y foldr1 son iguales a las versiones sin '1', pero no toman un valor inicial; seleccionan inmediatamente el primer valor de la lista, el más a la izquierda en 'foldr1' y el más a la derecha en 'foldr1'.
Como posiblemente ya se haya notado, es muy común emplear los pliegues con la forma "pliegue", "función", "elemento neutro de la función", "lista".
