← Volver a los ejercicios

reduce y fold: elija el valor de cada expresión

Las 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.

1. Las cuatro definiciones

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.

2. Los ocho ítems

3. Lo que se lleva de aquí

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.