Patrón Type Class y Spark

En las pasadas entradas centradas en el patrón type class con título Patrón Type Class  y Patrón Type Class: definición de leyes y test, realicé una descripción de la estructura de dicho patrón. En la presente entrada, Patrón Type Class y Spark, me centraré en la definición de un API mediante el patrón type class utilizando Apache Spark.

Apache Spark es aquel motor de procesamiento y análisis de datos. Apache Spark es una solución muy utilizada en el ámbito del Big Data.

El problema del ejercicio solucionada con Apache Spark consiste en extraer los datos existentes en unas tablas de una base de datos, crear un fichero en formato parquet de los datos; y, dicho fichero, dejarlo en una estructura de directorios. Todo ello, lo más configurable posible.

La definición de las tablas fuentes de datos son tablas, con nombre y campos con un enfoque didáctico, es decir, son tablas con nombre no relevantes. Definiré dos tablas: la tabla libros, con los siguientes campos: codigo, nombre y población; y, la tabla dat_country, con los mismos campos.

El tipo básico del ejemplo es aquel tipo que puede trabajar con el valor parametrizado cuya definición es la siguiente: type Postgresql[T] = T. El tipo lo he identificado con Postgres porque es con la base de datos con la cual realizaré el ejercicio.

La definición del fichero sbt del ejecercicio es la siguiente:

import sbt.Keys.libraryDependencies
name := "EjemploTypeClassSpark"
version := "1.0"
scalaVersion := "2.11.9"
scalacOptions += "-Ypartial-unification" // 2.11.9+
val spark_version = "2.3.1" 
libraryDependencies ++= Seq(
  "org.apache.spark" %% "spark-core" % spark_version,
  "org.apache.spark" %% "spark-sql" % spark_version,
  "com.typesafe" % "config" % "1.3.2",
  "org.scalatest" %% "scalatest" % "3.0.1" % Test
)

La definición del API con nombre Engine estará formada por una única función con nombre dataExtraction la cual realizará la extración de datos, creación de un fichero en formato parquet y escritura en un path sin datos de retorno, es decir, de tipo Unit. Así, la definición de la parte funcional del type class es la siguiente:

import java.util.{ Properties}
import org.apache.spark.sql.SparkSession
import org.slf4j.LoggerFactory
import conf.Configuration
import typeclass.DTO.DataConfiguration
import util.Util
trait Engine[P[_]] {
  def dataExtraction(): P[Unit]
}
object Engine extends EngineInstances with EngineSyntax
trait EngineSyntax{
  object syntax{
    def |-> [P[_]]()(implicit BDI:Engine[P]): P[Unit] = BDI.dataExtraction()
  }
}

En el snippet anterior, definimos los siguientes elementos: el trait Engine del API, la definición del objeto Engine que hereda de las instancias y se comporta como un elemento como EngineSyntax. En este ejercicio, por simplificar, se omite la definición del trait con la definición del lenguaje y las leyes matemáticas que debe de cumplir.

La definición de las instancias con los efectos de lado es la siguiente:

trait EngineInstances{
  def apply[P[_]](implicit BDI:Engine[P]): Engine[P] = BDI
  import typeclass.Types.Postgresql
  implicit object EnginePostgress extends Engine[Postgresql]{
  def logger = LoggerFactory.getLogger(this.getClass)
  def loadTableField(nombreTable:String): List[String] = {
    nombreTable match {
       case "pruebas.libros" => List("codigo","nombre","poblacion")
       case "pruebas.dat_country" => List("codigo","nombre","poblacion")
       case _ => List()
   }
 }
def loadTableToParquet( spark:SparkSession, dataConfiguration:DataConfiguration ): Unit = {
  val engineSpark = spark
    .read
    .format("jdbc")
    .option("driver", "org.postgresql.Driver")
    .option("url", dataConfiguration.url)
    .option("dbtable", dataConfiguration.nameTable)
    .option("user", dataConfiguration.user )
    .option("password", dataConfiguration.password)
    .option("fetchsize", "1000")
    .load()
    val parameter: List[String] = loadTableField(dataConfiguration.nameTable) //: _*
    engineSpark.select( parameter.toSeq.head, parameter.tail.toSeq: _* ).write.format("parquet").save( Util.getFilePathTarget(dataConfiguration.nameBucket ,dataConfiguration.nameTable)   )
}
def runSpark(url:String, user:String, password:String, numTables:Int, prop:Properties): Either[String, Unit] = {
  val spark = SparkSession.builder.appName("EjemploTypeClassSpark").getOrCreate()
  for(num <- 1 to numTables){
    try{
      val nameTable = prop.getProperty("table_" + num)
      if(!nameTable.equals(null) && !nameTable.equals("")){
        logger.info(s"[*****] Número tabla: ${num}, nombre tabla: ${nameTable}.")
        loadTableToParquet(spark, DataConfiguration(numTables=num, nameTable=nameTable, url=url, user=user, password=password, nameBucket = prop.getProperty("bucketName")) )
      }else{
        logger.info(s"[*****] Número tabla: table_${num} VACÍA")
      }
   } catch {
     case ex: Exception => {
       logger.info(s"[*****] Error en la carga de la tabla con número table_${num}")
       logger.error(s"Exception: ${ex.getMessage}")
     }
   }
 }
 spark.close()
 Right(Unit)
}
override def dataExtraction(): Postgresql[Unit] = {
  for{
    environment <- Configuration.loadEnvironmentVariables.right
    properties <- Configuration.loadProperties(environment.configuration).right
    _ <- runSpark(environment.url, environment.user , environment.password, properties.numTables, properties.properties ).right
  }yield{
    Right(Unit)
  }
 }
}
[...]
}

En el snippet anterior, definimos un trait EngineInstances con un constructor y un objeto implícito EnginePostgress el cual hereda del API Engine. En este trait, si definimos otro tipo de parámetro, como por ejemplo:Either[String,T] definido como type Oracle[T] = Either[String,T], sería el lugar para su implementación.

El objeto EnginePostgress define la función dataExtraction la cual define el programa con las siguientes sentencias: primero, larga de variables de entorno; segunda, carga de la configuración de los ficheros de properties; tercero, las operaciones con Spark; y, por último, el retorno de un elemento de tipo Unit. Las tres funciones son funciones que retornan un contenedor binario de tipo Either.

La función runSpark es aquella función que realiza la constructuctión de una sesión de Spark para realizar una operación sobre una tabla configurada; dicha función, se realiza en la función loadTableToParquet.

La función loadTableToParquet es aquella función que realiza la carga de la configuración del motor Spark para una tabla de una base de datos determinada, extrae los datos en formato parquet y deja el fichero en una ubicación determinada.

La aplicación cliente del API Engine es la siguiente:

import typeclass.Engine.syntax._
import typeclass.Types.Postgresql
object App extends App{
  val startTime: Long = System.currentTimeMillis()
  |->[Postgresql]()
}

El fichero properties con la configuración con el nombre de las tablas, el número de tablas a extraer y el path con el directorio en donde se almacena el resultado es el siguiente:

bucketName=~/tmp/
num_tables=2
table_1=pruebas.libros
table_2=pruebas.dat_country

La variables de entorno a configurar para la ejecución de la aplicación son las siguientes:

export url=jdbc:postgresql://localhost:5432/prueba
export user=postgres
export password=password
export configuration=~/workspace/EjemploTypeClassSpark/src/main/resources/configuration_bdi.properties

