Pliegues, una forma de encapsular las iteraciones en listas

Es muy común que trabajemos con listas y también es muy común que tengamos que recorrerlas para obtener un valor. Por ejemplo si queremos el promedio de una lista de números, debemos sumar todos los números para luego dividirlos por la cantidad.

Este es un patrón muy común y por lo tanto en Haskell nos brinda unas cuantas funciones muy útiles para encapsular este comportamiento. Estas funciones son llamadas pliegues (o folds en ingles).

Un pliegue toma una función binaria, un valor inicial (llamémoslo acumulador) y una lista que plegar. La función binaria toma dos parámetros por si misma. La función binaria es llamada con el acumulador y el primer (o último) elemento y produce un nuevo acumulador. Luego, la función binaria se vuelve a llamar junto al nuevo acumulador y al nuevo primer (o último) elemento de la lista, y así sucesivamente. Cuando se ha recorrido la lista completa, solo permanece un acumulador, que es el valor al que se ha reducido la lista.

La función foldl, también llamada pliegue por la izquierda. Esta pliega la lista empezando desde la izquierda. La función binaria es aplicada junto a el valor inicial y la cabeza de la lista. Esto produce un nuevo acumulador y la función binaria es vuelta a llamar con ese nuevo valor y el siguiente elemento, etc.

Vamos a implementar una función “sumarLista”:

sumaLista :: (Num a) => [a] -> a
sumaLista xs = foldl (\acc x -> acc + x) 0 xs

Probamos:

ghci> sumaLista [1,2,3,4]
10

Vamos a analizar un poco este pliegue. \acc x -> acc + x es la función binaria donde suma sus parámetros. 0 es el valor inicial y xs es la lista que debe ser plegada. Al inicio acc es igual a 0 (dado que esto lo indicamos en el segundo parámetro) y x toma el primer elemento de la lista 1, el resultado de la suma es 1 y va a ser el valor del acumulador para la segunda iteración.

Si tenemos en cuenta que las funciones están currificadas, podemos escribir esta implementación de forma más bonita como:

sumaLista :: (Num a) => [a] -> a
sumaLista = foldl (+) 0

La función lambda (\acc x -> acc + x) es lo mismo que (+). Podemos omitir el parámetro xs ya que al llamar a foldl (+) 0 nos devuelve una función que toma una lista. Generalmente, si tienes una función del tipo foo a = bar b a la puedes escribir como foo = bar b gracias a la currificación.

Ahora los pliegues por la derecha funcionan igual que los pliegues por la izquierda, solo que el acumulador consume elemento por la derecha. La función binaria de los pliegues por la izquierda como primer parámetro el acumulador y el valor actual como segundo parámetro, la función binaria de los pliegues por la derecha tiene el valor actual como primer parámetro y el acumulador después. Tiene sentido ya que el pliegue por la derecha tiene el acumulador a la derecha.

Las funciones foldl1 y foldr1 son muy parecidas a foldl y foldr, solo que en lugar que no necesitas indicar un valor de inicio. Asumen que el primer (o el último) elemento de la lista es valor de inicio, luego empiezan a plegar la lista por el elemento siguiente. Por lo tanto la función sumaLista puede ser implementada como: sumaLista = foldl1 (+)

Los pliegues no son una característica únicamente de Haskell, están presentes en varios lenguajes como Ruby, Java 8, Scala, Swift, Python, C#, Clojure, Erlang, Groovy, javascript, PHP, Smalltalk, etc.

Veamos nuestro ejemplo de sumaLista en otros lenguajes:

Ruby

> (1..4).inject(&:+)
=> 10
>(1..4).reduce(&:+)
=> 10

Groovy

[1, 2, 3, 4].inject(0, { sum, value -> sum + value })

Javascript

[1, 2, 3,4].reduce(function(x,y){return x+y})
10
[1, 2, 3,4].reduceRight(function(x,y){return x+y})
10

Clojure

(reduce + [1 2 3 4])
10

Scala

List(1,2,3,4).foldLeft(0)((x, sum) => sum + x)  //> res0: Int = 10

Erlang

lists:foldl(fun(X, Sum) -> X + Sum end, 0, [1, 2, 3, 4]).
10

Los pliegues nos permiten recorrer listas escribiendo muy poco código, ayudando a la legibilidad y a que los programadores perezosos escribamos menos.

Más información | Pliegues Wikipedia | Pliegues