reduce y fold: elija el valor de cada expresiónLas cuatro funciones combinan los elementos de una lista en un solo valor con un operador binario. Se diferencian en dos cosas: hacia qué lado asocian y si reciben un valor inicial. Abajo hay ocho expresiones, cada una con cuatro valores posibles y uno solo correcto.
Las dos versiones Left pasan el acumulador
hacia adentro y devuelven el resultado de la llamada recursiva; las dos
versiones Right aplican el operador sobre lo que esa llamada
devuelve. Los dos reduce no tienen caso para
Nil que devuelva un valor.
La diferencia entre reduce y
fold está en de dónde sale el acumulador inicial.
foldLeft lo recibe como parámetro, y su primer caso,
case Nil => z, devuelve ese valor cuando no hay nada que
combinar: sobre la lista vacía responde 0 con la suma y
1 con el producto, según lo que se haya escrito.
reduceLeft usa el primer elemento de la lista, como se ve en
case x :: xs => (xs foldLeft x)(op), y por eso sobre
Nil no tiene con qué arrancar. El operador que recibe tampoco
se lo puede decir: (T, T) => T no trae el neutro de la
operación. La definición (0 :: xs).reduceLeft(_ + _) resuelve
eso metiendo el neutro como un elemento más.
La asociatividad es la otra diferencia, y se lee en qué lado del operador
queda el resultado de la llamada recursiva. En foldLeft el
acumulador viaja por el primer parámetro, op(z, x), así que la
cadena se arma de izquierda a derecha y el valor inicial abre la expresión:
((0 - 1) - 2) - 3. En foldRight el operador se
aplica a op(x, ...), con el resultado de la cola a la derecha,
así que el valor inicial cierra la expresión:
1 - (2 - (3 - 0)). Con la suma y el producto las dos formas
coinciden; con la resta y la división no, y la diferencia no es un detalle
de implementación sino el resultado.
De los tipos sale la última consecuencia. El operador de
foldLeft es (U, T) => U, con el acumulador a la
izquierda, y el de foldRight es (T, U) => U,
con el elemento a la izquierda. Un operador como ::, cuyo tipo
es (T, List[T]) => List[T], encaja con el segundo y no con
el primero. También cambia la forma de la recursión: el cuerpo de
foldLeft termina en la llamada recursiva, mientras el de
foldRight tiene que esperar a que la llamada devuelva para
aplicar el operador.