Los componentes software para la carga de las variables de entorno y carga de ficheros properties nos las describo en la entrada para reducir el tamaño y por centrar el ejemplo en el patrón type class.

Para finalizar y poder ejecutar la aplicación en local con Apache Spark se ejecuta con el siguiente comando:

cd ~/scala/spark-2.3.1-bin-hadoop2.7/bin
spark-submit --driver-class-path postgresql-42.1.4.jre6.jar --class "App" --master local[2] ~/workspace/EjemploTypeClassSpark/target/scala-2.11/ejemplotypeclassspark_2.11-1.0.jar

El resultado de la ejecución es la creación del fichero con los datos extraídos en la carpeta ~/tmp/ del sistema de directorios.

Patrón Type Class: definición de leyes y test

En la entrada anterior, Patrón Type Class , realicé la definición, descripción y mostré ejemplos del patrón type class. La estructura del patrón está compuesta por un conjunto de elementos trait y un objeto que se comporta como dichos trait. A este objeto, para ciertos tipos de datos, se pueden definir leyes matemáticas para poder realizar test de dicho componente.

En la presente entrada, Patrón Type Class: definición de leyes y test , realizaré la definición del type class monoiede para la operación lógica suma y producto. Para ello, definiré un Type Class con la estructura definida en la anterior entrada añadiendo la definición de las leyes.

Definición de Monoide

En la serie que llevo publicado de la librería Scalaz, publiqué un post con título Scalaz IV: Tipos etiquetados, propiedad asociativa y monoides , en donde se describe el concepto de Monoide, así como, la descripción de unos ejemplos.

En la programación funcional, aparecen escenarios en donde es necesario definir funciones binarias cuyos parámetros de entrada y de salida son del mismo tipo; este tipo de función, se define en la entidad Semigrupos. Desde un punto de vista del lenguaje Scala, un Semigrupo se define de la siguiente forma:

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

El Semigrupo lo definimos con un trait que recibe un tipo parametrizado A y define una función combine cuyos dos parámetros de entrada y la salida son del mismo tipo.

Unos ejemplo matemáticos que representan el Semigroup[A] pueden ser los siguientes:

  1.  1 + 2
  2.  2 + 1
  3. 1 + (2 + 3)
  4. (1 + 2) + 3
  5. (1 * 2) * 3
  6. 1 * (2 * 3)

Como deducimos de los ejemplos anteriores: podemos decir que se cumple la propiedad asociativa, comparando los resultados de los puntos de los ejemplo 1-2, 2-3 y 5-6. Así, podemos afirmar que Semigroup[A] cumple la propiedad asociativa; pero, en función de la operación que se aplique, puede no cumplir esta regla; por ejemplo, la operación resta, no cumple la propiedad asociativa. Unos ejemplos pueden ser los siguientes:

  1. 1 – (2 – 3)
  2. (1 – 2) – 3

De los ejemplos anteriores de la operación resta, el resultado de las operaciones es distinto en los ejemplos del punto 1 y 2.

Las operaciones matemáticas pueden cumplir otras propiedades; como por ejemplo, la propiedad de identidad. La propiedad de identidad necesita un valor vacío o valor zero el cual, en función de la operación, el valor del elemento no varía; por ejemplo: en la operación de suma, el valor zero o vacío es el valor 0; y, para la operación de multiplicación, el valor zero o vacío es el valor 1. Unos ejemplos con el entero 2 y aplicando el elemento vacío, cuyo resultado no cambia el entero, son los siguientes:

  1. Operación suma por la izquierda: 2 + 0 = 2
  2. Operación suma por la derecha: 0 + 2 = 2
  3. Operación multiplicación por la izquierda: 2 * 1 = 2
  4. Operación multiplicación por la derecha: 1 * 2 = 2

Llegado a este punto, los escenarios de conjuntos de elementos en donde se definen unas funciones que cumple las propiedades de asociatividad e identidad, son definidos como Monoides. La definición de Monoide en lenguaje Scala es la siguiente:

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

En los siguientes apartados, realizaré la descripción de monoides para las funciones lógicas suma (OR) y multiplicación (AND).

Monoide: operación lógica suma (OR)

La definición del Type class de la operación lógica suma (OR) en lenguaje Scala es la siguiente:

trait MonoidSuma[A] extends Monoid[A]{}
object MonoidSuma extends MonoidSumaInstances with MonoidSumaSyntax with MonoidSumaLaws
trait MonoidSumaInstances{
  def apply[A](implicit monoid: MonoidSuma[A]) = monoid
  implicit val monoidBooleanSuma = new MonoidSuma[Boolean] {
    // 1-FORMA
    // override def combine(x: Boolean, y: Boolean): Boolean = (x, y) match{
    // case (true, true ) => true
    // case (true, false) => true
    // case (false, true) => true
    // case (false, false) => false
    // }
    override def combine(x: Boolean, y: Boolean): Boolean = x || y
    override def empty: Boolean = false
  }
}
trait MonoidSumaSyntax{
  object syntax{
    def ++++[A](a:A, b:A)(implicit monoide: MonoidSuma[A]) = monoide.combine(a,b)
    def emptySuma [A](implicit monoide: MonoidSuma[A]) = monoide.empty
  }
}
trait MonoidSumaLaws{
  import MonoidSuma.syntax._
  trait Laws[A]{
    implicit val instance: MonoidSuma[A]
    def asociatividad(a1:A, a2:A, a3:A): Boolean = ++++( ++++(a1,a2), a3) == ++++(a1, ++++(a2,a3) )
    def izquierdaIdentidad(a1:A): Boolean = ++++( a1, emptySuma ) == a1
    def derechaIdentidad(a1:A): Boolean = ++++( emptySuma, a1 ) == a1
  }
  object Laws{
    def apply[A](implicit monoide:MonoidSuma[A]) = new Laws[A] {
      implicit val instance: MonoidSuma[A] = monoide // Dfinición de la referencia del trait.
    }
  }
}

La estructura del type class es la siguiente: trait MonoidSuma, objeto MonoidSuma, trait MonoidSumaInstances, trait MonoidSumaSyntax y MonoidSumaLaws. De la estructura de type class descrita en la entrada anterior, aparece el elemento nuevo trait MonoidSumaLaws en donde se define las funciones con las propiedades matemáticas de asociatividad y de identidad, así como, el objeto con el constructor del monoide.

Para realizar las pruebas del type class de la operación suma es necesario probar las leyes del type class y, para realizar las pruebas, se definen unos test que verifican las leyes matemáticas del type class los cuáles, para el type class función suma lógica, es el siguiente:

class MyMonoidTest extends FlatSpec with Matchers{
  "Test de las leyes del Monoide lógico Suma" should "cumple las leyes asociativas y de identidad" in {
    import es.ams.cap2monoidsemigroup.MonoidSuma.Laws
    val laws = Laws.apply
    assert( laws.asociatividad( true, false, true) == true)
    assert( laws.izquierdaIdentidad(true) == true )
    assert( laws.derechaIdentidad(true) == true )
  }
}

Monoide: operación lógica producto (AND)

La definición del Type class de la operación lógica producto es la siguiente:

