Álgebras y funciones: patrones en programación funcional

0
3787

Índice de contenidos


1. Introducción

Como todos ya sabemos, la programación funcional establece un enfoque mediante el cual las computaciones se consideran como la evaluación de funciones matemáticas, tratando de evitar en todo momento los, tan perjudiciales, cambios de estado o los efectos de lado.

En ocasiones, lograr evitar este tipo de problemas puede llegar a resultar imposible si no contamos con un conjunto de herramientas que nos permitan lidiar con ello.

Es precisamente en el ámbito matemático, donde encontramos las herramientas más potentes de abstracción que nos permiten mantener la transparencia referencial y/o la mutación de datos en contextos complejos. Más concretamente en la teoría de categorías nos ofrece una serie de conceptos que nos permiten alcanzar las cotas de abstracción necesarias para dar solución a este tipo de problemas.

En este tutorial vamos a ir repasando algunos de los conceptos más importantes y su representación en una de las librerías de referencia para Scala: Cats.

La aproximación que vamos a realizar será plantear inicialmente plantearemos la definición matemática del concepto en si mismo y a continuación veremos las implementaciones que se han realizado para traspasar la idea al código.


2. Estructuras Algebraicas – Los básicos


2.1. Semigrupo

Sistema algebraico compuesto por (A,⊚), donde:

  • A es un conjunto no vacío.
  • es una operación que debe cumplir, junto con A, dos propiedades:
    • Operación interna.
    • Operación asociativa.

En notación matemática se expresaría como:

Semigrupo cumple:
    * ∀ x,y ∈ A  : x ⊚ y ∈ A
    * ∀ x,y,z ∈ A: x ⊚ ( y ⊚ z ) = ( x ⊚ y ) ⊚ z 

Un ejemplo muy sencillo de Semigrupo podría ser la estructura algebraica formada por los números enteros con la suma (ℤ,+).

Este semigrupo cumple con las reglas requeridas:

  • ∀ x,y ∈ A : x ⊚ y ∈ A: Al sumar un número natural con otro obtendremos otro número natural.
  • ∀ x,y,z ∈ A: x ⊚ ( y ⊚ z ) = ( x ⊚ y ) ⊚ z: No importa el orden, puesto que siempre dará el mismo resultado.

La implementación que mantiene Cats sobre este concepto es la siguiente:

trait Semigroup[A] {
    def combine(x: A, y: A): A
}

A través de este trait se establece una mecánica para definir Semigrupos, sobre un tipo A y con una operación combine que parte de dos valores de A y devuelve otro valor de A.

A continuación se muestra el ejemplo del semigrupo (ℤ,+), en este caso con el conjunto de los enteros:

implicit val intAdditionSemigroup: Semigroup[Int] = new Semigroup[Int] {
    def combine(x: Int, y: Int): Int = x + y
}


2.2. Monoide

Los monoides son sistemas algebraicos compuestos por (A,⊚,e) que cumplen con la estructura de Semigrupo y añaden una nueva restricción: el elemento neutro.

En notación matemática:

    * ∃!e ∈ , ∀ x ∈ A: x ⊚ e = e ⊚ x = x

Continuando con el ejemplo que planteábamos inicialmente, podemos decir que el sistema algebraico formado por los números enteros, con la operación suma y el elemento neutro 0, (ℤ,+,0), es un monoide.

A continuación se muestra la implementación establecida en Cats:

trait Monoid[A] extends Semigroup[A] {
    def empty: A
}

Un ejemplo de implementación de monoide:

implicit val intAdditionMonoid: Monoid[Int] = new Monoid[Int] {
    def combine(x: Int, y: Int): Int = x + y
    def empty: Int = 0
}


3. Estructuras Algebraicas – Categorías


3.1. Introducción

Una categoría es un sistema algebraico compuesto por objetos, morfismos, y una serie de propiedades que debe cumplir.

  • Objetos: El concepto matemático de objeto se puede definir como cualquier cosa que se puede definir formalmente y con la cual se puede realizar razonamientos deductivos y demostraciones matemáticas. Entre los objetos más comunes encontramos, por ejemplo, números, conjuntos o cuerpos geométricos.
  • Morfismos: Representados como flechas normalmente, para cada par de objetos X e Y, un morfismo (f) es una función de X a Y
  • Propiedades:
    • Composición de morfismos (∘): Dada una función f de X a Y y dada una función g de Y a Z,
      entonces g ∘ f sería el morfismo de X en a Z.
    • Propiedad asociativa en la composición: ( h ∘ g ) ∘ f = h ∘ ( g ∘ f )
    • Morfismo identidad: f ∘ f’ = f’ ∘ f = f


3.2. Funtor

Los funtores definen correspondencias entre categorías, es decir, para dos categorías A y B un funtor F asocia a cada objeto de la categoría A con un objeto de la categoría B.

    * A:
        a -f-> b
    * B:
        Fa -Ff-> Fb

Cats establece la siguiente implementación para los funtores:

trait Functor[F[_]] {
    def map[A, B](fa: F[A])(f: A => B): F[B]
}

Y un ejemplo sería el funtor para Option:

implicit val functorForOption: Functor[Option] = new Functor[Option] {
    def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa match {
        case None => None
        case Some(a) => Some(f(a))
    }
}

