Patrón Fodable en Cats

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)
}

fold, foldRight, foldLeft

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.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s