trait MonoidProducto[A] extends Monoid[A]{}
object MonoidProducto extends MonoidProductoInstances with MonoidProductoSyntax with MonoidProductoLaws
trait MonoidProductoInstances{
  def apply[A](implicit monoid: MonoidProducto[A]) = monoid
  implicit val monoidProductoSuma = new MonoidProducto[Boolean] {
    // 1-FORMA
    // override def combine(x: Boolean, y: Boolean): Boolean = (x, y) match{
    // case (true, true ) => true
    // case (true, false) => false
    // case (false, true) => false
    // case (false, false) => false
    // }
    override def combine(x: Boolean, y: Boolean): Boolean = x && y
    override def empty: Boolean = true
  }
}
trait MonoidProductoSyntax{
  object syntax{
    def ****[A](a:A, b:A)(implicit monoide: MonoidProducto[A]) = monoide.combine(a,b)
    def emptyProducto [A](implicit monoide: MonoidProducto[A]) = monoide.empty
  }
}
trait MonoidProductoLaws{
  import MonoidProducto.syntax._
  trait Laws[A]{
    implicit val instance : MonoidProducto[A]
    def asociatividad(a1:A, a2:A, a3:A):Boolean = ****( ****(a1, a2), a3) == ****( a2, ****(a2, a3))
    def izquierdaIdentidad(a1:A):Boolean = ****(a1, emptyProducto) == a1
    def derechaIdentidad(a1:A):Boolean = ****(emptyProducto, a1) == a1
  }
  object Laws{
    def apply[A](implicit monoide:MonoidProducto[A]) = new Laws[A]{
      implicit val instance: MonoidProducto[A] = monoide
    }
  }
}

La estructura del type class es la siguiente: trait MonoidProducto, objeto MonoidProducto, trait MonoidProductoSyntax, trait MonoidProductoLaws y MonoidProductoLaws. De la estructura de type class descrita en la entrada anterior, aparece el elemento nuevo trait MonoidProductoLaws en donde se definen las funciones con las propiedades matemáticas de asociatividad y de identidad, así como, el objeto con el constructor del monoide.

Para realizar las pruebas del type class es necesario probar las leyes y, para realizar las pruebas, se define un test que verifican las leyes matemáticas del type class los cuáles, para el type class función producto lógica, es el siguiente:

class MyMonoidTest extends FlatSpec with Matchers{
  "Test de las leyes del Monoide lógico Producto" should "cumple las leyes asociativas y de identidad" in {
    import es.ams.cap2monoidsemigroup.MonoidProducto.Laws
    val laws = Laws.apply
    assert( laws.asociatividad( true, false, true) == true)
    assert( laws.izquierdaIdentidad(true) == true )
    assert( laws.derechaIdentidad(true) == true )
  }
}

La definición de las leyes se realiza utilizando las funciones definidas en la sintaxis y referenciando a los elementos implícitos de las instancias. ScalaTest es el framework seleccionado para la definición y ejecución de los test definidos de los type class.

Patrón Type Class

Las entradas que he publicado hasta la fecha, en su su mayoría, son descripciones y ejemplos de componentes de librerías como Scalaz o Circe. Todas las librerías aplican, en función del problema a resolver, un patrón común el cual es el Patrón Type Class. De la misma manera que en programación orientada a objetos está la clase y la herencia, en la programación funcional, se presenta el patrón Type Class que nos permite el polimorfismo en función del tipo de elementos a tratar.

El patrón Type Class apareció por primera vez con el lenguaje Haskell, lenguaje puramente funcional, para implementar operadores sobrecargados de aritmética e igualdad. En nuestro caso, el patrón type class lo utilizaremos para definir API’s.

La estructura del patrón type class está formado por cuatro elementos básicos los cuales son los siguientes:

  1. Definición del trait con la definición del API.
  2. Definición del trait con las instancias de los elementos que implementa el API en función del tipo.
  3. Definición del trait con la sintaxis.
  4. Definición del objeto que hereda de las instancias y se comportan como el resto de elementos trait.

Este patrón es utilizado en las librerías genéricas de Scala como Scalaz y Cats; librerías que complementan al propio lenguaje y solucionan determinados problemas de la programación funcional. Cada librería, organiza el patrón y estructura sus componentes de forma diferente; pero, en líneas generales, la estructura es la del patrón.

Para realizar la demostración, realizaré la implementación del patrón type class para diferentes funcionalidades.

API Impresión (Printable)

El API de impresión definirá la funcionalidad para realizar la conversión de tipos enteros, string y una entidad a tipo String para poder mostrar por consola. Evidentemente, el tipo String no tiene mucho sentido convertirlo porque ya es tipo String pero, realizaré la funcionalidad necesaria para que sea ilustrativa al lector.

El código del type class de impresión se define en el siguiente snippet del API Printable2 de la siguiente forma:

package es.ams.cap1introduccion
case class Cat(name:String, age:Int, color:String)
trait Printable2[A] {
  def format(a: => A):String
}
object Printable2 extends PrintableInstances2 with PrintableSyntax2
trait PrintableInstances2{
  def apply[A](implicit P:Printable[A]) = P
  implicit val printable2String = new Printable2[String]{
    def format(a: => String): String = a
  }
  implicit val printable2Int = new Printable2[Int]{
    def format(a: => Int): String = a.toString
  }
  implicit val printable2Cat = new Printable2[Cat]{
    def format(a: => Cat): String = a.name + " tiene " + a.age + " y es de color " + a.color
  }
}
trait PrintableSyntax2{
  object syntax{
    def format[A](elem: => A)(implicit P:Printable2[A]): String = P.format(elem)
      def printer[A](elem: => A)(implicit P:Printable2[A]): Unit = println(s"=>${P.format(elem)}")
      implicit class PrintableSyntax2Ops[A](elem: => A)(implicit P:Printable2[A]){
        def formatOps():String = P.format( elem )
        def printOps(): Unit = println( s" ===>${P.format(elem)}" )
      }
  }
}

El primer elemento del type class es el trait Printable2 para un tipo genérico A. El API define la función format el cual recibe un elemento de tipo A que lo transforma en un String.

El segundo elemento del type class es el object Printable2 que hereda de las instancias definidas en el trait Printable2Instances y se comporta como las funciones definidas en el trait Printable2Syntax.

El tecer elemento del type class es el trait Printable2Instances2 el cual define todos los elementos que implementan el API Printable2 para los tipos especificados. En nuestro caso, se implementan las instancias del API Printable2 para los siguientes tipos: String, con el objeto printable2String; Int, con el objeto printable2Int; y, Cat, con el elemento printable2Cat. Para los tres casos, la funcionalidad es sencilla, simplemente, los parámetros de la función format se pasan a String. Además, las tres implementaciones están definidas de forma implicita con la palabra implicit.

Por otro lado, para este tercer caso, es importante la definición de la función apply la cual realiza la construcción de aquella instancia que se requiere en función del tipo, representado por la letra A.

El cuarto y último elemento en este type class es el trait PrintableSyntax2 el cual define las aquellas funciones genéricas para los tipos definidos en el trait con las instancias. En nuestro caso, defino dos funciones y una clase. Las funciones definen las funciones helper y, la clase, define aquellas funciones para elementos de tipo A. Como puede analizar el lector, los elementos operativos son los objetos implícitos que se definen con los parámetros implicit.

A continuación, muestro unos ejemplos de uso de la utilización del API Printable2:

