Implementando reduce y construyendo map en Scala

Una de las ideas más interesantes de la programación funcional es que muchas operaciones sobre colecciones pueden construirse a partir de una sola función general: fold (o un reduce más flexible).

Por ejemplo, este reduce recursivo:

def reduce[A, B](list: List[A], initial: B)(f: (B, A) => B): B =

  if (list.isEmpty) initial

  else reduce(list.tail, f(initial, list.head))(f)

Recorre la lista acumulando un resultado.

¿Qué hace exactamente?

La función recibe:

• una lista
• un valor inicial
• una función acumuladora

La función f recibe:

(B, A) => B

Es decir:

• el acumulador actual (B)
• el elemento actual (A)
• y devuelve un nuevo acumulador (B)

Ejemplo: sumar números

val numbers = List(1, 2, 3, 4)

val result =  reduce(numbers, 0)((acc, n) => acc + n)

println(result)

Salida: 10

El proceso sería algo así:

(((0 + 1) + 2) + 3) + 4

Ejemplo: concatenar strings

val words = List("Hola", "Scala", "!")

val result =  reduce(words, "")((acc, word) => acc + " " + word)

println(result)

Salida: Hola Scala !

Acá viene la parte interesante.

map transforma cada elemento de una lista:

List(1, 2, 3).map(_ * 2)

Resultado: List(2, 4, 6)

Pero podemos implementarlo usando únicamente nuestro reduce.

def map[A, B](list: List[A])(f: A => B): List[B] =

  reduce(list, List.empty[B]) { (acc, elem) =>

    acc :+ f(elem)

  }

val numbers = List(1, 2, 3)

val doubled =  map(numbers)(_ * 2)

println(doubled)

Salida: List(2, 4, 6)

En cada iteración:

acc :+ f(elem)

1. Se transforma el elemento con f

2. Se agrega al acumulador

Por ejemplo:

List()

List(2)

List(2, 4)

List(2, 4, 6)

Lo interesante es que:

• sum
• filter
• map
• count
• flatMap

y muchas otras operaciones funcionales pueden construirse a partir de un único patrón: recorrer una estructura acumulando un resultado. Ese patrón es justamente fold.