En la programación funcional uno de los conceptos base son los tipos de datos algebráicos (ADT) Los ADT son estructuras de datos basadas en las matemáticas cuyas operaciones se realizan mediante morfismos; y, los mosfirmos, se realizan mediante la función fold y sus derivados: foldRight y foldLeft. En la entrada de hoy, Patrón Foldable en Cats, realizaré la descripción de los morfismos utilizando la type class Foldable de la librería Cats.

1.- Definición de un ADT de tipo List

Un ADT es aquel tipo de dato con el que podemos realizar unas operaciones, como por ejemplo: la operación suma y producto; y, además, cumple unas propiedades  matemáticas como pueden ser la propiedad asociativa, distributiva, o bien, de identidad.

En el siguiente ejemplo, se muestra la definición del ADT de tipo MyList, el cual equivale al ADT de tipo List.

sealed trait MyList[+A]
case object Nil extends MyList[Nothing]
case class Cons[+A](elem: A, lista: MyList[A]) extends MyList[A]

La operación suma es aquella operación que, a nivel de programación, se corresponde con las relaciones de herencia entre la clase Cons y el objeto Nil con el trait MyList. La operación producto es aquella operación que, a nivel de programación, se corresponde con los parámetros de la clase Cons: elem y lista.

Una vez definido el ADT una de las formas de manipular dicha estructura es utilizando morfismos, función fold y sus derivados. La función fold equivale a la función foldRight. La definición de la función foldRight y foldLeft con el ADT MyList son los siguientes:

• Morfismo foldRight para el ADT MyList.

def foldRight[A, B](lista: MyList[A], elem: B)(f: (A, B) => B): B = lista match {
  case Nil => elem
  case Cons(head, tail) => f(head, foldRight(tail, elem)(f))
}

• Morfismo foldLeft para el ADT MyList.

@annotation.tailrec
def foldLeft[A, B](lista: MyList[A], elem: B)(f: (B, A) => B): B = lista match {
  case Nil => elem
  case Cons(head, tail) => foldLeft(tail, f(elem, head))(f)
}

En los siguientes apartados, realizaremos la descripción de ejemplos de uso de las operaciones fold con el type class que proporciona la librería Cats y con la librería estándar.

2.- Ejemplos de morfismos con el tipo List

En el presente apartado, realizaré la descripción de ejemplos con la función fold del ADT List de la librería estándar.

• Ejemplos básicos de morfismo foldRight.- Definición de una construcción de una lista y suma de sus elementos con una lista de tipos de enteros y foldRight.

println(s"1.- foldRight=${ List(1,2,3).foldRight(List.empty[Int])( (e, acc) => e :: acc) }")
println(s"2.- foldRight=${ List(1,2,3).foldRight(0)( (e, acc) => e + acc ) }")
println(s"Suma con foldRight=${List(1, 2, 3, 4).foldRight(0)(_ + _)}")

La salida por consola es la siguiente:

1.- foldRight=List(1, 2, 3)
2.- foldRight=6
Suma con foldRight=10

• Ejemplos básicos de morfismo foldLeft.- Definición de una construcción de una lista y suma de sus elementos con una lista de tipos de enteros y foldLeft.

println(s"1.- foldLeft=${ List(1,2,3).foldLeft(List.empty[Int])((acc, e) => e :: acc) }")
println(s"2.- foldLeft=${ List(1,2,3).foldLeft(0)( (acc, e) => acc + e ) }")

La salida por consola es la siguiente:

1.- foldLeft=List(3, 2, 1)
2.- foldLeft=6

• FoldRight y el tipo Numeric.- Definición de una función suma empleando una lista de enteros y el tipo Numeric.

import scala.math.Numeric
def sumaConNumeric[A](list:List[A])(implicit numeric: Numeric[A]): A =
list.foldRight(numeric.zero)(numeric.plus)
println(s"Suma con Numeric=${sumaConNumeric(List(1, 2, 3, 4))}")
println

La salida por consola es la siguiente:

Suma con Numeric=10

• FoldRight y monoides.- Definición de la operación suma sobre una lista de enteros empleando monoides.