import Printable2.syntax._
println( "->" + format(69) )
println
printer( 89 )
println
val gato: Cat = Cat( name = "John", age=18, color="Blanco")
println( "-->" + format(gato) )
println
printer( Cat( name = "John", age=28, color="Rojo") )
println
val gato = Cat( name = "John", age=38, color="Verde")
println(s"Gato:${gato formatOps()}" )
println
val gato2 = Cat( name = "John", age=48, color="Rosa")
gato2.printOps()
println

La salida por consola es la siguiente:

->69
=>89
-->John tiene 18 y es de color Blanco
=>John tiene 28 y es de color Rojo
Gato:John tiene 38 y es de color Verde
===>John tiene 48 y es de color Rosa

Como observamos en los ejemplos, es necesaria la importación de la sintaxis y el compilador, tras la inferencia de tipos, infiere qué instancia implícita es la que tiene que utilizar.

API Visualización (Show)

En muchas ocasiones no es necesaria la creación de cualquier API porque las librerías genéricas Scalaz o Cats nos propocionan esas API. En el presente apartado, realizaré la encapsulación del API Show existente en la librería Cats. Este ejemplo sigue la misma estructura y es meramente ilustrativo.

Para realizar dicho ejemplo es necesario definir en el fichero build.sbt la dependencia con la librería Cats. La dependencia se define de la siguiente forma:

libraryDependencies += "org.typelevel" %% "cats-core" % "1.0.0-MF"

Para importar los elementos necesarios en la aplicación, se realiza de la siguiente forma:

import cats._
import cats.implicits._

La definición del API MyShow que encapsula el API Show de Cats es el siguiente:

trait MyShow[A] {
  def show(elem:A):String
}
object MyShow extends MyShowInstances with MyShowSyntax
trait MyShowInstances{
  def apply[A](implicit S:MyShow[A]) = S
  implicit val myShowInt = new MyShow[Int] {
    def show(elem:Int): String = {
      Show.apply[Int].show(elem)
    }
  }
  implicit val myShowString = new MyShow[String] {
    def show(elem:String): String = {
      elem.show
    }
  }
  implicit val myShowCat = new MyShow[Cat] {
    def show(elem:Cat): String = {
      elem.name.capitalize.show + " tiene " + elem.age.show + " y es de color " + elem.color.show
    }
  }
}
trait MyShowSyntax{
  object syntax{
    def show[A](elem:A)(implicit S: MyShow[A]) = S.show(elem)
    implicit class MyShowOps[A](elem:A)(implicit S: MyShow[A]){
      def show():String = S.show(elem)
      def =*=>():String = S.show(elem)
    }
  }
}

La estructura y elementos del APi son las mismas que en el caso del API Printable2. La diferencia reside en las instancias implícitas del trait MyShowInstances las cuáles utilizan el API Show de Cats.

Los ejemeplos de utilización del API MyShow son los siguientes:

import MyShow.syntax._
println( "[Syntax] show(69) = " + show(69) )
println
val gato: Cat = Cat(name="gato", age=18, color="Rosa")
println( "[Syntax] show(69) = " + 69 )
println
println( "[Syntax] =*=>()= " + gato.=*=>() )
println
println( "[Syntax] show()= " + gato.show() )
println

La salida por consola es la siguiente:

[Syntax] show(69) = 69
[Syntax] show(69) = 69
[Syntax] =*=>()= Gato tiene 18 y es de color Rosa
[Syntax] show()= Gato tiene 18 y es de color Rosa

Visión funcional

Una función es pura cuando en un programa se puede sustituir una función por el resultado de dicha función y, el funcionamiento del programa, sigue siendo el mismo. Una función no es pura cuando presenta efectos de lado los cuáles son todas aquellas operaciones que suponen a la función que tenga resultados distintos en cada ejecución; como por ejemplo: una operación de entrada-salida, una operación a una base de datos, o bien, una excepción.

En el patrón type class, se diferencian las funciones puras y las funciones que pueden presentar efectos de lado. Las funciones no puras son aquellas que se definen en las instancias del API y, las funciones puras, son las definidas en el trait de la sintaxis y en el API. Así, podemos definir un API entendible por negocio y, la parte de infraestructura, en las instancias; consiguiendo separar los dos ámbitos: el ámbito del mundo de negocio y el ámbito de la infraestructura.

Conclusión

La estructura del patrón Type Class es siempre la misma. Para su correcta entendimiento, es necesario tener claro cómo funcionan los elementos implícitos y, sobre todo, saber diferenciar los elementos funcionales puros y los elementos con efectos de lados; efectos, que suponen que las funciones no sean puras. Este patrón es utilizado por ejemplo para la implementación de Monoides, Funtores o Mónadas.

Scalaz III: Apply y Applicative

En la primera entrada de la serie, Scalaz I: Functores y funciones como functores , realicé la descripción de functores y cómo utilizar funciones como functores. En la presente entrada, Scalaz III: Apply y Aplicative, me centraré en describir las API Apply y Applicative.

En Scalaz, Apply hereda de la Functor; y, Applicative, hereda a su vez de Apply.

Apply

El API Apply permite aplicar una función a un functor y, al estar definido mediante el patrón type classes, contiene un conjunto de funciones dentro de la sintaxis del type class.

La función principal es la función ap la cual define una función que es aplicada al functor. Así, una definición básica de Apply es la siguiente:

 trait Apply[F[_]] extends Functor[F] { self =>
   def ap[A,B](fa: => F[A])(f: => F[A => B]): F[B]
   [...]
 }

Analizando la función ap realizamos la siguiente lectura, dado un functor fa, se le aplica la función f; y,  en función del número de functores, podemos definir ap2, para dos functores, hasta ap8, para 8 functores.

Para poder operar con Apply, es necesario realizar las importaciones en el código de la siguiente manera:

import scala.language.higherKinds
import scalaz.Apply
import scalaz.Scalaz._

Ejemplo Apply con un functor

Dada una función con nombre incrementoMas2 la cual realiza el incremento en dos unidades de un entero, se aplica la función ap de Apply para realizar el incremento de un functor definido por un elemento Option de valores enteros de la siguiente forma:

 val incrementoMas2 = (x: Int) => x + 2
 println(s"[2] Apply[Option].ap(Some(3))(Some(incrementoMas2))=${Apply[Option].ap(Some(3))(Some(incrementoMas2))}")

La salida por consola es la siguiente:

 [2] Apply[Option].ap(Some(3))(Some(incrementoMas2))=Some(5)

Como he comentado antes, Scalaz contiene funciones de la sintaxis de Apply. Así, la función de la sintaxis de la función ap es el símbolo “<*>”. El ejemplo anterior utilizando la sintaxis y utilizando una función que incrementa un entero en 3 unidades, es el siguiente:

 println(s"[3] 3.some <*> {(_: Int) + 3}.some=${3.some <*> {(_: Int) + 3}.some}")
 println(s"[3.1] 3.some <*> incrementoMas2.some=${3.some <*> incrementoMas2.some}")

La salida por consola es la siguiente:

 [3] 3.some <*> {(_: Int) + 3}.some=Some(6)
 [3.1] 3.some <*> incrementoMas2.some=Some(5)

Ejemplo Apply con dos functores

Dada una función con nombre sumaDosEntores la cual realiza la suma de dos enteros, se aplica la función ap2 de Apply para realizar la suma de dos functores definido por dos elementos Option de valores enteros de la siguiente forma:

 val sumaDosEnteros = (e1:Int, e2:Int) => e1 + e2
 val result2 = Apply[Option].ap2(Some(3), Some(4))(Some(sumaDosEnteros))
 println(s"[2] Apply[Option].ap2(Some(3), Some(4))(Some(sumaDosEnteros))=${result2}")

