reduce, foldl, inject, accum, etcetera

Guido Van Rossum, el diseñador de Python, dice que no le gusta la funcion reduce, tambien conocida como foldl, inject o accum. Le parece complicada, y dice que cada vez que la ve haciendo algo mas o menos complicado, tiene que agarrar lapiz y papel para darse cuenta de lo que esta haciendo.

Francamente no entiendo por que, ya que es una funcion sencilla, solo hay que encararla correctamente. Así que, voy a explicarles como usar reduce, así ya se disipa el misticismo.

En primer lugar, vamos a definir reduce. Voy a usar una sintaxis tipo javascript, que es como la de C. Alcanza con que sepan lo siguiente de la sintaxis, que lo diferencia de C, Java, C# y demases: Primero, que no hay tipos en las variables.

function (arg1, arg2, ...) { declaraciones } en javascript.

Aunque ausente de muchos lenguajes como Java o C++, en lenguajes como Python, Ruby, Lisp, Haskell, Smalltalk, Javascript, etc; las funciones son valores como cualquier otro, se pueden asignar a variables, pasar como parametros, devolverse, etc. Toda funcion que reciba una funcion por parametro o devuelva una funcion se llama "funcion de orden superior". Entonces

function (x) { return x + x; }

es una funcion dado un valor, devuelve el doble. Aclaro que cuando en javascript ponemos

function nombre (x) { etc... }

escribir eso en javascript es equivalente a escribir

var nombre = function (x) { etc...}

Vamos a definir reduce, sin más. Reduce recibe tres argumentos, un valor inicial "vi", una funcion "f", y una lista/vector/coleccion/etc "lista". La funcion "f" recibe dos valores, un valor acumulado y un elemento de la lista "lista", y devuelve otro valor. reduce aplica la "f" al primer elemento de la lista, pasandole como valor acumulado el valor inicial "vi". Lo que devuelve "f" se convierte en el nuevo valor acumulado, y asi hasta pasar por todos los elementos de la lista.

algo así:

function reduce(vi,f,lista)
{
     for(var i = 0, var accum = vi; i < lista.length; i++)
     {
           accum = f(accum, lista[i]); 
     }
     return accum; 
}

Entonces, veamos que hace esta funcion, graficamente hablando:



Entonces, podemos ver, suponiendo que lista tenga los elementos 1, 2 y 3.

reduce llama a la funcion, totalAcumulado vale el valor inicial, 0, y elem, 1. La funcion devuelve la suma de 0 + 1, entonces la funcion devuelve 1. Este valor pasa a ser el nuevo totalAcumulado. Ahora, reduce llama a la funcion de nuevo, pero ahora, totalAcumulado vale 1, y elem vale 2. La funcion devuelve la suma de los elementos, entonces totalAcumulado pasa a ser 3 y elem pasa a ser 3, y la suma devuelve 9. como no hay mas elementos en la lista, reduce devuelve 6, que es la sumatoria de todos los elementos de la lista.

Expresado en una tablita:



como podemos ver, lo que devuelve la funcion pasa a ser el nuevo total acumulado.

Por cierto, aca podemos ver cierta recursividad, fijense como podemos decir que el resultado de la funcion pasa a ser el nuevo valor inicial. Una definicion recursiva de reduce vendria a ser:

function reduce(vi, f, lista) 
{
 if(lista.length == 0) return vi;
 return reduce(f(vi, first(lista)), rest(lista));
}

donde first(lista) devuelve el primer elemento de la lista, y rest(lista) devuelve una nueva lista sin el primer elemento.

si tantos parentesis les marean, veanlo de vuelta así

function reduce(vi, f, lista) 
{
 /* si la lista esta vacía, devuelvo vi */
 if(lista.length == 0) return vi;
 /* primer elemento de la lista */
        var pri = first(lista); 
 /* primer elemento de la lista */
        var resto = rest(lista); 
 /* nuevo valor inicial, vi es el total acumulado, pri es el valor de la lista */
        var nuevoVI = f(vi, pri);
 return reduce(nuevoVI, f, resto);
}

repitiendo el ejemplo de antes, estamos diciendo que (imaginemos por un momento que javascript tiene una sintaxis para las listas/vectores del tipo [elemento1, elemento2, elemento3, ...]:

var f = function (totalAcumulado, elem) { return totalAcumulado + elem; };
reduce(0, f, [1,2,3]);

devuelve

reduce(f(0,1), f, [2,3]);

(y como f(0,1) = 1, devuelve)

reduce(f(1,2), f, [3]);

(y como f(1,2) = 3, devuelve)

reduce(f(3,3), f, []);

(y como f(3,3) = 6, y la lista esta vacia, devuelve el valor inicial, que es 6).

En general, cada ves que vemos

reduce(vi, function(total, elem) { return expresion }, lista)

podemos suponerlo aproximadamente equivalente a

total = vi;
for(elem in lista)
{
    total = expresion;
}
return total;


resumiendo este embole, es claro ver que hay una redundacia de elementos al escribir el algoritmo entero. Realmente se gana claridad por sobre reduce?

Por ultimo, y ya que guido van rossum dice que todo uso de reduce mas alla de reduce(0, +, listaDeNumeros) o reduce(1, *, listaDeNumeros) es complicado, piensen que hacen estas funciones

reduce(-1, function(total, elem) { return total > elem ? total : elem; }, listaDeNumeros);

reduce(0, function(total, elem) { return total + elem.length; }, listaDeStrings);

(recuerden que aca "total" se refiere no al total completo, sino el total computado hasta el momento).