import cats.Monoid
import cats.instances.int._ // for Monoid
def sumaConMonoid[A](list:List[A])(implicit monoid: Monoid[A]): A =
list.foldRight(monoid.empty)(monoid.combine)
println(s"Suma con Momoid=${sumaConMonoid(List(1, 2, 3, 4))}")

La salida por consola es la siguiente:

Suma con Momoid=10

• FoldRight y definición de filtros.- Definición de unos filtros sobre una lista de enteros

val elemFilter1: Int = 3
println(s"List(1, 2, 3, 4) existe el 3?=${List(1, 2, 3, 4).foldRight(false)( (elem, resul) => resul || elem.equals(elemFilter1))}")
val elemFilter2: Int = 5
println(s"List(1, 2, 3, 4) existe el 5?=${List(1, 2, 3, 4).foldRight(false)( (elem, resul) => resul || elem.equals(elemFilter2))}")
def myfilter[A](list: List[A])(func: A => Boolean): List[A] =
list.foldRight(List.empty[A]) { (item, accum) => if(func(item)) item :: accum else accum }
println(s"List(1, 2, 3, 4) filtra los pares.=${ myfilter(List(1, 2, 3, 4))(_%2==0) }")

La salida por consola es la siguiente:

List(1, 2, 3, 4) existe el 3?=true
List(1, 2, 3, 4) existe el 5?=false
List(1, 2, 3, 4) filtra los pares.=List(2, 4)

• FoldRight y definición de función map.- Definición de una función map con foldRight.

def myMap[A,B](list: List[A])(f: A => B): List[B] = list.foldRight(List.empty[B])( (elem, result) => f(elem) :: result )
println(s"List(1, 2, 3) map to String=${List(1, 2, 3).foldRight(List.empty[String])( (elem, resul) => s"-${elem.toString}-" :: resul)}")
println(s"List(1, 2, 3) map to String=${ myMap(List(1, 2, 3))( (elem:Int) => s"*${elem.toString}*" ) }")
println

La salida pos consola es la siguiente:

List(1, 2, 3) map to String=List(-1-, -2-, -3-)
List(1, 2, 3) map to String=List(*1*, *2*, *3*)

• FoldRight y definición de función flatMap.- Definición de una función flatMap con foldRight.

def flatMap[A, B](list: List[A])(func: A => List[B]): List[B] =
list.foldRight(List.empty[B]) { (item, accum) => func(item) ::: accum }
println(s"-->>${flatMap(List(1, 2, 3))(a => List(a, a * 10, a * 100))}")
println

La salida por consola es la siguiente:

-->>List(1, 10, 100, 2, 20, 200, 3, 30, 300)

3.- Ejemplos con Foldable de cats.

Para poder operar con el tipo Foldable es necesario, al menos, realizar la importación de los siguientes tipos:

import cats.Foldable
import cats.instances.all._

• Ejemplo de Foldable con función foldLeft con los tipos List, Vector, Stream y Option.

println(s"Suma List(1, 2, 3)=${Foldable[List].foldLeft(List(1, 2, 3), 0)( _ + _ )}")
println(s"Suma Vector(1, 2, 3)=${Foldable[Vector].foldLeft(Vector(1, 2, 3), 0)( _ + _ )}")
println(s"Suma Stream(1, 2, 3)=${Foldable[Stream].foldLeft(Stream(1, 2, 3), 0)( _ + _ )}")
println(s"Suma Option(10) + 5=${Foldable[Option].foldLeft(Option(10), 0)( (acc, elem) => elem + 5 )}")

La salida por consola es la siguiente:

Suma List(1, 2, 3)=6
Suma Vector(1, 2, 3)=6
Suma Stream(1, 2, 3)=6
Suma Option(10) + 5=15

• StackOverflowError con función foldRight.

Supongamos que queramos realizar la suma de una estructura de tipo Stream de 100000 elementos, la definición de la solución sería la siguiente:

val lista = (1 to 100000).toStream
println(s"Suma (1 to 100000).toStream->${ lista.foldRight(0L)(_ + _) }")

El resultado de la ejecución del snippet anterior es errónea porque se produce un desbordamiento de la pila del sistema y nos aparece en consola un error de tipo StackOverflowError. Una solución a este problema utilizando la función foldRight es utilizando la mónada Eval. Si el lector está interesado en la mónada Eval, pude ir a las siguientes enlace.El snippet es el siguiente:

import cats.Eval
val resultEvalStream = Foldable[Stream].foldRight(lista, Eval.now(0L)) ((num, acc) => acc.map( _ + num))
println(s"Suma (1 to 100000).toStream->${ resultEvalStream.value }")

La salida por consola es la siguiente:

Suma (1 to 100000).toStream->5000050000

• Ejemplos de funciones básicos de Foldable con tipo Option.

println(s"Foldable[Option].nonEmpty(Option(42))=${Foldable[Option].nonEmpty(Option(42))}" )
println(s"Foldable[Option].isEmpty(Option(42))=${Foldable[Option].isEmpty(Option(42))}" )
println(s"Foldable[Option].size(Option(42))=${Foldable[Option].size(Option(42))}" )
println(s"Foldable[Option].get(Option(42))(0)=${Foldable[Option].get(Option(42))(0) }" )
println(s"Foldable[Option].find(Option(42))( elem => elem>30)=${Foldable[Option].find(Option(42))( elem => elem>30) }" )
println

La salida por consola es la siguiente:

Foldable[Option].nonEmpty(Option(42))=true
Foldable[Option].isEmpty(Option(42))=false
Foldable[Option].size(Option(42))=1
Foldable[Option].get(Option(42))(0)=Some(42)
Foldable[Option].find(Option(42))( elem => elem>30)=Some(42)

• Ejemplos de funciones básicas de Foldable con tipo List.

println(s"Foldable[Option].nonEmpty(List(1, 2, 3)=${Foldable[List].nonEmpty(List(1, 2, 3))}" )
println(s"Foldable[Option].isEmpty(List(1, 2, 3))=${Foldable[List].isEmpty(List(1, 2, 3))}" )
println(s"Foldable[Option].size(List(1, 2, 3)=${Foldable[List].size(List(1, 2, 3))}" )
println(s"Foldable[Option].get(List(1, 2, 3)(0)=${Foldable[List].get(List(1, 2, 3))(0)}" )
println(s"Foldable[Option].get(List(1, 2, 3)(1)=${Foldable[List].get(List(1, 2, 3))(1)}" )
println(s"Foldable[Option].get(List(1, 2, 3)(4)=${Foldable[List].get(List(1, 2, 3))(4)}" )
println(s"Foldable[Option].find(List(1, 2, 3)(4)=${Foldable[List].find(List(1, 2, 3))( elem => (elem%2==0) )}" )
println(s"Foldable[Option].find(List(1, 2, 3)(4)=${Foldable[List].find(List(1, 2, 3))( elem => (elem%2!=0) )}" )
println

La salida por consola es la siguiente:

Foldable[Option].nonEmpty(List(1, 2, 3)=true
Foldable[Option].isEmpty(List(1, 2, 3))=false
Foldable[Option].size(List(1, 2, 3)=3
Foldable[Option].get(List(1, 2, 3)(0)=Some(1)
Foldable[Option].get(List(1, 2, 3)(1)=Some(2)
Foldable[Option].get(List(1, 2, 3)(4)=None
Foldable[Option].find(List(1, 2, 3)(4)=Some(2)
Foldable[Option].find(List(1, 2, 3)(4)=Some(1)

• Ejemplo de Foldable con monoides. El tipo Foldable define operaciones con monoides.

import cats.instances.all._
println(s"Foldable[Option].combineAll(List(1, 2, 3))=${Foldable[List].combineAll(List(1, 2, 3))}" )
println

La salida por consola es la siguiente:

Foldable[Option].combineAll(List(1, 2, 3))=6

• Ejemplo de Foldable con función map. El tipo Foldable define la función foldMap para definir funciones con la funcionalidad de fold y la función map.

import cats.instances.all._
println(s"Foldable[List].foldMap(List(1, 2, 3))( elem => elem + 20) =${Foldable[List].foldMap(List(1, 2, 3))( elem => elem + 20) }")
println

La salida por consola es la siguiente:

Foldable[List].foldMap(List(1, 2, 3))( elem => elem + 20) =66

El entendimiento y el uso de los  morfismos facilita y simplifica el código; y, la utilización de Foldable, permite una versatilidad para cualquier operación.