La salida por consola es la siguiente:

 [2] Apply[Option].ap2(Some(3), Some(4))(Some(sumaDosEnteros))=Some(7)

Aplicando la función “<*>” de la sintaxis de Apply, el ejemplo anterior, se define de la siguiente forma:

 println(s"[3.2] 3.some + 4.some <*> sumaDosEnteros.some=${ 3.some <*> {4.some <*> {sumaDosEnteros.curried.some}} }")

La salida por consola es la siguiente:

 [3.2] 3.some + 4.some <*> sumaDosEnteros.some=Some(7)

La sintaxis contiene otras funciones, como por ejemplo:

  •  función <*, dado dos functores se selecciona el functor de la izquierda
 println(s"1.some <* 2.some=${1.some <* 2.some}")
 println(s"none <* 2.some=${none <* 2.some}")

La salida por consola es la siguiente:

 1.some <* 2.some=Some(1)
 none <* 2.some=None
  • función *>, dado dos functores, se selecciona el functor de la derecha.
 println(s"1.some *> 2.some=${1.some *> 2.some}")
 println(s"1.some *> none=${1.some *> none}")

La salida por consola es la siguiente:

 1.some *> 2.some=Some(2)
 1.some *> none=None

Applicative

El API Applicative permite mapear una función con N parámetros. El API Applicative hereda del API Apply con lo cual el API opera con functores. Las funciones principales del API es la función point y su alias pure, las cuales permiten definir un functor a partir de un elemento de un determinado tipo. La definición de las funciones son las siguientes:

trait Applicative[F[_]] extends Apply[F] { self =>
 def point[A](a: => A): F[A]
 def pure[A](a: => A): F[A] = point(a)
 [...]
}

Ejemplos básicos Applicative

Dado un número entero, se aplica la función point del API Applicative para crear un functor Option y List de la siguiente forma:

 val result4 = Applicative[Option].point(3)
 println(s"[0] Applicative[Option].point(3)=${result4}")
 val result5 = Applicative[List].point(3)
 println(s"[0_1] Applicative[List].point(3)=${result5}")

La salida por consola es la siguiente:

[0] Applicative[Option].point(3)=Some(3)
[0_1] Applicative[List].point(3)=List(3)

Composición de funciones con Applicative

Dado una función que realiza el incremento de 10 unidades de un elemento entero, se define un elemento Applicative del tipo List de la siguiente forma:

 val result6 = Applicative[List].point(3).map( (elem:Int) => elem + 10 )
 println(s"[0_2] Applicative[List].point(3)=${result6}")

La salida por consola es la siguiente:

[0_2] Applicative[List].point(3)=List(13)

Función ap y apX en Applicative

  • Dada una función de incremento de un entero en dos unidades y un functor representado por un Option de enteros, se aplica la función ap del API Applicative de la siguiente forma:
 val inc: Int => Int = (x: Int) => x + 2
 val result1 = Applicative[Option].ap(Some(1))(Some(inc))
 println(s"[1] inc = (x: Int) => x + 2")
 println(s"[1] Applicative[Option].ap(Some(1))(Some(inc))=${result1}")

La salida por consola es la siguiente:

 [1] inc = (x: Int) => x + 2
 [1] Applicative[Option].ap(Some(1))(Some(inc))=Some(3)
  • Dada una función que transforma un entero en un functor del tipo Option; dada una función que realiza la operación de incremento de un elemento Option de enteros en dos unidades, se aplica la función ap del API Applicative de la siguiente forma:
 val inc: Int => Int = (x: Int) => x + 2
 val enteroASome: Int => Some[Int] = (x:Int) => Some(x)
 val optionDeFuncionDeEntero: Some[Int => Int] = Some(inc)
 val result1_1 = Applicative[Option].ap(enteroASome(1))( optionDeFuncionDeEntero )
 println(s"[1_1] Applicative[Option].ap(enteroASome(1))( optionDeFuncionDeEntero )=${result1_1}")

La salida por consola es la siguiente:

[1_1] Applicative[Option].ap(enteroASome(1))( optionDeFuncionDeEntero )=Some(3)
  • Dado un functor del tipo Option de enteros y ninguna función, el resultado de aplicar la función ap del API Applicative es el siguiente:
 val result1_2 = Applicative[Option].ap(Some(1))(None)
 println(s"[1_2] Applicative[Option].ap(Some(1))(None)=${result1_2}")

La salida por consola es la siguiente:

[1_2] Applicative[Option].ap(Some(1))(None)=None
  • Dada una función que realiza la suma de tres elementos enteros, se aplica la función ap3 del API Applicative de tres functores definidos en tres elementos Option de enteros de la siguiente forma:
 val sumaDe3 = (a: Int, b: Int, c: Int) => a + b + c
 val result2 = Applicative[Option].ap3(Some(1), Some(2), Some(3))(Some(sumaDe3))
 println(s"[1_3] Applicative[Option].ap3( Some(1), Some(2), Some(3) )(Some(sumaDe3))=${result2}")

La salida por consola es la siguiente:

[1_3] Applicative[Option].ap3( Some(1), Some(2), Some(3) )(Some(sumaDe3))=Some(6)
  • Dada una función que realiza la suma de tres elementos enteros, se aplica la función ap3 del API Applicative de tres functores definidos en tres elementos Option de enteros, uno de los cuales con valor None, de la forma siguiente:
 val sumaDe3 = (a: Int, b: Int, c: Int) => a + b + c
 val result2_1 = Applicative[Option].ap3(Some(1), None, Some(3))(Some(sumaDe3))
 println(s"[1_4] Applicative[Option].ap3( Some(1), None, Some(3) )(Some(sumaDe3))=${result2_1}")
 println

La salida por consola es la siguiente:

[1_4] Applicative[Option].ap3( Some(1), None, Some(3) )(Some(sumaDe3))=None
  • Dada una función que realiza la suma de tres elementos enteros, se aplica la función ap3 del API Applicative de tres functores definidos en tres elementos List de enteros de la siguiente forma:
 val sumaDe3 = (a: Int, b: Int, c: Int) => a + b + c
 val result3 = Applicative[List].ap3(List(1), List(2), List(3))(List(sumaDe3))
 println(s"[1_5] Applicative[List].ap3( List(1), List(2), List(3) )(List(sumaDe3))=${result3}")
 println

La salida por consola es la siguiente:

[1_5] Applicative[List].ap3( List(1), List(2), List(3) )(List(sumaDe3))=List(6)

Función Lift

  • Dada una función que realiza la suma de tres elementos de enteros, se define una función liftSumaDe3 a partir de la función de sumas de tres enteros para realizar la suma de tres elementos del tipo definido en el Applicative. El snippet es el siguiente:
 val sumaDe3 = (a: Int, b: Int, c: Int) => a + b + c
 val liftSumaDe3 = Applicative[Option].lift3( sumaDe3 )
 println(s"[1_6] liftSumaDe3( Some(2), Some(3), Some(5) )=${liftSumaDe3( Some(2), Some(3), Some(5) )}")
 println

La salida por consola es la siguiente:

[1_6] liftSumaDe3( Some(2), Some(3), Some(5) )=Some(10)