El nivel de abstracción representado por F[_] establece que trabajamos a nivel de constructores de tipos, también se le puede llamar efecto o contexto de computación. En el ejemplo trabajamos con el contexto «Option» que nos abstrae de valores potencialmente ausentes, con lo que map solo aplicará sobre los valores de tipo Some. Otros ejemplos de efectos los tenemos en Try para abstraernos de posibles excepciones o Either, para modelar flujos alternativos, por citar algunos ejemplos.

De manera general podemos decir que los Funtores nos permiten trabajar con un único efecto.


3.3. Aplicativos

Los aplicativos son una estructura a mitad de camino entre los funtores y las mónadas. Estas estructuras nos permiten secuenciar computaciones independientes entre sí.

Los aplicativos, desde el punto de vista matemático, son funtores monoidales, esto es un funtor que trabaja entre dos categorías monoidales.

Una categoría monoidal o (categoría tensorial) es una categoría que cumple con:

  • Tiene un bifuntor: ⊗: C x C –> C
  • Un objeto identidad: I
  • Tres isomorfismos naturales que cumplen con:
    • Son asociativos
    • Objeto identidad por la derecha.
    • Objeto identidad por la izquierda.

La implementación que aporta Cats a este respecto:

trait Applicative[F[_]] extends Functor[F]{
    def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]

    def pure[A](a: A): F[A]

    def map[A, B](fa: F[A])(f: A => B): F[B] = ap(pure(f))(fa)
}

Esta implementación, básicamente, amplia la definición de Funtor añadiendo dos operaciones: ap y pure.

Mediante la operación pure podemos introducir un valor en el contexto de computación que aporta F.

La operación ap nos permite aplicar una función que se encuentra en el contexto de computación sobre un valor que se encuentra en el mismo contexto de computación.

A continuación, se muestra un ejemplo de implementación de Aplicativo que trabaja en el contexto de valores ausentes (Option):

implicit def optionApplicative extends Applicative[Option] {
    
    def ap[A, B](ff: Option[A => B])(fa: Option[A]): Option[B] = for {
        f <- ff
        a  B): Option[B] = ap(pure(f))(fa)

}


3.4. Mónadas

Las mónadas son endofuntores (funtores que mapean una categoría sobre si misma) con dos tranformaciones naturales:

  • Dadas dos categorías C y D y Dos Functores F y G de C a D, para un mismo objeto a en la categoría C cada Functor mapeará el objeto a en dos objetos distintos en la categoría D: Fa y Ga
  • Al morfismo en D que transforma Fa en Ga se le denomina Transformación Natural (αa).

Una Monada se crea definiendo:

  • Un constructor de tipos M.
  • Una operación unaria return ==> Esta operación toma un valor a y crea un valor monádico M[a] mediante el constructor de tipos.
  • Una operación binaria bind ==> Esta operación toma como argumentos un valor monádico M[a] y una función a -> M[b] que transforme el valor.

La implementación aportada por Cats para las mónadas es la siguiente:

trait Monad[F[_]] with Applicative[F] {
     def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]     
 }

Se puede observar que la implementación de la Mónada extiende la implementación de Aplicativo añadiendo la operación flatMap, que nos permitirá secuenciar computaciones dependientes entre sí.

Continuando con los ejemplos de implementación para Option, a continuación se muestra la implementación de Monad:

implicit def optionMonad(implicit app: Applicative[Option]) = new Monad[Option] {

    override def flatMap[A, B](fa: Option[A])(f: A => Option[B]): Option[B] = app.map(fa)(f).flatten //bind

    override def pure[A](a: A): Option[A] = app.pure(a)

}

¿Por qué utilizar aplicativos en lugar de mónadas?

  1. En algunas ocasiones no se tiene la posibilidad de elegir entre un código aplicativo o monádico.
  2. Es buena práctica utilizar la abstracción menos potente que realice el trabajo.
  3. Evita establecer dependencias innecesarias entre computaciones

A continuación, se muestra un ejemplo a través del cual comparar las distintas aproximaciones:

case class Foo(s: Symbol, n: Int)

/*Código monádico:*/

val maybeFoo = for {
  s <- maybeComputeS(whatever)
  n <- maybeComputeN(whatever)
} yield Foo(s, n)

/*Código aplicativo:*/

 val maybeFoo = (maybeComputeS(whatever) |@| maybeComputeN(whatever))(Foo(_, _))


4. Conclusiones

A lo largo de este tutorial hemos visto algunas de las estructuras algebraicas más utilizadas en la programación funcional y una aproximación muy superficial a la teoría subyacente con la intención de dejar constancia de la relación entre la teoría y la práctica, en concreto, a través de la librería cats.

En futuros tutoriales veremos algunas aplicaciones prácticas de estas estructuras y de que manera nos pueden ayudar a la hora de alcanzar grados mayores de abstracción a la hora de abordar nuestros problemas desde la programación funcional.


5. Referencias

DEJA UNA RESPUESTA

Por favor ingrese su comentario!

He leído y acepto la política de privacidad

Por favor ingrese su nombre aquí

Información básica acerca de la protección de datos

  • Responsable:
  • Finalidad:
  • Legitimación:
  • Destinatarios:
  • Derechos:
  • Más información: Puedes ampliar información acerca de la protección de datos en el siguiente enlace:política de privacidad