Función sequence

  • La función sequence realiza la conversión de tipos del elemento pasado por parámetro, es decir, dado un elemento P[G[_]], lo convierte en G[P[_]]. El snippet ejemplo es el siguiente:
 val resultApplicativeSequence = Applicative[Option].sequence(List(some(1), some(2), some(3)))
 println(s"[1_7] Applicative[Option].sequence(List(some(1), some(2), some(3)))=${Applicative[Option].sequence(List(some(1), some(2), some(3)))}")
 println

La salida por consola es la siguiente:

[1_7] Applicative[Option].sequence(List(some(1), some(2), some(3)))=Some(List(1, 2, 3))

Para el lector interesado, las entradas que he realizado sobre Scalaz son las siguientes:

Scalaz I: Functores y funciones como functores

Scalaz es una librería de programación funcional para el lenguaje Scala. Scalaz proporciona un conjunto de estructuras de datos para completar la biblioteca Scala; todas estas estructuras, están definidas sobre type classes y sus correspondientes instancias.

En la presente entrada, Scalaz I: Functores y funciones como functores, me centraré en los functores y en definir funciones como functores mediante los elementos de la librería Scalaz.

Definición de función curring

Las funciones curring es aquella técnica funcional nombrada en honor al matemática Haskell Curry el cual fue el creador del lenguaje funcional Haskell.

Una función curry es aquella función que define un conjunto de parámetros y, en las invocaciones a dicha función, pueden emplearse un número menor de parámetros. Así, podemos definir un conjunto de funciones a partir de una función base. Un ejemplo de función curry es la siguiente:

 def funcionBase(x:Int)(y:Int)= x + y
 val funcionCurry1 = funcionBase(2)(_)
 println(s"funcionCurry1(3)=${funcionCurry1(3)}")

La función base con técnica curring es la función funcionBase la cual define una lista de parámetros separados con paréntesis. A partir de la función base, definimos la función funcionCurry1 cuyo primer parámetro tiene el valor fijo 2 y, el segundo parámetro, un valor a determinar. Una vez definida la funcionCurry, se realiza la invocación de la función con el valor variable.

La salida por consola del ejemplo anterior es la siguiente:

 funcionCurry1(3)=5

La función funcionCurry1 tiene como primer parámetro el valor enteror 2 y, si quisiéramos, podríamos definir tantas funciones como valores enteros como primer parámetro.

Definición de Functor

La teoría de categorías es aquel estudio de las matemáticas que trata mediante axiomas estructuras abstractas como si fueran una, utilizando objetos y morfismos. Los objetos y los morfirmos forman una categoría. Así, una categoría es un conjunto de objetos y unos morfismos los cuales son las transformaciones entre dichos objetos.

Dada una categoría A, un functor es aquel morfismo que transforma la categoría A en otro categoría B. A nivel práctico, desde un punto de vista de un desarrollador, un functor se puede ver como aquella operación que transforma un elemento A en otro B y, a un bajo nivel en el lenguaje Scala, se corresponde con la función map.

Funciones como curry

En el apartado anterior, Definición de función curring, he definido una función de tipo curry y, en el presente apartado, describiré cómo se transforma una función como tipo curry. Para transformar una función como curry hay que aplicar la función curried.

En el siguiente ejemplo, se define una función curry con nombre lista1; se define una lista de enteros a la cual se aplica una función para realizar la multiplicación de los elementos por un número; y, una vez definida, se realiza la invocación de la función por el operador a multiplicar. Como se observa en la segunda línea del siguiente ejemplo, se aplica la función map con un valor entero fijo correspondiente con el segundo parámetro de la función de lista1.

 val lista1 = List(1, 2, 3, 4) map { (_: Int) * (_: Int) }.curried
 val resultadoLista1 = lista1.map {_ (9)}
 println(s"Resultado1=${resultadoLista1}")
 println

La salida por consola del ejemplo anterior es la siguiente:

 Resultado1=List(9, 18, 27, 36)

Funciones como functores

En el apartado anterior con nombre Definición de Functor, he realiza una descripción a alto nivel de un functor. En el presente apartado, describiré cómo definir functores con funciones.

Las importaciones de los elementos necesarios de Scalaz para los ejemplos siguientes, son los siguientes:

 import scala.language.higherKinds
 import scalaz.std.list._
 import scalaz.std.option._
 import scalaz.syntax.functor._
 import scalaz.{Functor, Monad}

La definición de un Functor con Scalaz de una lista de enteros y un Option de enteros es el siguiente:

 val list: List[Int] = Functor[List].map(List(1, 2, 3))(_ * 2)
 val option: Option[String] = Functor[Option].map(Some(123))(_.toString)
 println("List(1, 2, 3), [_ * 2] =>" + list)
 println("Some(123), _.toString =>" + option)

En el ejemplo anterior, defino un Functor de un tipo List y un segundo Functor de tipo Option. A estos dos functores, se aplican la función map para realizar la transformación, mediante una función, de una lista y de un Option. La función map del elemento scalaz.Functor tiene como parámetros los datos y la función que los modifica.

La salida por consola del ejemplo es la siguiente:

 List(1, 2, 3), [_ * 2] =>List(2, 4, 6)
 Some(123), _.toString =>Some(123)

En muchos casos, es necesario realizar la función de un tipo genérico sin conocer los datos; para ello, utilizamos la función lift. Así, como ejemplo, podemos definir un Functor para un Option de la siguiente manera:

 def lifted: (Option[Int]) => Option[Int] = Functor[Option].lift((x: Int) => x + 1)
 println("0.- lift((x: Int) => x + 1; Some(54) =>" + lifted(Some(54)))

La salida por consola es la siguiente:

 0.- lift((x: Int) => x + 1; Some(54) =>Some(55)

Si deseamos realizar alguna operación sobre el resultado, se puede aplicar la función map como sigue:

 println("0.1.- lift((x: Int) => x + 1; Some(54) =>" + lifted(Some(54)).map((x: Int) => x + 5))

La salida por consola es la siguiente:

 0.1.- lift((x: Int) => x + 1; Some(54) =>Some(60)

Los ejemplos descritos hasta el momento han partido de la definición de un elemento Functor; pero, si deseamos definir una función y utilizarla como un Functor o una Mónada, ¿cómo se realiza? Para ello, es necesario definir la función y emplear la función lift. Para el caso de una Mónada, un ejemplo es el siguiente:

 val func = ((x: Int) => x + 1) lift Monad[Option]
 println("1 ->" + func(Some(87)))

La salida por consola es la siguiente:

 1 ->Some(88)

Si deseamos aplicar mas transformaciones con la función map de la Mónada, se realiza de la siguiente forma:

 println("1.1 ->" + func(Some(87)).map((x: Int) => x + 1))
 println("1.2 ->" + func(Some(87)).map((x: Int) => x + 1).map((x: Int) => x + 10))

La salida por consola es la siguiente:

 1.1 ->Some(89)
 1.2 ->Some(99)

Si deseamos definir la transformación como una función, se puede realizar de la siguiente forma:

 def func2(elem: Int) = func(Some(elem)).map((x: Int) => x + 1).map((x: Int) => x + 10)
 println("1.3 ->" + func2(87))

La salida por consola es la siguiente:

 1.3 ->Some(99)

La definición de una función para realizar un morfismo de una lista de enteros en otra lista de enteros, se puede definir de la siguiente manera.

 def liftedListInt: (List[Int] => List[Int]) = Functor[List].lift((x: Int) => x * 5)
 println("2 ->" + liftedListInt(List(1, 2, 3)))
 println("2.1 ->" + liftedListInt(List(1, 2, 3)).map((x: Int) => x * 5))

La salida por consola es la siguiente:

 2 ->List(5, 10, 15)
 2.1 ->List(25, 50, 75)

Otras funciones

Scalaz es un conjunto de componentes de type classes y, el patrón type classes, permite la definición de sintaxis. En el presente apartado, se identifican un conjunto de funciones pertenecientes a la sintaxis de functores. La importación de los elementos necesarios para los ejemplos son las siguientes:

 import scalaz.Functor
 import scalaz.Scalaz._

La selección de las funciones que he realizado son las siguientes:

  • Para convertir todos los elementos de una estructura a un elemento determinado, se emplea la función >|. Un ejemplo es el siguiente:
 val listaX = List(1,2,3) >| "x"
 println(s"List(1,2,3) >| 'x'=${listaX}")

La salida por consola es la siguiente:

 List(1,2,3) >| 'x'=List(x, x, x)
  • Para convertir todos los elementos de una estructura a un elemento determinado, se emplea la función as. Un ejemplo es el siguiente:
 val listaAs = List(1,2,3) as "x"
 println(s"List(1,2,3) as 'x'=${listaAs}")

La salida por consola es la siguiente:

 List(1,2,3) as 'x'=List(x, x, x)
  • Para convertir un conjunto de entrada en un conjunto de tuplas con elementos duplicados, se emplea la función fpair. Un ejemplo es el siguiente:
 val listaFPair = List(1,2,3).fpair
 println(s"List(1,2,3).fpair=${listaFPair}")

La salida por consola es la siguiente:

 List(1,2,3).fpair=List((1,1), (2,2), (3,3))
  • Para convertir un conjunto de entrada en un conjunto de duplas cuyo elemento derecho sea uno determinada, se emplea la función strengthR. Un ejemplo es el siguiente:
 val listaStrengthR = List(1,2,3).strengthR("x")
 println(s"List(1,2,3).strengthR('x')=${listaStrengthR}")

La salida por consola es la siguiente:

 List(1,2,3).strengthR('x')=List((1,x), (2,x), (3,x))
  • Para convertir un conjunto de entrada en un conjunto de duplas cuyo elemento izquierdo sea uno determinada, se emplea la función strengthL. Un ejemplo es el siguiente:
 val listaStrengthL = List(1,2,3).strengthL("x")
 println(s"List(1,2,3).strengthL('x')=${listaStrengthL}")

La salida por consola es la siguiente:

 List(1,2,3).strengthL('x')=List((x,1), (x,2), (x,3))
  • Para convertir un conjunto de entrada en un conjunto de tuplas vacías, se emplea la función void. Un ejemplo es el siguiente:
 val listaVoid = List(1,2,3).void
 println(s"List(1,2,3).void=${listaVoid}")

La salida por consola es la siguiente:

 List(1,2,3).void=List((), (), ())

La definición de un Functor o una Mónada mediante el patrón funcional type classes es una operación que requiere, para el desarrollador principiante en la programación funcional, un entendimiento de conceptos complejos. Mediante la utilización de Scalaz utilizar Functores y definir funciones como functores es un proceso comprensible y fácil de entender.

Para el lector interesado, las entradas que he realizado sobre Scalaz son las siguientes:

Notas de programación funcional

En la entrada de hoy, “Notas de programación funcional”, describiré ciertos conceptos generales de la programación funcional. Serán pequeñas píldoras documentales, o bien, mis notas sobre los conceptos iniciales en la programación funcional. No pretendo realizar definiciones formales, ni que la entrada sea formal; solo pretendo crear pequeñas notas las cuáles sirvan para allanar los primeros pasos en el estudio de la programación funcional.

El lenguaje Scala es un lenguaje híbrido con en el que se aplican dos paradigmas: el paradigma funcional y el paradigma orientado a objetos. El creador del lenguaje es Martin Odersky en el 2004. El lenguaje Scala está basado en el lenguaje Haskell y el lenguaje Erlang, adquiriendo de estos dos lenguajes, lo mejor de ellos. Del lenguaje Haskell, los principios de la programación funcional y, del lenguaje Erlang, el modelo de actores para la programación concurrente.

Funciones

En Scala hay diferentes tipos de funciones: funciones totales, funciones parciales, first class function,…No voy a realizar una descripción total de todas ellas, pero me centraré en el concepto de función genérico.

Definimos una función con la siguiente estructura:

 def nombreFunción([lista de parámetros]): [Tipo de retorno] = {
   Cuerpo de la función
   return [expresiónRetorno]
 }

Un ejemplo de función es la siguiente:

 def suma( operador1:Int, operador2:Int ): Int = {
   var suma: Int = 0
   suma = operador1 + operador2
   return suma
 }

En Scala, tenemos la posibilidad de definir funciones como variables, sin la necesidad de definir una función de forma específica; este caso, se conoce como first class function. Un ejemplo de first class function es el siguiente:

 val suma: (Int,Int) => Int = (a:Int, b:Int) => a + b
 println(s"suma(2,3)=${suma(2,3)}")
 println

El compilador Scala, realiza la transformación de la función suma como una clase de tipo Function, permitiendo la posibilidad de definir este tipo de variables función de forma sencilla.

Las funciones parciales son aquellas funciones en donde se define parte de la función. En el siguiente ejemplo, defino una función parcial suma en donde se define el primer operando y, el segundo operando, es pasado por parámetro.

val suma2: PartialFunction[Int, Int] = {
 case d:Int => 2 + d
 }
 println(s"suma2(2+3)=${suma2(3)}")
 println

Recursividad

La recursividad es aquella forma en la cual una función se define basada en su propia definición. Una función recursiva se define en función de dos pasos: el caso base, solución a la instancia mas sencilla; y, el caso de inducción, solución a los casos complejos.

Un ejemplo típico de recursividad es la función factorial, la cual se define en lenguaje Scala como sigue:

 def factorial(n: Int): Int = {
   if (n > 1)
     n * factorial(n-1)
   else
     1
   }
 println(s"factorial(3)=${factorial(3)}")
 println

Las funciones recursivas son utilizas en estructuras de datos recursivas, como por ejemplo, una lista o un árbol.

Existe dos tipos de recursividad: la recursividad por la cabecera y la recursividad por la cola.

La recursividad por la cabecera es aquella recursividad que se realiza aplicando el cálculo de la operación con la cabecera de la estructura y, una vez realizada, se realiza la llamada recursiva con la cola. Con esta recursividad, para el caso de una lista, se realiza el recorrido desde el inicio de la estructura (cabecera) hasta el final de la lista.

La recursividad por la cola es aquella recursividad que se realiza aplicando las llamadas recursivas a la función y, una vez llamadas, se realiza el cálculo; es decir, recorres la lista con las llamadas y, en el retorno de la recursividad, aplicas el cálculo. Con esta recursividad, para el caso de una lista, se realiza el recorrido desde el final de la estructura hasta el inicio.

ADT

Scala es un lenguaje tipado, como por ejemplo: tipo entero, Int; tipo alfanumérico, String; tipo lógico, Boolean;… Con la combinación de estos tipos, podemos definir tipos más complejos, mediante las operaciones suma y producto.

Definimos un ADT (Algebraic Data Type), tipo de datos algebraico, como aquel tipo conformado por tipos simples los cuales, mediante las operaciones de suma y producto, formamos tipos más complejos. La operación suma es aquella operación que corresponde con la herencia y, la operación producto, es aquella operación que corresponde con las definiciones de los parámetros de las case class.

Un ejemplo de un ADT que define un tipo Lista con tipos enteros, es el siguiente:

sealed trait MiLista
case class Null extends MiLista
case class Nodo(cabeza:Int, cola:MiLista)

De la definición anterior, podemos decir que tenemos la definición de una estructura de tipo lista de enteros de una forma matemática clara y sencilla; pero, ¿y si queremos definir una lista de otro tipo? La primera solución, es definir otro ADT para el tipo seleccionado; y, la segunda solución, consiste en definir un ADT con la capacidad de soportar polimosfirmo paramétrico. Un ejemplo de una lista con polimorfísmo paramétrico es el siguiente:

sealed trait MiLista[T]
case class Null[T]() extends MiLista[T]
case class Nodo[T](cabeza:[T], cola:MiLista[T])

Con la definición anterior, podemos definir una lista de cualquier tipo.

Funciones de Orden Superior (HOF – Hight Order Function)

Las funciones de orden superior son aquellas funciones que permiten definir como parámetro otra función, es decir, un parámetro de la función puede ser una función. Un ejemplo básico y sencillo de función HOF, puede ser el siguiente:

 def ejemploHOF(mensaje:String, f: (Int,Int) => Int, operador1:Int, operador2:Int ): Unit = {
   println(mensaje + "=" + f(operador1, operador2))
 }
 ejemploHOF( "Resultado de la suma(2,3)", suma, 2, 3 )

La salida por consola del ejemplo es el siguiente:

Resultado de la suma(2,3)=5

El ejemplo parece sencillo pero a partir de este concepto se construyen muchos patrones de la programación funcional que no son tan sencillos.

Catamorfismo

En los apartados anteriores describí conceptos como los ADT’s y funciones de orden superior; pero, llegado a este punto, hay que preguntarse: ¿cómo trabajo con los ADT’s?, ¿cómo realizo un cálculo sobre un ADT?, ¿con qué mecanismos los puedo manipular? La respuesta es sencilla, trabajamos los ADT’s con los catamorfismos.

Definimos catamorfismo como aquella formar de interpretar, manipular o consumir un ADT. Se puede definir con cualquier ADT y, a nivel práctico, se corresponde con la función fold.

El ADT es aquel tipo definido desde un punto de vista matemático y, la programación funcional, tiene un aspecto matemático; con lo cual, la forma de pensar debe de ser matemática.

Sea el ADT que define la estructura Lista del apartado anterior definido de la siguiente forma:

sealed trait MiLista[T] // Caso abstracto
case class Null[T]() extends MiLista[T] // Caso Base
case class Nodo[T](cabeza:[T], cola:MiLista[T]) extends MiLista[T]// Caso de Inducción

A nivel conceptual, una lista se puede representar con la anterior definición de la siguiente forma:

Lista(1,2,3) => val lista: MiLista[Int] = Nodo(1, Nodo(2, Nodo(3, Null) ) )

Dado el siguiente problema a resolver: cálculo de la suma de los elementos de una lista, es decir: dada un elemento de tipo MiLista[Int], se desea definir una función que calcule la suma de los elementos y retorne un número entero.

La definición del ADT está formada por tres elementos: caso base, caso de inducción y caso abstracto. Con estos tres casos definimos el catamorfismo de la siguiente forma:

  • Caso Base. Dado un elemento de tipo Null[Int], ¿qué tengo que realizar para retornar como resultado un entero(B)?.
Null[Int] ---(B)---> Int; Resultado: B=0

Dado el caso base, tenemos que retornar el valor 0. Para toda lista vacía, la suma de los elementos de una lista es cero.

  •  Caso de inducción. Dado un elemento de tipo Nodo[Int], ¿qué tengo que realizar para calcular la suma de sus elementos(B)?
Node[Int] -----(A:Int, B:MiLista[Int]) => B(Int)---> Int; Resultado: (A, B) => B

Un Node está formado por una cabeza(parte A) y un cola de tipo MiLista(parte B). La suma de la parte A y de la parte B tiene que tener como resultado un número B entero, es decir, todo elemento A mas B (resultado de la cola) tiene que tener como resultado B

  • Caso abstracto. El caso abstracto lo forma la unión del caso base y el caso de inducción; es decir, la operación suma y la operación producto. Así, tenemos:
    • caso base: Null[Int] => B
    • caso inducción: Nodo[T](cabeza:[T], cola:MiLista[T]); (A, B) => B
    • caso abstracto: caso base más caso inducción: Null[Int] U Nodo[T](cabeza:[T], cola:MiLista[T]) => (B, (A,B)=> B)

Así, la función fold queda definida de la siguiente forma:

 def fold[A,B](lista:MiLista[A])(base:B, f: (A, B) => B): B = lista match{
   case Null() => base
   case Nodo(h,t) => f(h, fold(t)(base,f))
 }

Fold, FoldRight

La función fold es idéntica a la función foldRight. Estas funciones están enfocadas a una recursividad de cabacera.

Así, la función foldRight queda definida como sigue:

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

Desde un punto de vista de las llamadas a realizar y qué elementos intervienen en cada una de las llamadas, se puede ver como sigue:

-> 1 + foldRight(–)
-> 1 + (2 + foldRight(–) )
-> 1 + (2 + (3 + foldRight(–) ) )
-> 1 + (2 + (3 + ( 4 + foldRight(–) ) ) )

Por cada llamada, se van insertando una entrada en la pila del sistema. Cuando se termina el espacio, la ejecución falla. Un ejemplo para llegar a esta situación es el siguiente:

 val listaEnteros = (1 to 325000).toList
 println( foldRight(listaEnteros)(0, (a:Int, b:Int) => a + b) )

La salida por consola es la siguiente:

Exception in thread "main" java.lang.StackOverflowError

FoldLeft

La función foldLeft tiene un parecido con las funciones fold y foldRight, la diferencia, reside en el orden de los parámetros de la función pasada por parámetro. El tipo de recursividad es por la cola, es decir, se realiza la llamada recursiva y, una vez llamada, se realiza el cálculo. La función foldLeft se define como sigue:

@annotation.tailrec
 def foldLeft[A,B](l:List[A])(zero:B, f:(B,A)=>B): B = l match {
 case Nil => zero
 case head::tail => foldLeft(tail)( f(zero,head), f )
 }

Este tipo de recursión en Scala es la más eficiente porque se llama a la función con el valor acumulado.

Para demostrar la eficiencia de esta función, realizamos el cálculo de la suma de la lista de ejemplo de foldRight.

 val listaEnteros = (1 to 325000).toList
 println( foldLeft(listaEnteros)(0, (a:Int, b:Int) => a + b) )

La salida por consola es la siguiente:

1273054948

Como he comentado al inicio de la entrada, no he querido ser formal, simplemente he querido mostrar pequeñas píldoras documentales para que, a la persona iniciada en la programación funcional, le permita comprender las piedras iniciales. Desde mi experiencia, pasadas estas primeras piedras, el proceso de comprensión del resto de conceptos es más sencillo.