Programación Funcional para Mortales con Scalaz
Programación Funcional para Mortales con Scalaz
Buy on Leanpub

Tabla de contenidos

“El amor es sabio; el odio es tonto. En este mundo, que está interconectado cada vez más, tenemos que aprender a tolerarnos unos a otros, tenemos que aprender a soportar el hecho de que algunas personas dirán cosas que no nos agraden. Es la única manera en la que podemos vivir juntos. Pero si hemos de vivir juntos, y no morir juntos, debemos aprender una clase de caridad y clase de tolerancia, que es absolutamente vital para la continuidad de la vida humana en este planeta.”

― Bertrand Russell

Acerca de este libro

Este libro es para el desarrollador de Scala típico, probablemente con conocimientos previos de Java, que tiene escepticismo y curiosidad sobre el paradigma de Programación Funcional (PF). Este libro justifica cada concepto con ejemplos prácticos, incluyendo la escritura de una aplicación web.

Este libro usa Scalaz 7.2, la librería para Programación Funcional en Scala más exhaustiva, popular, estable y basada en principios.

Este libro está diseñado para leerse de principio a fin, en el orden presentado, con un descanso entre capítulos. Los primeros capítulos incentivan estilos de programación que más tarde serán desacreditados: de manera similar a cómo aprendimos la teoría la gravedad de Newton cuando eramos niños, y progresamos a Riemann/Einstein/Maxwell si nos convertimos en estudiantes de física.

No es necesaria una computadora mientras se lee el libro, pero se recomienda el estudio del código fuente de Scalaz. Algunos de los ejemplos de código más complejos se encuentran con el código fuente del libro y se anima a aquellos que deseen ejercicios prácticos a reimplementar Scalaz (y la aplicación de ejemplo) usando las descripciones parciales presentadas en este libro.

También recomendamos El libro rojo como lectura adicional. Éste libro enseña cómo escribir una librería de Programación Funcional en Scala usando principios fundamentales.

Aviso de Copyleft

Este libro es Libre y sigue la filosofía de Free Software: usted puede usar este libro como desee, el código fuente está disponible y puede redistribuir este libro y puede distribuir su propia versión. Esto significa que puede imprimirlo, fotocopiarlos, enviarlo por correo electrónico, subirlo a sitios web, cambiarlo, traducirlo, cobrar por él, mezclarlo, borrar partes de él, y dibujar encima de él.

Este libro es Copyleft: si usted cambia el libro y distribuye su propia version, también debe pasar estas libertades a quienes lo reciban.

Este libro usa la licencia Atribución/Reconocimiento-CompartirIgual 4.0 Internacional (CC BY-SA 4.0).

Todos los fragmentos de código en este libro están licenciadas de manera separada de acuerdo con CC0, y usted puede usarlos sin restricción. Los fragmentos de Scalaz y librerías relacionadas mantienen su propia licencia, que se reproduce de manera completa en el apéndice.

La aplicación de ejemplo drone-dynamic-agents se distribuye bajo los términos de la licencia GPLv3: sólo los fragmentos de código en este libro están disponibles sin restricción alguna.

Agradecimientos

Diego Esteban Alonso Blas, Raúl Raja Martínez y Peter Neyens de 47 degrees, Rúnar Bjarnason, Tony Morris, John de Goes y Edward Kmett por su ayuda explicando los principios de la Programación Funcional. Kenji Yoshida y Jason Zaugg por ser los principales autores de Scalaz, y Paul Chiusano / Miles Sabin por arreglar un error crítico en el compilador de Scala (SI-2712).

Muchas gracias a los lectores que dieron retroalimentación de los primeros bosquejos de este texto.

Cierto material fue particularmente valioso para mi propio entendimiento de los conceptos que están en este libro. Gracias a Juan Manuel Serrano por All Roads Lead to Lambda, Pere Villega por On Free Monads, Dick Wall y Josh Suereth por For: What is it Good For?, Erik Bakker por Options in Futures, how to unsuck them, Noel Markham por ADTs for the Win!, Sukant Hajra por Classy Monad Transformers, Luka Jacobowitz por Optimizing Tagless Final, Vincent Marquez por Index your State, Gabriel Gonzalez por The Continuation Monad, y Yi Lin Wei / Zainab Ali por sus tutoriales en los meetups Hack The Tower.

A las almas serviciales que pacientemente me explicaron cosas a mi: Merlin Göttlinger, Edmund Noble, Fabio Labella, Adelbert Chang, Michael Pilquist, Paul Snively, Daniel Spiewak, Stephen Compall, Brian McKenna, Ryan Delucchi, Pedro Rodriguez, Emily Pillmore, Aaron Vargo, Tomas Mikula, Jean-Baptiste Giraudeau, Itamar Ravid, Ross A. Baker, Alexander Konovalov, Harrison Houghton, Alexandre Archambault, Christopher Davenport, Jose Cardona, Isaac Elliott.

Aspectos prácticos

Para configurar un proyecto que use las librerías presentadas en este libro, use una versión reciente de Scala con características específicas de Programación Funcional habilitadas (por ejemplo, en build.sbt):

  scalaVersion in ThisBuild := "2.12.6"
  scalacOptions in ThisBuild ++= Seq(
    "-language:_",
    "-Ypartial-unification",
    "-Xfatal-warnings"
  )

  libraryDependencies ++= Seq(
    "com.github.mpilquist" %% "simulacrum"     % "0.13.0",
    "org.scalaz"           %% "scalaz-core"    % "7.2.26"
  )

  addCompilerPlugin("org.spire-math" %% "kind-projector" % "0.9.7")
  addCompilerPlugin("org.scalamacros" % "paradise" % "2.1.1" cross CrossVersion.full)

Con el objetivo de mantener la brevedad en los fragmentos de código, omitiremos la sección de import. A menos que se diga lo contrario, asumimos que todos los fragmentos tienen las siguientes sentencias de import:

  import scalaz._, Scalaz._
  import simulacrum._

1. Introducción

Es parte de la naturaleza humana permanecer escéptico a un nuevo paradigma. Para poner en perspectiva qué tan lejos hemos llegado, y los cambios que ya hemos aceptado en la JVM (de las siglas en inglés para Máquina Virtual de Java), empecemos recapitulando brevemente los últimos 20 años.

Java 1.2 introdujo la API de Colecciones, permitiéndonos escribir métodos que abstraen sobre colecciones mutables. Era útil para escribir algoritmos de propósito general y era el fundamento de nuestras bases de código.

Pero había un problema, teníamos que hacer casting en tiempo de ejecución:

  public String first(Collection collection) {
    return (String)(collection.get(0));
  }

En respuesta, los desarrolladores definieron objectos en su lógica de negocios que eran efectivamente ColeccionesDeCosas, y la API de Colecciones se convirtió en un detalle de implementación.

En 2005, Java 5 introdujo los genéricos, permitiéndonos definir una Coleccion<Cosa>, abstrayendo no sólo el contenedor sino sus elementos. Los genéricos cambiaron la forma en que escribimos Java.

El autor del compilador de genéricos para Java, Martin Odersky, creó Scala después, con un systema de tipo más fuerte, estructuras inmutables y herencia múltiple. Esto trajo consigo una fusión de la Programación Orientada a Objectos (POO) y la Programación Funcional (PF).

Para la mayoría de los desarrolladores, PF significa usar datos inmutables tanto como sea posible, pero consideran que el estado mutable todavía es un mal necesario que debe aislarse y controlarse, por ejemplo con actores de Akka o clases sincronizadas. Este estilo de PF resulta en programas simples que son fáciles de paralelizar y distribuir: definitivamente es una mejora con respecto a Java. Pero este enfoque solo toca la amplia superficie de beneficios de PF, como descubriremos en este libro.

Scala también incorpora Future, haciendo simple escribir aplicaciones asíncronas. Pero cuando un Future se usa en un tipo de retorno, todo necesita reescribirse para usarlos, incluyendo las pruebas, que ahora están sujetas a timeouts arbitrarios.

Nos encontramos con un problema similar al que se tuvo con Java 1.0: no hay forma de abstraer la ejecución, así como no se tenía una manera de abstraer sobre las colecciones.

1.1 Abstrayendo sobre la ejecución

Suponga que deseamos interactuar con el usuario a través de la línea de comandos. Podemos leer (read) lo que el usuario teclea y entonces podemos escribirle (write) un mensaje.

  trait TerminalSync {
    def read(): String
    def write(t: String): Unit
  }

  trait TerminalAsync {
    def read(): Future[String]
    def write(t: String): Future[Unit]
  }

¿Cómo podemos escribir código genérico que haga algo tan simple como un eco de la entrada del usuario, ya sea de manera síncrona o asíncrona, dependiendo de nuestra implementación para tiempo de ejecución?

Podríamos escribir una versión síncrona y envolverla en un Future pero ahora tendríamos que preocuparnos por cuál thread pool debemos usar para ejecutar el trabajo, o podríamos esperar el Future con Await.result y bloquear el thread. En ambos casos, es mucho código tedioso y fundamentalmente estamos lidiando con dos APIs que no están unificadas.

Podríamos resolver el problema, como con Java 1.2, con un padre común usando el soporte de Scala para higher-kinded types (HKT).

Deseamos definir Terminal para un constructor de tipo C[_]. Si definimos Now (en español, ahora) de modo que sea equivalente a su parámetro de tipo (como Id), es posible implementar una interfaz común para terminales síncronas y asíncronas:

  trait Terminal[C[_]] {
    def read: C[String]
    def write(t: String): C[Unit]
  }

  type Now[X] = X

  object TerminalSync extends Terminal[Now] {
    def read: String = ???
    def write(t: String): Unit = ???
  }

  object TerminalAsync extends Terminal[Future] {
    def read: Future[String] = ???
    def write(t: String): Future[Unit] = ???
  }

Podemos pensar en C como un Contexto porque decimos “en el contexto de ejecución Now (ahora)” o “en el Futuro”.

Pero no sabemos nada sobre C y tampoco podemos hacer algo con un C[String]. Lo que necesitamos es un contexto/ambiente de ejecución que nos permita invocar un método que devuelva C[T] y después sea capaz de hacer algo con la T, incluyendo la invocación de otro método sobre Terminal. También necesitamos una forma de envolver un valor como un C[_]. La siguiente signatura funciona bien:

  trait Execution[C[_]] {
    def chain[A, B](c: C[A])(f: A => C[B]): C[B]
    def create[B](b: B): C[B]
  }

que nos permite escribir:

  def echo[C[_]](t: Terminal[C], e: Execution[C]): C[String] =
    e.chain(t.read) { in: String =>
      e.chain(t.write(in)) { _: Unit =>
        e.create(in)
      }
    }

Ahora podemos compartir la implementación de echo en código síncrono y asíncrono. Podemos escribir una implementación simulada de Terminal[Now] y usarla en nuestras pruebas sin ningún tiempo límite (timeout).

Las implementaciones de Execution[Now] y Execution[Future] son reusables por métodos genéricos como echo.

Pero el código para echo es horrible!

La característica de clases implícitas del lenguaje Scala puede darle a C algunos métodos. Llamaremos a estos métodos flatMap y map por razones que serán más claras en un momento. Cada método acepta un implicit Execution[C]. Estos no son más que los métodos flatMap y map a los que estamos acostumbrados a usar con Seq, Option y Future.

  object Execution {
    implicit class Ops[A, C[_]](c: C[A]) {
      def flatMap[B](f: A => C[B])(implicit e: Execution[C]): C[B] =
            e.chain(c)(f)
      def map[B](f: A => B)(implicit e: Execution[C]): C[B] =
            e.chain(c)(f andThen e.create)
    }
  }

  def echo[C[_]](implicit t: Terminal[C], e: Execution[C]): C[String] =
    t.read.flatMap { in: String =>
      t.write(in).map { _: Unit =>
        in
      }
    }

Ahora podemos revelar porqué usamos flatMap como el nombre del método: nos permite usar una for comprehension, que es una conveniencia sintáctica (syntax sugar) para flatMap y map anidados.

  def echo[C[_]](implicit t: Terminal[C], e: Execution[C]): C[String] =
    for {
      in <- t.read
       _ <- t.write(in)
    } yield in

Nuestro contexto Execution tiene las mismas signaturas que una trait en Scalaz llamada Monad, excepto que chain es bind y create es pure. Decimos que C es monádica cuando hay una Monad[C] implícita disponible en el ámbito. Además, Scalaz tiene el alias de tipo Id.

En resumen, si escribimos métodos que operen en tipos monádicos, entonces podemos escribir código sequencial que puede abstraer sobre su contexto de ejecución. Aquí, hemos mostrado una abstracción sobre la ejecución síncrona y asíncrona pero también puede ser con el propósito de conseguir un manejo más riguroso de los errores (donde C[_] es Either[Error, ?]), administrar o controlar el acceso a estado volátil, realizar I/O, o la revisión de la sesión.

1.2 Programación Funcional Pura

La programación funcional es el acto de escribir programas con funciones puras. Las funciones puras tienen tres propiedades:

  • Totales: devuelven un valor para cada entrada posible.
  • Deterministas: devuelven el mismo valor para la misma entrada.
  • Inculpable: no interactúan (directamente) con el mundo o el estado del programa.

Juntas, estas propiedades nos dan una habilidad sin precedentes para razonar sobre nuestro código. Por ejemplo, la validación de entradas es más fácil de aislar gracias a la totalidad, el almacenamiento en caché es posible cuando las funciones son deterministas, y la interacción con el mundo es más fácil de controlar, y probar, cuando las funciones son inculpables.

Los tipos de cosas que violan estas propiedades son efectos laterales: el acceso o cambio directo de estado mutable (por ejemplo, mantener una var en una clase o el uso de una API antigua e impura), la comunicación con recursos externos (por ejemplo, archivos o una búsqueda en la red), o lanzar y atrapar excepciones.

Escribimos funciones puras mediante evitar las excepciones, e interactuando con el mundo únicamente a través de un contexto de ejecución F[_] seguro.

En la sección previa, se hizo una abstracción sobre la ejecución y se definieron echo[Id] y echo[Future]. Tal vez esperaríamos, razonablemente, que la invocación de cualquier echo no realizara ningún efecto lateral, porque es puro. Sin embargo, si usamos Future o Id como nuestro contexto de ejecución, nuestra aplicación empezará a escuchar a stdin:

  val futureEcho: Future[String] = echo[Future]

Estaríamos violando la pureza y no estaríamos escribiendo código puramente funcional: futureEchoes el resultado de invocar echo una vez. Future combina la definición de un programa con su interpretación (su ejecución). Como resultado, es más difícil razonar sobre las aplicaciones construidas con Future.

Podemos definir un contexto de ejecución simple F[_]:

  final class IO[A](val interpret: () => A) {
    def map[B](f: A => B): IO[B] = IO(f(interpret()))
    def flatMap[B](f: A => IO[B]): IO[B] = IO(f(interpret()).interpret())
  }
  object IO {
    def apply[A](a: =>A): IO[A] = new IO(() => a)
  }

que evalúa un thunk de manera perezosa (o por necesidad). IO es simplemente una estructura de datos que referencia (posiblemente) código impuro, y no está, en realidad, ejecutando algo. Podemos implementar Terminal[IO]:

  object TerminalIO extends Terminal[IO] {
    def read: IO[String]           = IO { io.StdIn.readLine }
    def write(t: String): IO[Unit] = IO { println(t) }
  }

e invocar echo[IO] para obtener de vuelta el valor

  val delayed: IO[String] = echo[IO]

Este val delayed puede ser reutilizado, es simplemente la definición del trabajo que debe hacerse. Podemos mapear la cadena y componer (en el sentido funcional) programas, tal como podríamos mapear un Futuro. IO nos mantiene honestos al hacer explícito que dependemos de una interacción con el mundo, pero no nos detiene de acceder a la salida de tal interacción.

El código impuro dentro de IO solo es evaluado cuando se invoca .interpret() sobre el valor, y se trata de una acción impura

  delayed.interpret()

Una aplicación compuesta de programas IO solamente se interpreta una vez, en el método main, que tambié se llama el fin del mundo.

En este libro, expandiremos los conceptos introducidos en este capítulo y mostraremos cómo escribir funciones mantenibles y puras, que logren nuestros objetivos de negocio.

2. Comprensión for

La comprensión for de Scala es la abstracción ideal de la programación funcional para los programas secuenciales que interactúan con el mundo. Dado que la usaremos mucho, vamos a reaprender los principios de for y cómo Scalaz puede ayudarnos a escribir código más claro.

Este capítulo no intenta enseñarnos a escribir programas puros y las técnicas son aplicables a bases de código que no sean puramente funcionales.

2.1 Conveniencia sintáctica

for en Scala es simplemente una regla de reescritura, llamada también una conveniencia sintáctica (azúcar sintáctico) y no tiene ninguna información contextual.

Para ver qué es lo que hace una for comprehension, usamos la característica show y reify de la REPL (Read-Eval-Print-Loop) para mostrar cómo se ve el código después de la inferencia de tipos.

  scala> import scala.reflect.runtime.universe._
  scala> val a, b, c = Option(1)
  scala> show { reify {
           for { i <- a ; j <- b ; k <- c } yield (i + j + k)
         } }

  res:
  $read.a.flatMap(
    ((i) => $read.b.flatMap(
      ((j) => $read.c.map(
        ((k) => i.$plus(j).$plus(k)))))))

Existe mucho “ruido” debido a las conveniencias sintácticas adicionales (por ejemplo, + se reescribe $plus, etc.). No mostraremos el show y el reify por brevedad cuando la línea del REPL se muestre como reify, y manualmente limpiaremos el código generado de modo que no se vuelva una distracción.

  reify> for { i <- a ; j <- b ; k <- c } yield (i + j + k)

  a.flatMap {
    i => b.flatMap {
      j => c.map {
        k => i + j + k }}}

La regla de oro es que cada <- (llamada un generador) es una invocación anidada de flatMap, siendo el último generador un map que contiene el cuerpo del yield.

2.1.1 Asignación

Podemos asignar valores al vuelo (inline) como ij = i + j (no es necesaria la palabra reservada val).

  reify> for {
           i <- a
           j <- b
           ij = i + j
           k <- c
         } yield (ij + k)

  a.flatMap {
    i => b.map { j => (j, i + j) }.flatMap {
      case (j, ij) => c.map {
        k => ij + k }}}

Un map sobre la b introduce la ij, sobre la cual se llama un flatMap junto con la j, y entonces se invoca a un map final sobre el código en el yield.

Desgraciadamente no podemos realizar ninguna asignación antes de algún generador. Esta característica ya ha sido solicitada para que sea soportada por el lenguaje, pero la implementación no se ha llevado a cabo: https://github.com/scala/bug/issues/907

  scala> for {
           initial = getDefault
           i <- a
         } yield initial + i
  <console>:1: error: '<-' expected but '=' found.

Podemos proporcionar una solución alternativa al definir un val fuera del for

  scala> val initial = getDefault
  scala> for { i <- a } yield initial + i

o crear un Option a partir de la asignación inicial

  scala> for {
           initial <- Option(getDefault)
           i <- a
         } yield initial + i

2.1.2 Filter

Es posible poner sentencias if después de un generador para filtrar los valores usando un predicado

  reify> for {
           i  <- a
           j  <- b
           if i > j
           k  <- c
         } yield (i + j + k)

  a.flatMap {
    i => b.withFilter {
      j => i > j }.flatMap {
        j => c.map {
          k => i + j + k }}}

Versiones anteriores de Scala usaban filter, pero Traversable.filter crea nuevas colecciones para cada predicado, de modo que withFilter se introdujo como una alternativa de mayor rendimiento. Podemos ocasionar accidentalmente la invocación de withFilter al proporcionar información de tipo, interpretada como un empate de patrones.

  reify> for { i: Int <- a } yield i

  a.withFilter {
    case i: Int => true
    case _      => false
  }.map { case i: Int => i }

Como la asignación, un generador puede usar un empate de patrones en el lado izquierdo. Pero a diferencia de una asignación (que lanza un MatchError al fallar) los generadores son filtrados y no fallarán en tiempo de ejecución. Sin embargo, existe una aplicación ineficiente, doble, del patrón.

2.1.3 For Each

Finalmente, si no hay un yield, el compilador usará foreach en lugar de flatMap, que es útil únicamente por los efectos colaterales.

  reify> for { i <- a ; j <- b } println(s"$i $j")

  a.foreach { i => b.foreach { j => println(s"$i $j") } }

2.1.4 Resumen

El conjunto completo de métodos soportados por las for comprehensions no comparten un super tipo común; cada fragmento generado es compilado de manera independiente. Si hubiera un trait, se vería aproximadamente así:

  trait ForComprehensible[C[_]] {
    def map[A, B](f: A => B): C[B]
    def flatMap[A, B](f: A => C[B]): C[B]
    def withFilter[A](p: A => Boolean): C[A]
    def foreach[A](f: A => Unit): Unit
  }

Si el contexto (C[_]) de una for comprehension no proporciona su propio map y flatMap, no todo está perdido. Si existe un valor implícito de scalaz.Bind[T] para la T en cuestión, este proporcionará el map y el flatMap.

2.2 El camino dificultoso

Hasta el momento sólo hemos observado las reglas de reescritura, no lo que está sucediendo en el map y en el flatMap. Considere lo que sucede cuando el contexto del for decide que no se puede proceder más.

En el ejemplo del Option, el yield se invoca únicamente cuando todos i, j, k están definidos.

  for {
    i <- a
    j <- b
    k <- c
  } yield (i + j + k)

Si cualquiera de a, b, c es None, la comprehension se corto-circuita con None pero no nos indica qué fue lo que salió mal.

Si usamos Either, entonces un Left ocasionará que la for comprehension se corto circuite con información extra, mucho mejor que Option para reporte de errores:

  scala> val a = Right(1)
  scala> val b = Right(2)
  scala> val c: Either[String, Int] = Left("sorry, no c")
  scala> for { i <- a ; j <- b ; k <- c } yield (i + j + k)

  Left(sorry, no c)

Y por último, veamos que sucede con un Future que falla:

  scala> import scala.concurrent._
  scala> import ExecutionContext.Implicits.global
  scala> for {
           i <- Future.failed[Int](new Throwable)
           j <- Future { println("hello") ; 1 }
         } yield (i + j)
  scala> Await.result(f, duration.Duration.Inf)
  caught java.lang.Throwable

El Future que imprime a la terminal nunca se invoca porque, como Option y Either, la for comprehension se corto circuita.

El corto circuito para el camino difícil es un tema común e importante. Las for comprehensions no pueden expresar la limpieza de recursos: no hay forma de realizar un try/finally. Esto es bueno, en PF asigna claramente la responsabilidad por la recuperación inesperada de errores y la limpieza de recursos en el contexto (que normalmente es una Monad como veremos más tarde), no la lógica del negocio.

2.3 Gimnasia

Aunque es sencillo reescribir código secuencial simple como una for comprehension, algunas veces desearemos hacer algo que parezca requerir hacer volteretas mentales. Esta sección recolecta algunos ejemplos prácticos de cómo lidiar con ellos.

2.3.1 Lógica de respaldo

Digamos que estamos llamando a un método que regresa un Option. Si no es exitoso deseamos ejecutar otro método como respaldo (y así consecutivamente), como cuando estamos unando un cache:

  def getFromRedis(s: String): Option[String]
  def getFromSql(s: String): Option[String]

  getFromRedis(key) orElse getFromSql(key)

Si tenemos que hacer esto para una versión asíncrona de la misma API

  def getFromRedis(s: String): Future[Option[String]]
  def getFromSql(s: String): Future[Option[String]]

entonces tenemos que ser cuidadosos de no hacer trabajo extra porque

  for {
    cache <- getFromRedis(key)
    sql   <- getFromSql(key)
  } yield cache orElse sql

ejecutará ambas consultas. Podemos hacer empate de patrones en el primer resultado pero el tipo es incorrecto

  for {
    cache <- getFromRedis(key)
    res   <- cache match {
               case Some(_) => cache !!! wrong type !!!
               case None    => getFromSql(key)
             }
  } yield res

Necesitamos crear un Future a partir del cache

  for {
    cache <- getFromRedis(key)
    res   <- cache match {
               case Some(_) => Future.successful(cache)
               case None    => getFromSql(key)
             }
  } yield res

Future.successful crea un nuevo Future, de manera muy similar a cómo un Option o un constructor de List.

2.3.2 Salida temprana

Digamos que tenemos alguna condición que implique la terminación temprana con un valor exitoso.

Si deseamos terminar de manera temprana con un error, es práctica estándar en programación orientada a objectos lanzar una excepción

  def getA: Int = ...

  val a = getA
  require(a > 0, s"$a must be positive")
  a * 10

que puede reescribirse de manera asíncrona

  def getA: Future[Int] = ...
  def error(msg: String): Future[Nothing] =
    Future.failed(new RuntimeException(msg))

  for {
    a <- getA
    b <- if (a <= 0) error(s"$a must be positive")
         else Future.successful(a)
  } yield b * 10

Pero si deseamos terminar temprano con un valor de retorno exitoso, el código síncrono simple:

  def getB: Int = ...

  val a = getA
  if (a <= 0) 0
  else a * getB

se traduce a for comprehension anidados cuando nuestras dependencias son asíncronas:

  def getB: Future[Int] = ...

  for {
    a <- getA
    c <- if (a <= 0) Future.successful(0)
         else for { b <- getB } yield a * b
  } yield c

2.4 Sin posibilidad de usar for comprehension

El contexto que sobre el que estamos haciendo la for comprehension debe ser el mismo: no es posible mezclar contextos.

  scala> def option: Option[Int] = ...
  scala> def future: Future[Int] = ...
  scala> for {
           a <- option
           b <- future
         } yield a * b
  <console>:23: error: type mismatch;
   found   : Future[Int]
   required: Option[?]
           b <- future
                ^

Nada puede ayudarnos a mezclar contextos arbitrarios en una for comprehension porque el significado no está bien definido.

Cuando tenemos contextos anidados la intención es normalmente obvia, pero sin embargo, el compilador no aceptará nuestro código.

  scala> def getA: Future[Option[Int]] = ...
  scala> def getB: Future[Option[Int]] = ...
  scala> for {
           a <- getA
           b <- getB
         } yield a * b
                   ^
  <console>:30: error: value * is not a member of Option[Int]

Aquí deseamos que for se ocupe del contexto externo y nos deje escribir nuestro código en el Option interno. Esconder el contexto externo es exactamente lo que hace un transformador de mónadas, y Scalaz proporciona implementaciones para Option y Either llamadas OptionT y EitherT respectivamente.

El contexto externo puede ser cualquier cosa que normalmente funcione en una for comprehension, pero necesita ser el mismo a través de toda la comprehension.

Aquí creamos un OptionT por cada invocación de método. Esto cambia el contexto del for de un Future[Option[_]] a OptionT[Future, _].

  scala> val result = for {
           a <- OptionT(getA)
           b <- OptionT(getB)
         } yield a * b
  result: OptionT[Future, Int] = OptionT(Future(<not completed>))

.run nos devuelve el contexto original.

  scala> result.run
  res: Future[Option[Int]] = Future(<not completed>)

El transformador de mónadas también nos permite mezclar invocaciones a Future[Option[_]] con métodos que simplemente devuelven Future mediante el uso de .liftM[OptionT] (proporcionado por Scalaz):

  scala> def getC: Future[Int] = ...
  scala> val result = for {
           a <- OptionT(getA)
           b <- OptionT(getB)
           c <- getC.liftM[OptionT]
         } yield a * b / c
  result: OptionT[Future, Int] = OptionT(Future(<not completed>))

y así podemos mezclar métodos que devuelven un Option simple al envolverlos en un Future.successful (.pure[Future]) seguido de un OptionT

  scala> def getD: Option[Int] = ...
  scala> val result = for {
           a <- OptionT(getA)
           b <- OptionT(getB)
           c <- getC.liftM[OptionT]
           d <- OptionT(getD.pure[Future])
         } yield (a * b) / (c * d)
  result: OptionT[Future, Int] = OptionT(Future(<not completed>))

De nuevo, el código es algo enmarañado, pero es mejor que escribir flatMap y map anidados manualmente. Podríamos limpiarlo un poco con un Domain Specific Language (DSL) que se encargue de todas las conversiones a OptionT[Future, _] que sean necesarias

  def liftFutureOption[A](f: Future[Option[A]]) = OptionT(f)
  def liftFuture[A](f: Future[A]) = f.liftM[OptionT]
  def liftOption[A](o: Option[A]) = OptionT(o.pure[Future])
  def lift[A](a: A)               = liftOption(Option(a))

combinados con el operador |>, que aplica la función de la derecha al valor a la izquierda, para separar visualmente la lógica de los transformadores

  scala> val result = for {
           a <- getA       |> liftFutureOption
           b <- getB       |> liftFutureOption
           c <- getC       |> liftFuture
           d <- getD       |> liftOption
           e <- 10         |> lift
         } yield e * (a * b) / (c * d)
  result: OptionT[Future, Int] = OptionT(Future(<not completed>))

Este enfoque también funciona para EitherT (y otros) como el contexto interno, pero sus métodos para hacer lifting som más complejos y requieren parámetros. Scalaz proporciona transformadores de mónadas para muchos de sus propios tipos, de modo que vale la pena verificar si hay alguno disponible.

3. Diseño de aplicaciones

En este capítulo escribiremos la lógica de negocio y las pruebas para una aplicación de servidor puramente funcional. El código fuente para esta aplicación se incluye bajo el directorio example junto con la fuente del libro, aunque se recomienda no leer el código fuente hasta el final del capítulo porque habrá refactorizaciones significativas a medida que aprendamos más sobre la programación funcional.

3.1 Especificación

Nuestra aplicación administrará una granja de compilación just-in-time (justo a tiempo) con un presupuesto limitado. Escuchará al servidor de integración continua Drone, y creará agentes trabajadores usando Google Container Engine (GKE) para lograr las demandas de la cola de trabajo.

El drone recibe trabajo cuando un contribuidor manda un pull request de github a uno de los proyectos administrados. El dron asigna el trabajo a sus agentes, cada uno procesando una actividad a la vez.

La meta de nuestra aplicación es asegurar que hay suficientes agentes para completar el trabajo, con un límite de capacidad para el número de agentes, a la vez que se minimiza el costo total. Nuestra aplicación necesita conocer el número de artículos en el backlog y el número disponible de agentes.

Google puede crear nodos, y cada uno puede hospedar múltiples agentes de dron. Cuando un agente inicia, se registra a sí mismo con un dron y el dron se encarga del ciclo de vida (incluyendo las invocaciones de supervivencia para detectar los agentes removidos).

GKE cobra una cuota por minuto de tiempo de actividad, redondeado (hacia arriba) al la hora más cercana para cada nodo. No se trata de simplemente crear un nuevo nodo por cada trabajo en la cola de actividades, debemos reusar nodos y retenerlos haste su minuto # 58 para obtener el mayor valor por el dinero.

Nuestra aplicación necesita ser capaz de empezar y detener nodos, así como verificar su estatus (por ejemplo, los tiempos de actividad, y una lista de los nodos inactivos) y conocer qué tiempos GKE piensa que debe haber.

Además, no hay una API para hablar directamente con un agente de modo que no sabemos si alguno de los agentes individuales está realizando algún trabajo para el servidor de drones. Si accidentalmente detenemos un agente mientras está realizando trabajo, es inconveniente y requiere que un humano reinicie el trabajo.

Los contribuidores pueden añadir agentes manualmente a la granja, de modo que contar agentes y nodos no es equivalente. No es necesario proporcionar algún nodo si hay agentes disponibles.

El modo de falla siempre debería tomar al menos la opción menos costosa.

Tanto Drone como GKE tienen una interfaz JSON sobre una API REST con autenticación OAuth 2.0.

3.2 Interfaces / Algebras

Ahora codificaremos el diagrama de arquitectura de la sección previa. Primeramente, necesitamos definir un tipo de datos simple para almacenar un momento (tiempo) en milisegundos porque este concepto simple no existe ni en la librería estándar de Java ni en la de Scala:

  import scala.concurrent.duration._

  final case class Epoch(millis: Long) extends AnyVal {
    def +(d: FiniteDuration): Epoch = Epoch(millis + d.toMillis)
    def -(e: Epoch): FiniteDuration = (millis - e.millis).millis
  }

En PF, una álgebra toma el lugar de una interface en Java, o el conjunto de mensajes válidos para un Actor de Akka. Esta es la capa donde definimos todas las interacciones colaterales de nuestro sistema.

Existe una interacción estrecha entre la escritura de la lógica de negocio y su álgebra: es un buen nivel de abstracción para diseñar un sistema.

  trait Drone[F[_]] {
    def getBacklog: F[Int]
    def getAgents: F[Int]
  }

  final case class MachineNode(id: String)
  trait Machines[F[_]] {
    def getTime: F[Epoch]
    def getManaged: F[NonEmptyList[MachineNode]]
    def getAlive: F[Map[MachineNode, Epoch]]
    def start(node: MachineNode): F[MachineNode]
    def stop(node: MachineNode): F[MachineNode]
  }

Ya hemos usado NonEmptyList, creado fácilmente mediante la invocación de .toNel sobre un objecto List de la librería estándar (que devuelve un Option[NonEmptyList]), y el resto debería resultar familiar.

3.3 Lógica de negocios

Ahora escribiremos la lógica de negocios que define el comportamiento de la aplicación, considerando únicamente la situación más positiva.

Necesitamos una clase WorldView para mantener una instantánea de nuestro conocimiento del mundo. Si estuvieramos diseñando esta aplicación en Akka, WorldView probablemente sería un var en un Actor con estado.

WorldView acumula los valores de retorno de todos los métodos en las álgebras, y agrega un campo pendiente (pending) para darle seguimiento a peticiones que no han sido satisfechas.

  final case class WorldView(
    backlog: Int,
    agents: Int,
    managed: NonEmptyList[MachineNode],
    alive: Map[MachineNode, Epoch],
    pending: Map[MachineNode, Epoch],
    time: Epoch
  )

Ahora estamos listos para escribir nuestra lógica de negocio, pero necesitamos indicar que dependemos de Droney de Machines.

Podemos escribir la interfaz para nuestra lógica de negocio

  trait DynAgents[F[_]] {
    def initial: F[WorldView]
    def update(old: WorldView): F[WorldView]
    def act(world: WorldView): F[WorldView]
  }

e implementarla con un módulo. Un módulo depende únicamente de otros módulos, álgebras y funciones puras, y puede ser abstraída sobre F. Si una implementación de una interfaz algebraica está acoplada a cierto tipo específico, por ejemplo, IO, se llama un intérprete.

  final class DynAgentsModule[F[_]: Monad](D: Drone[F], M: Machines[F])
    extends DynAgents[F] {

El límite de contexto Monad significa que F es monádico, permitiéndonos usar map, pure y, por supuesto, flatMap por medio de for comprehensions.

Requerimos acceso al álgebra de Drone y Machines como D y M, respectivamente. El uso de una sola letra mayúscula para el nombre es una convención de nombre común para las implementaciones de mónadas y álgebras.

Nuestra lógica de negocio se ejecutará en un ciclo infinito (pseudocódigo)

  state = initial()
  while True:
    state = update(state)
    state = act(state)

3.3.1 initial

En initial llamamos a todos los servicios externos y acumulamos sus resultados en un WorldView. Por default se asigna el campo pending a un Map vacío.

  def initial: F[WorldView] = for {
    db <- D.getBacklog
    da <- D.getAgents
    mm <- M.getManaged
    ma <- M.getAlive
    mt <- M.getTime
  } yield WorldView(db, da, mm, ma, Map.empty, mt)

Recuerde del Capítulo 1 que flatMap (es decir, cuando usamos el generador <-) nos permite operar sobre un valor que se calcula en tiempo de ejecución. Cuando devolvemos un F[_] devolvemos otro programa que será interpretado en tiempo de ejecución, sobre el cual podemos a continuación invocar flatMap. Es de esta manera como encadenamos secuencialmente código con efectos colaterales, al mismo tiempo que somos capaces de proporcionar una implementación pura para las pruebas. PF podría ser descrita como Extreme Mocking.

3.3.2 update

update debería llamar a initial para refrescar nuestra visión del mundo, preservando acciones pending conocidas.

Si un nodo ha cambiado su estado, la quitamos de pending y si una acción pendiente está tomando más de 10 minutos para lograr algo, asumimos que ha fallado y olvidamos que se solicitó trabajo al mismo.

  def update(old: WorldView): F[WorldView] = for {
    snap <- initial
    changed = symdiff(old.alive.keySet, snap.alive.keySet)
    pending = (old.pending -- changed).filterNot {
      case (_, started) => (snap.time - started) >= 10.minutes
    }
    update = snap.copy(pending = pending)
  } yield update

  private def symdiff[T](a: Set[T], b: Set[T]): Set[T] =
    (a union b) -- (a intersect b)

Funciones concretas como .symdiff no requieren intérpretes de prueba, tienen entradas y salidas explícitas, de modo que podríamos mover todo el código puro a métodos autónomos en un object sin estado, que se puede probar en aislamiento. Estamos conformes con probar únicamente los métodos públicos, prefiriendo que nuestra lógica de negocios sea fácil de leer.

3.3.3 act

El método act es ligeramente más complejo, de modo que lo dividiremos en dos partes por claridad: la detección de cúando es necesario tomar una acción, seguida de la ejecución de la acción. Esta simplificación significa que únicamente podemos realizar una acción por invocación, pero esto es razonable porque podemos controlar las invocaciones y podemos escoger ejecutar nuevamente act hasta que no se tome acción alguna.

Escribiremos los detectores de los diferentes escenarios como extractores para WorldView, los cuáles no son más que formas expresivas de escribir condiciones if / else.

Necesitamos agregar agentes a la granja si existe una lista de trabajo pendiente (backlog), no tenemos agentes, no tenemos nodos vivos, y no hay acciones pendientes. Regresamos un nodo candidato que nos gustaría iniciar:

  private object NeedsAgent {
    def unapply(world: WorldView): Option[MachineNode] = world match {
      case WorldView(backlog, 0, managed, alive, pending, _)
           if backlog > 0 && alive.isEmpty && pending.isEmpty
             => Option(managed.head)
      case _ => None
    }
  }

Si no hay backlog, deberíamos detener todos los nodos que están detenidos (no están haciendo ningún trabajo). Sin embargo, dado que Google cobra por hora nosotros únicamente apagamos las máquinas en su minuto 58, para obtener el máximo de nuestro dinero. Devolvemos una lista no vacía de los nodos que hay que detener.

Como una red de seguridad financiera, todos los nodos deben tener un tiempo de vida máximo de 5 horas.

  private object Stale {
    def unapply(world: WorldView): Option[NonEmptyList[MachineNode]] = world match {
      case WorldView(backlog, _, _, alive, pending, time) if alive.nonEmpty =>
        (alive -- pending.keys).collect {
          case (n, started) if backlog == 0 && (time - started).toMinutes % 60 >= 58 => n
          case (n, started) if (time - started) >= 5.hours => n
        }.toList.toNel

      case _ => None
    }
  }

Ahora que hemos detectado los escenario que pueden ocurrir, podemos escribir el método act. Cuando se planea que un nodo se inicie o se detenga, lo agregamos a pending tomando nota del tiempo en el que se programó la acción.

  def act(world: WorldView): F[WorldView] = world match {
    case NeedsAgent(node) =>
      for {
        _ <- M.start(node)
        update = world.copy(pending = Map(node -> world.time))
      } yield update

    case Stale(nodes) =>
      nodes.foldLeftM(world) { (world, n) =>
        for {
          _ <- M.stop(n)
          update = world.copy(pending = world.pending + (n -> world.time))
        } yield update
      }

    case _ => world.pure[F]
  }

Dado que NeedsAgent y Stale no cubren todas las situaciones posibles, requerimos de un case _ que atrape todas las situaciones posibles restantes, y que no haga nada. Recuerde del Capítulo 2 que .pure crea el contexto monádico del for a partir de un valor.

foldLeftM es como foldLeft, pero cada iteración de un fold puede devolver un valor monádico. En nuestro caso, cada iteración del fold devuelve F[WorldView]. El M es por Monádico. Nos encontraremos con más de estos métodos lifted (alzados) que se comportan como uno esperaría, tomando valores monádicos en lugar de valores.

3.4 Unit Tests

El enfoque de FP de escribir aplicaciones es el sueño de un diseñador: delegar la escritura de las implementaciones algebraicas a otros miembros del equipo mientras que se enfoca en lograr que la lógica de negocios cumpla con los requerimientos.

Nuestra aplicación es altamente dependiente de la temporización y de los servicios web de terceros. Si esta fuera una aplicación POO tradicional, crearíamos mocks para todas las invocaciones de métodos, o probaríamos los buzones de salida de los actores. El mocking en PF es equivalente a proporcionar implementaciones alternativas de las álgebras dependientes. Las álgebras ya aislan las partes del sistema que necesitan tener un mock, por ejemplo, interpretándolas de manera distinta en las pruebas unitarias.

Empezaremos con algunos datos de prueba

  object Data {
    val node1   = MachineNode("1243d1af-828f-4ba3-9fc0-a19d86852b5a")
    val node2   = MachineNode("550c4943-229e-47b0-b6be-3d686c5f013f")
    val managed = NonEmptyList(node1, node2)

    val time1: Epoch = epoch"2017-03-03T18:07:00Z"
    val time2: Epoch = epoch"2017-03-03T18:59:00Z" // +52 mins
    val time3: Epoch = epoch"2017-03-03T19:06:00Z" // +59 mins
    val time4: Epoch = epoch"2017-03-03T23:07:00Z" // +5 hours

    val needsAgents = WorldView(5, 0, managed, Map.empty, Map.empty, time1)
  }
  import Data._

Implementamos algebras al extender Drone y Machines con un contexto monádico específico, siendo Id el más simple.

Nuestras implementaciones mock simplemente repiten un WorldView fijo. Ya hemos aislado el estado de nuestro sistema, de modo que podemos usar var para almacenar el estado:

  class Mutable(state: WorldView) {
    var started, stopped: Int = 0

    private val D: Drone[Id] = new Drone[Id] {
      def getBacklog: Int = state.backlog
      def getAgents: Int = state.agents
    }

    private val M: Machines[Id] = new Machines[Id] {
      def getAlive: Map[MachineNode, Epoch] = state.alive
      def getManaged: NonEmptyList[MachineNode] = state.managed
      def getTime: Epoch = state.time
      def start(node: MachineNode): MachineNode = { started += 1 ; node }
      def stop(node: MachineNode): MachineNode = { stopped += 1 ; node }
    }

    val program = new DynAgentsModule[Id](D, M)
  }

Cuando escribimos una prueba unitaria (aquí usando FlatSpec desde ScalaTest), creamos una instancia de Mutable y entonces importamos todos sus miembros.

Tanto nuestro drone y machine implícitos usan el contexto de ejecución Id y por lo tanto interpretar este programa con ellos devuelve un Id[WorldView] sobre el cual podemos hacer aserciones.

En este caso trivial simplemente verificamos que el método initial devuelva el mismo valor que usamos en nuestras implementaciones estáticas:

  "Business Logic" should "generate an initial world view" in {
    val mutable = new Mutable(needsAgents)
    import mutable._

    program.initial shouldBe needsAgents
  }

Entonces podemos crear pruebas más avanzadas de los métodos update y act, ayudándonos a eliminar bugs y refinar los requerimientos:

  it should "remove changed nodes from pending" in {
    val world = WorldView(0, 0, managed, Map(node1 -> time3), Map.empty, time3)
    val mutable = new Mutable(world)
    import mutable._

    val old = world.copy(alive = Map.empty,
                         pending = Map(node1 -> time2),
                         time = time2)
    program.update(old) shouldBe world
  }

  it should "request agents when needed" in {
    val mutable = new Mutable(needsAgents)
    import mutable._

    val expected = needsAgents.copy(
      pending = Map(node1 -> time1)
    )

    program.act(needsAgents) shouldBe expected

    mutable.stopped shouldBe 0
    mutable.started shouldBe 1
  }

Sería aburrido ejecutar el conjunto de pruebas completo. Las siguientes pruebas serían fáciles de implementar usando el mismo enfoque:

  • No solicitar agentes cuando haya pendientes
  • No apagar los agentes si los nodos son muy jóvenes
  • Apagar los agentes cuando no hay backlog y los nodos ocasionarán costos pronto
  • No apague a los agentes si hay acciones pendientes
  • Apague a los agentes cuando no hay backlog si son muy viejos
  • Apague a los agentes, incluso si potencialmente están haciendo trabajo, si son muy viejos
  • Ignore las acciones pendientes que no responden durante las actualizaciones

Todas estas pruebas son síncronas y aisladas al hilo de ejecutor de prueba (que podría estar ejecutando pruebas en paralelo). Si hubieramos diseñado nuestro conjunto de pruebas en Akka, nuestras pruebas estarían sujetas a tiempos de espera arbitrarias y las fallas estarían ocultas en los archivos de registro.

El disparo en la productividad de las pruebas simples para la lógica de negocios no puede ser exagerada. Considere que el 90% del tiempo ocupado por el desarrollador de aplicaciones usado en la interacción con el cliente está en la refinación, actualización y fijación de estas reglas de negocios. Todo lo demás es un detalle de implementación.

3.5 Paralelismo

La aplicación que hemos diseñado ejecuta cada uno de sus métodos algebraicos secuencialmente. Pero hay algunos lugares obvios donde el trabajo puede ejecutarse en paralelo.

3.5.1 initial

En nuestra definición de initial podríamos solicitar toda la información que requerimos a la vez en lugar de hacer una consulta a la vez.

En contraste con flatMap para operaciones secuenciales, Scalaz usa la sintaxis Apply para operaciones paralelas:

  ^^^^(D.getBacklog, D.getAgents, M.getManaged, M.getAlive, M.getTime)

y también puede usar notación infija:

  (D.getBacklog |@| D.getAgents |@| M.getManaged |@| M.getAlive |@| M.getTime)

Si cada una de las operaciones paralelas regresa un valor en el mismo contexto monádico, podemos aplicar una función a los resultados cuando todos ellos sean devueltos. Reescribiendo initial para tomar ventaja de esto:

  def initial: F[WorldView] =
    ^^^^(D.getBacklog, D.getAgents, M.getManaged, M.getAlive, M.getTime) {
      case (db, da, mm, ma, mt) => WorldView(db, da, mm, ma, Map.empty, mt)
    }

3.5.2 act

En la lógica actual para act, estamos deteniéndonos en cada nodo secuencialmente, esperando por el resultado, y entonces procediendo. Pero podríamos detener todos los nodos en paralelo y entonces actualizar nuestra vista del mundo.

Una desventaja de hacerlo de esta manera es que cualquier falla ocasionará que se paren los cómputos antes de actualizar el campo pending. Pero se trata de una concesión razonable dado que nuestra función update manejará el caso cuando un node se apague inesperadamente.

Necesitamos un método que funcione en NonEmptyList que nos permita hacer un map sobre cada elemento en un F[MachineNode], devolviendo un F[NonEmptyList[MachineNode]]. El método se llama traverse, y cuando invoquemos un flatMap sobre este tendremos un NonEmptyList[MachineNode] con el cuál lidiaremos de una manera sencilla:

  for {
    stopped <- nodes.traverse(M.stop)
    updates = stopped.map(_ -> world.time).toList.toMap
    update = world.copy(pending = world.pending ++ updates)
  } yield update

Podría argumentarse, que este código es más fácil de entender que la versión secuencial.

3.6 Summary

  1. Las algebras definen las interfaces entre sistemas.
  2. Los módulos son implementaciones de un álgebra en términos de otras álgebras.
  3. Los intérpretes son implementaciones concretas de un álgebra para una F[_] fija.
  4. Los intérpretes de prueba pueden reemplazar las partes con efectos colaterales de un sistema, proporcionando un grado elevado de cobertura de las pruebas.

4. Datos y funcionalidad

De la POO estamos acostumbrados a pensar en datos y funcionalidad a la vez: las jerarquías de clases llevan métodos, y mediante el uso de traits podemos demandar que existan campos de datos. El polimorfismo en tiempo de ejecución se da en términos de relaciones “is a” (“es un”), requiriendo que las clases hereden de interfaces comunes. Esto puede llegar a complicarse a medida que la base de código crece. Los tipos de datos simples se vuelven obscuros al complicarse con cientos de líneas de métodos, los mixins con traits sufren a causa del orden de inicialización, y las pruebas y mocking de componentes altamente acoplados se convierte en una carga.

La PF toma un enfoque distinto, definiendo los datos y la funcionalidad de manera separada. En este capítulo, se estudiará lo básico de los tipos de datos y las ventajas de restringirnos a un subconjunto del lenguaje de programación Scala. También descubriremos las typeclasses como una forma de lograr polimorfismo en tiempo de compilación: pensando en la funcionalidad de una estructura de datos en términos de “has a” (“tiene un”), más bien que relaciones del tipo “es un”.

4.1 Datos

Los bloques de construcción fundamentales de los tipos son

  • final case class también conocidos como productos
  • sealed abstract class también conocidos como coproductos
  • case object e Int, Double, String, (etc.), valores.

sin métodos o campos más que los parámetros del constructor. Preferimos usar abstract class a trait para lograr mejor compatibilidad binaria y para evitar la mezcla de traits.

El nombre colectivo para productos, coproductos y valores es Tipo de Datos Algebraico (del inglés Algebraic Data Type o ADT).

Formamos la composición de tipos de datos a partir de AND y XOR (OR exclusivos) del álgebra booleana: un producto contiene cada uno de los tipos de los que está compuesto, pero un coproducto puede ser únicamente uno de ellos. Por ejemplo

  • producto: ABC = a AND b AND c
  • coproducto: XYZ = x XOR y XOR z

escrito en Scala

  // values
  case object A
  type B = String
  type C = Int

  // product
  final case class ABC(a: A.type, b: B, c: C)

  // coproduct
  sealed abstract class XYZ
  case object X extends XYZ
  case object Y extends XYZ
  final case class Z(b: B) extends XYZ

4.1.1 Estructuras de datos recursivas

Cuando un ADT se refiere a sí misma, la llamamos Tipo de Datos Algebraico Recursivo.

scalaz.IList, una alternativa segura a List de la librería estándar, es recursiva porque ICons contiene una referencia a IList.:

  sealed abstract class IList[A]
  final case class INil[A]() extends IList[A]
  final case class ICons[A](head: A, tail: IList[A]) extends IList[A]

4.1.2 Funciones sobre ADTs

Las ADTs pueden tener funciones puras

  final case class UserConfiguration(accepts: Int => Boolean)

Pero las ADTs que contienen funciones tienen consigo algunas limitaciones dado que no se pueden traducir de manera perfecta a la JVM. Por ejemplo, los antiguos métodos Serializable, hashCode, equals y toString no se comportan como uno podría razonablemente esperar.

Desgraciadamente, Serializable es usado por frameworks populares, a pesar de que existen alternativas superiores. Una trampa común es olvidar que Serializable podría intentar serializar la cerradura completa de una función, lo que podría ocasionar el fallo total de servidores de producción. Una trampa similar aplica a clases de Java antiguas tales como Throwable, que pueden llevar consigo referencias a objetos arbitrarios.

Exploraremos alternativas a los métodos antiguos cuando discutamos Scalaz en el próximo capítulo, a costa de perder interoperabilidad con algo de código antiguo de Java y Scala.

4.1.3 Exhaustividad

Es importante que usemos sealed abstract class, no simplemente abstract class, cuando definimos un tipo de datos. Sellar una class significa que todos los subtipos deben estar definidos en el mismo archivo, permitiendo que el compilador pueda verificar de manera exhaustiva durante el proceso de empate de patrones y en macros que eliminen el código repetitivo. Por ejemplo,

  scala> sealed abstract class Foo
         final case class Bar(flag: Boolean) extends Foo
         final case object Baz extends Foo

  scala> def thing(foo: Foo) = foo match {
           case Bar(_) => true
         }
  <console>:14: error: match may not be exhaustive.
  It would fail on the following input: Baz
         def thing(foo: Foo) = foo match {
                               ^

Esto muestra al desarrollador qué ha fallado cuando añaden un nuevo producto a la base de código. Aquí se está usando -Xfatal-warnings, porque de otra manera esto es solamente un warning o advertencia.

Sin embargo, el compilador no realizará un chequeo exhaustivo si la clase no está sellada o si existen guardas, por ejemplo

  scala> def thing(foo: Foo) = foo match {
           case Bar(flag) if flag => true
         }

  scala> thing(Baz)
  scala.MatchError: Baz (of class Baz$)
    at .thing(<console>:15)

para conseguir seguridad, es mejor evitar las guardas en los tipos sellados.

La bandera -Xstrict-patmat-analysis se ha propuesto como una mejora al lenguaje para realizar chequeos adicionales durante el proceso de empate de patrones.

4.1.4 Productos alternativos y coproductos

Otra forma de producto es la tupla, que es como una final case class sin etiqueta o nombre.

(A.type, B, C) es equivalente a ABC en el ejemplo de arriba, pero es mejor usar final case class cuando se trate de una parte de alguna ADT porque es algo difícil lidiar con la falta de nombres, y case class tiene mucho mejor performance para valores primitivos.

Otra forma de coproducto es aquella que se logra al anidar tipos Either, por ejemplo

  Either[X.type, Either[Y.type, Z]]

y es equivalente a la clase abstracta sellada XYZ. Se puede lograr una sintáxis más limpia al definir tipos Either anidados al crear un alias de tipo que termine en dos puntos, permitiendo así el uso de notación infija con asociación hacia la derecha:

  type |:[L,R] = Either[L, R]

  X.type |: Y.type |: Z

Esto es útil al crear coproductos anónimos cuando no podemos poner todas las implementaciones en el mismo archivo de código fuente.

  type Accepted = String |: Long |: Boolean

Otra forma de coproducto alternativa es creat un sealed abstract class especial con definiciones final case class que simplemente envuelvan a los tipos deseados:

  sealed abstract class Accepted
  final case class AcceptedString(value: String) extends Accepted
  final case class AcceptedLong(value: Long) extends Accepted
  final case class AcceptedBoolean(value: Boolean) extends Accepted

El empate de patrones en estas formas de coproducto puede ser tediosa, razón por la cual los tipos Unión están explorandose en la siguiente generación del compilador de Scala, Dotty. Macros tales como totalitarian y iotaz existen como formas alternativas de codificar coproductos anónimos.

4.1.5 Transmisión de información

Además de ser contenedores para información de negocios necesaria, los tipos de datos pueden usarse para codificar restricciones. Por ejemplo,

  final case class NonEmptyList[A](head: A, tail: IList[A])

nunca puede estar vacía. Esto hace que scalaz.NonEmptyList sea un tipo de datos útil a pesar de que contiene la misma información que IList.

Los tipos producto con frecuencia contienen tipos que son mucho más generales de lo que en realidad se requiere. En programación orientada a objetos tradicional, la situación se manejaría con validación de datos de entrada a través de aserciones:

  final case class Person(name: String, age: Int) {
    require(name.nonEmpty && age > 0) // breaks Totality, don't do this!
  }

En lugar de hacer esto, podríamos usar el tipo de datos Either para proporcionar Right[Person] para instancias válidas y protegernos de que instancias inválidas se propaguen. Note que el constructor es privado (private):

  final case class Person private(name: String, age: Int)
  object Person {
    def apply(name: String, age: Int): Either[String, Person] = {
      if (name.nonEmpty && age > 0) Right(new Person(name, age))
      else Left(s"bad input: $name, $age")
    }
  }

  def welcome(person: Person): String =
    s"${person.name} you look wonderful at ${person.age}!"

  for {
    person <- Person("", -1)
  } yield welcome(person)
4.1.5.1 Tipos de datos refinados

Una forma limpia de restringir los valores de un tipo general es con la librería refined, que provee una conjunto de restricciones al contenido de los datos. Para instalar refined, agregue la siguiente línea a su archivo build.sbt

  libraryDependencies += "eu.timepit" %% "refined-scalaz" % "0.9.2"

y los siguientes imports

  import eu.timepit.refined
  import refined.api.Refined

Refined permite definir Person usando tipos ad hoc refinados para capturar los requerimientos de manera exacta, escrito A Refined B.

  import refined.numeric.Positive
  import refined.collection.NonEmpty

  final case class Person(
    name: String Refined NonEmpty,
    age: Int Refined Positive
  )

El valor subyacente puede obtenerse con .value. Podemos construir un valor en tiempo de ejecución usando .refineV, que devuelve un Either

  scala> import refined.refineV
  scala> refineV[NonEmpty]("")
  Left(Predicate isEmpty() did not fail.)

  scala> refineV[NonEmpty]("Sam")
  Right(Sam)

Si agregamos el siguiente import

  import refined.auto._

podemos construir valores válidos en tiempo de compilación y obtener errores si el valor provisto no cumple con los requerimientos

  scala> val sam: String Refined NonEmpty = "Sam"
  Sam

  scala> val empty: String Refined NonEmpty = ""
  <console>:21: error: Predicate isEmpty() did not fail.

Es posible codificar requerimientos más completos, por ejemplo podríamos usar la regla MaxSize que con los siguientes imports

  import refined.W
  import refined.boolean.And
  import refined.collection.MaxSize

que captura los requerimientos de que String debe no ser vacía y además tener un máximo de 10 caracteres.

  type Name = NonEmpty And MaxSize[W.`10`.T]

  final case class Person(
    name: String Refined Name,
    age: Int Refined Positive
  )

Es fácil definir requerimientos a la medida que no estén cubiertos por la librería refined. Por ejemplo en drone-dynamic-agents necesitaremos una manera de asegurarnos de que String tenga contenido application/x-www-form-urlencoded. Podríamos crear una regla de Refined usando la librería de expresiones regulares de Java:

  sealed abstract class UrlEncoded
  object UrlEncoded {
    private[this] val valid: Pattern =
      Pattern.compile("\\A(\\p{Alnum}++|[-.*_+=&]++|%\\p{XDigit}{2})*\\z")

    implicit def urlValidate: Validate.Plain[String, UrlEncoded] =
      Validate.fromPredicate(
        s => valid.matcher(s).find(),
        identity,
        new UrlEncoded {}
      )
  }

4.1.6 Simple de compartir

Al no proporcionar ninguna funcionalidad, las ADTs pueden tener un conjunto mínimo de dependencias. Esto hace que sean fáciles de publicar y de compartir con otros desarrolladores. Al usar un lenguaje de modelado de datos simple, se hace posible la interacción con equipos interdisciplinarios, tales como DBAs, desarrolladores de interfaces de usuario y analistas de negocios, usando el código fuente actual en lugar de un documento escrito manualmente como la fuente de la verdad.

Más aún, las herramientas pueden ser escritas más fácilmente para producir o consumir esquemas de otros lenguajes de programación y protocolos físicos.

4.1.7 Contando la complejidad

La complejidad de un tipo de datos es la cuenta de los valores que puede tener. Un buen tipo de datos tiene la cantidad mínima de complejidad requerida para contener la información que transmite, y nada más.

Los valores tienen una complejidad inherente:

  • Unit tien un solo valor (razón por la cual se llama “unit”)
  • Boolean tiene dos valores
  • Int tiene 4,294,967,295 valores
  • String tiene valores infinitos, de manera práctica

Para encontrar la complejidad de un producto, multiplicamos la complejidad de cada parte

  • (Boolean, Boolean) tiene 4 valores, (2 * 2)
  • (Boolean, Boolean, Boolean) tiene 8 valores (2 * 2 * 2)

Para encontrar la complejidad de un coproducto, sumamos la complejidad de cada parte

  • (Boolean |: Boolean) tiene 4 valores (2 + 2)
  • (Boolean |: Boolean |: Boolean) tiene 6 valores (2 + 2 + 2)

Para encontrar la complejidad de un ADT con un parámetro de tipo, multiplique cada parte por la complejidad del parámetro de tipo:

  • Option[Boolean] tiene 3 valores, Some[Boolean] y None. (2 + 1).

En la PF, las funciones son totales y deben devolver el mismo valor para cada entrada, no una Exception. Minimizar la complejidad de las entradas y las salidas es la mejor forma de lograr totalidad. Como regla de oro, es un signo de una función con mal dise;o cuando la complejidad del valor de retorno es más grande que el producto de sus entradas: es una fuente de entropía.

La complejidad de una función total es el número de funciones posibles que pueden satisfacer la signatura del tipo: la salida a la potencia de la entrada.

  • Unit => Boolean tiene complejidad 2
  • Boolean => Boolean tiene complejidad 4
  • Option[Boolean] => Option[Boolean] tiene complejidad 27
  • Boolean => Int es como un quintillón, aproximándose a un sextillón.
  • Int => Boolean es tan grande que si a todas las implementaciones se les asignara un número único, cada una requeriría 4 gigabytes para representarla.

En la práctica, Int => Boolean será algo tan simple como isOdd, isEven o un BitSet disperso. Esta función, cuando se usa en una ADT, será mejor reemplazarla con un coproducto que asigne un nombre al conjunto de funciones que son relevantes.

Cuando la complejidad es “infinito a la entrada, infinito a la salida” deberíamos introducir tipos de datos que restrictivos y validaciones más cercanos al punto de entrada con Refined de la sección anterior.

La habilidad de contar la complejidad de una signatura de tipo tiene otra aplicación práctica: podemos encontrar signaturas de tipo más simples usando Álgebra de la secundaria! Para ir de una signatura de tipos al álgebra de las complejidades, simplemente reemplace

  • Either[A, B] con a + b
  • (A, B) con a * b
  • A => B con b ^ a

hacer algunos rearreglos, y convertir de vuelta. Por ejemplo, digamos que hemos diseñado un framework basado en callbacks y que hemos logrado llegar a la situación donde tenemos la siguiente signatura de tipos:

  (A => C) => ((B => C) => C)

Podríamos convertir y reordenar

  (c ^ (c ^ b)) ^ (c ^ a)
  = c ^ ((c ^ b) * (c ^ a))
  = c ^ (c ^ (a + b))

y convertir de vuelta a tipos y obtener

  (Either[A, B] => C) => C

que es mucho más simple: sólo es necesario pedir a los usuarios de nuestro framework que proporcionen un Either[A, B] => C.

La misma línea de razonamiento puede ser usada para probar que

  A => B => C

es equivalente a

  (A, B) => C

que también se conoce como Currying.

4.1.8 Prefiera coproducto en vez de producto

Un problema de modelado típico que surge con frecuencia es el que tenemos cuando hay parámetros de configuración mutuamente exclusivos a, b, y c. El producto (a: Boolean, b: Boolean, c: Boolean) tiene complejidad 8, mientras que el coproducto

  sealed abstract class Config
  object Config {
    case object A extends Config
    case object B extends Config
    case object C extends Config
  }

tiene una complejidad de 3. Es mejor modelar estos parámetros de configuración como un coproducto más bien que permitir la existencia de 5 estados inválidos.

La complejidad de un tipo de datos también tiene implicaciones a la hora de hacer pruebas. Es prácticamente imposible probar cada entrada a una función, pero es fácil probar una muestra de los valores con el framework para hacer pruebas de propiedades con Scalacheck.

Si una muestra aleatoria de un tipo de datos tiene una probabilidad baja de ser válida, tenemos una señal de que los datos están modelados incorrectamente.

4.1.9 Optimizaciones

Una gran ventaja de usar un conjunto simplificado del lenguaje Scala para representar tipos de datos es que el tooling puede optimizar la representación en bytecodes de la JVM.

Por ejemplo, podríamos empacar campos Boolean y Option en un Array[Byte], hacer un caché con los valores, memoizar hashCode, optimizar equals, usar sentencias @switch al momento de realizar empate de patrones, y mucho más.

Estas optimizaciones no son aplicables a jerarquías de clases en POO que tal vez manipulen el estado, lancen excepciones, o proporcionen implementaciones ad hoc de los métodos.

4.2 Funcionalidad

Las funciones puras están definidas típicamente como métodos en un object.

  package object math {
    def sin(x: Double): Double = java.lang.Math.sin(x)
    ...
  }

  math.sin(1.0)

Sin embargo, el uso de métodos en objects puede ser un poco torpe, dado que se lee de dentro hacia afuera, y no de izquierda a derecha. Además, una función en un object se roba el namespace. Si tuvieramos que definir sin(t: T) en algún otro lugar, tendríamos errores por referencias ambiguas. Este es el mismo problema de los métodos estáticos de Java vs los métodos de clase.

Con ayuda de la característica del lenguaje implicit class, (también conocida como metodología de extensión o sintaxis), y un poco de código tedioso, es posible lograr un estilo más familiar:

  scala> implicit class DoubleOps(x: Double) {
           def sin: Double = math.sin(x)
         }

  scala> (1.0).sin
  res: Double = 0.8414709848078965

Con frecuencia es mejor saltarnos la definición de un object e ir directo con una implicit class, manteniendo el código repetitivo al mínimo:

  implicit class DoubleOps(x: Double) {
    def sin: Double = java.lang.Math.sin(x)
  }

4.2.1 Funciones polimórficas

La clase de funciones más comunes es la función polimórfica, que vive en una typeclass. Una typeclass es un trait que:

  • no tiene estado
  • tiene un parámetro de tipo
  • tiene al menos un método abstracto (combinador primitivo)
  • puede contener métodos generalizadores (combinadores derivados)
  • puede extender a otros typeclases

Sólo puede existir una implementación de una typeclass para un parámetro de tipo específico correspondiente, una propiedad conocida también como coherencia de typeclass. Las typeclasses se ven superficialmente similares a las interfaces algebraicas del capítulo anterior, pero las álgebras no tienen que ser coherentes.

Las typeclasses son usadas en la librería estándar de Scala. Exploraremos una versión simplificada de scala.math.Numeric para demostrar el principio:

  trait Ordering[T] {
    def compare(x: T, y: T): Int

    def lt(x: T, y: T): Boolean = compare(x, y) < 0
    def gt(x: T, y: T): Boolean = compare(x, y) > 0
  }

  trait Numeric[T] extends Ordering[T] {
    def plus(x: T, y: T): T
    def times(x: T, y: T): T
    def negate(x: T): T
    def zero: T

    def abs(x: T): T = if (lt(x, zero)) negate(x) else x
  }

Podemos ver las características clave de una typeclass en acción:

  • no hay estado
  • Ordering y Numeric tienen un parámetro de tipo T
  • Ordering tiene un compare abstracto, y Numeric tiene un plus, times, negate y zero abstractos.
  • Ordering define un lt generalizado, y gt basados en compare, Numeric define abs en términos de lt, negate y zero.
  • Numeric extiende Ordering.

Ahora podemos escribir funciones para tipos que “tengan un(a)” typeclass Numeric:

  def signOfTheTimes[T](t: T)(implicit N: Numeric[T]): T = {
    import N._
    times(negate(abs(t)), t)
  }

Ya no dependemos de la jerarquía POO de nuestros tipos de entrada, es decir, no demandamos que nuestra entrada sea (“is a”) Numeric, lo cual es vitalmente importante si deseamos soportar clases de terceros que no podemos redefinir.

Otra ventaja de las typeclasses es que la asociación de funcionalidad a los datos se da en tiempo de compilación, en oposición del despacho dinámico en tiempo de ejecución de la POO.

Por ejemplo, mientras que la clase List solo puede tener una implementación de un método, una typeclasss nos permite tener diferentes implementaciones dependiendo del contenido de List y por lo tanto nos permite descargar el trabajo al tiempo de compilación en lugar de dejarlo al tiempo de ejecución.

4.2.2 Sintaxis

La sintaxis para escribir signOfTheTimes es un poco torpe, y hay algunas cosas que podemos hacer para limpiarla.

Los usuarios finales de nuestro código, preferirán que nuestro métod use context bounds, dado que la signatura se lee limpiamente como “toma una T que tiene un Numeric

  def signOfTheTimes[T: Numeric](t: T): T = ...

pero ahora tenemos que usar implicitly[Numeric[T]] en todos lados. Al definir el código repetitivo en el companion object de la typeclass

  object Numeric {
    def apply[T](implicit numeric: Numeric[T]): Numeric[T] = numeric
  }

podemos obtener el implícito con menos ruido

  def signOfTheTimes[T: Numeric](t: T): T = {
    val N = Numeric[T]
    import N._
    times(negate(abs(t)), t)
  }

Pero es todavía peor para nosotros como los implementadores. Tenemos el problema sintáctico de métodos estáticos afuera vs métodos de la clase. Una forma de lidiar con esta situación es mediante introducir ops en el companion de la typeclass:

  object Numeric {
    def apply[T](implicit numeric: Numeric[T]): Numeric[T] = numeric

    object ops {
      implicit class NumericOps[T](t: T)(implicit N: Numeric[T]) {
        def +(o: T): T = N.plus(t, o)
        def *(o: T): T = N.times(t, o)
        def unary_-: T = N.negate(t)
        def abs: T = N.abs(t)

        // duplicated from Ordering.ops
        def <(o: T): T = N.lt(t, o)
        def >(o: T): T = N.gt(t, o)
      }
    }
  }

Note que -x se expande a x.unary_- mediante las conveniencias sintácticas del compilador, razón por la cual definimos unary_- como un método de extensión. Podemos ahora escribir la forma mucho más clara:

  import Numeric.ops._
  def signOfTheTimes[T: Numeric](t: T): T = -(t.abs) * t

La buena noticia es que nunca necesitamos escribir este tipo de código repetitivo porque Simulacrum proporciona una anotación @typeclass que genera automáticamente los métodos apply y ops. Incluso nos permite definir nombres alternativos (normalmente simbólicos) para métodos comunes. Mostrando el código completo:

  import simulacrum._

  @typeclass trait Ordering[T] {
    def compare(x: T, y: T): Int
    @op("<") def lt(x: T, y: T): Boolean = compare(x, y) < 0
    @op(">") def gt(x: T, y: T): Boolean = compare(x, y) > 0
  }

  @typeclass trait Numeric[T] extends Ordering[T] {
    @op("+") def plus(x: T, y: T): T
    @op("*") def times(x: T, y: T): T
    @op("unary_-") def negate(x: T): T
    def zero: T
    def abs(x: T): T = if (lt(x, zero)) negate(x) else x
  }

  import Numeric.ops._
  def signOfTheTimes[T: Numeric](t: T): T = -(t.abs) * t

Cuando existe un operador simbólico personalizado (@op), se puede pronunciar como el nombre del método, por ejemplo, < se pronuncia “menor que”, y no “paréntesis angular izquierdo”.

4.2.3 Instancias

Las instancias de Numeric (que también son instancias de Ordering) se definen como un implicit val que extiende a la typeclass, y que proporciona implementaciones optimizadas pra los métodos generalizados:

  implicit val NumericDouble: Numeric[Double] = new Numeric[Double] {
    def plus(x: Double, y: Double): Double = x + y
    def times(x: Double, y: Double): Double = x * y
    def negate(x: Double): Double = -x
    def zero: Double = 0.0
    def compare(x: Double, y: Double): Int = java.lang.Double.compare(x, y)

    // optimised
    override def lt(x: Double, y: Double): Boolean = x < y
    override def gt(x: Double, y: Double): Boolean = x > y
    override def abs(x: Double): Double = java.lang.Math.abs(x)
  }

Aunque estamos usando +, *, unary_- , < y > aquí, que están en el ops (y podría ser un loop infinito!) estos métodos ya existen en Double. Los métodos de una clase siempre se usan en preferencia a los métodos de extensión. En realidad, el compilador de Scala realiza un manejo especial de los tipos primitivos y convierte estas llamadas en instrucciones directas dadd, dmul, dcmpl, y dcmpg, respectivamente.

También podemos implementar Numeric para la clase de Java BigDecimal (evite `scala.BigDecimal, it is fundamentally broken)

  import java.math.{ BigDecimal => BD }

  implicit val NumericBD: Numeric[BD] = new Numeric[BD] {
    def plus(x: BD, y: BD): BD = x.add(y)
    def times(x: BD, y: BD): BD = x.multiply(y)
    def negate(x: BD): BD = x.negate
    def zero: BD = BD.ZERO
    def compare(x: BD, y: BD): Int = x.compareTo(y)
  }

Podríamos crear nuestra propia estructura de datos para números complejos:

  final case class Complex[T](r: T, i: T)

y construir un Numeric[Complex[T]] si Numeric[T] existe. Dado que estas instancias dependen del parámetro de tipo, es un def y no un val.

  implicit def numericComplex[T: Numeric]: Numeric[Complex[T]] =
    new Numeric[Complex[T]] {
      type CT = Complex[T]
      def plus(x: CT, y: CT): CT = Complex(x.r + y.r, x.i + y.i)
      def times(x: CT, y: CT): CT =
        Complex(x.r * y.r + (-x.i * y.i), x.r * y.i + x.i * y.r)
      def negate(x: CT): CT = Complex(-x.r, -x.i)
      def zero: CT = Complex(Numeric[T].zero, Numeric[T].zero)
      def compare(x: CT, y: CT): Int = {
        val real = (Numeric[T].compare(x.r, y.r))
        if (real != 0) real
        else Numeric[T].compare(x.i, y.i)
      }
    }

El lector observador podrá notar que abs no es lo que un matemático esperaría. El valor de retorno correcto para abs debería ser de tipo T, y no Complex[T].

scala.math.Numeric intenta hacer muchas cosas y no generaliza adecuadamente más allá de los números reales. esta es una buena lección que muestra que typeclasses pequeñas, bien definidas, son con frecuencia mejores que una colección monolítica de características demasiado específicas.

4.2.4 Resolución implícita

Ya hemos discutido los implícitos bastante: esta sección es para clarificar qué son los implícitos y de cómo funcionan.

Los parámetros implícitos se usan cuando un método solicita que una instancia única de un tipo particular exista en el ámbito/alcance implícito (implicit scope) del que realiza la llamada al método, con una sintáxis especial para las instancias de las typeclasses. Los parámetros implícitos son una manera limpia de pasar configuración a una aplicación.

En este ejemplo, foo requiere que las instancias de typeclass de Numeric y Typeable estén disponibles para A, así como un objecto implícito Handler que toma dos parámetros de tipo

  def foo[A: Numeric: Typeable](implicit A: Handler[String, A]) = ...

Las conversiones implícitas se usan cuando existe un implicit def. Un uso posible de dichas conversiones implícitas es para habilitar la metodología de extensión. Cuando el compilador está calculando cómo invocar un método, primero verifica si el método existe en el tipo, luego en sus ancestros (reglas similares a las de Java). Si no encuentra un emparejamiento, entonces buscará en conversiones implícitas en el alcance implícito, y entonces buscará métodos sobre esos tipos.

Otro uso de las conversiones implícitas es en la derivación de typeclasses. En la sección anterior escribimos una implicit def que construía un Numeric[Complex[T]] si existía un Numeric[T] en el alcance implícito. Es posible encadenar juntas muchas implicit def (incluyendo las que pudieran invocarse de manera recursiva) y esto forma la bese de la programación con tipos, permitiendo que cálculos se realicen en tiempo de compilación más bien que en tiempo de ejecución.

El pegamento que combina parámetros implícitos (receptores) con conversiones implícitas (proveedores) es la resolución implícita.

Primero, se buscan implícitos en el ámbito/alcance de variables normales, en orden:

  • alcance local, incluyendo imports dentro del alcance (por ejemplo, en el bloque o el método)
  • alcance externo, incluyendo imports detro del alcance (por ejemplo miembros de la clase)
  • ancestros (por ejemplo miembros en la super clase)
  • el objeto paquete actual
  • el objeto paquete de los ancestros (cuando se usan paquetes anidados)
  • los imports del archivo

Si se falla en encontrar un emparejamiento, se busca en el alcance especial, la cual se realiza para encontrar instancias implícitas dentro del companion del tipo, su paquete de objetos, objetos externos (si están anidados), y entonces se repite para sus ancestros. Esto se realiza, en orden, para:

  • el parámetro de tipo dado
  • el parámetro de tipo esperado
  • el parámetro de tipo (si hay alguno)

Si se encuentran dos implícitos que emparejen en la misma fase de resolución implícita, se lanza un error de implícito ambiguo (ambiguous implicit).

Los implícitos con frecuencia se definen un un `trait, el cual se extiende con un objecto. Esto es para controlar la prioridad de un implícito con referencia a otro más específico, para evitar implícitos ambiguos.

La Especificación del lenguaje de Scala es un tanto vaga para los casos poco comunes, y en realidad la implementación del compilador es el estándar real. Hay algunas reglas de oro que usaremos en este libro, por ejemplo preferir implicit val en lugar de implicit object a pesar de la tentación de teclear menos. Es una capricho de la resolución implícita que los implicit object en los objetos companion no sean tratados de la misma manera que un implicit val.

La resolución implícita se queda corta cuando existe una jerarquía de typeclasses, como Ordering y Numeric. Si escribimos una función que tome un implícito de Ordering, y la llamamos para un tipo primitivo que tiene una instancia de Numeric definido en el companion Numeric, el compilador fallará en encontrarlo.

La resolución implícita es particularmente mala si se usan aliases de tipo donde la forma de los parámetros implícitos son cambiados. Por ejemplo un parámetro implícito usando un alias tal como type Values[A] = List[Option[A]] probablemente fallará al encontrar implícitos definidos como un List[Option[A]] porque la forma se cambió de una cosa de cosas de A a una cosa de As.

4.3 Modelling OAuth2

Terminaremos este capítulo con un ejemplo práctico de modelado de datos y derivación de typeclasses, combinado con el diseño del álgebra/módulo del capítulo anterior.

En nuestra aplicación drone-dynamic-agents, debemos comunicarnos con Drone y Google Cloud usando JSON sobre REST. Ambos servicios usan OAuth2 para la autenticación.

Hay muchas maneras de interpretar OAuth2, pero nos enfocaremos en la versión que funciona para Google Cloud (la versión para Drone es aún más sencilla).

4.3.1 Descripción

Cada aplicación de Google Cloud necesita tener una OAuth 2.0 Client key configurada en

  https://console.developers.google.com/apis/credentials?project={PROJECT_ID}

y así se obtiene un Client ID y un Client secret.

La aplicación puede entonces un código para usarse una sola vez, al hacer que el usuario realice una Authorization Request (petición de autorización) en su navegador (sí, de verdad, en su navegador). Necesitamos hacer que esta página se abra en el navegador:

  https://accounts.google.com/o/oauth2/v2/auth?\
    redirect_uri={CALLBACK_URI}&\
    prompt=consent&\
    response_type=code&\
    scope={SCOPE}&\
    access_type=offline&\
    client_id={CLIENT_ID}

El código se entrega al {CALLBACK_URI} en una petición GET. Para capturarla en nuestra aplicación, necesitamos un servidor web escuchando en localhost.

Una vez que tenemos el código, podemos realizar una petición Acess Token Request:

  POST /oauth2/v4/token HTTP/1.1
  Host: www.googleapis.com
  Content-length: {CONTENT_LENGTH}
  content-type: application/x-www-form-urlencoded
  user-agent: google-oauth-playground
  code={CODE}&\
    redirect_uri={CALLBACK_URI}&\
    client_id={CLIENT_ID}&\
    client_secret={CLIENT_SECRET}&\
    scope={SCOPE}&\
    grant_type=authorization_code

y entonces se tiene una respuesta JSON en el payload

  {
    "access_token": "BEARER_TOKEN",
    "token_type": "Bearer",
    "expires_in": 3600,
    "refresh_token": "REFRESH_TOKEN"
  }

Todas las peticiones al servidor, provenientes del usuario, deben incluir el encabezado

  Authorization: Bearer BEARER_TOKEN

después de sustituir el BEARER_TOKEN real.

Google hace que expiren todas excepto las 50 más recientes bearer tokens, de modo que los tiempos de expiración son únicamente una guía. Los refresh tokens persisten entre sesiones y pueden expirar manualmente por el usuario. Por lo tanto podemos tener una aplicación de configuración que se use una sola vez para obtener el refresh token y entonces incluirlo como una configuración para la instalación del usuario del servidor headless.

Drone no implementa el endpoint /auth, o el refresco, y simplemente proporciona un BEARER_TOKEN a través de su interfaz de usuario.

4.3.2 Datos

El primer paso es modelar los datos necesarios para OAuth2. Creamos un ADT con los campos teniendo el mismo nombre como es requerido por el servidor OAuth2. Usaremos String y Long por brevedad, pero podríamos usar tipos refinados

  import refined.api.Refined
  import refined.string.Url

  final case class AuthRequest(
    redirect_uri: String Refined Url,
    scope: String,
    client_id: String,
    prompt: String = "consent",
    response_type: String = "code",
    access_type: String = "offline"
  )
  final case class AccessRequest(
    code: String,
    redirect_uri: String Refined Url,
    client_id: String,
    client_secret: String,
    scope: String = "",
    grant_type: String = "authorization_code"
  )
  final case class AccessResponse(
    access_token: String,
    token_type: String,
    expires_in: Long,
    refresh_token: String
  )
  final case class RefreshRequest(
    client_secret: String,
    refresh_token: String,
    client_id: String,
    grant_type: String = "refresh_token"
  )
  final case class RefreshResponse(
    access_token: String,
    token_type: String,
    expires_in: Long
  )

4.3.3 Funcionalidad

Es necesario serializar las clases de datos que definimos en la sección previa en JSON, URL, y las formas codificadas POST. Dado que esto requiere de polimorfismo, necesitaremos typeclasses.

jsonformat es una librería JSON simple que estudiaremos en más detalle en un capítulo posterior, dado que ha sido escrita con principios de PF y facilidad de lectura como sus objetivos de diseño primario. Consiste de una AST JSON y typeclasses de codificadores/decodificadores:

  package jsonformat

  sealed abstract class JsValue
  final case object JsNull                                    extends JsValue
  final case class JsObject(fields: IList[(String, JsValue)]) extends JsValue
  final case class JsArray(elements: IList[JsValue])          extends JsValue
  final case class JsBoolean(value: Boolean)                  extends JsValue
  final case class JsString(value: String)                    extends JsValue
  final case class JsDouble(value: Double)                    extends JsValue
  final case class JsInteger(value: Long)                     extends JsValue

  @typeclass trait JsEncoder[A] {
    def toJson(obj: A): JsValue
  }

  @typeclass trait JsDecoder[A] {
    def fromJson(json: JsValue): String \/ A
  }

Necesitamos instancias de JsDecoder[AccessResponse] y JsDecoder[RefreshResponse]. Podemos hacer esto mediante el uso de una función auxiliar:

  implicit class JsValueOps(j: JsValue) {
    def getAs[A: JsDecoder](key: String): String \/ A = ...
  }

Ponemos las instancias de los companions en nuestros tipos de datos, de modo que siempre estén en el alcance/ámbito implícito:

  import jsonformat._, JsDecoder.ops._

  object AccessResponse {
    implicit val json: JsDecoder[AccessResponse] = j =>
      for {
        acc <- j.getAs[String]("access_token")
        tpe <- j.getAs[String]("token_type")
        exp <- j.getAs[Long]("expires_in")
        ref <- j.getAs[String]("refresh_token")
      } yield AccessResponse(acc, tpe, exp, ref)
  }

  object RefreshResponse {
    implicit val json: JsDecoder[RefreshResponse] = j =>
      for {
        acc <- j.getAs[String]("access_token")
        tpe <- j.getAs[String]("token_type")
        exp <- j.getAs[Long]("expires_in")
      } yield RefreshResponse(acc, tpe, exp)
  }

Podemos entonces parsear una cadena en un AccessResponse o una RefreshResponse

  scala> import jsonformat._, JsDecoder.ops._
  scala> val json = JsParser("""
                       {
                         "access_token": "BEARER_TOKEN",
                         "token_type": "Bearer",
                         "expires_in": 3600,
                         "refresh_token": "REFRESH_TOKEN"
                       }
                       """)

  scala> json.map(_.as[AccessResponse])
  AccessResponse(BEARER_TOKEN,Bearer,3600,REFRESH_TOKEN)

Es necesario escribir nuestra propia typeclass para codificación de URL y POST. El siguiente fragmento de código es un diseño razonable:

  // URL query key=value pairs, in un-encoded form.
  final case class UrlQuery(params: List[(String, String)])

  @typeclass trait UrlQueryWriter[A] {
    def toUrlQuery(a: A): UrlQuery
  }

  @typeclass trait UrlEncodedWriter[A] {
    def toUrlEncoded(a: A): String Refined UrlEncoded
  }

Es necesario proporcionar instancias de una typeclass para los tipos básicos:

  import java.net.URLEncoder

  object UrlEncodedWriter {
    implicit val encoded: UrlEncodedWriter[String Refined UrlEncoded] = identity

    implicit val string: UrlEncodedWriter[String] =
      (s => Refined.unsafeApply(URLEncoder.encode(s, "UTF-8")))

    implicit val long: UrlEncodedWriter[Long] =
      (s => Refined.unsafeApply(s.toString))

    implicit def ilist[K: UrlEncodedWriter, V: UrlEncodedWriter]
      : UrlEncodedWriter[IList[(K, V)]] = { m =>
      val raw = m.map {
        case (k, v) => k.toUrlEncoded.value + "=" + v.toUrlEncoded.value
      }.intercalate("&")
      Refined.unsafeApply(raw) // by deduction
    }

  }

Usamos Refined.unsafeApply cuando podemos deducir lógicamente que el contenido de una cadena ya está codificado como una url, dejando de hacer verificaciones adicionales.

ilist es un ejemplo de derivación de typeclass simple, así como derivamos Numeric[Complex] de la representación numérica subyacente. El método .intercalate es como .mkString pero más general.

En un capítulo dedicado a la derivación de typeclasses calcularemos instancias de UrlQueryWriter automáticamente, y también limpiaremos lo que ya hemos escrito, pero por ahora escribiremos el código repetitivo para los tipos que deseemos convertir:

  import UrlEncodedWriter.ops._
  object AuthRequest {
    implicit val query: UrlQueryWriter[AuthRequest] = { a =>
      UriQuery(List(
        ("redirect_uri"  -> a.redirect_uri.value),
        ("scope"         -> a.scope),
        ("client_id"     -> a.client_id),
        ("prompt"        -> a.prompt),
        ("response_type" -> a.response_type),
        ("access_type"   -> a.access_type))
    }
  }
  object AccessRequest {
    implicit val encoded: UrlEncodedWriter[AccessRequest] = { a =>
      List(
        "code"          -> a.code.toUrlEncoded,
        "redirect_uri"  -> a.redirect_uri.toUrlEncoded,
        "client_id"     -> a.client_id.toUrlEncoded,
        "client_secret" -> a.client_secret.toUrlEncoded,
        "scope"         -> a.scope.toUrlEncoded,
        "grant_type"    -> a.grant_type.toUrlEncoded
      ).toUrlEncoded
    }
  }
  object RefreshRequest {
    implicit val encoded: UrlEncodedWriter[RefreshRequest] = { r =>
      List(
        "client_secret" -> r.client_secret.toUrlEncoded,
        "refresh_token" -> r.refresh_token.toUrlEncoded,
        "client_id"     -> r.client_id.toUrlEncoded,
        "grant_type"    -> r.grant_type.toUrlEncoded
      ).toUrlEncoded
    }
  }

4.3.4 Módulo

Esto concluye con el modelado de los datos y funcionalidad requeridos para implementar OAuth2. Recuerde del capítulo anterior que definimos componentes que necesitan interactuar con el mundo como álgebras, y debemos definir la lógica de negocio en un módulo, de modo que pueda ser probada por completo.

Definimos nuestra dependencia de las álgebras, y usamos los límites de contexto para mostrar que nuestras respuestas deben tener un JsDecoder y nuestro payload POST debe tener un UrlEncodedWriter:

  trait JsonClient[F[_]] {
    def get[A: JsDecoder](
      uri: String Refined Url,
      headers: IList[(String, String)]
    ): F[A]

    def post[P: UrlEncodedWriter, A: JsDecoder](
      uri: String Refined Url,
      payload: P,
      headers: IList[(String, String]
    ): F[A]
  }

Note que nosotros únicamente definimos el camino fácil en la API JsonClient. Veremos como lidiar con los errores en un capítulo posterior.

Obtener un CodeToken de un servidor OAuth2 de Google envuelve

  1. iniciar un servidor HTTP en la máquina local, y obtener su número de puerto.
  2. hacer que el usuario abra una página web en su navegador, lo que les permite identificarse con sus credenciales de Google y autorizar la aplicación, con una redirección de vuelta a la máquina local.
  3. capturar el código, informando al usuario de los siguientes pasos, y cerrar el servidor HTTP.

Podemos modelar esto con tres métodos en una álgebra UserInteraction

  final case class CodeToken(token: String, redirect_uri: String Refined Url)

  trait UserInteraction[F[_]] {
    def start: F[String Refined Url]
    def open(uri: String Refined Url): F[Unit]
    def stop: F[CodeToken]
  }

Casi suena fácil cuando lo escribimos de esta manera.

También requerimos de un álgebra para abstraer el sistema local de tiempo

  trait LocalClock[F[_]] {
    def now: F[Epoch]
  }

E introducimos los tipos de datos que usaremos en la lógica de refresco

  final case class ServerConfig(
    auth: String Refined Url,
    access: String Refined Url,
    refresh: String Refined Url,
    scope: String,
    clientId: String,
    clientSecret: String
  )
  final case class RefreshToken(token: String)
  final case class BearerToken(token: String, expires: Epoch)

y ahora podemos escribir un módulo cliente para OAuth2:

  import http.encoding.UrlQueryWriter.ops._

  class OAuth2Client[F[_]: Monad](
    config: ServerConfig
  )(
    user: UserInteraction[F],
    client: JsonClient[F],
    clock: LocalClock[F]
  ) {
    def authenticate: F[CodeToken] =
      for {
        callback <- user.start
        params   = AuthRequest(callback, config.scope, config.clientId)
        _        <- user.open(params.toUrlQuery.forUrl(config.auth))
        code     <- user.stop
      } yield code

    def access(code: CodeToken): F[(RefreshToken, BearerToken)] =
      for {
        request <- AccessRequest(code.token,
                                 code.redirect_uri,
                                 config.clientId,
                                 config.clientSecret).pure[F]
        msg     <- client.post[AccessRequest, AccessResponse](
                     config.access, request)
        time    <- clock.now
        expires = time + msg.expires_in.seconds
        refresh = RefreshToken(msg.refresh_token)
        bearer  = BearerToken(msg.access_token, expires)
      } yield (refresh, bearer)

    def bearer(refresh: RefreshToken): F[BearerToken] =
      for {
        request <- RefreshRequest(config.clientSecret,
                                  refresh.token,
                                  config.clientId).pure[F]
        msg     <- client.post[RefreshRequest, RefreshResponse](
                     config.refresh, request)
        time    <- clock.now
        expires = time + msg.expires_in.seconds
        bearer  = BearerToken(msg.access_token, expires)
      } yield bearer
  }

4.4 Resumen

  • Los ADTs (tipos de datos algebraicos) están definidos como productos (final case class) y coproductos (sealed abstract class).
  • Los tipos refined hacen cumplir las invariantes/restricciones sobre los valores.
  • Las funciones concretas pueden definirse en una clase implícita, para mantener el flujo de izquierda a derecha.
  • Las funciones polimórficas están definidas en typeclasses. La funcionalidad se proporciona por medio de límites de contexto (“has a”), más bién que por medio de jerarquías de clases.
  • Las instancias de typeclasses son implementaciones de una typeclass.
  • @simulacrum.typeclass genera .ops en el companion, proporcionando sintaxis conveniente para las funciones de la typeclass.
  • La derivación de typeclasses es una composición en tiempo de compilación de instancias de typeclass.

5. Scalaz Typeclasses

En este capítulo tendremos un tour de la mayoría de las typeclasses en scalaz-core. No usamos todas en drone-dynamic-agents de modo que daremos ejemplos standalone cuando sea apropiado.

Ha habido críticas con respecto a los nombres usados en Scalaz, y en la programación funcional en general. La mayoría de los nombres siguen las convenciones introducidas en el lenguaje de programación funcional Haskell, basándose en la Teoría de las Categorías. Siéntase libre de crear type aliases si los verbos basados en la funcionalidad primaria son más fáciles de recordar cuando esté aprendiendo (por ejemplo, Mappable, Pureable, FlatMappable).

Antes de introducir la jerarquía de typeclasses, echaremos un vistazo a los cuatro métodos más importantes desde una perspectiva de control de flujo: los métodos que usaremos más en las aplicaciones típicas de PF:

Typeclass Method Desde Dado Hacia
Functor map F[A] A => B F[B]
Applicative pure A   F[A]
Monad flatMap F[A] A => F[B] F[B]
Traverse sequence F[G[A]]   G[F[A]]

Sabemos que las operaciones que regresan un F[_] pueden ejecutarse secuencialmente en una comprensión for mediante .flatMap definida en su Monad[F]. El contexto F[_] puede considerarse como un contenedor para un efecto intencional que tiene una A como la salida: flatMap nos permite generar nuevos efectos F[B] en tiempo de ejecución basándose en los resultados de evaluar efectos previos.

Por supuesto, no todos los constructores de tipo F[_] tienen efectos, incluso si tienen una Monad[_]. Con frecuencia son estructuras de datos. Mediante el uso de la abstracción menos específica, podemos reusar código para List, Either, Future y más.

Si únicamente necesitamos transformar la salida de un F[_], esto simplemente es un map, introducido por Functor. En el capítulo 3, ejecutamos efectos en paralelo mediante la creación de un producto y realizando un mapeo sobre ellos. En programación funcional, los cómputos paralelizables son considerados menos poderosos que los secuenciales.

Entre Monad y Functor se encuentra Applicative, que define pure que nos permite alzar un valor en un efecto, o la creación de una estructura de datos a partir de un único valor.

.sequence es útil para rearreglar constructores de tipo. Si tenemos un F[G[_]] pero requerimos un G[F[_]], por ejemplo, List[Future[Int]] pero requerimos un Future[List[_]], entonces ocupamos .sequence.

5.1 Agenda

Este capítulo es más largo de lo usual y está repleto de información: es perfectamente razonable abordarlo en varias sesiones de estudio. Recordar todo requeriría poderes sobrehumanos, de modo que trate este capítulo como una manera de buscar más información.

Es notable la ausencia de typeclasses que extienden Monad. Estas tendrán su propio capítulo más adelante.

Scalaz usa generación de código, no simulacrum. Sin embargo, por brevedad, presentaremos los fragmentos de código con @typeclass. La sintaxis equivalente estará disponible cuando hagamos un import scalaz._, Scalaz._ y estará disponible en el paquete scalaz.syntax en el código fuente de Scalaz.

5.2 Cosas que pueden agregarse

  @typeclass trait Semigroup[A] {
    @op("|+|") def append(x: A, y: =>A): A

    def multiply1(value: F, n: Int): F = ...
  }

  @typeclass trait Monoid[A] extends Semigroup[A] {
    def zero: A

    def multiply(value: F, n: Int): F =
      if (n <= 0) zero else multiply1(value, n - 1)
  }

  @typeclass trait Band[A] extends Semigroup[A]

Un Semigroup puede definirse para un tipo si dos valores pueden combinarse. El operador debe ser asociativo, es decir, que el orden de las operaciones anidadas no debería importar, es decir

  (a |+| b) |+| c == a |+| (b |+| c)

  (1 |+| 2) |+| 3 == 1 |+| (2 |+| 3)

Un Monoid es un Semigroup con un elemento zero (también llamado empty –vacío– o identity –identidad–). Combinar zero con cualquier otra a debería dar otra a .

  a |+| zero == a

  a |+| 0 == a

Esto probablemente le traiga memorias sobre Numeric del capítulo 4. Existen implementaciones de Monoid para todos los tipos numéricos primitivos, pero el concepto de cosas que se pueden agregar es útil más allá de los números.

  scala> "hello" |+| " " |+| "world!"
  res: String = "hello world!"

  scala> List(1, 2) |+| List(3, 4)
  res: List[Int] = List(1, 2, 3, 4)

Band tiene la ley de que la operación append de dos elementos iguales es idempotente, es decir devuelve el mismo valor. Ejemplos de esto pueden ser cualesquier cosa que sólo pueda tener un valor, tales como Unit, los límites superiores más pequeños, o un Set (conjunto). Band no proporciona métodos adicionales y sin embargo los usuarios pueden aprovechar las garantías que brinda con fines de optimización del rendimiento.

Como un ejemplo realista de Monoid, considere un sistema de comercio que tenga una base de datos grande de plantillas de transacciones comerciales reutilizables. Llenar las plantillas por default para una nueva transacción implica la selección y combinación de múltiples plantillas, con la regla del “último gana” para realizar uniones si dos plantillas proporcionan un valor para el mismo campo. El trabajo de “seleccionar” trabajo ya se realiza por nosotros mediante otro sistema, es nuestro trabajo combinar las plantillas en orden.

Crearemos un esquema simple de plantillas para demostrar el principio, pero tenga en mente que un sistema realista tendría un ADT más complicado.

  sealed abstract class Currency
  case object EUR extends Currency
  case object USD extends Currency

  final case class TradeTemplate(
    payments: List[java.time.LocalDate],
    ccy: Option[Currency],
    otc: Option[Boolean]
  )

Si escribimos un método que tome templates: List[TradeTemplate], entonces necesitaremos llamar únicamente

  val zero = Monoid[TradeTemplate].zero
  templates.foldLeft(zero)(_ |+| _)

¡y nuestro trabajo está hecho!

Pero para poder usar zero o invocar |+| debemos tener una instancia de Monoid[TradeTemplate]. Aunque derivaremos genéricamente este en un capítulo posterior, por ahora crearemos la instancia en el companion:

  object TradeTemplate {
    implicit val monoid: Monoid[TradeTemplate] = Monoid.instance(
      (a, b) => TradeTemplate(a.payments |+| b.payments,
                              a.ccy |+| b.ccy,
                              a.otc |+| b.otc),
      TradeTemplate(Nil, None, None)
    )
  }

Sin embargo, esto no hace lo que queremos porque Monoid[Option[A]] realizará una agregación de su contenido, por ejemplo,

  scala> Option(2) |+| None
  res: Option[Int] = Some(2)
  scala> Option(2) |+| Option(1)
  res: Option[Int] = Some(3)

mientras que deseamos implementar la regla del “último gana”. Podríamos hacer un override del valor default Monoid[Option[A]] con el nuestro propio:

  implicit def lastWins[A]: Monoid[Option[A]] = Monoid.instance(
    {
      case (None, None)   => None
      case (only, None)   => only
      case (None, only)   => only
      case (_   , winner) => winner
    },
    None
  )

Ahora todo compila, de modo que si lo intentamos…

  scala> import java.time.{LocalDate => LD}
  scala> val templates = List(
           TradeTemplate(Nil,                     None,      None),
           TradeTemplate(Nil,                     Some(EUR), None),
           TradeTemplate(List(LD.of(2017, 8, 5)), Some(USD), None),
           TradeTemplate(List(LD.of(2017, 9, 5)), None,      Some(true)),
           TradeTemplate(Nil,                     None,      Some(false))
         )

  scala> templates.foldLeft(zero)(_ |+| _)
  res: TradeTemplate = TradeTemplate(
                         List(2017-08-05,2017-09-05),
                         Some(USD),
                         Some(false))

Todo lo que tuvimos que hacer fue implementar una pieza de lógica de negocios y, !el Monoid se encargó de todo por nosotros!

Note que la lista de payments se concatenó. Esto es debido a que el Monoid[List] por default usa concatenación de elementos y simplemente ocurre que este es el comportamiento deseado aquí. Si el requerimiento de negocios fuera distinto, la solución sería proporcionar un Monoid[List[LocalDate]] personalizado. Recuerde del capítulo 4 que con el polimorfismo de tiempo de compilación tenemos una implementacion distinta de append dependiendo de la E en List[E], no sólo de la clase de tiempo de ejecución List.

5.3 Cosas parecidas a objetos

En el capítulo sobre Datos y Funcionalidad dijimos que la noción de la JVM de igualdad se derrumba para muchas cosas que podemos poner en una ADT. El problema es que la JVM fue diseñada para Java, y equals está definido sobre java.lang.Object aunque esto tenga sentido o no. No existe manera de remover equals y no hay forma de garantizar que esté implementado.

Sin embargo, en PF preferimos el uso de typeclasses para tener funcionalidad polimórfica e incluso el concepto de igualdad es capturado en tiempo de compilación.

  @typeclass trait Equal[F]  {
    @op("===") def equal(a1: F, a2: F): Boolean
    @op("/==") def notEqual(a1: F, a2: F): Boolean = !equal(a1, a2)
  }

En verdad === (triple igual) es más seguro desde la perspectiva de tipos que ==(doble igual) porque únicamente puede compilarse cuando los tipos son los mismos en ambos lados de la comparación. Esto atrapa muchos errores.

equal tiene los mismos requisitos de implementación que Object.equals

  • conmutativo f1 === f2 implica f2 === f1
  • reflexivo f === f
  • transitivo f1 === f2 && f2 === f3 implica que f1 === f3

Al desechar el concepto universal de Object.equals no damos por sentado el concepto de igualdad cuando construimos un ADT, y nos detiene en tiempo de compilación de esperar igualdad cuando en realidad no existe tal.

Continuando con la tendencia de reemplazar conceptos viejos de Java, más bien que considerar que los datos son un java.lang.Comparable, ahora tienen un Order de acuerdo con

  @typeclass trait Order[F] extends Equal[F] {
    @op("?|?") def order(x: F, y: F): Ordering

    override  def equal(x: F, y: F): Boolean = order(x, y) == Ordering.EQ
    @op("<" ) def lt(x: F, y: F): Boolean = ...
    @op("<=") def lte(x: F, y: F): Boolean = ...
    @op(">" ) def gt(x: F, y: F): Boolean = ...
    @op(">=") def gte(x: F, y: F): Boolean = ...

    def max(x: F, y: F): F = ...
    def min(x: F, y: F): F = ...
    def sort(x: F, y: F): (F, F) = ...
  }

  sealed abstract class Ordering
  object Ordering {
    case object LT extends Ordering
    case object EQ extends Ordering
    case object GT extends Ordering
  }

Order implementa .equal en términos de la primitiva nueva .order. Cuando una typeclass implementa el combinador primitivo de su padre con un combinador derivado, se agrega una ley implicación de sustitución para el typeclass. Si una instancia de Order fuera a hacer un override de .equal por razones de desempeño, debería comportase de manera idéntica a la original.

Las cosas que tienen un orden también podrían ser discretas, permitiéndonos avanzar o retroceder hacia un sucesor o predecesor:

  @typeclass trait Enum[F] extends Order[F] {
    def succ(a: F): F
    def pred(a: F): F
    def min: Option[F]
    def max: Option[F]

    @op("-+-") def succn(n: Int, a: F): F = ...
    @op("---") def predn(n: Int, a: F): F = ...

    @op("|->" ) def fromToL(from: F, to: F): List[F] = ...
    @op("|-->") def fromStepToL(from: F, step: Int, to: F): List[F] = ...
    @op("|=>" ) def fromTo(from: F, to: F): EphemeralStream[F] = ...
    @op("|==>") def fromStepTo(from: F, step: Int, to: F): EphemeralStream[F] = ...
  }
  scala> 10 |--> (2, 20)
  res: List[Int] = List(10, 12, 14, 16, 18, 20)

  scala> 'm' |-> 'u'
  res: List[Char] = List(m, n, o, p, q, r, s, t, u)

Discutiremos EphemeralStream en el siguiente capítulo, por ahora sólo necesitamos saber que se trata de una estructura de datos potencialmente infinita que evita los problemas de retención de memoria en el tipo Stream de la librería estándar.

De manera similar a Object.equals, el concepto de .toString en toda clases no tiene sentido en Java. Nos gustaría hacer cumplir el concepto de “poder representar como cadena” en tiempo de compilación y esto es exactamente lo que se consigue con Show:

  trait Show[F] {
    def show(f: F): Cord = ...
    def shows(f: F): String = ...
  }

Exploraremos Cord con más detalle en el capítulo que trate los tipos de datos, por ahora sólo necesitamos saber que es una estructura de datos eficiente para el almacenamiento y manipulación de String.

5.4 Cosas que se pueden mapear o transformar

Ahora nos enfocamos en las cosas que pueden mapearse, o recorrerse, en cierto sentido:

5.4.1 Functor

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

    def void[A](fa: F[A]): F[Unit] = map(fa)(_ => ())
    def fproduct[A, B](fa: F[A])(f: A => B): F[(A, B)] = map(fa)(a => (a, f(a)))

    def fpair[A](fa: F[A]): F[(A, A)] = map(fa)(a => (a, a))
    def strengthL[A, B](a: A, f: F[B]): F[(A, B)] = map(f)(b => (a, b))
    def strengthR[A, B](f: F[A], b: B): F[(A, B)] = map(f)(a => (a, b))

    def lift[A, B](f: A => B): F[A] => F[B] = map(_)(f)
    def mapply[A, B](a: A)(f: F[A => B]): F[B] = map(f)((ff: A => B) => ff(a))
  }

El único método abstracto es map, y debe ser posible hacer una composición, es decir, mapear con una f y entonces nuevamente con una g es lo mismo que hacer un mapeo una única vez con la composición de f y g:

  fa.map(f).map(g) == fa.map(f.andThen(g))

El map también debe realizar una operación nula si la función provista es la identidad (es decir, x => x)

  fa.map(identity) == fa

  fa.map(x => x) == fa

Functor define algunos métodos convenientes alrededor de map que pueden optimizarse para algunas instancias específicas. La documentación ha sido intencionalmente omitida en las definiciones arriba para incentivar el análisis de lo que hace un método antes de que vea la implementación. Por favor, deténgase unos momentos estudiando únicamente las signaturas de tipo de los siguientes métodos antes de avanzar más:

  def void[A](fa: F[A]): F[Unit]
  def fproduct[A, B](fa: F[A])(f: A => B): F[(A, B)]

  def fpair[A](fa: F[A]): F[(A, A)]
  def strengthL[A, B](a: A, f: F[B]): F[(A, B)]
  def strengthR[A, B](f: F[A], b: B): F[(A, B)]

  // harder
  def lift[A, B](f: A => B): F[A] => F[B]
  def mapply[A, B](a: A)(f: F[A => B]): F[B]
  1. void toma una instancia de F[A] y siempre devuelve un F[Unit], y se olvida de todos los valores a la vez que preserva la estructura.
  2. fproduct toma la misma entrada que map pero devuelve F[(A, B)], es decir, devuelve el contenido dentro de una tupla, con el resultado obtenido al aplicar la función. Esto es útil cuando deseamos retener la entrada.
  3. fpair repite todos los elementos de A en una tupla F[(A, A)]
  4. strengthL empareja el contenido de una F[B] con una constante A a la izquierda.
  5. strenghtR empareja el contenido de una F[A] con una constante B a la derecha.
  6. lift toma una función A => B y devuelve una F[A] => F[B]. En otras palabras, toma una función del contenido de una F[A] y devuelve una función que opera en el F[A] directamente.
  7. mapply nos obliga a pensar un poco. Digamos que tenemos una F[_] de funciones A => B y el valor A, entonces podemos obtener un F[B]. Tiene una firma/signatura similar a la de pure pero requiere que el que hace la llamada proporcione F[A => B].

fpair, strenghL y strengthR tal vez parezcan inútiles, pero mostrarán su utilidad cuando deseemos retener algo de información que de otra manera se perdería en el ámbito.

Functor tiene una sintaxis especial:

  implicit class FunctorOps[F[_]: Functor, A](self: F[A]) {
    def as[B](b: =>B): F[B] = Functor[F].map(self)(_ => b)
    def >|[B](b: =>B): F[B] = as(b)
  }

.as y >| es una forma de reemplazar la salida con una constante.

En nuestra aplicación de ejemplo, como un hack espantoso (que no admitimos hasta ahora), definimos start y stop de modo que devolvieran su entrada:

  def start(node: MachineNode): F[MachineNode]
  def stop (node: MachineNode): F[MachineNode]

Esto nos permitió escribir lógica breve de negocios como

  for {
    _      <- m.start(node)
    update = world.copy(pending = Map(node -> world.time))
  } yield update

y

  for {
    stopped <- nodes.traverse(m.stop)
    updates = stopped.map(_ -> world.time).toList.toMap
    update  = world.copy(pending = world.pending ++ updates)
  } yield update

pero este hack nos obliga a poner complejidad innecesaria en las implementaciones. Es mejor si dejamos que nuestras álgebras regresen F[Unit] y usar as:

  m.start(node) as world.copy(pending = Map(node -> world.time))

y

  for {
    stopped <- nodes.traverse(a => m.stop(a) as a)
    updates = stopped.map(_ -> world.time).toList.toMap
    update  = world.copy(pending = world.pending ++ updates)
  } yield update

5.4.2 Foldable

Técnicamente, Foldable es para estructuras de datos que pueden recorrerse y producir un valor que las resuma. Sin embargo, esto no dice lo suficiente sobre el hecho de que se trata de un arma poderosa proporcionada por las typeclasses que nos puede proporcionar la mayoría de lo que esperamos ver en una API de colecciones.

Hay tantos métodos que necesitaremos revisarlos en partes, empezando con los métodos abstractos:

  @typeclass trait Foldable[F[_]] {
    def foldMap[A, B: Monoid](fa: F[A])(f: A => B): B
    def foldRight[A, B](fa: F[A], z: =>B)(f: (A, =>B) => B): B
    def foldLeft[A, B](fa: F[A], z: B)(f: (B, A) => B): B = ...

Una instancia de Foldable necesita implementar únicamente foldMap y foldRight para obtener toda la funcionalidad en esta typeclass, aunque los métodos están típicamente optimizqados para estructuras de datos específicas.

.foldMap tiene un nombre usado en mercadotecnia: MapReduce. Dada una F[A], una función de A a B, y una forma de combinar una B (proporcionada por el Monoid, junto con el zero B), podemos producir el valor resumen de tipo B. No existe un orden impuesto en las operaciones, permitiendonos realizar cómputos paralelos.

foldRight no requiere que sus parámetros tengan un Monoid, significando esto que necesita un valor inicial z y una manera de combinar cada elemento de la estructura de datos con el valor resumen. El orden en el que se recorren los elementos es de derecha a izquierda y es por esta razón que no puede paralelizarse.

foldLeft recorre los elementos de izquierda a derecha. foldLeft puede implementarse en términos de foldMap, pero la mayoría de las instancias escogen implementarlas porque se trata de una operación básica. Dado que normalmente se implementa con recursión de cola, no existen parámetros byname.

La única ley para Foldable es que foldLeft y foldRight deberían ser consistentes con foldMap para operaciones monoidales, por ejemplo, agregando un elemento a una lista para foldLeft y anteponiendo un elemento a la lista para foldRight. Sin embargo, foldLeft y foldRight no necesitan ser consistentes la una con la otra: de hecho con frecuencia producen el inverso que produce el otro.

La cosa más sencilla que se puede hacer con foldMap es usar la función identity (identidad), proporcionando fold (la suma natural de los elementos monoidales), con variantes derecha/izquierda para permitirnos escoger basándonos en criterios de rendimiento:

  def fold[A: Monoid](t: F[A]): A = ...
  def sumr[A: Monoid](fa: F[A]): A = ...
  def suml[A: Monoid](fa: F[A]): A = ...

Recuerde que cuando aprendimos sobre Monoid, escribimos lo siguiente:

  scala> templates.foldLeft(Monoid[TradeTemplate].zero)(_ |+| _)

Sabemos que esto es tonto y que pudimos escribir:

  scala> templates.toIList.fold
  res: TradeTemplate = TradeTemplate(
                         List(2017-08-05,2017-09-05),
                         Some(USD),
                         Some(false))

.fold no funciona en la List estándar debido a que ya tiene un método llamado fold que hace su propia cosa a su manera especial.

El método llamado de manera extraña intercalate inserta una A específica entre cada elemento antes de realizar el fold

  def intercalate[A: Monoid](fa: F[A], a: A): A = ...

que es una versión generalizada del método de la librería estándar mkString:

  scala> List("foo", "bar").intercalate(",")
  res: String = "foo,bar"

El foldLeft proporciona el medio para obtener cualquier elemento mediante un índice para recorrer la estructura, incluyendo un grupo grande de métodos relacionados:

  def index[A](fa: F[A], i: Int): Option[A] = ...
  def indexOr[A](fa: F[A], default: =>A, i: Int): A = ...
  def length[A](fa: F[A]): Int = ...
  def count[A](fa: F[A]): Int = length(fa)
  def empty[A](fa: F[A]): Boolean = ...
  def element[A: Equal](fa: F[A], a: A): Boolean = ...

Scalaz es una librería funcional pura que tiene únicamente funciones totales. Mientras que List(0) puede lanzar excepciones, Foldable.index devuelve una Option[A] con el método conveniente .indexOr regreseando una A cuando se proporciona un valor por default. .element es similar al método de la librería estándar .contains pero usa Equal más bien que la mal definida igualdad de la JVM.

Estos métods realmente suenan como una API de colecciones. Y, por supuesto, toda cosa con una instancia de Foldable puede convertirse en una List

  def toList[A](fa: F[A]): List[A] = ...

También existen conversiones a otros tipos de datos de la librería estándar de Scala y de Scalaz, tales como .toSet, .toVector, .toStream, .to[T <: TraversableLike], toIList y la lista continúa.

Existen verificadores de predicados útiles

  def filterLength[A](fa: F[A])(f: A => Boolean): Int = ...
  def all[A](fa: F[A])(p: A => Boolean): Boolean = ...
  def any[A](fa: F[A])(p: A => Boolean): Boolean = ...

filterLenght es una forma de contar cuántos elementos son true para el predicado, all y any\ devuelven true is todos (o algún) elemento cumple con el predicado, y pueden terminar de manera temprana.

Podemos dividir en partes una F[A] que resulten en la misma B con splitBy

  def splitBy[A, B: Equal](fa: F[A])(f: A => B): IList[(B, Nel[A])] = ...
  def splitByRelation[A](fa: F[A])(r: (A, A) => Boolean): IList[Nel[A]] = ...
  def splitWith[A](fa: F[A])(p: A => Boolean): List[Nel[A]] = ...
  def selectSplit[A](fa: F[A])(p: A => Boolean): List[Nel[A]] = ...

  def findLeft[A](fa: F[A])(f: A => Boolean): Option[A] = ...
  def findRight[A](fa: F[A])(f: A => Boolean): Option[A] = ...

por ejemplo

  scala> IList("foo", "bar", "bar", "faz", "gaz", "baz").splitBy(_.charAt(0))
  res = [(f, [foo]), (b, [bar, bar]), (f, [faz]), (g, [gaz]), (b, [baz])]

haciendo la observación de que sólamente existen dos valores indexados por 'b'.

splitByRelation evita la necesidad de tener una Equal pero debemos proporcionar el operador de comparación.

splitWith divide los elementos en grupos que alternativamente satisfacen y no el predicado. selectSplit selecciona grupos de elementos que satisfacen el predicado, descartando los otros. Este es uno de esos casos raros en donde dos métodos comparten la misma firma/signatura, pero tienen significados distintos.

findLeft y findRight sirven para extraer el primer elemento (de la izquierda o de la derecha) que cumpla un predicado.

Haciendo uso adicional de Equal y Order, tenemos métodos distinct que devuelven agrupaciones.

  def distinct[A: Order](fa: F[A]): IList[A] = ...
  def distinctE[A: Equal](fa: F[A]): IList[A] = ...
  def distinctBy[A, B: Equal](fa: F[A])(f: A => B): IList[A] =

distinct se implementa de manera más eficiente que distinctE debido a que puede usar el ordenamiento y por lo tanto usar un algoritmo tipo quicksort que es mucho más rápido que la implementación ingenua de List.distinct. Las estructuras de datos (tales como los conjuntos) pueden implementar distinct y su Foldable sin realizar ningún trabajo.

distinctBy permite la agrupación mediante la aplicación de una función a sus elementos. Por ejemplo, agrupar nombres por su letra inicial.

Podemos hacer uso adicional de Order al extraer el elemento mínimo o máximo (o ambos extremos) incluyendo variaciones usando el patrón Of o By para mapear primero a otro tipo o usar un tipo diferente para hacer la otra comparación.

  def maximum[A: Order](fa: F[A]): Option[A] = ...
  def maximumOf[A, B: Order](fa: F[A])(f: A => B): Option[B] = ...
  def maximumBy[A, B: Order](fa: F[A])(f: A => B): Option[A] = ...

  def minimum[A: Order](fa: F[A]): Option[A] = ...
  def minimumOf[A, B: Order](fa: F[A])(f: A => B): Option[B] = ...
  def minimumBy[A, B: Order](fa: F[A])(f: A => B): Option[A] = ...

  def extrema[A: Order](fa: F[A]): Option[(A, A)] = ...
  def extremaOf[A, B: Order](fa: F[A])(f: A => B): Option[(B, B)] = ...
  def extremaBy[A, B: Order](fa: F[A])(f: A => B): Option[(A, A)] =

Por ejemplo podríamos preguntar cuál String es máxima By (por) longitud, o cuál es la máxima longitud Of (de) los elementos.

  scala> List("foo", "fazz").maximumBy(_.length)
  res: Option[String] = Some(fazz)

  scala> List("foo", "fazz").maximumOf(_.length)
  res: Option[Int] = Some(4)

Esto concluye con las características clave de Foldable. El punto clave a recordar es que cualquier cosa que esperaríamos encontrar en una librearía de colecciones está probablemente en Foldable y si no está ahí, probablemente debería estarlo.

Concluiremos con algunas variantes de los métodos que ya hemos visto. Primero, existen métodos que toman un Semigroup en lugar de un Monoid:

  def fold1Opt[A: Semigroup](fa: F[A]): Option[A] = ...
  def foldMap1Opt[A, B: Semigroup](fa: F[A])(f: A => B): Option[B] = ...
  def sumr1Opt[A: Semigroup](fa: F[A]): Option[A] = ...
  def suml1Opt[A: Semigroup](fa: F[A]): Option[A] = ...
  ...

devolviendo Option para tomar encuenta las estructuras de datos vacías (recuerde que Semigroup no tiene un zero).

La typeclass Foldable1 contiene muchas más variantes usando Semigroup de los métodos que usan Monoid mostrados aquí (todos ellos con el sufijo 1) y tienen sentido para estructuras de datos que nunca están vacías, sin requerrir la existencia de un Monoid para los elementos.

De manera importante, existen variantes que toman valores de retorno monádicos. Ya hemos usado foldLeft cuando escribimos por primera vez la lógica de negocios de nuestra aplicación, ahora sabemos que proviene de Foldable:

  def foldLeftM[G[_]: Monad, A, B](fa: F[A], z: B)(f: (B, A) => G[B]): G[B] = ...
  def foldRightM[G[_]: Monad, A, B](fa: F[A], z: =>B)(f: (A, =>B) => G[B]): G[B] = ...
  def foldMapM[G[_]: Monad, A, B: Monoid](fa: F[A])(f: A => G[B]): G[B] = ...
  def findMapM[M[_]: Monad, A, B](fa: F[A])(f: A => M[Option[B]]): M[Option[B]] = ...
  def allM[G[_]: Monad, A](fa: F[A])(p: A => G[Boolean]): G[Boolean] = ...
  def anyM[G[_]: Monad, A](fa: F[A])(p: A => G[Boolean]): G[Boolean] = ...
  ...

5.4.3 Traverse

Traverse es lo que sucede cuando hacemos el cruce de un Functor con un Foldable

  trait Traverse[F[_]] extends Functor[F] with Foldable[F] {
    def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
    def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] = ...

    def reverse[A](fa: F[A]): F[A] = ...

    def zipL[A, B](fa: F[A], fb: F[B]): F[(A, Option[B])] = ...
    def zipR[A, B](fa: F[A], fb: F[B]): F[(Option[A], B)] = ...
    def indexed[A](fa: F[A]): F[(Int, A)] = ...
    def zipWithL[A, B, C](fa: F[A], fb: F[B])(f: (A, Option[B]) => C): F[C] = ...
    def zipWithR[A, B, C](fa: F[A], fb: F[B])(f: (Option[A], B) => C): F[C] = ...

    def mapAccumL[S, A, B](fa: F[A], z: S)(f: (S, A) => (S, B)): (S, F[B]) = ...
    def mapAccumR[S, A, B](fa: F[A], z: S)(f: (S, A) => (S, B)): (S, F[B]) = ...
  }

Al principio del capítulo mostramos la importancia de traverse y sequence para invertir los constructores de tipo para que se ajusten a un requerimiento (por ejemplo, de List[Future[_]] a Future[List[_]]).

En Foldable no fuimos capaces de asumir que reverse fuera un concepto universal, pero ahora podemos invertir algo.

También podemos hacer un zip de dos cosas que tengan un Traverse, obteniendo un None cuando uno de los dos lados se queda sin elementos, usando zipL o zipR para decidir cuál lado truncar cuando las longitudes no empatan. Un caso especial de zip es agregar un índice a cada entrada con indexed.

zipWithL y zipWithR permiten la combinación de dos lados de un zip en un nuevo tipo, y entonces devuelven simplemente un F[C].

mapAccumL y mapAccumR son map regular combinado con un acumulador. Si nos topamos con la situación de que nuestra costumbre vieja proveniente de Java nos quiere hacer usar una var, y deseamos referirnos a ella en un map, deberíamos estar usando mapAccumL.

Por ejemplo, digamos que tenemos una lista de palabras y que deseamos borrar las palabras que ya hemos encontrado. El algoritmo de filtrado no permite procesar las palabras de la lista una segunda vez de modo que pueda escalarse a un stream infinito:

  scala> val freedom =
  """We campaign for these freedoms because everyone deserves them.
     With these freedoms, the users (both individually and collectively)
     control the program and what it does for them."""
     .split("\\s+")
     .toList

  scala> def clean(s: String): String = s.toLowerCase.replaceAll("[,.()]+", "")

  scala> freedom
         .mapAccumL(Set.empty[String]) { (seen, word) =>
           val cleaned = clean(word)
           (seen + cleaned, if (seen(cleaned)) "_" else word)
         }
         ._2
         .intercalate(" ")

  res: String =
  """We campaign for these freedoms because everyone deserves them.
     With _ _ the users (both individually and collectively)
     control _ program _ what it does _ _"""

Finalmente Traversable1, como Foldable1, proporciona variantes de estos métodos para las estructuras de datos que no pueden estar vacías, aceptando Semigroup (más débil) en lugar de un Monoid, y un Apply en lugar de un Applicative. Recuerde que Semigroup no tiene que proporcionar un .empty, y Apply no tiene que proporcionar un .point.

5.4.4 Align

Align es sobre unir y rellenar algo con un Functor. Antes de revisar Align, conozca al tipo de datos \&/ (pronunciado como These, o ¡Viva!).

  sealed abstract class \&/[+A, +B]
  final case class This[A](aa: A) extends (A \&/ Nothing)
  final case class That[B](bb: B) extends (Nothing \&/ B)
  final case class Both[A, B](aa: A, bb: B) extends (A \&/ B)

es decir, se trata de una codificación con datos de un OR lógico inclusivo. A o B o ambos A y B.

  @typeclass trait Align[F[_]] extends Functor[F] {
    def alignWith[A, B, C](f: A \&/ B => C): (F[A], F[B]) => F[C]
    def align[A, B](a: F[A], b: F[B]): F[A \&/ B] = ...

    def merge[A: Semigroup](a1: F[A], a2: F[A]): F[A] = ...

    def pad[A, B]: (F[A], F[B]) => F[(Option[A], Option[B])] = ...
    def padWith[A, B, C](f: (Option[A], Option[B]) => C): (F[A], F[B]) => F[C] = ...

alignWith toma una función de ya sea una A o una B (o ambos) a una C y devuelve una función alzada de una tupla de F[A] y F[B] a una F[C]. align construye \&/ a partir de dos F[_].

merge nos permite combinar dos F[A] cuando A tiene un Semigroup. Por ejemplo, la implementación de Semigroup[Map[K, V]] delega a un Semigroup[V], combinando dos entradas de resultados en la combinación de sus valores, teniendo la consecuencia de que Map[K, List[A]] se comporta como un multimapa:

  scala> Map("foo" -> List(1)) merge Map("foo" -> List(1), "bar" -> List(2))
  res = Map(foo -> List(1, 1), bar -> List(2))

y un Map[K, Int] simplemente totaliza sus contenidos cuando hace la unión

  scala> Map("foo" -> 1) merge Map("foo" -> 1, "bar" -> 2)
  res = Map(foo -> 2, bar -> 2)

.pad y .padWith son para realizar una unión parcial de dos estructuras de datos que puedieran tener valores faltantes en uno de los lados. Por ejemplo si desearamos agregar votos independientes y retener el conocimiento de donde vinieron los votos

  scala> Map("foo" -> 1) pad Map("foo" -> 1, "bar" -> 2)
  res = Map(foo -> (Some(1),Some(1)), bar -> (None,Some(2)))

  scala> Map("foo" -> 1, "bar" -> 2) pad Map("foo" -> 1)
  res = Map(foo -> (Some(1),Some(1)), bar -> (Some(2),None))

Existen variantes convenientes de align que se aprovechan de la estructura de \&/

  ...
    def alignSwap[A, B](a: F[A], b: F[B]): F[B \&/ A] = ...
    def alignA[A, B](a: F[A], b: F[B]): F[Option[A]] = ...
    def alignB[A, B](a: F[A], b: F[B]): F[Option[B]] = ...
    def alignThis[A, B](a: F[A], b: F[B]): F[Option[A]] = ...
    def alignThat[A, B](a: F[A], b: F[B]): F[Option[B]] = ...
    def alignBoth[A, B](a: F[A], b: F[B]): F[Option[(A, B)]] = ...
  }

las cuáles deberían tener sentido a partir de las firmas/signaturas de tipo. Ejemplos:

  scala> List(1,2,3) alignSwap List(4,5)
  res = List(Both(4,1), Both(5,2), That(3))

  scala> List(1,2,3) alignA List(4,5)
  res = List(Some(1), Some(2), Some(3))

  scala> List(1,2,3) alignB List(4,5)
  res = List(Some(4), Some(5), None)

  scala> List(1,2,3) alignThis List(4,5)
  res = List(None, None, Some(3))

  scala> List(1,2,3) alignThat List(4,5)
  res = List(None, None, None)

  scala> List(1,2,3) alignBoth List(4,5)
  res = List(Some((1,4)), Some((2,5)), None)

Note que las variantes A y B usan OR inclusivo, mientras que las variantes This y That son exclusivas, devolviendo None si existe un valor en ambos lados, o ningún valor en algún lado.

5.5 Variancia

Debemos regresar a Functor por un momento y discutir un ancestro que previamente habíamos ignorado:

InvariantFunctor, también conocido como el functor exponencial, tiene un método xmap que dice que dada una función de A a B, y una función de B a A, podemos entonces convertir F[A] a F[B].

Functor es una abreviación de lo que deberíamos llamar functor covariante. Pero dado que Functor es tan popular este conserva la abreviación. De manera similar, Contravariant debería ser llamado functor contravariante.

Functor implementa xmap con map e ignora la función de B a A. Contravariant, por otra parte, implementa xmap con contramap e ignora la función de A a B:

  @typeclass trait InvariantFunctor[F[_]] {
    def xmap[A, B](fa: F[A], f: A => B, g: B => A): F[B]
    ...
  }

  @typeclass trait Functor[F[_]] extends InvariantFunctor[F] {
    def map[A, B](fa: F[A])(f: A => B): F[B]
    def xmap[A, B](fa: F[A], f: A => B, g: B => A): F[B] = map(fa)(f)
    ...
  }

  @typeclass trait Contravariant[F[_]] extends InvariantFunctor[F] {
    def contramap[A, B](fa: F[A])(f: B => A): F[B]
    def xmap[A, B](fa: F[A], f: A => B, g: B => A): F[B] = contramap(fa)(g)
    ...
  }

Es importante notar que, aunque están relacionados a nivel teórico, las palabras covariante, contravariante e invariante no se refieren directamente a la variancia de tipos en Scala (es decir, con los prefijos + y - que pudieran escribirse en las firmas/signaturas de los tipos). Invariancia aquí significa que es posible mapear el contenido de la estructura F[A] en F[B]. Usando la función identidad (identity) podemos ver que A puede convertirse de manera segura en una B dependiendo de la variancia del functor.

.map puede entenderse por medio del contrato “si me das una F de A y una forma de convertir una B en una A, entonces puedo darte una F de B”.

Consideraremos un ejemplo: en nuestra aplicación introducimos tipos específicos del dominio Alpha, Beta, Gamma, etc, para asegurar que no estemos mezclando números en un cálculo financiero:

  final case class Alpha(value: Double)

pero ahora nos encontramos con el problema de que no tenemos ninguna typeclass para estos nuevos tipos. Si usamos los valores en los documentos JSON, entonces tenemos que escribir instancias de JsEncoder y JsDecoder.

Sin embargo, JsEncoder tiene un Contravariant y JsDecoder tiene un Functor, de modo que es posible derivar instancias. Llenando el contrato:

  • “si me das un JsDecoder para un Double, y una manera de ir de un Double a un Alpha, entonces yo puedo darte un JsDecoder para un Alpha”.
  • “si me das un JsEncoder par un Double, y una manera de ir de un Alpha a un Double, entonces yo puedo darte un JsEncoder para un Alpha”.
  object Alpha {
    implicit val decoder: JsDecoder[Alpha] = JsDecoder[Double].map(_.value)
    implicit val encoder: JsEncoder[Alpha] = JsEncoder[Double].contramap(_.value)
  }

Los métodos en una typeclass pueden tener sus parámetros de tipo en posición contravariante (parámetros de método) o en posición covariante (tipo de retorno). Si una typeclass tiene una combinación de posiciones covariantes y contravariantes, tal vez también tenga un functor invariante. Por ejemplo, Semigroup y Monoid tienen un InvariantFunctor, pero no un Functor o un Contravariant.

5.6 Apply y Bind

Considere ésto un calentamiento para Applicative y Monad

5.6.1 Apply

Apply extiende Functor al agregar un método llamado ap que es similar a map en el sentido de que aplica una función a valores. Sin embargo, con ap, la función está en el mismo contexto que los valores.

  @typeclass trait Apply[F[_]] extends Functor[F] {
    @op("<*>") def ap[A, B](fa: =>F[A])(f: =>F[A => B]): F[B]
    ...

Vale la pena tomarse un momento y considerar lo que significa para una estructura de datos simple como Option[A], el que tenga la siguiente implementación de .ap

  implicit def option[A]: Apply[Option[A]] = new Apply[Option[A]] {
    override def ap[A, B](fa: =>Option[A])(f: =>Option[A => B]) = f match {
      case Some(ff) => fa.map(ff)
      case None    => None
    }
    ...
  }

Para implementar .ap primero debemos extraer la función ff: A => B de f: Option[A => B], y entonces podemos mapear sobre fa. La extracción de la función a partir del contexto es el poder importante que Apply tiene, permitiendo que múltiples funciones se combinen dentro del contexto.

Regresando a Apply, encontramos la función auxiliar .applyX que nos permite combinar funciones paralelas y entonces mapear sobre la salida combinada:

  @typeclass trait Apply[F[_]] extends Functor[F] {
    ...
    def apply2[A,B,C](fa: =>F[A], fb: =>F[B])(f: (A, B) => C): F[C] = ...
    def apply3[A,B,C,D](fa: =>F[A],fb: =>F[B],fc: =>F[C])(f: (A,B,C) =>D): F[D] = ...
    ...
    def apply12[...]

Lea .apply2 como un contrato con la promesa siguiente: “si usted me da una F de A y una F de B, con una forma de combinar A y B en una C, entonces puedo devolverle una F de C”. Existen muchos casos de uso para este contrato y los dos más importantes son:

  • construir algunas typeclasses para el tipo producto C a partir de sus constituyentes A y B
  • ejecutar efectos en paralelo, como en las álgebras del drone y de google que creamos en el Capítulo 3, y entonces combinando sus resultados.

En verdad, Apply es tan útil que tiene una sintaxis especial:

  implicit class ApplyOps[F[_]: Apply, A](self: F[A]) {
    def *>[B](fb: F[B]): F[B] = Apply[F].apply2(self,fb)((_,b) => b)
    def <*[B](fb: F[B]): F[A] = Apply[F].apply2(self,fb)((a,_) => a)
    def |@|[B](fb: F[B]): ApplicativeBuilder[F, A, B] = ...
  }

  class ApplicativeBuilder[F[_]: Apply, A, B](a: F[A], b: F[B]) {
    def tupled: F[(A, B)] = Apply[F].apply2(a, b)(Tuple2(_))
    def |@|[C](cc: F[C]): ApplicativeBuilder3[C] = ...

    sealed abstract class ApplicativeBuilder3[C](c: F[C]) {
      ..ApplicativeBuilder4
        ...
          ..ApplicativeBuilder12
  }

que es exactamente lo que se usó en el Capítulo 3:

  (d.getBacklog |@| d.getAgents |@| m.getManaged |@| m.getAlive |@| m.getTime)

La sintaxis <*y *> (el ave hacia la izquierda y hacia la derecha) ofrece una manera conveniente de ignorar la salida de uno de dos efectos paralelos.

Desgraciadamente, aunque la syntaxis con |@| es clara, hay un problema pues se crea un nuevo objeto de tipo ApplicativeBuilder por cada efecto adicional. Si el trabajo es principalmente de naturaleza I/O, el costo de la asignación de memoria es insignificante. Sin embargo, cuando el trabajo es mayormente de naturaleza computacional, es preferible usar la sintaxis alternativa de alzamiento con aridad, que no produce ningún objeto intermedio:

  def ^[F[_]: Apply,A,B,C](fa: =>F[A],fb: =>F[B])(f: (A,B) =>C): F[C] = ...
  def ^^[F[_]: Apply,A,B,C,D](fa: =>F[A],fb: =>F[B],fc: =>F[C])(f: (A,B,C) =>D): F[D] = ...
  ...
  def ^^^^^^[F[_]: Apply, ...]

y se usa así:

  ^^^^(d.getBacklog, d.getAgents, m.getManaged, m.getAlive, m.getTime)

o haga una invocación directa de `applyX

  Apply[F].apply5(d.getBacklog, d.getAgents, m.getManaged, m.getAlive, m.getTime)

A pesar de ser más común su uso con efectos, Applyfunciona también con estructuras de datos. Considere reescribir

  for {
    foo <- data.foo: Option[String]
    bar <- data.bar: Option[Int]
  } yield foo + bar.shows

como

  (data.foo |@| data.bar)(_ + _.shows)

Si nosotros deseamos únicamente la salida combinada como una tupla, existen métodos para hacer sólo eso:

  @op("tuple") def tuple2[A,B](fa: =>F[A],fb: =>F[B]): F[(A,B)] = ...
  def tuple3[A,B,C](fa: =>F[A],fb: =>F[B],fc: =>F[C]): F[(A,B,C)] = ...
  ...
  def tuple12[...]
  (data.foo tuple data.bar) : Option[(String, Int)]

Existen también versiones generalizadas de ap para más de dos parámetros:

  def ap2[A,B,C](fa: =>F[A],fb: =>F[B])(f: F[(A,B) => C]): F[C] = ...
  def ap3[A,B,C,D](fa: =>F[A],fb: =>F[B],fc: =>F[C])(f: F[(A,B,C) => D]): F[D] = ...
  ...
  def ap12[...]

junto con métodos .lift que toman funciones normales y las alzan al contexto F[_], la generalización de Functor.lift

  def lift2[A,B,C](f: (A,B) => C): (F[A],F[B]) => F[C] = ...
  def lift3[A,B,C,D](f: (A,B,C) => D): (F[A],F[B],F[C]) => F[D] = ...
  ...
  def lift12[...]

y .apF, una sintáxis parcialmente aplicada para ap

  def apF[A,B](f: =>F[A => B]): F[A] => F[B] = ...

Finalmente .forever

  def forever[A, B](fa: F[A]): F[B] = ...

que repite el efecto sin detenerse. La instancia de Apply debe tener un uso seguro del stack o tendremos StackOverflowError.

5.6.2 Bind

Bind introduces .bind, que es un sinónimo de .flatMap, que permite funciones sobre el resultado de un efecto regresar un nuevo efecto, o para funciones sobre los valores de una estructura de datos devolver nuevas estructuras de datos que entonces son unidas.

  @typeclass trait Bind[F[_]] extends Apply[F] {

    @op(">>=") def bind[A, B](fa: F[A])(f: A => F[B]): F[B]
    def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B] = bind(fa)(f)

    override def ap[A, B](fa: =>F[A])(f: =>F[A => B]): F[B] =
      bind(f)(x => map(fa)(x))
    override def apply2[A, B, C](fa: =>F[A], fb: =>F[B])(f: (A, B) => C): F[C] =
      bind(fa)(a => map(fb)(b => f(a, b)))

    def join[A](ffa: F[F[A]]): F[A] = bind(ffa)(identity)

    def mproduct[A, B](fa: F[A])(f: A => F[B]): F[(A, B)] = ...
    def ifM[B](value: F[Boolean], t: =>F[B], f: =>F[B]): F[B] = ...

  }

El método .join debe ser familiar a los usuarios de .flatten en la librería estándar, y toma un contexto anidado y lo convierte en uno sólo.

Combinadores derivados se introducen para .ap y .apply2 que requieren consistencia con .bind. Veremos más adelante que esta ley tiene consecuencias para las estrategias de paralelización.

mproduct es como Functor.fproduct y empareja la entrada de una función con su salida, dentro de F.

ifM es una forma de construir una estructura de datos o efecto condicional:

  scala> List(true, false, true).ifM(List(0), List(1, 1))
  res: List[Int] = List(0, 1, 1, 0)

ifM y ap están optimizados para crear un cache y reusar las ramas de código, compare a la forma más larga

  scala> List(true, false, true).flatMap { b => if (b) List(0) else List(1, 1) }

que produce una nueva List(0) o List(1, 1) cada vez que se invoca una alternativa.

Bind también tiene sintaxis especial

  implicit class BindOps[F[_]: Bind, A] (self: F[A]) {
    def >>[B](b: =>F[B]): F[B] = Bind[F].bind(self)(_ => b)
    def >>![B](f: A => F[B]): F[A] = Bind[F].bind(self)(a => f(a).map(_ => a))
  }

>> se usa cuando deseamos descartar la entrada a bind y >>! cuando deseamos ejecutar un efecto pero descartar su salida.

5.7 Applicative y Monad

Desde un punto de vista de funcionalidad, Applicative es Apply con un método pure, y Monad extiende Applicative con Bind.

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

  @typeclass trait Monad[F[_]] extends Applicative[F] with Bind[F]

En muchos sentidos, Applicative y Monad son la culminación de todo lo que hemos visto en este capítulo. .pure (o .point como se conoce más comúnmente para las estructuras de datos) nos permite crear efectos o estructuras de datos a partir de valores.

Las instancias de Applicative deben satisfacer algunas leyes, asegurándose así de que todos los métodos sean consistentes:

  • Identidad: fa <*> pure(identity) === fa, (donde fa está en F[A]) es decir, aplicar pure(identity) no realiza ninguna operación.
  • Homomorfismo: pure(a) <*> pure(ab) === pure(ab(a)) (donde ab es una A => B), es decir aplicar una función pure a un valor pure es lo mismo que aplicar la función al valor y entonces usar pure sobre el resultado.
  • Intercambio: pure(a) <*> fab === fab <*> pure (f => f(a)), (donde fab es una F[A => B]), es decir pure es la identidad por la izquierda y por la derecha.
  • Mapeo: map(fa)(f) === fa <*> pure(f)

Monad agrega leyes adicionales:

  • Identidad por la izquierda: pure(a).bind(f) === f(a)
  • Identidad por la derecha: a.bind(pure(_)) === a
  • Asociatividad: fa.bind(f).bind(g) === fa.bind(a => f(a).bind(g)) donde fa es una F[A], f es una A => F[B] y g es una B => F[C].

La asociatividad dice que invocaciones repetidas de bind deben resultar en lo mismo que invocaciones anidadas de bind. Sin embargo, esto no significa que podamos reordenar, lo que sería conmutatividad. Por ejemplo, recordando que flatMap es un alias de bind, no podemos reordenar

  for {
    _ <- machine.start(node1)
    _ <- machine.stop(node1)
  } yield true

como

  for {
    _ <- machine.stop(node1)
    _ <- machine.start(node1)
  } yield true

start y stop no son conmutativas, porque ¡el efecto deseado de iniciar y luego detener un nodo es diferente a detenerlo y luego iniciarlo!

Pero start es conmutativo consigo mismo, y stop es conmutativo consigo mismo, de modo que podemos reescribir

  for {
    _ <- machine.start(node1)
    _ <- machine.start(node2)
  } yield true

como

  for {
    _ <- machine.start(node2)
    _ <- machine.start(node1)
  } yield true

que son equivalentes para nuestra álgebra, pero no en general. Aquí se están haciendo muchas suposiciones sobre la API de Google Container, pero es una elección razonable que podemos hacer.

Una consecuencia práctica es que una Monad debe ser conmutativa si sus métodos applyX pueden ser ejecutados en paralelo. En el capítulo 3 hicimos trampa cuando ejecutamos estos efectos en paralelo

  (d.getBacklog |@| d.getAgents |@| m.getManaged |@| m.getAlive |@| m.getTime)

porque sabemos que son conmutativos entre sí. Cuando tengamos que interpretar nuestra aplicación, más adelante en el libro, tendremos que proporcionar evidencia de que estos efectos son de hecho conmutativos, o una implementación asíncrona podría escoger efectuar las operaciones de manera secuencial por seguridad.

Las sutilezas de cómo lidiar con el reordenamiento de efectos, y cuáles son estos efectos, merece un capítulo dedicado sobre mónadas avanzadas.

5.8 Divide y conquistarás

Divide es el análogo Contravariant de Apply

  @typeclass trait Divide[F[_]] extends Contravariant[F] {
    def divide[A, B, C](fa: F[A], fb: F[B])(f: C => (A, B)): F[C] = divide2(fa, fb)(f)

    def divide1[A1, Z](a1: F[A1])(f: Z => A1): F[Z] = ...
    def divide2[A, B, C](fa: F[A], fb: F[B])(f: C => (A, B)): F[C] = ...
    ...
    def divide22[...] = ...

divide dice que si podemos partir una C en una A y una B, y se nos da una F[A] y una F[B], entonces podemos tener una F[C]. De ahí la frase divide y conquistarás.

Esta es una gran manera de generar instancias contravariantes de una typeclass para tipos producto mediante la separación de los productos en sus partes constituyentes. Scalaz tiene una instancia de Divide[Equal], así que vamos a construir un Equal para un nuevo tipo producto Foo

  scala> case class Foo(s: String, i: Int)
  scala> implicit val fooEqual: Equal[Foo] =
           Divide[Equal].divide2(Equal[String], Equal[Int]) {
             (foo: Foo) => (foo.s, foo.i)
           }
  scala> Foo("foo", 1) === Foo("bar", 1)
  res: Boolean = false

Siguiendo los patrones en Apply, Divide también tiene una sintaxis clara para las tuplas. Es un enfoque más suave que divide de modo que podamos reinar con el objetivo de dominar el mundo:

  ...
    def tuple2[A1, A2](a1: F[A1], a2: F[A2]): F[(A1, A2)] = ...
    ...
    def tuple22[...] = ...
  }

Generalmente, si las typeclasses de un codificador pueden proporcionar una instancia de Divide, más bien que detenerse en Contravariant, entonces se hace posible la derivación de instancias para cualquier case class. De manera similar, las typeclasses de decodificadores pueden proporcionar una instancia de Apply. Exploraremos esto en un capítulo dedicado a la derivación de typeclasses.

Divisible es el análogo contravariante (Contravariant) de Applicative e introduce .conquer, el equivalente a .pure

  @typeclass trait Divisible[F[_]] extends Divide[F] {
    def conquer[A]: F[A]
  }

.conquer también permite la creación trivial de implementaciones donde el parámetro de tipo es ignorado. Tales valores se llaman universalmente cuantificados. Por ejemplo, Divisible[Equal].conquer[INil[String]] devuelve una implementación de Equal para una lista vacía de String que siempre es true.

5.9 Plus

Plus es un Semigroup pero para constructores de tipo, y PlusEmpty es el equivalente de Monoid (incluso tienen las mismas leyes) mientras que IsEmpty es novedoso y nos permite consultar si un F[A] está vacío:

  @typeclass trait Plus[F[_]] {
    @op("<+>") def plus[A](a: F[A], b: =>F[A]): F[A]
  }
  @typeclass trait PlusEmpty[F[_]] extends Plus[F] {
    def empty[A]: F[A]
  }
  @typeclass trait IsEmpty[F[_]] extends PlusEmpty[F] {
    def isEmpty[A](fa: F[A]): Boolean
  }

Aunque superficialmente pueda parecer como si <+> se comportara como |+|

  scala> List(2,3) |+| List(7)
  res = List(2, 3, 7)

  scala> List(2,3) <+> List(7)
  res = List(2, 3, 7)

es mejor pensar que este operador funciona únicamente al nivel de F[_], nunca viendo al contenido. Plus tiene la convención de que debería ignorar las fallas y “escoger al primer ganador”. <+> puede por lo tanto ser usado como un mecanismo de salida temprana (con pérdida de información) y de manejo de fallas mediante alternativas:

  scala> Option(1) |+| Option(2)
  res = Some(3)

  scala> Option(1) <+> Option(2)
  res = Some(1)

  scala> Option.empty[Int] <+> Option(1)
  res = Some(1)

Por ejemplo, si tenemos una NonEmptyList[Option[Int]] y deseamos ignorar los valores None (fallas) y escoger el primer ganador (Some), podemos invocar <+> de Foldable1.foldRight1:

  scala> NonEmptyList(None, None, Some(1), Some(2), None)
         .foldRight1(_ <+> _)
  res: Option[Int] = Some(1)

De hecho, ahora que sabemos de Plus, nos damos cuenta de que no era necesaria violar la coherencia de typeclases (cuando definimos un Monoid[Option[A]] con alcance local) en la sección sobre Cosas que se pueden agregar. Nuestro objectivo era “escoger el último ganador”, que es lo mismo que “escoge al ganador” si los argumentos se intercambian. Note el uso del interceptor TIE para ccy y otc con los argumentos intercambiados.

  implicit val monoid: Monoid[TradeTemplate] = Monoid.instance(
    (a, b) => TradeTemplate(a.payments |+| b.payments,
                            b.ccy <+> a.ccy,
                            b.otc <+> a.otc),
    TradeTemplate(Nil, None, None)
  )

Applicative y Monad tienen versiones especializadas de PlusEmpty

  @typeclass trait ApplicativePlus[F[_]] extends Applicative[F] with PlusEmpty[F]

  @typeclass trait MonadPlus[F[_]] extends Monad[F] with ApplicativePlus[F] {
    def unite[T[_]: Foldable, A](ts: F[T[A]]): F[A] = ...

    def withFilter[A](fa: F[A])(f: A => Boolean): F[A] = ...
  }

.unite nos permite hacer un fold de una estructura de datos usando el contenedor externo PlusEmpy[F].monoid más bien que el contenido interno Monoid. Para List[Either[String, Int]] esto significa que los valores se convierten en .empty, cuando todo se concatena. Una forma conveniente de descartar los errores:

  scala> List(Right(1), Left("boo"), Right(2)).unite
  res: List[Int] = List(1, 2)

  scala> val boo: Either[String, Int] = Left("boo")
         boo.foldMap(a => a.pure[List])
  res: List[String] = List()

  scala> val n: Either[String, Int] = Right(1)
         n.foldMap(a => a.pure[List])
  res: List[Int] = List(1)

withFilternos permite hacer uso del soporte para for comprehension de Scala, como se discutió en el capítulo 2. Es justo decir que el lenguaje Scala tiene soporte incluído para MonadPlus, no sólo Monad!

Regresando a Foldable por un momento, podemos revelar algunos métodos que no discutimos antes:

  @typeclass trait Foldable[F[_]] {
    ...
    def msuml[G[_]: PlusEmpty, A](fa: F[G[A]]): G[A] = ...
    def collapse[X[_]: ApplicativePlus, A](x: F[A]): X[A] = ...
    ...
  }

msuml realiza un fold utilizando el Monoidde PlusEmpty[G] y collapse realiza un foldRight usando PlusEmpty del tipo target:

  scala> IList(Option(1), Option.empty[Int], Option(2)).fold
  res: Option[Int] = Some(3) // uses Monoid[Option[Int]]

  scala> IList(Option(1), Option.empty[Int], Option(2)).msuml
  res: Option[Int] = Some(1) // uses PlusEmpty[Option].monoid

  scala> IList(1, 2).collapse[Option]
  res: Option[Int] = Some(1)

5.10 Lobos solitarios

Algunas typeclasses en Scalaz existen por sí mismas y no son parte de una jerarquía más grande.

5.10.1 Zippy

  @typeclass trait Zip[F[_]]  {
    def zip[A, B](a: =>F[A], b: =>F[B]): F[(A, B)]

    def zipWith[A, B, C](fa: =>F[A], fb: =>F[B])(f: (A, B) => C)
                        (implicit F: Functor[F]): F[C] = ...

    def ap(implicit F: Functor[F]): Apply[F] = ...

    @op("<*|*>") def apzip[A, B](f: =>F[A] => F[B], a: =>F[A]): F[(A, B)] = ...

  }

El método esencial zip que es una versión menos poderosa que Divide.tuple2, y si un Functor[F] se proporciona entonces zipWithpuede comportarse como Apply.apply2. En verdad, un Apply[F] puede crearse a partir de Zip[F] y un Functor[F] mediante invocar ap.

apzip toma un F[A] y una función elevada de F[A] => F[B], produciendo un F[(A, B)] similar a Functor.fproduct.

  @typeclass trait Unzip[F[_]]  {
    @op("unfzip") def unzip[A, B](a: F[(A, B)]): (F[A], F[B])

    def firsts[A, B](a: F[(A, B)]): F[A] = ...
    def seconds[A, B](a: F[(A, B)]): F[B] = ...

    def unzip3[A, B, C](x: F[(A, (B, C))]): (F[A], F[B], F[C]) = ...
    ...
    def unzip7[A ... H](x: F[(A, (B, ... H))]): ...
  }

El método central es unzip con firsts y seconds que permite elegir ya sea el primer o segundo elemento de una tupla en la F. De manera importante, unzip es lo opuesto de zip.

Los métodos unzip3 a unzip7 son aplicaciones repetidas de unzip para evitar escribir código repetitivo. Por ejemplo, si se le proporcionara un conjunto de tuplas anidadas, el Unzip[Id] es una manera sencilla de deshacer la anidación:

  scala> Unzip[Id].unzip7((1, (2, (3, (4, (5, (6, 7)))))))
  res = (1,2,3,4,5,6,7)

En resumen, Zip y Unzip son versiones menos poderosas de Divide y Apply, y proporcionan características poderosas sin requerir que F haga demasiadas promesas.

5.10.2 Optional

Optional es una generalización de estructuras de datos que opcionalmente pueden contener un valor, como Option y Either.

Recuerde que una \/ (disjunción) es la versión mejorada de Scalaz de Scalaz.Either. También veremos Maybe de Scalaz, que es la versión mejorada de scala.Option.

  sealed abstract class Maybe[A]
  final case class Empty[A]()    extends Maybe[A]
  final case class Just[A](a: A) extends Maybe[A]
  @typeclass trait Optional[F[_]] {
    def pextract[B, A](fa: F[A]): F[B] \/ A

    def getOrElse[A](fa: F[A])(default: =>A): A = ...
    def orElse[A](fa: F[A])(alt: =>F[A]): F[A] = ...

    def isDefined[A](fa: F[A]): Boolean = ...
    def nonEmpty[A](fa: F[A]): Boolean = ...
    def isEmpty[A](fa: F[A]): Boolean = ...

    def toOption[A](fa: F[A]): Option[A] = ...
    def toMaybe[A](fa: F[A]): Maybe[A] = ...
  }

Estos métodos le deberían ser familiares, con la excepción, quizá, de pextract, que es una forma de dejar que F[_] regrese una implementación específica F[B] o el valor. Por ejemplo, Optional[Option].pextract devuelve Option[Nothing] \/ A, es decir, None \/ A.

Scalaz proporciona un operador ternario para las cosas que tienen un Optional

  implicit class OptionalOps[F[_]: Optional, A](fa: F[A]) {
    def ?[X](some: =>X): Conditional[X] = new Conditional[X](some)
    final class Conditional[X](some: =>X) {
      def |(none: =>X): X = if (Optional[F].isDefined(fa)) some else none
    }
  }

por ejemplo

  scala> val knock_knock: Option[String] = ...
         knock_knock ? "who's there?" | "<tumbleweed>"

5.11 Co-cosa

Una co-cosa típicamente tiene la firma/signatura de tipo opuesta a lo que sea que una cosa hace, pero no necesariamente a la inversa. Para enfatizar la relación entre una cosa y una co-cosa, incluiremos la firma/signatura de la cosa siempre que sea posible.

5.11.1 Cobind

  @typeclass trait Cobind[F[_]] extends Functor[F] {
    def cobind[A, B](fa: F[A])(f: F[A] => B): F[B]
  //def   bind[A, B](fa: F[A])(f: A => F[B]): F[B]

    def cojoin[A](fa: F[A]): F[F[A]] = ...
  //def   join[A](ffa: F[F[A]]): F[A] = ...
  }

cobind (también conocido como coflatmap) toma una F[A] => B que actúa en una F[A] más bien que sobre sus elementos. Pero no se trata necesariamente de una fa completa, es con frecuencia alguna subestructura como la define un cojoin (también conocida como coflatten) que expande una estructura de datos.

Los casos de uso interesantes para Cobind son raros, aunque cuando son mostrados en la tabla de permutación de la tabla Functor (para F[_], A, y B) es difícil discutir porqué cualquier método debería ser menos importante que los otros:

método parámetro
map A => B
contramap B => A
xmap (A => B, B => A)
ap F[A => B]
bind A => F[B]
cobind F[A] => B

5.11.2 Comonad

  @typeclass trait Comonad[F[_]] extends Cobind[F] {
    def copoint[A](p: F[A]): A
  //def   point[A](a: =>A): F[A]
  }

.copoint (también coonocido como .copure) desenvuelve un elemento de su contexto. Los efectos no tienen típicamente una instancia de Comonad dado que se violaría la transparencia referencial al interpretar una IO[A] en una A. Pero para estructuras de datos similares a colecciones, es una forma de construir una vista de todos los elementos al mismo tiempo que de su vecindad.

Considere la vecindad de una lista que contiene todos los elementos a la izquierda de un elemento (lefts), el elemento en sí mismo (el focus), y todos los elementos a su derecha (rights).

  final case class Hood[A](lefts: IList[A], focus: A, rights: IList[A])

Los lefts y los rights deberían ordenarse con el elemento más cercano al focus en la cabeza, de modo que sea posible recuperar la lista original IList por medio de .toList.

  object Hood {
    implicit class Ops[A](hood: Hood[A]) {
      def toIList: IList[A] = hood.lefts.reverse ::: hood.focus :: hood.rights

Podemos escribir métodos que nos dejen mover el foco una posición a la izquierda (previous), y una posición a la derecha (next)

  ...
      def previous: Maybe[Hood[A]] = hood.lefts match {
        case INil() => Empty()
        case ICons(head, tail) =>
          Just(Hood(tail, head, hood.focus :: hood.rights))
      }
      def next: Maybe[Hood[A]] = hood.rights match {
        case INil() => Empty()
        case ICons(head, tail) =>
          Just(Hood(hood.focus :: hood.lefts, head, tail))
      }

Mediante la introducción de more para aplicar repetidamente una función opcional a Hood podemos calcular todas las positions (posiciones) que Hood puede tomar en la lista

  ...
      def more(f: Hood[A] => Maybe[Hood[A]]): IList[Hood[A]] =
        f(hood) match {
          case Empty() => INil()
          case Just(r) => ICons(r, r.more(f))
        }
      def positions: Hood[Hood[A]] = {
        val left  = hood.more(_.previous)
        val right = hood.more(_.next)
        Hood(left, hood, right)
      }
    }

Ahora podemos implementar una Comonad[Hood]

  ...
    implicit val comonad: Comonad[Hood] = new Comonad[Hood] {
      def map[A, B](fa: Hood[A])(f: A => B): Hood[B] =
        Hood(fa.lefts.map(f), f(fa.focus), fa.rights.map(f))
      def cobind[A, B](fa: Hood[A])(f: Hood[A] => B): Hood[B] =
        fa.positions.map(f)
      def copoint[A](fa: Hood[A]): A = fa.focus
    }
  }

cojoin nos da proporciona una Hood[Hood[IList]] que contiene todas las posibles vecindades en nuestra IList.

  scala> val middle = Hood(IList(4, 3, 2, 1), 5, IList(6, 7, 8, 9))
  scala> middle.cojoin
  res = Hood(
          [Hood([3,2,1],4,[5,6,7,8,9]),
           Hood([2,1],3,[4,5,6,7,8,9]),
           Hood([1],2,[3,4,5,6,7,8,9]),
           Hood([],1,[2,3,4,5,6,7,8,9])],
          Hood([4,3,2,1],5,[6,7,8,9]),
          [Hood([5,4,3,2,1],6,[7,8,9]),
           Hood([6,5,4,3,2,1],7,[8,9]),
           Hood([7,6,5,4,3,2,1],8,[9]),
           Hood([8,7,6,5,4,3,2,1],9,[])])

En verdad, ¡cojoin es simplemente positions! Podríamos hacer un override con una implementación más directa y eficiente

  override def cojoin[A](fa: Hood[A]): Hood[Hood[A]] = fa.positions

Comonad generaliza el concepto de Hood a estructuras de datos arbitrarias. Hood es un ejemplo de un zipper (que no está relacionado a Zip). Scalaz viene con un tipo de datos Zipper para los streams (es decir , estructuras de datos infinitas unidimensionales), que discutiremos en el siguiente capítulo.

Una aplicación de zipper es para automatas celulares, que calculan el valor de cada celda en la siguiente generación mediante realizar un cómputo basándose en la vecindad de dicha celda.

5.11.3 Cozip

  @typeclass trait Cozip[F[_]] {
    def cozip[A, B](x: F[A \/ B]): F[A] \/ F[B]
  //def   zip[A, B](a: =>F[A], b: =>F[B]): F[(A, B)]
  //def unzip[A, B](a: F[(A, B)]): (F[A], F[B])

    def cozip3[A, B, C](x: F[A \/ (B \/ C)]): F[A] \/ (F[B] \/ F[C]) = ...
    ...
    def cozip7[A ... H](x: F[(A \/ (... H))]): F[A] \/ (... F[H]) = ...
  }

Aunque se llame cozip, quizá es más apropiado enfocar nuestra atención en su simetría con unzip. Mientras que unzip divide F[_] de tuplas (productos) en tuplas de F[_], cozip divide F[_] de disjunciones (coproductos) en disjunciones de F[_].

5.12 Bi-cosas

Algunas veces podríamos encontrar una cosa que tiene dos hoyos de tipo y deseemos realizar un map en ambos lados. Por ejemplo, podríamos estar rastreando las fallas a la izquierda de un Either y tal vez querríamos hacer algo con los mensajes de error.

La typeclass Functor/Foldable/Traverse tienen parientes extraños que nos permiten hacer un mapeo de ambas maneras.

  @typeclass trait Bifunctor[F[_, _]] {
    def bimap[A, B, C, D](fab: F[A, B])(f: A => C, g: B => D): F[C, D]

    @op("<-:") def leftMap[A, B, C](fab: F[A, B])(f: A => C): F[C, B] = ...
    @op(":->") def rightMap[A, B, D](fab: F[A, B])(g: B => D): F[A, D] = ...
    @op("<:>") def umap[A, B](faa: F[A, A])(f: A => B): F[B, B] = ...
  }

  @typeclass trait Bifoldable[F[_, _]] {
    def bifoldMap[A, B, M: Monoid](fa: F[A, B])(f: A => M)(g: B => M): M

    def bifoldRight[A,B,C](fa: F[A, B], z: =>C)(f: (A, =>C) => C)(g: (B, =>C) => C): C
    def bifoldLeft[A,B,C](fa: F[A, B], z: C)(f: (C, A) => C)(g: (C, B) => C): C = ...

    def bifoldMap1[A, B, M: Semigroup](fa: F[A,B])(f: A => M)(g: B => M): Option[M] = ...
  }

  @typeclass trait Bitraverse[F[_, _]] extends Bifunctor[F] with Bifoldable[F] {
    def bitraverse[G[_]: Applicative, A, B, C, D](fab: F[A, B])
                                                 (f: A => G[C])
                                                 (g: B => G[D]): G[F[C, D]]

    def bisequence[G[_]: Applicative, A, B](x: F[G[A], G[B]]): G[F[A, B]] = ...
  }

Aunque las signaturas de tipo son verbosas, no son más que los métodos esenciales de Functor, Foldable, y Bitraverse que toman dos funciones en vez de una sola, con frecuencia requiriendo que ambas funciones devuelvan el mismo tipo de modo que sus resultados puedan ser combinados con un Monoid o un Semigroup.

  scala> val a: Either[String, Int] = Left("fail")
         val b: Either[String, Int] = Right(13)

  scala> b.bimap(_.toUpperCase, _ * 2)
  res: Either[String, Int] = Right(26)

  scala> a.bimap(_.toUpperCase, _ * 2)
  res: Either[String, Int] = Left(FAIL)

  scala> b :-> (_ * 2)
  res: Either[String,Int] = Right(26)

  scala> a :-> (_ * 2)
  res: Either[String, Int] = Left(fail)

  scala> { s: String => s.length } <-: a
  res: Either[Int, Int] = Left(4)

  scala> a.bifoldMap(_.length)(identity)
  res: Int = 4

  scala> b.bitraverse(s => Future(s.length), i => Future(i))
  res: Future[Either[Int, Int]] = Future(<not completed>)

Adicionalmente, podemos revisitar MonadPlus (recuerde que se trata de un Monad con la habilidad extra de realizar un filterWith y unite) y ver que puede separar el contenido Bifoldable de un Monad.

  @typeclass trait MonadPlus[F[_]] {
    ...
    def separate[G[_, _]: Bifoldable, A, B](value: F[G[A, B]]): (F[A], F[B]) = ...
    ...
  }

Esto es muy útil se tenemos una colección de bi-cosas y desamos reorganizarlas en una colección de\ A y una colección de B.

  scala> val list: List[Either[Int, String]] =
           List(Right("hello"), Left(1), Left(2), Right("world"))

  scala> list.separate
  res: (List[Int], List[String]) = (List(1, 2), List(hello, world))

5.13 Resumen

!Esto fue bastante material! Hemos apenas explorado la librería estándar de funcionalidad polimórfica. Pero para poner el asunto en perspectiva: hay más traits en la API de collecciones de la librería estándar de Scala que typeclasses en Scalaz.

Es normal que una aplicación de PF usar un porcentaje pequeño de la jerarquía de tipos, con la mayoría de su funcionalidad viniendo de álgebras particulares del dominio y de typeclasses. Inclusive si las typeclasses del dominio específico son simples clones especializados de algo que ya existe en Scalaz, está bien refactorizarlo después.

Para ayudar al lector, hemos incluído un sumario de las typeclasses y sus métodos primarios en el apéndice, tomando inspiración del sumario cuyo autor es Adam Rosien’s: Scalaz Cheatsheet.

Para ayudarle, Valentin Kasas explica cómo combinar Ncosas:

6. Tipos de datos de Scalaz

¿Quién no ama una buena estructura de datos? La respuesta es nadie, porque las estructuras de datos son increíbles.

En este capítulo exploraremos los tipos de datos en Scalaz que son similares a colecciones, así como los tipos de datos que aumentan Scala, como lenguaje, con semántica y seguridad de tipos adicional.

La razón principal por la que nos preocupamos por tener muchas colecciones a nuestra disposición es por rendimiento. Un vector y una lista pueden hacer lo mismo, pero sus características son diferentes: un vector tiene un costo de búsqueda constante mientras que una lista debe ser recorrida.

Todas las colecciones presentadas aquí son persistentes: si agregamos o removemos un elemento todavía podemos usar la versión anterior. Compartir estructuralmente es esencial para el rendimiento de las estructuras de datos persistentes, de otra manera la colección entera se reconstruye con cada operación.

A diferencia de las colecciones de Java y Scala, no hay jerarquía de datos en Scalaz: estas colecciones son mucho más simples de entender. La funcionalidad polimórfica se proporciona por instancias opmitizadas de typeclases que estudiamos en el capítulo anterior. Esto simplifica cambiar implementaciones por razones de rendimiento, y proporcionar la propia.

6.1 Variancia de tipo

Muchos de los tipos de datos de Scalaz son invariantes en sus parámetros de tipo. Por ejemplo, IList[A] no es un subtipo de IList[B] cuando A <: B.

6.1.1 Covariancia

El problema con los tipos de parámetro covariantes, tales como class List[+A], es que List[A] es un subtipo de List[Any] y es fácil perder accidentalmente información de tipo.

  scala> List("hello") ++ List(' ') ++ List("world!")
  res: List[Any] = List(hello,  , world!)

Note que la segunda lista es una List[Char] y que el compilador ha inferido incorrectamente el LUB (Least Upper Bound, o límite mínimo inferior) es Any. Compare con IList, que requiere una aplicación explícita de .widen[Any] para ejecutar el crimen atroz:

  scala> IList("hello") ++ IList(' ') ++ IList("world!")
  <console>:35: error: type mismatch;
   found   : Char(' ')
   required: String

  scala> IList("hello").widen[Any]
           ++ IList(' ').widen[Any]
           ++ IList("world!").widen[Any]
  res: IList[Any] = [hello, ,world!]

De manera similar, cuando el compilador infiere el tipo como with Product with Serializable es un indicador fuerte de que un ensanchamiento accidental ha ocurrido debido a la covariancia.

Desafortunadamente debemos ser cuidadosos cuando construimos tipos de datos invariantes debido a que los cálculos LUB se realizan sobre los parámetros:

  scala> IList("hello", ' ', "world")
  res: IList[Any] = [hello, ,world]

Otro problema similar surge a partir del tipo Nothing, el cuál es un subtipo del resto de tipos, incluyendo ADTs selladas (sealed), clases finales (final), primitivas y null.

No hay valores de tipo Nothing: las funciones que toman un Nothing como un parámetro no pueden ejecutarse y las funciones que devuelven Nothing nunca devuelven un valor (o terminan). Nothing fue introducido como un mecanismo para habilitar los tipos de parámetros covariantes, pero una consecuencia es que podemos escribir código que no puede ejecutarse, por accidente. Scalaz dice que no necesitamos parámetros de tipo covariantes lo que significa que nos estamos limitando a nosotros mismos a escribir código práctico que puede ser ejecutado.

6.1.2 Contrarivarianza

Por otro lado, los tipos de parámetro contravariantes, tales como trait Thing[-A] pueden poner de manifiesto errores devastadores en el compilador. Considere la demostración de Paul Phillips’ (ex miembro del equipo del compilador scalac) de lo que él llama contrarivarianza:

  scala> :paste
         trait Thing[-A]
         def f(x: Thing[ Seq[Int]]): Byte   = 1
         def f(x: Thing[List[Int]]): Short  = 2

  scala> f(new Thing[ Seq[Int]] { })
         f(new Thing[List[Int]] { })

  res = 1
  res = 2

Como era de esperarse, el compilador está encontrando el argumento más específico en cada invocación de f. Sin embargo, la resolución implícita da resultados inesperados:

  scala> :paste
         implicit val t1: Thing[ Seq[Int]] =
           new Thing[ Seq[Int]] { override def toString = "1" }
         implicit val t2: Thing[List[Int]] =
           new Thing[List[Int]] { override def toString = "2" }

  scala> implicitly[Thing[ Seq[Int]]]
         implicitly[Thing[List[Int]]]

  res = 1
  res = 1

La resolución implícita hace un intercambio de su definición de “más específico” para los tipos contravariantes, logrando que sean inútiles para los typeclases o para cualquier cosa que requiera funcionalidad polimórfica. Este comportamiento es fijo en Dotty.

6.1.3 Las limitaciones del mecanismo de subclases

scala.Option tiene un método .flatten que los dejará convertir Option[Option[B]] en un Option[B]. Sin embargo, el sistema de tipos de Scala es incapaz de dejarnos escribir la signatura de tipos requerida. Considere lo siguiente que parece correcto, pero que tiene un error sutil:

  sealed abstract class Option[+A] {
    def flatten[B, A <: Option[B]]: Option[B] = ...
  }

The A introducida en .flatten está ocultando la A introducida por la clase. Es equivalente a escribir

  sealed abstract class Option[+A] {
    def flatten[B, C <: Option[B]]: Option[B] = ...
  }

que no es la restricción deseada.

Para resolver esta limitación, Scala define clases infijas <:< y =:= junto con la evidencia implícita que siempre crea un testigo (witness).

  sealed abstract class <:<[-From, +To] extends (From => To)
  implicit def conforms[A]: A <:< A = new <:<[A, A] { def apply(x: A): A = x }

  sealed abstract class =:=[ From,  To] extends (From => To)
  implicit def tpEquals[A]: A =:= A = new =:=[A, A] { def apply(x: A): A = x }

=:= puede usarse para requerir que dos parámetros de tipo sean exactamente iguales y <:< se usa para describir relaciones de subtipo, dejandonos implementar .flatten como

  sealed abstract class Option[+A] {
    def flatten[B](implicit ev: A <:< Option[B]): Option[B] = this match {
      case None        => None
      case Some(value) => ev(value)
    }
  }
  final case class Some[+A](value: A) extends Option[A]
  case object None                    extends Option[Nothing]

Scalaz mejora sobre <:< y =:= con Liskov (que tiene el alias <~<) y Leibniz (====).

  sealed abstract class Liskov[-A, +B] {
    def apply(a: A): B = ...
    def subst[F[-_]](p: F[B]): F[A]

    def andThen[C](that: Liskov[B, C]): Liskov[A, C] = ...
    def onF[X](fa: X => A): X => B = ...
    ...
  }
  object Liskov {
    type <~<[-A, +B] = Liskov[A, B]
    type >~>[+B, -A] = Liskov[A, B]

    implicit def refl[A]: (A <~< A) = ...
    implicit def isa[A, B >: A]: A <~< B = ...

    implicit def witness[A, B](lt: A <~< B): A => B = ...
    ...
  }

  // type signatures have been simplified
  sealed abstract class Leibniz[A, B] {
    def apply(a: A): B = ...
    def subst[F[_]](p: F[A]): F[B]

    def flip: Leibniz[B, A] = ...
    def andThen[C](that: Leibniz[B, C]): Leibniz[A, C] = ...
    def onF[X](fa: X => A): X => B = ...
    ...
  }
  object Leibniz {
    type ===[A, B] = Leibniz[A, B]

    implicit def refl[A]: Leibniz[A, A] = ...

    implicit def subst[A, B](a: A)(implicit f: A === B): B = ...
    implicit def witness[A, B](f: A === B): A => B = ...
    ...
  }

Además de los métodos generalmente útiles y las conversiones implícitas, la evidencia de Scalaz <~< y === usa mejores principios que en la librería estándar.

6.2 Evaluación

Java es un lenguaje con evaluación estricta: todos los parámetros para un método deben evaluarse a un valor antes de llamar el método. Scala introduce la noción de parámetros por nombre (by-name) en los métodos con la sintaxis a: => A. Estos parámetros se envuelven en una finción de cero argumentos que se invoca cada vez que se referencia la a. Hemos visto por nombre muchas veces en las typeclases.

Scala también tiene por necesidad (by-need), con la palabra lazy: el cómputo se evalúa a lo sumo una vez para producir el valor. Desgraciadamente, Scala no soporta la evaluación por necesidad de los parámetros del método.

Scalaz formaliza los tres estrategias de evaluación con un ADT

  sealed abstract class Name[A] {
    def value: A
  }
  object Name {
    def apply[A](a: =>A) = new Name[A] { def value = a }
    ...
  }

  sealed abstract class Need[A] extends Name[A]
  object Need {
    def apply[A](a: =>A): Need[A] = new Need[A] {
      private lazy val value0: A = a
      def value = value0
    }
    ...
  }

  final case class Value[A](value: A) extends Need[A]

La forma de evaluación más débil es Name, que no proporciona garantías computacionales. A continuación está Need, que garantiza la evaluación como máximo una vez.

Si deseamos ser super escrupulosos podríamos revisar todas las typeclases y hacer sus métodos tomar parámetros por Name, Need o Value. En vez de esto, podemos asumir que los parámetros normales siempre pueden envolverse en un Value, y que los parámetros (by-name) por nombre pueden envolverse con Name.

Cuando escribimos programas puros, somos libres de reemplazar cualquier Name con Need o Value, y viceversa, sin necesidad de cambiar lo correcto del programa. Esta es la esencia de la transparencia referencial: la habilidad de cambiar un cómputo por su valor, o un valor por su respectivo cómputo.

En la programación funcional casi siempre deseamos Value o Need (también conocido como estricto y perezoso): hay poco valor en Name. Debido a que no hay soporte a nivel de lenguaje para parámetros de método perezosos, los métodos típicamente solicitan un parámetro por nombre y entonces lo convierten a Need de manera interna, proporcionando un aumento en el rendimiento.

Name proporciona instancias de las siguientes typeclases

  • Monad
  • Comonad
  • Traverse1
  • Align
  • Zip / Unzip / Cozip

6.3 Memoisation

Scalaz tiene la capacidad de memoizar funciones, formalizada por Memo, que no hace ninguna garantía sobre la evaluación debido a la diversidad de implementaciones:

  sealed abstract class Memo[K, V] {
    def apply(z: K => V): K => V
  }
  object Memo {
    def memo[K, V](f: (K => V) => K => V): Memo[K, V]

    def nilMemo[K, V]: Memo[K, V] = memo[K, V](identity)

    def arrayMemo[V >: Null : ClassTag](n: Int): Memo[Int, V] = ...
    def doubleArrayMemo(n: Int, sentinel: Double = 0.0): Memo[Int, Double] = ...

    def immutableHashMapMemo[K, V]: Memo[K, V] = ...
    def immutableTreeMapMemo[K: scala.Ordering, V]: Memo[K, V] = ...
  }

memo nos permite crear implementaciones de Memo, nilMemo no memoiza, evaluando la función normalmente. Las implementaciones resultantes interceptan llamadas a la función y guardan en cache los resultados obtenidos en una implementación que usa colecciones de la librería estándar.

Para usar Memo simplemente envolvemos una función con una implementación de Memo y entonces invocamos a la función memoizada:

  scala> def foo(n: Int): String = {
           println("running")
           if (n > 10) "wibble" else "wobble"
         }

  scala> val mem = Memo.arrayMemo[String](100)
         val mfoo = mem(foo)

  scala> mfoo(1)
  running // evaluated
  res: String = wobble

  scala> mfoo(1)
  res: String = wobble // memoised

Si la función toma más de un parámetro, entonces debemos invocar .tupled sobre el método, con la versión memoisada tomando una tupla.

  scala> def bar(n: Int, m: Int): String = "hello"
         val mem = Memo.immutableHashMapMemo[(Int, Int), String]
         val mbar = mem((bar _).tupled)

  scala> mbar((1, 2))
  res: String = "hello"

Memo típicamente se trata como un artificio especial y la regla usual sobre la pureza se relaja para las implementaciones. La pureza únicamente requiere que nuestras implementaciones de Memo sean referencialmente transparentes en la evaluación de K => V. Podríamos usar datos mutables y realizar I/O en la implementación de Memo, por ejemplo usando un LRU o un caché distribuido, sin tener que declarar un efecto en las signaturas de tipo. Otros lenguajes de programación funcional tienen memoización manejada por el ambiente de runtime y Memo es nuestra manera de extender la JVM para tener un soporte similar, aunque desgraciadamente únicamente de una manera que requiere opt-in.

6.4 Tagging (etiquetar)

En la sección que se introdujo Monoid construimos un Monoid[TradeTeamplate] y nos dimos cuenta de que Scalaz no hace lo que desearíamos con Monoid[Option[A]]. Este no es una omisión de Scalaz, con frecuencia podemos notar que un tipo de datos puede implementar una tipeclass fundamental en múltiples formas válidas y que la implementación por default no hace lo que deseariamos, o simplemente no está definida.

Los ejemplos básicos son Monoid[Boolean] (la conjunción && vs la disjunción ||) y Monoid[Int] (multiplicación vs adición).

Para implementar Monoid[TradeTemplate] tuvimos que romper la coherencia de typeclases, o usar una typeclass distinta.

scalaz.Tag está diseñada para lidiar con el problema de coherencia que surge con múltiples implementaciones de typeclases, sin romper la coherencia de las typeclases.

La definición es algo compleja, pero la sintáxis al usar scalaz.Tag es bastante limpia. Así es como logramos convencer al compilador para que nos permita definir el tipo infijo A @@ T que es borrado en A en tiempo de ejecución:

  type @@[A, T] = Tag.k.@@[A, T]

  object Tag {
    @inline val k: TagKind = IdTagKind
    @inline def apply[A, T](a: A): A @@ T = k(a)
    ...

    final class TagOf[T] private[Tag]() { ... }
    def of[T]: TagOf[T] = new TagOf[T]
  }
  sealed abstract class TagKind {
    type @@[A, T]
    def apply[A, T](a: A): A @@ T
    ...
  }
  private[scalaz] object IdTagKind extends TagKind {
    type @@[A, T] = A
    @inline override def apply[A, T](a: A): A = a
    ...
  }

Algunas etiquetas/tags útiles se proporcionan en el objeto Tags

  object Tags {
    sealed trait First
    val First = Tag.of[First]

    sealed trait Last
    val Last = Tag.of[Last]

    sealed trait Multiplication
    val Multiplication = Tag.of[Multiplication]

    sealed trait Disjunction
    val Disjunction = Tag.of[Disjunction]

    sealed trait Conjunction
    val Conjunction = Tag.of[Conjunction]

    ...
  }

First/Last se usan para seleccionar instancias d Monoid que escogen el primero o el último (diferente de cero) operando. Multiplication es para multiplicación numérica en vez de adición. Disjunction/Conjuntion son para seleccionar && o ||, respectivamente.

En nuestro TradeTemplate, en lugar de usar Option[Currency] podríamos usar Option[Currency] @@ Tags.Last. En verdad, este uso es tan común que podemos usar el alias previamente definido, LastOption.

  type LastOption[A] = Option[A] @@ Tags.Last

y esto nos permite escribir una implementación mucho más limpia de Monoid[TradeTemplate]

  final case class TradeTemplate(
    payments: List[java.time.LocalDate],
    ccy: LastOption[Currency],
    otc: LastOption[Boolean]
  )
  object TradeTemplate {
    implicit val monoid: Monoid[TradeTemplate] = Monoid.instance(
      (a, b) =>
        TradeTemplate(a.payments |+| b.payments,
                      a.ccy |+| b.ccy,
                      a.otc |+| b.otc),
        TradeTemplate(Nil, Tag(None), Tag(None))
    )
  }

Para crear un valor de tipo LastOption, aplicamos Tag a un Option. Aquí estamos invocando Tag(None).

En el capítulo sobre derivación de typeclases, iremos un paso más allá y derivaremos automáticamente el monoid.

Es tentador usar Tag para marcar tipos de datos para alguna forma de validación (por ejemplo, String @@ PersonName), pero deberíamos evitar esto porque no existe un chequeo del contenido en tiempo de ejecución. Tag únicamente debería ser usado para propósitos de selección de typeclases. Prefiera el uso de la librería Refined, que se introdujo en el Capítulo 4, para restringir valores.

6.5 Transformaciones naturales

Una función de un tipo a otro se escribe en Scala como A => B, y se trata de una conveniencia sintáctica para Function1[A, B]. Scalaz proporciona una conveniencia sintáctica F ~> G para funciones sobre los constructores de tipo F[_] a G[_].

Esta notación, F ~ G, se conoce como transformación natural y son universalmente cuantificables debido a que no nos importa el contenido de F[_].

  type ~>[-F[_], +G[_]] = NaturalTransformation[F, G]
  trait NaturalTransformation[-F[_], +G[_]] {
    def apply[A](fa: F[A]): G[A]

    def compose[E[_]](f: E ~> F): E ~> G = ...
    def andThen[H[_]](f: G ~> H): F ~> H = ...
  }

Un ejemplo de una transformación natural es la función que convierte una IList en una List.

  scala> val convert = new (IList ~> List) {
           def apply[A](fa: IList[A]): List[A] = fa.toList
         }

  scala> convert(IList(1, 2, 3))
  res: List[Int] = List(1, 2, 3)

O, de manera más concisa, usando las conveniencias sintácticas proporcionadas por el plugin kind-projector:

  scala> val convert = λ[IList ~> List](_.toList)

  scala> val convert = Lambda[IList ~> List](_.toList)

Sin embargo, en el desarrollo del día a día, es mucho más probable que usemos una transformación natural para mapear entre álgebras. Por ejemplo, en drone-dynamic-agents tal vez deseemos implementar nuestra álgebra de Machines que usa Google Container Engine con una álgebra ad-hoc, BigMachines. En lugar de cambiar toda nuestra lógica de negocio y probar usando esta nueva interfaz BigMachines, podríamos escribir una transformación natural de Machines ~> BigMachines. Volveremos a esta idea en el capítulo de Mónadas Avanzadas.

6.6 Isomorphism (isomorfismos)

Algunas veces tenemos dos tipos que en realidad son equivalentes (la misma cosa), lo que ocasiona problemas de compatibiliad debido a que el compilador no sabe lo que nosotros sí sabemos. Esto pasa típicamente cuando usamos código de terceros que tiene algo que ya tenemos.

Ahí es cuando Isomorphism nos puede ayudar. Un isomorfismo define una relación formal “es equivalente a” entre dos tipos. Existen tres variantes, para

  object Isomorphism {
    trait Iso[Arr[_, _], A, B] {
      def to: Arr[A, B]
      def from: Arr[B, A]
    }
    type IsoSet[A, B] = Iso[Function1, A, B]
    type <=>[A, B] = IsoSet[A, B]
    object IsoSet {
      def apply[A, B](to: A => B, from: B => A): A <=> B = ...
    }

    trait Iso2[Arr[_[_], _[_]], F[_], G[_]] {
      def to: Arr[F, G]
      def from: Arr[G, F]
    }
    type IsoFunctor[F[_], G[_]] = Iso2[NaturalTransformation, F, G]
    type <~>[F[_], G[_]] = IsoFunctor[F, G]
    object IsoFunctor {
      def apply[F[_], G[_]](to: F ~> G, from: G ~> F): F <~> G = ...
    }

    trait Iso3[Arr[_[_, _], _[_, _]], F[_, _], G[_, _]] {
      def to: Arr[F, G]
      def from: Arr[G, F]
    }
    type IsoBifunctor[F[_, _], G[_, _]] = Iso3[~~>, F, G]
    type <~~>[F[_, _], G[_, _]] = IsoBifunctor[F, G]

    ...
  }

Los aliases de tipos IsoSet, IsoFunctor e IsoBifunctor cubren los casos comunes: una función regular, una transformación natural y binatural. Las funciones de conveniencia nos permiten generar instancias de funciones existentes o transformaciones naturales. Sin embargo, con frecuencia es más fácil usar una de las clases abstractas Template para definir un isomorfismo. Por ejemplo:

  val listIListIso: List <~> IList =
    new IsoFunctorTemplate[List, IList] {
      def to[A](fa: List[A]) = fromList(fa)
      def from[A](fa: IList[A]) = fa.toList
    }

Si introducimos un isomorfismo, con frecuencia podemos generar muchas de las typeclases estándar. Por ejemplo,

  trait IsomorphismSemigroup[F, G] extends Semigroup[F] {
    implicit def G: Semigroup[G]
    def iso: F <=> G
    def append(f1: F, f2: =>F): F = iso.from(G.append(iso.to(f1), iso.to(f2)))
  }

lo que nos permite derivar un Semigroup[F] para un tipo F si ya tenemos un isomorfismo F <=> G y un semigrupo Semigroup[G]. Casi todas las typeclases en la jerarquía proporcionan una invariante isomórfica. Si nos encontramos en la situación en la que copiamos y pegamos una implementación de una typeclass, es útil considerar si Isomorphism es una mejor solución.

6.7 Contenedores

6.7.1 Maybe

Ya nos hemos encontrado con la mejora de Scalaz sobre scala.Option, que se llama Maybe. Es una mejora porque es invariante y no tiene ningún método inseguro como Option.get, el cual puede lanzar una excepción.

Con frecuencia se usa para representar una cosa que puede o no estar presente sin proporcionar ninguna información adicional de porqué falta información.

  sealed abstract class Maybe[A] { ... }
  object Maybe {
    final case class Empty[A]()    extends Maybe[A]
    final case class Just[A](a: A) extends Maybe[A]

    def empty[A]: Maybe[A] = Empty()
    def just[A](a: A): Maybe[A] = Just(a)

    def fromOption[A](oa: Option[A]): Maybe[A] = ...
    def fromNullable[A](a: A): Maybe[A] = if (null == a) empty else just(a)
    ...
  }

Los métodos .empty y .just en el objeto compañero son preferidas en lugar de usar Empty o Just debido a que regresan Maybe, ayudándonos con la inferencia de tipos. Este patrón con frecuencia es preferido a regresar un tipo suma, que es cuando tenemos múltiples implementaciones de un sealed trait pero nunca usamos un subtipo específico en una signatura de método.

Una clase implícita conveniente nos permite invocar.just sobre cualquier valor y recibir un Maybe.

  implicit class MaybeOps[A](self: A) {
    def just: Maybe[A] = Maybe.just(self)
  }

Maybe tiene una instancia de typeclass para todas las cosas

  • Align
  • Traverse
  • MonadPlus / IsEmpty
  • Cobind
  • Cozip / Zip / Unzip
  • Optional

e instancias delegadas que dependen de A

  • Monoid / Band
  • Equal / Order / Show

Además de las instancias arriba mencionadas, Maybe tiene funcionalidad que no es soportada por una typeclass polimórfica.

  sealed abstract class Maybe[A] {
    def cata[B](f: A => B, b: =>B): B = this match {
      case Just(a) => f(a)
      case Empty() => b
    }

    def |(a: =>A): A = cata(identity, a)
    def toLeft[B](b: =>B): A \/ B = cata(\/.left, \/-(b))
    def toRight[B](b: =>B): B \/ A = cata(\/.right, -\/(b))
    def <\/[B](b: =>B): A \/ B = toLeft(b)
    def \/>[B](b: =>B): B \/ A = toRight(b)

    def orZero(implicit A: Monoid[A]): A = getOrElse(A.zero)
    def orEmpty[F[_]: Applicative: PlusEmpty]: F[A] =
      cata(Applicative[F].point(_), PlusEmpty[F].empty)
    ...
  }

.cata proporciona una alternativa más simple para .map(f).gerOrElse(b) y tiene la forma más simple | si el mapeo es identity (es decir, simplemente .getOrElse).

.toLeft y .toRight, y sus aliases simbólicos, crean una disjunción (explicada en la sección siguiente) al tomar un valor por default para el caso Empty.

.orZero toma un Monoid para definir el valor por defecto.

.orEmpty usa un ApplicativePlus para crear un elemento único o un contenedor vacío, sin olvidar que ya tenemos soporte para las colecciones de la librería estándar con el método .to que viene de la instancia Foldable.

  scala> 1.just.orZero
  res: Int = 1

  scala> Maybe.empty[Int].orZero
  res: Int = 0

  scala> Maybe.empty[Int].orEmpty[IList]
  res: IList[Int] = []

  scala> 1.just.orEmpty[IList]
  res: IList[Int] = [1]

  scala> 1.just.to[List] // from Foldable
  res: List[Int] = List(1)

6.7.2 Either

La mejora de Scalaz sobre scalaz.Either es simbólica, pero es común hablar de este caso como either o una Disjunction.

  sealed abstract class \/[+A, +B] { ... }
  final case class -\/[+A](a: A) extends (A \/ Nothing)
  final case class \/-[+B](b: B) extends (Nothing \/ B)

  type Disjunction[+A, +B] = \/[A, B]

  object \/ {
    def left [A, B]: A => A \/ B = -\/(_)
    def right[A, B]: B => A \/ B = \/-(_)

    def fromEither[A, B](e: Either[A, B]): A \/ B = ...
    ...
  }

con la sintaxis correspondiente

  implicit class EitherOps[A](val self: A) {
    final def left [B]: (A \/ B) = -\/(self)
    final def right[B]: (B \/ A) = \/-(self)
  }

y permite una construcción sencilla de los valores. Note que los métodos de extensión toman el tipo del otro lado. De modo que si deseamos crear un valor de tipo String \/ Int y tenemos un Int, debemos pasar String cuando llamamos .right.

  scala> 1.right[String]
  res: String \/ Int = \/-(1)

  scala> "hello".left[Int]
  res: String \/ Int = -\/(hello)

La naturaleza simbólica de \/ hace que sea de fácil lectura cuando se muestra con notación infija. Note que los tipos simbólicos en Scala se asocian desde el lado izquierdo y que \/ deben tener paréntesis, por ejemplo (A \/ (B \/ (C \/ D)).

\/ tiene instancias sesgadas a la derecha (es decir, flatMap aplica a \/-) para:

  • Monad / MonadError
  • Traverse / Bitraverse
  • Plus
  • Optional
  • Cozip

y dependiendo del contenido

  • Equal / Order
  • Semigroup / Monoid / Band

Además, hay métodos especiales

  sealed abstract class \/[+A, +B] { self =>
    def fold[X](l: A => X, r: B => X): X = self match {
      case -\/(a) => l(a)
      case \/-(b) => r(b)
    }

    def swap: (B \/ A) = self match {
      case -\/(a) => \/-(a)
      case \/-(b) => -\/(b)
    }

    def |[BB >: B](x: =>BB): BB = getOrElse(x) // Optional[_]
    def |||[C, BB >: B](x: =>C \/ BB): C \/ BB = orElse(x) // Optional[_]

    def +++[AA >: A: Semigroup, BB >: B: Semigroup](x: =>AA \/ BB): AA \/ BB = ...

    def toEither: Either[A, B] = ...

    final class SwitchingDisjunction[X](right: =>X) {
      def <<?:(left: =>X): X = ...
    }
    def :?>>[X](right: =>X) = new SwitchingDisjunction[X](right)
    ...
  }

.fold es similar a Maybe.cata y requiere que tanto el lado derecho como el lado izquierdo se mapeen al mismo tipo.

.swap intercambia los lados izquierdo y derecho.

El alias | para getOrElse parece similar a Maybe.

The | alias to getOrElse appears similarly to Maybe. We also get ||| as an alias to orElse.

+++ es para combinar disjunciones con los lados izquierdos tomando precedencia sobre los lados derechos:

  • right(v1) +++ right(v2) da right(v1 |+| v2)
  • right(v1) +++ left (v2) da left (v2)
  • left (v1) +++ right(v2) da left (v1)
  • left (v1) +++ left (v2) da left (v1 |+| v2)

.toEither está para proporcionar compatibilidad hacia atrás con la librería estándar de Scala.

La combinación de :?>> y <<? son una sintáxis conveniente para ignorar el contenido de una \/, pero escoger un valor por default basándose en su tipo.

  scala> 1 <<?: foo :?>> 2
  res: Int = 2 // foo is a \/-

  scala> 1 <<?: foo.swap :?>> 2
  res: Int = 1

6.7.3 Validation

A primera vista, Validation (con alias simbólico \?/, Elvis feliz) aparece ser un clon de Disjunction:

  sealed abstract class Validation[+E, +A] { ... }
  final case class Success[A](a: A) extends Validation[Nothing, A]
  final case class Failure[E](e: E) extends Validation[E, Nothing]

  type ValidationNel[E, +X] = Validation[NonEmptyList[E], X]

  object Validation {
    type \?/[+E, +A] = Validation[E, A]

    def success[E, A]: A => Validation[E, A] = Success(_)
    def failure[E, A]: E => Validation[E, A] = Failure(_)
    def failureNel[E, A](e: E): ValidationNel[E, A] = Failure(NonEmptyList(e))

    def lift[E, A](a: A)(f: A => Boolean, fail: E): Validation[E, A] = ...
    def liftNel[E, A](a: A)(f: A => Boolean, fail: E): ValidationNel[E, A] = ...
    def fromEither[E, A](e: Either[E, A]): Validation[E, A] = ...
    ...
  }

Con sintáxis conveniente

  implicit class ValidationOps[A](self: A) {
    def success[X]: Validation[X, A] = Validation.success[X, A](self)
    def successNel[X]: ValidationNel[X, A] = success
    def failure[X]: Validation[A, X] = Validation.failure[A, X](self)
    def failureNel[X]: ValidationNel[A, X] = Validation.failureNel[A, X](self)
  }

Sin embargo, la estructura de datos no es la historia completa. En Scalaz, Validation no tiene una instancia de ninguna Monad, y esto es intencional, restringiéndose a versiones sesgadas a la derecha de:

  • Applicative
  • Traverse / Bitraverse
  • Cozip
  • Plus
  • Optional

y dependiendo del contenido

  • Equal / Order
  • Show
  • Semigroup / Monoid

La gran ventaja de restringirnos a Applicative es que Validation es explícitamente para situaciones donde deseamos reportar todas las fallas, mientras que Disjunction se usa para detenernos en el primer fallo. Para lograr la acumulación de fallas, una forma popular de Validation es ValidationNel, teniendo un NonEmptyList[E] en la posición de fracaso.

Considere realizar validación de datos proporcionados por un usuario con ayuda de Disjunction and flatMap:

  scala> :paste
         final case class Credentials(user: Username, name: Fullname)
         final case class Username(value: String) extends AnyVal
         final case class Fullname(value: String) extends AnyVal

         def username(in: String): String \/ Username =
           if (in.isEmpty) "empty username".left
           else if (in.contains(" ")) "username contains spaces".left
           else Username(in).right

         def realname(in: String): String \/ Fullname =
           if (in.isEmpty) "empty real name".left
           else Fullname(in).right

  scala> for {
           u <- username("sam halliday")
           r <- realname("")
         } yield Credentials(u, r)
  res = -\/(username contains spaces)

Si usamos la sintáxis |@|

  scala> (username("sam halliday") |@| realname("")) (Credentials.apply)
  res = -\/(username contains spaces)

Todavía obtenemos el primer error. Esto es porque Disjuntion es una Monad, y sus métodos .applyX deben ser consistentes con .flatMap y no asumir que ninguna operación pueden realizarse fuera de orden. Compare con:

  scala> :paste
         def username(in: String): ValidationNel[String, Username] =
           if (in.isEmpty) "empty username".failureNel
           else if (in.contains(" ")) "username contains spaces".failureNel
           else Username(in).success

         def realname(in: String): ValidationNel[String, Fullname] =
           if (in.isEmpty) "empty real name".failureNel
           else Fullname(in).success

  scala> (username("sam halliday") |@| realname("")) (Credentials.apply)
  res = Failure(NonEmpty[username contains spaces,empty real name])

Esta vez, tenemos todas las fallas!

Validation tiene muchos de los métodos en Disjunction, tales como .fold, .swap y +++, además de algunas extra:

  sealed abstract class Validation[+E, +A] {
    def append[F >: E: Semigroup, B >: A: Semigroup](x: F \?/ B]): F \?/ B = ...

    def disjunction: (E \/ A) = ...
    ...
  }

.append (con el alias simbólico +|+) tiene la misma signatura de tipo que +++ pero da preferencia al caso de éxito

  • failure(v1) +|+ failure(v2) da failure(v1 |+| v2)
  • failure(v1) +|+ success(v2) da success(v2)
  • success(v1) +|+ failure(v2) da success(v1)
  • success(v1) +|+ success(v2) da success(v1 |+| v2)

.disjunction convierte un valor Validated[A, B] en un A \/ B. Disjunction tiene los métodos .validation y .validationNel para convertir en una Validation, permitiendo la fácil conversión entre acumulación sequencial y paralela de errores.

\/ y Validation son las versiones de PF con mayor rendimiento, equivalentes a una excepción de validación de entrada, evitando tanto un stacktrace y requiriendo que el que realiza la invocación lidie con las fallas resultando en sistemas más robustos.

6.7.4 These

Encontramos These, un codificación en forma de datos de un OR lógicamente inclusivo, cuando aprendimos sobre Align

  sealed abstract class \&/[+A, +B] { ... }
  object \&/ {
    type These[A, B] = A \&/ B

    final case class This[A](aa: A) extends (A \&/ Nothing)
    final case class That[B](bb: B) extends (Nothing \&/ B)
    final case class Both[A, B](aa: A, bb: B) extends (A \&/ B)

    def apply[A, B](a: A, b: B): These[A, B] = Both(a, b)
  }

y con una sintáxis para una construcción conveniente

  implicit class TheseOps[A](self: A) {
    final def wrapThis[B]: A \&/ B = \&/.This(self)
    final def wrapThat[B]: B \&/ A = \&/.That(self)
  }
  implicit class ThesePairOps[A, B](self: (A, B)) {
    final def both: A \&/ B = \&/.Both(self._1, self._2)
  }

These tiene instancias de una typeclass para

  • Monad
  • Bitraverse
  • Traverse
  • Cobind

y dependiendo del contenido

  • Semigroup / Monoid / Band
  • Equal / Order
  • Show

These (\&/) tiene muchos de los métodos que que esperamos de ``Disjunction (\/) y Validation (?/`)

  sealed abstract class \&/[+A, +B] {
    def fold[X](s: A => X, t: B => X, q: (A, B) => X): X = ...
    def swap: (B \&/ A) = ...

    def append[X >: A: Semigroup, Y >: B: Semigroup](o: =>(X \&/ Y)): X \&/ Y = ...

    def &&&[X >: A: Semigroup, C](t: X \&/ C): X \&/ (B, C) = ...
    ...
  }

.append tiene 9 posibles arreglos y los datos nunca se tiran porque los casos de This y That siempre pueden convertirse en Both.

.flatMap está sesgado hacia la derecha (Both y That), tomando un Semigroup del contenido de la izquierda (This) para combinar en lugar de fallar temprano. &&& es una manera conveniente de hacer un binding sobre dos valores de tipo These, creando una tupla a la derecha y perdiendo datos si no está presente en cada uno de estos (these).

Aunque es tentador usar \&/ en los tipos de retorno, el uso excesivo es un antipatrón. La razón principal para usar \&/ es para combinar o dividir streams de datos potencialmente infinitos en memoria finita. En el objeto compañero existen funciones convenientes para lidiar con EphemeralStream (con un alias para que quepan en una sola línea) o cualquier cosa con un MonadPlus.

  type EStream[A] = EphemeralStream[A]

  object \&/ {
    def concatThisStream[A, B](x: EStream[A \&/ B]): EStream[A] = ...
    def concatThis[F[_]: MonadPlus, A, B](x: F[A \&/ B]): F[A] = ...

    def concatThatStream[A, B](x: EStream[A \&/ B]): EStream[B] = ...
    def concatThat[F[_]: MonadPlus, A, B](x: F[A \&/ B]): F[B] = ...

    def unalignStream[A, B](x: EStream[A \&/ B]): (EStream[A], EStream[B]) = ...
    def unalign[F[_]: MonadPlus, A, B](x: F[A \&/ B]): (F[A], F[B]) = ...

    def merge[A: Semigroup](t: A \&/ A): A = ...
    ...
  }

6.7.5 Higher Kinded Either

El tipo de datos Coproduct (no confunda con el concepto más general de un coproducto en un ADT) envuelve una Disjunction para los constructores de tipo:

  final case class Coproduct[F[_], G[_], A](run: F[A] \/ G[A]) { ... }
  object Coproduct {
    def leftc[F[_], G[_], A](x: F[A]): Coproduct[F, G, A] = Coproduct(-\/(x))
    def rightc[F[_], G[_], A](x: G[A]): Coproduct[F, G, A] = Coproduct(\/-(x))
    ...
  }

Las instancias de un typeclass simplemente delegan a aquellos de F[_] y G[_].

El caso de uso más popular para un Coproduct es cuando deseamos crear un coproducto anónimo de múltiples ADTs.

6.7.6 No tan estricta

Las tuplas de Scala integradas, y los tipos de datos básicos como Maybe y la Disjunction son tipos de valores evaluados de manera estricta.

Por conveniencia, las alternativas por nombre para Name se proporcionan, teniendo las instancias de typeclass esperadas:

  sealed abstract class LazyTuple2[A, B] {
    def _1: A
    def _2: B
  }
  ...
  sealed abstract class LazyTuple4[A, B, C, D] {
    def _1: A
    def _2: B
    def _3: C
    def _4: D
  }

  sealed abstract class LazyOption[+A] { ... }
  private final case class LazySome[A](a: () => A) extends LazyOption[A]
  private case object LazyNone extends LazyOption[Nothing]

  sealed abstract class LazyEither[+A, +B] { ... }
  private case class LazyLeft[A, B](a: () => A) extends LazyEither[A, B]
  private case class LazyRight[A, B](b: () => B) extends LazyEither[A, B]

El lector astuto notará que Lazy no está bien nombrado, y estos tipos de datos quizá deberían ser: ByNameTupleX, ByNameOption y ByNameEither.

6.7.7 Const

Const, para constante, es un envoltorio para un valor de tipo A, junto con un parámetro de tipo B.

  final case class Const[A, B](getConst: A)

Const proporciona una instancia de Applicative[Const[A, ?]] si hay un Monoid[A] disponible:

  implicit def applicative[A: Monoid]: Applicative[Const[A, ?]] =
    new Applicative[Const[A, ?]] {
      def point[B](b: =>B): Const[A, B] =
        Const(Monoid[A].zero)
      def ap[B, C](fa: =>Const[A, B])(fbc: =>Const[A, B => C]): Const[A, C] =
        Const(fbc.getConst |+| fa.getConst)
    }

La cosa más importante sobre este Applicative es que ignora los parámetros B, continuando sin fallar y únicamente combinando los valores constantes que encuentra.

Volviendo atrás a nuestra aplicación de ejemplo drone-dynamic-agents, deberíamos refactorizar nuestro archivo logic.scala para usar Applicative en lugar de Monad. Escribimos logic.scala antes de que supieramos sobre Applicative y ahora lo sabemos mejor:

  final class DynAgentsModule[F[_]: Applicative](D: Drone[F], M: Machines[F])
    extends DynAgents[F] {
    ...
    def act(world: WorldView): F[WorldView] = world match {
      case NeedsAgent(node) =>
        M.start(node) >| world.copy(pending = Map(node -> world.time))

      case Stale(nodes) =>
        nodes.traverse { node =>
          M.stop(node) >| node
        }.map { stopped =>
          val updates = stopped.strengthR(world.time).toList.toMap
          world.copy(pending = world.pending ++ updates)
        }

      case _ => world.pure[F]
    }
    ...
  }

Dado que nuestra lógica de negocio únicamente requiere de un Applicative, podemos escribir implementaciones simuladas con F[a] como Const[String, a]. En tal caso, devolvemos los nombres de la función que se invoca:

  object ConstImpl {
    type F[a] = Const[String, a]

    private val D = new Drone[F] {
      def getBacklog: F[Int] = Const("backlog")
      def getAgents: F[Int]  = Const("agents")
    }

    private val M = new Machines[F] {
      def getAlive: F[Map[MachineNode, Epoch]]     = Const("alive")
      def getManaged: F[NonEmptyList[MachineNode]] = Const("managed")
      def getTime: F[Epoch]                        = Const("time")
      def start(node: MachineNode): F[Unit]        = Const("start")
      def stop(node: MachineNode): F[Unit]         = Const("stop")
    }

    val program = new DynAgentsModule[F](D, M)
  }

Con nuestra interpretación de nuestro programa, podemos realizar aserciones sobre los métodos que son invocados:

  it should "call the expected methods" in {
    import ConstImpl._

    val alive    = Map(node1 -> time1, node2 -> time1)
    val world    = WorldView(1, 1, managed, alive, Map.empty, time4)

    program.act(world).getConst shouldBe "stopstop"
  }

De manera alternativa, podríamos haber contado el total de métodos al usar Const[Int, ?] o en un IMap[String, Int].

Con esta prueba, hemos ido más allá de realizar pruebas con implementaciones simuladas con una prueba Const que hace aserciones sobre lo que se invoca sin tener que proporcionar implementaciones. Esto es útil si nuestra especificación demanda que hagamos ciertas llamadas para ciertas entradas, por ejemplo, para propósitos de contabilidad. Además, hemos conseguido esto con seguridad en tiempo de compilación.

Tomando esta línea de pensamiento un poco más allá, digamos que deseamos monitorear (en tiempo de producción) los nodos que estamos deteniendo en act. Podemos crear implementaciones de Drone y Machines con Const, invocándolos desde nuestra versión envuelta de act

  final class Monitored[U[_]: Functor](program: DynAgents[U]) {
    type F[a] = Const[Set[MachineNode], a]
    private val D = new Drone[F] {
      def getBacklog: F[Int] = Const(Set.empty)
      def getAgents: F[Int]  = Const(Set.empty)
    }
    private val M = new Machines[F] {
      def getAlive: F[Map[MachineNode, Epoch]]     = Const(Set.empty)
      def getManaged: F[NonEmptyList[MachineNode]] = Const(Set.empty)
      def getTime: F[Epoch]                        = Const(Set.empty)
      def start(node: MachineNode): F[Unit]        = Const(Set.empty)
      def stop(node: MachineNode): F[Unit]         = Const(Set(node))
    }
    val monitor = new DynAgentsModule[F](D, M)

    def act(world: WorldView): U[(WorldView, Set[MachineNode])] = {
      val stopped = monitor.act(world).getConst
      program.act(world).strengthR(stopped)
    }
  }

Podemos hacer esto porque monitor es puro y ejecutarlo no produce efectos laterales.

Esto ejecuta el programa con ConstImpl, extrayendo todas las llamadas a Machines.stop, entonces devolviéndolos junto con la WorldView. Podemos hacer pruebas unitarias así:

  it should "monitor stopped nodes" in {
    val underlying = new Mutable(needsAgents).program

    val alive = Map(node1 -> time1, node2 -> time1)
    val world = WorldView(1, 1, managed, alive, Map.empty, time4)
    val expected = world.copy(pending = Map(node1 -> time4, node2 -> time4))

    val monitored = new Monitored(underlying)
    monitored.act(world) shouldBe (expected -> Set(node1, node2))
  }

Hemos usado Const para hacer algo que es como la Programación Orientada a Aspectos (Aspect Oriented Programming), que alguna vez fue popular en Java. Construimos encima de nuestra lógica de negocios para soportar una preocupación de monitoreo, sin tener que complicar la lógica de negocios.

Se pone incluso mejor. Podemos ejecutar ConstImpl en producción para reunir lo que deseamos para detenernos (stop), y entonces proporcionar una implementación optimizada de act que puede usar llamadas por batches/lotes que puede ser de implementación específica.

El héroe siliencioso de esta historia es Applicative. Const nos deja ver lo que es posible. Si necesitamos cambiar nuestro programa para que requiera una Monad, no podemos seguir usando Const y es necesario escribir mocks completos para poder hacer aserciones sobre lo que se llama sobre ciertas entradas. La Regla del Poder Mínimo demanda que usemos Applicative en lugar de Monad siempre que podamos.

6.8 Colecciones

A diferencia de la API de colecciones de la librería estándar, Scalaz describe comportamientos en las colecciones en la jerarquía de typeclases, por ejemplo, Foldable, Traverse, Monoid. Lo que resta por estudiar son las implementaciones en términos de estructuras de datos, que tienen características de rendimiento distintas y métodos muy específicos.

Esta sección estudia detalles de implementación para cada tipo de datos. No es esencial recordar todo lo que se presenta aquí: la meta es ganar entendimiento a un nivel de abstracción alto de cómo funciona cada estructura de datos.

Debido a que los tipos de datos de todas las colecciones nos proporcionan más o menos la misma lista de instancias de typeclases, debemos evitar repetir la lista, que siempre es una variación de la lista:

  • Monoid
  • Traverse / Foldable
  • MonadPlus / IsEmpty
  • Cobind / Comonad
  • Zip / Unzip
  • Align
  • Equal / Order
  • Show

Las estructuras de datos que es posible probar que no son vacías pueden proporcionar:

  • Traverse1 / Foldable1

y proporcionar Semigroup en lugar de Monoid, Plus en lugar de IsEmpty.

6.8.1 Listas

Ya hemos usado IList[A] y NonEmptyList[A] tantas veces al momento que a estas alturas deberían ser familiares. Codifican una estructura de datos clásica, la lista ligada:

  sealed abstract class IList[A] {
    def ::(a: A): IList[A] = ...
    def :::(as: IList[A]): IList[A] = ...
    def toList: List[A] = ...
    def toNel: Option[NonEmptyList[A]] = ...
    ...
  }
  final case class INil[A]() extends IList[A]
  final case class ICons[A](head: A, tail: IList[A]) extends IList[A]

  final case class NonEmptyList[A](head: A, tail: IList[A]) {
    def <::(b: A): NonEmptyList[A] = nel(b, head :: tail)
    def <:::(bs: IList[A]): NonEmptyList[A] = ...
    ...
  }

La ventaja principal de IList sobre List de la librería estándar es que no hay métodos inseguros, como .head que lanza una excepción sobre listas vacías.

Adicionalmente, IList es mucho más simple, sin tener una jerarquía de clases y un tamaño del bytecode mucho más pequeño. Además, List de la librería estándar tiene una implementación terrible que usa var para parchar problemas de rendimiento en el diseño de las colecciones de la librería estándar:

  package scala.collection.immutable

  sealed abstract class List[+A]
    extends AbstractSeq[A]
    with LinearSeq[A]
    with GenericTraversableTemplate[A, List]
    with LinearSeqOptimized[A, List[A]] { ... }
  case object Nil extends List[Nothing] { ... }
  final case class ::[B](
    override val head: B,
    private[scala] var tl: List[B]
  ) extends List[B] { ... }

La creación de una instancia de List requiere de la creación cuidadosa, y lenta, de sincronización de Threads para asegurar una publicación segura. IList no requiere de tales hacks y por lo tanto puede superar a List.

6.8.2 EphemeralStream

Stream de la librería estándar es una versión perezosa de List, pero está plagada con fugas de memoria y métodos inseguros. EphemeralStream no mantiene referencias a valores calculados, ayudando a mitigar los problemas de retención de memoria, removiendo los métodos inseguros en el mismo espíritu que IList.

  sealed abstract class EphemeralStream[A] {
    def headOption: Option[A]
    def tailOption: Option[EphemeralStream[A]]
    ...
  }
  // private implementations
  object EphemeralStream extends EphemeralStreamInstances {
    type EStream[A] = EphemeralStream[A]

    def emptyEphemeralStream[A]: EStream[A] = ...
    def cons[A](a: =>A, as: =>EStream[A]): EStream[A] = ...
    def unfold[A, B](start: =>B)(f: B => Option[(A, B)]): EStream[A] = ...
    def iterate[A](start: A)(f: A => A): EStream[A] = ...

    implicit class ConsWrap[A](e: =>EStream[A]) {
      def ##::(h: A): EStream[A] = cons(h, e)
    }
    object ##:: {
      def unapply[A](xs: EStream[A]): Option[(A, EStream[A])] =
        if (xs.isEmpty) None
        else Some((xs.head(), xs.tail()))
    }
    ...
  }

.cons, .unfold e .iterate son mecanismos para la creación de streams, y la sintaxis conveniente ##:: pone un nuevo elemento en la cabeza de una referencia por nombre EStream. .unfold es para la creación de un stream finito (pero posiblemente infinito) al aplicar repetidamente una función f para obtener el siguiente valor y la entrada para la siguiente f. .iterate crea un stream infinito al aplicar repetidamente una función f en el elemento previo.

EStream puede aparecer en patrones de emparejamiento con el símbolo ##::, haciendo un match para la sintaxis para .cons.

Aunque EStream lidia con el problema de retención de valores de memoria, todavía es posible sufrir de fugas de memoria lentas si una referencia viva apunta a la cabeza de un stream infinito. Los problemas de esta naturaleza, así como la necesidad de realizar composición de streams con efectos, es la razón de que fs2 exista.

6.8.3 CorecursiveList

La correcursión es cuando empezamos de un estado base y producimos pasos subsecuentes de manera determinística, como el método EphemeralStream.unfold que acabamos de estudiar:

  def unfold[A, B](b: =>B)(f: B => Option[(A, B)]): EStream[A] = ...

Contraste con una recursion, que pone datos en un estado base y entonces termina.

Una CorecursiveList es una codificación de datos de un EphemeralStream.unfold, ofreciendo una alternativa a EStream que puede lograr un rendimiento mejor en algunas circunstancias:

  sealed abstract class CorecursiveList[A] {
    type S
    def init: S
    def step: S => Maybe[(S, A)]
  }

  object CorecursiveList {
    private final case class CorecursiveListImpl[S0, A](
      init: S0,
      step: S0 => Maybe[(S0, A)]
    ) extends CorecursiveList[A] { type S = S0 }

    def apply[S, A](init: S)(step: S => Maybe[(S, A)]): CorecursiveList[A] =
      CorecursiveListImpl(init, step)

    ...
  }

La correcursión es útil cuando estamos implementando Comonad.cojoin, como en nuestro ejemplo de Hood. CorecursiveList es una buena manera de codificar ecuaciones con recurrencia no lineales como las que se usan en el modelado de poblaciones de biología, sistemas de control, macro economía, y los modelos de inversión de bancos.

6.8.4 ImmutableArray

Un simple wrapper alrededor del Array mutable de la librería estándar, con especializaciones primitivas:

  sealed abstract class ImmutableArray[+A] {
    def ++[B >: A: ClassTag](o: ImmutableArray[B]): ImmutableArray[B]
    ...
  }
  object ImmutableArray {
    final class StringArray(s: String) extends ImmutableArray[Char] { ... }
    sealed class ImmutableArray1[+A](as: Array[A]) extends ImmutableArray[A] { ... }
    final class ofRef[A <: AnyRef](as: Array[A]) extends ImmutableArray1[A](as)
    ...
    final class ofLong(as: Array[Long]) extends ImmutableArray1[Long](as)

    def fromArray[A](x: Array[A]): ImmutableArray[A] = ...
    def fromString(str: String): ImmutableArray[Char] = ...
    ...
  }

Array no tiene rival en términos de rendimiento al hacer lectura y el tamaño del heap. Sin embargo, no se está comportiendo memoria estructuralmente cuando se crean nuevos arreglos, y por lo tanto los arreglos se usan típicamente cuando no se espera que los contenidos cambien, o como una manera segura de envolver de manera segura datos crudos de un sistema antiguo/legacy.

6.8.5 Dequeue

Un Dequeue (pronunciado como en “deck of cards”) es una lista ligada que permite que los elementos se coloquen o se devuelvan del frente (cons) o en la parte trasera (snoc) en tiempo constante. Remover un elemento de cualquiera de los extremos es una operación de tiempo constante, en promedio.

  sealed abstract class Dequeue[A] {
    def frontMaybe: Maybe[A]
    def backMaybe: Maybe[A]

    def ++(o: Dequeue[A]): Dequeue[A] = ...
    def +:(a: A): Dequeue[A] = cons(a)
    def :+(a: A): Dequeue[A] = snoc(a)
    def cons(a: A): Dequeue[A] = ...
    def snoc(a: A): Dequeue[A] = ...
    def uncons: Maybe[(A, Dequeue[A])] = ...
    def unsnoc: Maybe[(A, Dequeue[A])] = ...
    ...
  }
  private final case class SingletonDequeue[A](single: A) extends Dequeue[A] { ... }
  private final case class FullDequeue[A](
    front: NonEmptyList[A],
    fsize: Int,
    back: NonEmptyList[A],
    backSize: Int) extends Dequeue[A] { ... }
  private final case object EmptyDequeue extends Dequeue[Nothing] { ... }

  object Dequeue {
    def empty[A]: Dequeue[A] = EmptyDequeue()
    def apply[A](as: A*): Dequeue[A] = ...
    def fromFoldable[F[_]: Foldable, A](fa: F[A]): Dequeue[A] = ...
    ...
  }

La forma en la que funciona es que existen dos listas, una para los datos al frente y otra para los datos en la parte trasera. Considere una instancia para mantener los símbolos a0, a1, a2, a3, a4, a5, a6

  FullDequeue(
    NonEmptyList('a0, IList('a1, 'a2, 'a3)), 4,
    NonEmptyList('a6, IList('a5, 'a4)), 3)

que puede visualizarse como

Note que la lista que mantiene back está en orden inverso.

Leer el elemento final, snoc, es una simple lectura en back.head. Añadir un elemento al final del Dequeue significa añadir un nuevo elemento al frente de la lista back, y recrear el envoltorio FullDequeue (que incrementará el tamaño de backSize en uno). Casi toda la estructura original es compartida. Compare a agregar un nuevo elemento al final de una IList, que envolvería recrear la estructura completa.

El frontSize y el backSize se usan para rebalancear el front y el back de modo que casi siempre son del mismo tamaño. Rebalancear significa que algunas operaciones sean más lentas que otras (por ejemplo, cuando la estructura de datos debe ser reconstruida) pero debido a que únicamente ocurre ocasionalmente, podríamos tomar el promedio del costo y decir que es constante.

6.8.6 DList

Las listas ligadas tienen características de rendimiento muy pobres cuando se añaden grandes listas. Considere el trabajo que está envuelto en evaluar lo siguiente:

  ((as ::: bs) ::: (cs ::: ds)) ::: (es ::: (fs ::: gs))

Esto crea seis listas intermedias, recorriendo y reconstruyendo cada lista tres veces (con la excepción de gs que se comparte durante todas las etapas).

La DList (de lista por diferencias) es la solución más eficiente para este escenario. En lugar de realizar cálculos en cada etapa, es representada como la función IList[A] => IList[A]

  final case class DList[A](f: IList[A] => IList[A]) {
    def toIList: IList[A] = f(IList.empty)
    def ++(as: DList[A]): DList[A] = DList(xs => f(as.f(xs)))
    ...
  }
  object DList {
    def fromIList[A](as: IList[A]): DList[A] = DList(xs => as ::: xs)
  }

El cálculo equivalente es (los símbolos son creados a partir de DList.fromIList)

  (((a ++ b) ++ (c ++ d)) ++ (e ++ (f ++ g))).toIList

que reparte el trabajo en appends asociativos a la derecha (es decir, rápidos)

  (as ::: (bs ::: (cs ::: (ds ::: (es ::: (fs ::: gs))))))

utilizando el constructor rápido sobre IList.

Como siempre, no hay nada gratis. Existe un costo extra de asignación dinámica de memoria que puede reducir la velocidad del código que resulta naturalmente en appends asociativos a la derecha. El incremento de velocidad más grande ocurre cuando operaciones IList son asociativas hacia la izquierda, por ejemplo

  ((((((as ::: bs) ::: cs) ::: ds) ::: es) ::: fs) ::: gs)

Las listas de diferencia sufren de un marketing malo. Tal vez si su nombre fuera ListBuilderFactory estarían en la librería estándar.

6.8.7 ISet

Las estructuras de árboles son excelentes para almacenar datos ordenados, con cada nodo binario manteniendo elementos que son menores en una rama, y mayores en la otra. Sin embargo, implementaciones ingenuas de la estructura de datos árbol pueden desbalancearse dependiendo del orden de inserción. Es posible mantener un árbol perfectamente balanceado, pero es increíblemente ineficiente dado que cada inserción efectivamente reconstruye el árbol completo.

ISet es una implementación de un árbol con balanceo acotado, significando que está aproximadamente balanceado, usando el tamaño (size) de cada rama para balancear el nodo.

  sealed abstract class ISet[A] {
    val size: Int = this match {
      case Tip()        => 0
      case Bin(_, l, r) => 1 + l.size + r.size
    }
    ...
  }
  object ISet {
    private final case class Tip[A]() extends ISet[A]
    private final case class Bin[A](a: A, l: ISet[A], r: ISet[A]) extends ISet[A]

    def empty[A]: ISet[A] = Tip()
    def singleton[A](x: A): ISet[A] = Bin(x, Tip(), Tip())
    def fromFoldable[F[_]: Foldable, A: Order](xs: F[A]): ISet[A] =
      xs.foldLeft(empty[A])((a, b) => a insert b)
    ...
  }

ISet requiere que A tenga un Order. La instancia Order[A] debe permanecer igual entre llamadas o las invariantes internas serán inválidas, llevándonos a tener datos corrompidos: es decir, estamos asumiendo la coherencia de typeclases tales que Order[A] es única para cualquier A.

La ADT ISet desgraciadamente permite árboles inválidos. Nos esforzamos por escribir ADTs que describan completamente lo que es y no es válido usando restricciones de tipo, pero algunas veces tenemos situaciones donde únicamente es posible lograrlo con el toque inspirado de un inmortal. En lugar de esto, Tip / Bin son private, para evitar que los usuarios construyan, accidentalmente, árboles inválidos. .insert es la única manera de construir un ISet, y por lo tanto definir lo que es un árbol válido.

  sealed abstract class ISet[A] {
    ...
    def contains(x: A)(implicit o: Order[A]): Boolean = ...
    def union(other: ISet[A])(implicit o: Order[A]): ISet[A] = ...
    def delete(x: A)(implicit o: Order[A]): ISet[A] = ...

    def insert(x: A)(implicit o: Order[A]): ISet[A] = this match {
      case Tip() => ISet.singleton(x)
      case self @ Bin(y, l, r) => o.order(x, y) match {
        case LT => balanceL(y, l.insert(x), r)
        case GT => balanceR(y, l, r.insert(x))
        case EQ => self
      }
    }
    ...
  }

Los métodos internos .balanceL y .balanceR son espejos uno del otro, de modo que únicamente estudiamos .balanceL, que también se llama cuando el valor que estamos insertando es menor que el nodo actual. También se invoca por el método .delete.

  def balanceL[A](y: A, left: ISet[A], right: ISet[A]): ISet[A] = (left, right) match {
  ...

El balanceo requiere que clasifiquemos los escenarios que pueden ocurrir. Estudiaremos cada posible escenario, visualizando (y, left, right) al lado izquierdo de la página, con la estructura balanceada a la derecha, también conocido como el árbol rotado.

  • círculos llenos visualizan un Tip
  • tres columbas visualizan los campos left | value | right de Bin
  • los diamantes visualizan cualquier ISet

El primer escenario es el caso trivial, que es cuando, tanto el lado left y el right son Tip. De hecho, nunca encontraremos este escenario a partir de .insert, pero lo encontramos en .delete.

  case (Tip(), Tip()) => singleton(y)

El segundo caso es cuando left es un Bin que contiene únicamente a Tip, y no necesitamos balancear nada, simplemente creamos la conexión obvia:

  case (Bin(lx, Tip(), Tip()), Tip()) => Bin(y, left, Tip())

El tercer caso es cuando esto empieza a ponerse interesante: left es un Bin conteniendo únicamente un Bin a su right.

  case (Bin(lx, Tip(), Bin(lrx, _, _)), Tip()) =>
    Bin(lrx, singleton(lx), singleton(y))

Pero qué ocurrió a los dos diamantes que están debajo de lrx? No acabamos de perder información? No, no perdimos información, porque podemos razonar (basándonos en el balanceo del tamaño) que siempre son Tip! No hay regla en cuanto a cualquiera de los siguientes escenarios (o en .balanceR) que pueden producir un árbol donde los diamantes son Bin.

El cuarto caso es el opuesto del tercer caso.

  case (Bin(lx, ll, Tip()), Tip()) => Bin(lx, ll, singleton(y))

El quinto caso es cuando tenemos árboles completos en ambos lados del lado left y de todos modos debemos usar sus tamañaos relativos para decidir cómo rebalancear.

  case (Bin(lx, ll, lr), Tip()) if (2*ll.size > lr.size) =>
    Bin(lx, ll, Bin(y, lr, Tip()))
  case (Bin(lx, ll, Bin(lrx, lrl, lrr)), Tip()) =>
    Bin(lrx, Bin(lx, ll, lrl), Bin(y, lrr, Tip()))

Para la primera rama, 2*ll.size > lr.size

y para la segunda rama 2*ll.size <= lr.size

El sexto escenario introduce un árbol en lado (derecho) right. Cuando el lado left está vacío creamos la conexión obvia. Ese escenario nunca surge a partir de .insert porque el lado .left siempre está no vacío:

  case (Tip(), r) => Bin(y, Tip(), r)

El escenario final ocurre cuando tenemos árboles no vacíos en ambos lados. A menos que el lado left sea tres veces o más el tamaño del lado right, podemos hacer lo más sencillo y crear un nuevo Bin.

  case _ if l.size <= 3 * r.size => Bin(y, l, r)

Sin embargo, si el lado left debiera tener más de tres veces el tamaño del lado right, debemos balancear basándonos en los tamaños relativos de ll y lr, como en el escenario cinco.

  case (Bin(lx, ll, lr), r) if (2*ll.size > lr.size) =>
    Bin(lx, ll, Bin(y, lr, r))
  case (Bin(lx, ll, Bin(lrx, lrl, lrr)), r) =>
    Bin(lrx, Bin(lx, ll, lrl), Bin(y, lrr, r))

Esto concluye nuestro estudio del método .insert y cómo se construye un ISet. No debería ser sorpresivo que Foldable esté implementado en términos de una búsqueda en lo profundo, junto con left y right, como es apropiado. Métodos tales como .minimum y .maximum son óptimos porque la estructura de datos ya codifica el orden.

Es valioso hacer ntar quealgunos métodos de typeclass no pueden ser implementados de manera tan eficiente como quisieramos. Considere la signatura de Foldable.element

  @typeclass trait Foldable[F[_]] {
    ...
    def element[A: Equal](fa: F[A], a: A): Boolean
    ...
  }

Una implememntación obiva para .element es (de manera práctica) delegar a la búsqueda binaria ISet.contains. Sin embargo, no es posible debido a que .element proporciona Equal mientras que .contains requiere de Order.

ISet es incapaz de proporcionar un Functor por la misma razón. En la práctica esto es una restricción sensible: realizar un .map significaría reconstruir toda la estructura de datos completa. Tiene sentido convertir a un tipo de datos distinto, tales como IList, realizando el .map, y convirtiendo de vuelta. Una consecuencia es que ya no es posible tener un Traverse[ISet] o Applicative[Set].

6.8.8 IMap

  sealed abstract class ==>>[A, B] {
    val size: Int = this match {
      case Tip()           => 0
      case Bin(_, _, l, r) => 1 + l.size + r.size
    }
  }
  object ==>> {
    type IMap[A, B] = A ==>> B

    private final case class Tip[A, B]() extends (A ==>> B)
    private final case class Bin[A, B](
      key: A,
      value: B,
      left: A ==>> B,
      right: A ==>> B
    ) extends ==>>[A, B]

    def apply[A: Order, B](x: (A, B)*): A ==>> B = ...

    def empty[A, B]: A ==>> B = Tip[A, B]()
    def singleton[A, B](k: A, x: B): A ==>> B = Bin(k, x, Tip(), Tip())
    def fromFoldable[F[_]: Foldable, A: Order, B](fa: F[(A, B)]): A ==>> B = ...
    ...
  }

¡Esto es muy familiar! En realidad, IMap (un alias para el operador de la velocidad de la luz) es otro árbol balanceado en tamaño, pero con un campo extra value: B en cada rama del árbol binario, permitiendo almacenar pares de llave/valor. Únicamente el tipo clave A necesita un Order y una clase conveniente de métodos son proporcionados para permitir una actualización fácil de entradas.

  sealed abstract class ==>>[A, B] {
    ...
    def adjust(k: A, f: B => B)(implicit o: Order[A]): A ==>> B = ...
    def adjustWithKey(k: A, f: (A, B) => B)(implicit o: Order[A]): A ==>> B = ...
    ...
  }

Tree es una versión by need (por necesidad) de StrictTree con constructores convenientes

  class Tree[A](
    rootc: Need[A],
    forestc: Need[Stream[Tree[A]]]
  ) {
    def rootLabel = rootc.value
    def subForest = forestc.value
  }
  object Tree {
    object Node {
      def apply[A](root: =>A, forest: =>Stream[Tree[A]]): Tree[A] = ...
    }
    object Leaf {
      def apply[A](root: =>A): Tree[A] = ...
    }
  }

Se espera que el usuario de un Rose Tree lo balancee manualmente, lo que lo hace adecuado para casos donde es útil codificar conocimiento especializado de cierta jerarquía del dominio en la estructura de datos. Por ejemplo, en el campo de la inteligencia artificial, un árbol de Rose puede ser usado en algoritmos de agrupamiento para organizar datos en una jerarquía de cosas cada vez más similares. Es posible representar documentos XML con un árbol Rose.

Cuando trabajamos con datos jerárquicos, considere usar un árbol Rose en lugar de hacer una estructura de datos a la medida.

6.8.9 FingerTree

Los árboles de dedo son secuencias generalizadas con un costo de búsqueda amortizado y concatenación logarítmica. A es el tipo de datos, ignore V por ahora:

  sealed abstract class FingerTree[V, A] {
    def +:(a: A): FingerTree[V, A] = ...
    def :+(a: =>A): FingerTree[V, A] = ...
    def <++>(right: =>FingerTree[V, A]): FingerTree[V, A] = ...
    ...
  }
  object FingerTree {
    private class Empty[V, A]() extends FingerTree[V, A]
    private class Single[V, A](v: V, a: =>A) extends FingerTree[V, A]
    private class Deep[V, A](
      v: V,
      left: Finger[V, A],
      spine: =>FingerTree[V, Node[V, A]],
      right: Finger[V, A]
    ) extends FingerTree[V, A]

    sealed abstract class Finger[V, A]
    final case class One[V, A](v: V, a1: A) extends Finger[V, A]
    final case class Two[V, A](v: V, a1: A, a2: A) extends Finger[V, A]
    final case class Three[V, A](v: V, a1: A, a2: A, a3: A) extends Finger[V, A]
    final case class Four[V, A](v: V, a1: A, a2: A, a3: A, a4: A) extends Finger[V, A]

    sealed abstract class Node[V, A]
    private class Node2[V, A](v: V, a1: =>A, a2: =>A) extends Node[V, A]
    private class Node3[V, A](v: V, a1: =>A, a2: =>A, a3: =>A) extends Node[V, A]
    ...
  }

Visualizando FingerTree como puntos, Finger como cajas y Node como cajas dentro de cajas:

Agregar elementos al frente de un FingerTree con +: es eficiente porque Deep simplemente añade un nuevo elemento al dedo del lado left. Si el dedo es un Four, reconstruimos la espina (spine) para tomar 3 de los elementos como un Node3. Agregando al final, :+, es lo mismo pero en reversa.

Agregar cosas |+| (también <++>) es más eficiente que agregar un elemento a la vez debido a que el caso de dos árboles Deep pueden retener las ramas externas, reconstruyendo la espina basándose en las 16 posibles combinaciones de los dos valores Finger en la mitad.

En la discusión anterior nos saltamos V. En la descripción de la ADT no se muestra una implicit measurer: Reducer[A, V] en cada elemento de la ADT.

Reducer es una extensión de Monoid que permite que un solo elemento se agregue a una M.

  class Reducer[C, M: Monoid] {
    def unit(c: C): M

    def snoc(m: M, c: C): M = append(m, unit(c))
    def cons(c: C, m: M): M = append(unit(c), m)
  }

Por ejemplo, Reducer[A, IList[A]] puede proporcionar un .cons eficiente

  implicit def reducer[A]: Reducer[A, IList[A]] = new Reducer[A, IList[A]] {
    override def unit(a: A): IList[A] = IList.single(a)
    override def cons(a: A, as: IList[A]): IList[A] = a :: as
  }
6.8.9.1 IndSeq

Si usamos Int como V, podemos obtener una secuencia indexada, donde la medida es el tamaño, permitiéndonos realizar una búsqueda basada en el índice al comparar el índice deseado con el tamaño de cada rama en la estructura:

  final class IndSeq[A](val self: FingerTree[Int, A])
  object IndSeq {
    private implicit def sizer[A]: Reducer[A, Int] = _ => 1
    def apply[A](as: A*): IndSeq[A] = ...
  }

Otro uso de FingerTree es una secuencia ordenada, donde la medida almacena el valor más largo contenido en cada rama:

6.8.9.2 OrdSeq
  final class OrdSeq[A: Order](val self: FingerTree[LastOption[A], A]) {
    def partition(a: A): (OrdSeq[A], OrdSeq[A]) = ...
    def insert(a: A): OrdSeq[A] = ...
    def ++(xs: OrdSeq[A]): OrdSeq[A] = ...
  }
  object OrdSeq {
    private implicit def keyer[A]: Reducer[A, LastOption[A]] = a => Tag(Some(a))
    def apply[A: Order](as: A*): OrdSeq[A] = ...
  }

OrdSeq no tiene instancias de typeclases de modo que únicamente es útil para construir incrementalmente una secuencia ordenada, con duplicados. Podemos acceder al FingerTree subyacente cuando sea necesario.

6.8.9.3 Cord

El caso más común de FingerTree es un almacén intermedio para representaciones de String en Show. Construir una sola String puede ser miles de veces más rápido que la implementación default de case class de .toString anidadas, que construye una String para cada capa en la ADT.

  final case class Cord(self: FingerTree[Int, String]) {
    override def toString: String = {
      val sb = new java.lang.StringBuilder(self.measure)
      self.foreach(sb.append) // locally scoped side effect
      sb.toString
    }
    ...
  }

Por ejemplo, la instancia Cord[String] devuelve una Three con la cadena a la mitad y comillas en ambos lados

  implicit val show: Show[String] = s => Cord(FingerTree.Three("\"", s, "\""))

Por lo tanto una String se muestra tal y como se escribe en el código fuente

  scala> val s = "foo"
         s.toString
  res: String = foo

  scala> s.show
  res: Cord = "foo"

6.8.10 Cola de prioridad Heap

Una cola de prioridad es una estructura de datos que permite una rápida inserción de elementos ordenados, permitiendo duplicados, con un rápido acceso al valor mínimo (la prioridad más alta). La estructura no es necesaria para almacenar los elementos no mínimos en orden. Una implementación ingenua de una cola de prioridad podría ser

  final case class Vip[A] private (val peek: Maybe[A], xs: IList[A]) {
    def push(a: A)(implicit O: Order[A]): Vip[A] = peek match {
      case Maybe.Just(min) if a < min => Vip(a.just, min :: xs)
      case _                          => Vip(peek, a :: xs)
    }

    def pop(implicit O: Order[A]): Maybe[(A, Vip[A])] = peek strengthR reorder
    private def reorder(implicit O: Order[A]): Vip[A] = xs.sorted match {
      case INil()           => Vip(Maybe.empty, IList.empty)
      case ICons(min, rest) => Vip(min.just, rest)
    }
  }
  object Vip {
    def fromList[A: Order](xs: IList[A]): Vip[A] = Vip(Maybe.empty, xs).reorder
  }

Este push es muy rápido O(1), pero el reorder (y por lo tanto pop) depende de IList.sorted con un costo de O(n log n).

Scalaz codifica una cola de prioridad con una estructura de árbol donde cada nodo tiene un valor menor que sus hijos. Heap tiene un operaciones rápidas push (insert), union, size, pop (uncons) y peek (minimumO):

  sealed abstract class Heap[A] {
    def insert(a: A)(implicit O: Order[A]): Heap[A] = ...
    def +(a: A)(implicit O: Order[A]): Heap[A] = insert(a)

    def union(as: Heap[A])(implicit O: Order[A]): Heap[A] = ...

    def uncons(implicit O: Order[A]): Option[(A, Heap[A])] = minimumO strengthR deleteMin
    def minimumO: Option[A] = ...
    def deleteMin(implicit O: Order[A]): Heap[A] = ...

    ...
  }
  object Heap {
    def fromData[F[_]: Foldable, A: Order](as: F[A]): Heap[A] = ...

    private final case class Ranked[A](rank: Int, value: A)

    private final case class Empty[A]() extends Heap[A]
    private final case class NonEmpty[A](
      size: Int,
      tree: Tree[Ranked[A]]
    ) extends Heap[A]

    ...
  }

Heap está implementado con un Rose Tree de valores Ranked, donde rank es la profundidad del sub-árbol, permitiéndonos balancear la profundidad del árbol. Manualmente mantenemos el árbol de modo que el valor mínimo está en la raíz. Una ventaja de que se codifique el valor mínimo en la estructura de datos es que minimum0 (conocido también como peek) es una búsqueda inmediata y sin costo alguno:

  def minimumO: Option[A] = this match {
    case Empty()                        => None
    case NonEmpty(_, Tree.Node(min, _)) => Some(min.value)
  }

Cuando insertamos una nueva entrada, comparamos el valor mínimo actual y lo reemplazamos si la nueva entrada es más pequeña:

  def insert(a: A)(implicit O: Order[A]): Heap[A] = this match {
    case Empty() =>
      NonEmpty(1, Tree.Leaf(Ranked(0, a)))
    case NonEmpty(size, tree @ Tree.Node(min, _)) if a <= min.value =>
      NonEmpty(size + 1, Tree.Node(Ranked(0, a), Stream(tree)))
  ...

Las inserciones de valores que no son mínimos resulta en una estructura de datos desordenada en las ramas del nodo mínimo. Cuando encontramos dos o más sub-árboles de rango idéntico, colocamos el valor mínimo de manera optimista al frente:

  ...
    case NonEmpty(size, Tree.Node(min,
           (t1 @ Tree.Node(Ranked(r1, x1), xs1)) #::
           (t2 @ Tree.Node(Ranked(r2, x2), xs2)) #:: ts)) if r1 == r2 =>
      lazy val t0 = Tree.Leaf(Ranked(0, a))
      val sub =
        if (x1 <= a && x1 <= x2)
          Tree.Node(Ranked(r1 + 1, x1), t0 #:: t2 #:: xs1)
        else if (x2 <= a && x2 <= x1)
          Tree.Node(Ranked(r2 + 1, x2), t0 #:: t1 #:: xs2)
        else
          Tree.Node(Ranked(r1 + 1, a), t1 #:: t2 #:: Stream())

      NonEmpty(size + 1, Tree.Node(Ranked(0, min.value), sub #:: ts))

    case NonEmpty(size,  Tree.Node(min, rest)) =>
      val t0 = Tree.Leaf(Ranked(0, a))
      NonEmpty(size + 1, Tree.Node(Ranked(0, min.value), t0 #:: rest))
  }

Al evitar un ordenamiento completo del árbol hacemos que insert sea muy rápido, O(1), de modo que los productores que agregan elementos a la cola no son penalizados. Sin embargo, el consumidor paga el costo cuando invoca uncons, con deleteMin teniendo un costo O(log n) debido a que debe buscar el valor mínimo, y removerlo del árbol al reconstruirlo. Esto es rápido cuando se compara con una implementación ingenua.

La operación union también retrasa el ordenamiento permitiéndo que se realice en O(1).

Si Order[Foo] no captura correctamente la prioridad que deseamos para el Heap[Foo], podemos usar Tag y proporcionar un Order[Foo @@ Custom] ad-hoc para un Heap[Foo @@ Custom].

6.8.11 Diev (Discrete Intervals)

Podemos codificar eficientemente los valores enteros (desordenados) 6, 9, 2, 13, 8, 14, 10, 7, 5 como intervalos inclusivos [2, 2], [5, 10], [13, 14]. Diev tiene una codificación eficiente de intervalos para elementos A que tienen un Enum[A], haciéndose más eficientes a medida que el contenido se hace más denso.

  sealed abstract class Diev[A] {
    def +(interval: (A, A)): Diev[A]
    def +(value: A): Diev[A]
    def ++(other: Diev[A]): Diev[A]

    def -(interval: (A, A)): Diev[A]
    def -(value: A): Diev[A]
    def --(other: Diev[A]): Diev[A]

    def intervals: Vector[(A, A)]
    def contains(value: A): Boolean
    def contains(interval: (A, A)): Boolean
    ...
  }
  object Diev {
    private final case class DieVector[A: Enum](
      intervals: Vector[(A, A)]
    ) extends Diev[A]

    def empty[A: Enum]: Diev[A] = ...
    def fromValuesSeq[A: Enum](values: Seq[A]): Diev[A] = ...
    def fromIntervalsSeq[A: Enum](intervals: Seq[(A, A)]): Diev[A] = ...
  }

Cuando actualizamos el Diev, los intervalos adyacentes se fusionan (y entonces ordenados) tales que hay una representación única para un conjunto dado de valores.

  scala> Diev.fromValuesSeq(List(6, 9, 2, 13, 8, 14, 10, 7, 5))
  res: Diev[Int] = ((2,2)(5,10)(13,14))

  scala> Diev.fromValuesSeq(List(6, 9, 2, 13, 8, 14, 10, 7, 5).reverse)
  res: Diev[Int] = ((2,2)(5,10)(13,14))

Un gran caso de uso para Diev es para almacenar periodos de tiempo. Por ejemplo, en nuestro TradeTemplate del capítulo anterior

  final case class TradeTemplate(
    payments: List[java.time.LocalDate],
    ccy: Option[Currency],
    otc: Option[Boolean]
  )

si encontramos que los payments son muy densos, tal vez deseemos intercambiar a una representación Diev por razones de rendimiento, sin ningún cambio en nuestra lógica de negocios porque usamos un Monoid, no ningún método específico de List. Sin embargo, tendríamos que proporcionar un Enum[LocalDate], que de otra manera sería algo útil y bueno que tener.

6.8.12 OneAnd

Recuerde que Foldable es el equivalente de Scalaz de una API de colecciones y que Foldable1 es para colecciones no vacías. Hasta el momento hemos revisado únicamente NonEmptyList para proporcionar un Foldable1. La estructura de datos simple OneAnd envuelve cualquier otra colección y la convierte en un Foldable1.

  final case class OneAnd[F[_], A](head: A, tail: F[A])

NonEmptyList[A] podría ser un alias a OneAnd[IList, A]. De manera similar, podemos crear Stream no vacío, y estructuras DList y Tree. Sin embargo, podría terminar con las características de ordenamiento y unicidad de la estructura de datos subyacente: un OneAnd[ISet, A] no es un ISet no vacío, se trata de un ISet con la garantía de que se tiene un primer elemento que también puede estar en el ISet.

6.9 Sumario

En este capítulo hemos revisado rápidamente los tipos de datos que Scalaz tiene que ofrecer.

No es necesario recordad todo lo estudiado en este capítulo: piense que cada sección es la semilla o corazón de una idea.

El mundo de las estructuras de datos funcionales es una área activa de investigación. Publicaciones académicas aparecen regularmente con nuevos enfoques a viejos problemas. La implementación de una estructura de datos funcionales a partir de la literatura sería una buena contribución al ecosistema de Scalaz.

7. Mónadas avanzadas

Usted tiene que conocer cosas como las mónadas avanzadas para ser un programador funcional avanzado.

Sin embargo, somos desarrolladores buscando una vida simple, y nuestra idea de “avanzado” es modesta. Para ponernos en contexto: scala.concurrent.Future es más complicada y con más matices que cualquier Monad en este capítulo.

En este capítulo estudiaremos algunas de las implementaciones más importantes de Monad.

7.1 Future siempre está en movimiento

El problema más grande con Future es que programa trabajo rápidamente durante su construcción. Como descubrimos en la introducción, Future mezcla la definición del programa con su interpretación (es decir, con su ejecución).

Future también es malo desde una perspectiva de rendimiento: cada vez que .flatMap es llamado, una cerradura se manda al Ejecutor, resultando en una programación de hilos y en cambios de contexto innecesarios. No es inusual ver 50% del poder de nuestro CPU lidiando con planeación de hilos. Tanto es así que la paralelización de trabajo con Futuro puede volverlo más lento.

En combinación, la evaluación estricta y el despacho de ejecutores significa que es imposible de saber cuándo inició un trabajo, cuando terminó, o las sub-tareas que se despacharon para calcular el resultado final. No debería sorprendernos que las “soluciones” para el monitoreo de rendimiento para frameworks basados en Future sean buenas opciones para las ventas.

Además, Future.flatMap requiere de un ExecutionContext en el ámbito implícito: los usuarios están forzados a pensar sobre la lógica de negocios y la semántica de ejecución a la vez.

7.2 Efectos y efectos laterales

Si no podemos llamar métodos que realicen efectos laterales en nuestra lógica de negocios, o en Future (or Id, or Either, o Const, etc), entonces, ¿cuándo podemos escribirlos? La respuesta es: en una Monad que retrasa la ejecución hasta que es interpretada por el punto de entrada de la aplicación. En este punto, podemos referirnos a I/O y a la mutación como un efecto en el mundo, capturado por el sistema de tipos, en oposición a tener efectos laterales ocultos.

La implementación simple de tal Monad es IO, formalizando la versión que escribimos en la introducción:

  final class IO[A](val interpret: () => A)
  object IO {
    def apply[A](a: =>A): IO[A] = new IO(() => a)

    implicit val monad: Monad[IO] = new Monad[IO] {
      def point[A](a: =>A): IO[A] = IO(a)
      def bind[A, B](fa: IO[A])(f: A => IO[B]): IO[B] = IO(f(fa.interpret()).interpret())
    }
  }

El método .interpret se llama únicamente una vez, en el punto de entrada de una aplicación.

  def main(args: Array[String]): Unit = program.interpret()

Sin embargo, hay dos grandes problemas con este simple IO:

  1. Puede ocasionar un sobreflujo de la pila
  2. No soporta cómputos paralelos

Ambos problemas serán abordados en este capítulo. Sin embargo, sin importar lo complicado de una implementación interna de una Monad, los principios aquí descritos seguirán siendo ciertos: estamos modularizando la definición de un programa y su ejecución, tales que podemos capturar los efectos en la signatura de los tipos, permitiéndonos razonar sobre ellos, y reusar más código.

7.3 Seguridad de la pila

En la JVM, toda invocación a un método, agrega una entrada a la pila de llamadas del hilo (Thread), como agregar al frente de una List. Cuando el método completa, el método en la cabeza (head) es descartado/eliminado. La longitud máxima de la pila de llamadas es determinada por la bandera -Xss cuando se llama a java. Los métodos que realizan una recursión de cola, son detectados por el compilador de Scala y no agregan una entrada. Si alcanzamos el límite, al invocar demasiados métodos encadenados, obtenemos una excepción de StackOverflowError.

Desgraciadamente, toda invocación anidada de .flatMap (sobre una instancia de IO) agrega otro método de invocación a la pila. La forma más sencilla de ver esto es repetir esta acción por siempre, y ver si logra sobrevivir más de unos cuántos segundos. Podemos usar .forever, que viene de Apply (un “padre” de Monad):

  scala> val hello = IO { println("hello") }
  scala> Apply[IO].forever(hello).interpret()

  hello
  hello
  hello
  ...
  hello
  java.lang.StackOverflowError
      at java.io.FileOutputStream.write(FileOutputStream.java:326)
      at ...
      at monadio.IO$$anon$1.$anonfun$bind$1(monadio.scala:18)
      at monadio.IO$$anon$1.$anonfun$bind$1(monadio.scala:18)
      at ...

Scalaz tiene una typeclass que las instancias de Monad pueden implementar si son seguras: BindRec requiere de un espacio de pila constante para bind recursivo:

  @typeclass trait BindRec[F[_]] extends Bind[F] {
    def tailrecM[A, B](f: A => F[A \/ B])(a: A): F[B]

    override def forever[A, B](fa: F[A]): F[B] = ...
  }

No necesitamos BindRec para todos los programas, pero es esencial para una implementación de propósito general de Monad.

La manera de conseguir seguridad en la pila es la conversión de invocaciones de métodos en referencias a una ADT, la mónada Free:

  sealed abstract class Free[S[_], A]
  object Free {
    private final case class Return[S[_], A](a: A)     extends Free[S, A]
    private final case class Suspend[S[_], A](a: S[A]) extends Free[S, A]
    private final case class Gosub[S[_], A0, B](
      a: Free[S, A0],
      f: A0 => Free[S, B]
    ) extends Free[S, B] { type A = A0 }
    ...
  }

La ADT Free es una es una representación del tipo de datos natural de la interfaz Monad:

  1. Return representa .point
  2. Gosub representa .bind / .flatMap

Cuando una ADT es un reflejo de los argumentos de las funciones relacionadas, recibe el nombre de una codificación Church.

Free recibe este nombre debido a que puede ser generada de manera gratuita para cualquier S[_]. Por ejemplo, podríamos hacer que S sea una de las álgebras Drone o Machines del Capítulo 3 y generar una representación de la estructura de datos de nuestro programa. Regresaremos más tarde a este punto para explicar por qué razón esto es de utilidad.

7.3.1 Trampoline

Free es más general de lo necesario. Haciendo que el álgebra S[_] sea () => ?, un cálculo diferido o un thunk, obtenemos Trampoline que puede implementar una Monad de manera que se conserva el uso seguro de la pila.

  object Free {
    type Trampoline[A] = Free[() => ?, A]
    implicit val trampoline: Monad[Trampoline] with BindRec[Trampoline] =
      new Monad[Trampoline] with BindRec[Trampoline] {
        def point[A](a: =>A): Trampoline[A] = Return(a)
        def bind[A, B](fa: Trampoline[A])(f: A => Trampoline[B]): Trampoline[B] =
          Gosub(fa, f)

        def tailrecM[A, B](f: A => Trampoline[A \/ B])(a: A): Trampoline[B] =
          bind(f(a)) {
            case -\/(a) => tailrecM(f)(a)
            case \/-(b) => point(b)
          }
      }
    ...
  }

La implementación de BindRec, .tailrecM, ejecuta .bind hasta que obtenemos una B. Aunque no se trata, técnicamente, de una implementación @tailrec, usa un espacio de pila constante debido a que cada llamada devuelve un objeto en el heap, con recursión postergada.

Se proporcionan funciones convenientes para la creación estricta de un Trampoline (.done) o por nombre (.delay). También podemos crear un Trampoline a partir de un Trampoline por nombre (.suspend):

  object Trampoline {
    def done[A](a: A): Trampoline[A]                  = Return(a)
    def delay[A](a: =>A): Trampoline[A]               = suspend(done(a))
    def suspend[A](a: =>Trampoline[A]): Trampoline[A] = unit >> a

    private val unit: Trampoline[Unit] = Suspend(() => done(()))
  }

Cuando vemos un Trampoline[A] en el código, siempre es posible sustituirlo mentalmente con una A, debido a que únicamente está añadiendo seguridad al uso de la pila a un cómputo puro. Obtenemos la A al interpretar Free, provisto por .run.

7.3.2 Ejemplo: DList con seguridad en el manejo de la pila

En el capítulo anterior hemos descrito el tipo de datos DList como

  final case class DList[A](f: IList[A] => IList[A]) {
    def toIList: IList[A] = f(IList.empty)
    def ++(as: DList[A]): DList[A] = DList(xs => f(as.f(xs)))
    ...
  }

Sin embargo, la implementación actual se ve más parecida a:

  final case class DList[A](f: IList[A] => Trampoline[IList[A]]) {
    def toIList: IList[A] = f(IList.empty).run
    def ++(as: =>DList[A]): DList[A] = DList(xs => suspend(as.f(xs) >>= f))
    ...
  }

En lugar de aplicar llamadas anidadas a f, usamos un Trampoline suspendido. Interpretamos el trampolín con .run únicamente cuando es necesario, por ejemplo, en toIList. Los cambios son mínimo, pero ahora tenemos una DList con uso seguro de la pila que puede reordenar la concatenación de un número largo de listas sin ocasionar un sobreflujo de la pila.

7.3.3 IO con uso seguro de la pila

De manera similar, nuestra IO puede hacerse segura (respecto al uso de la pila), gracias a Trampoline:

  final class IO[A](val tramp: Trampoline[A]) {
    def unsafePerformIO(): A = tramp.run
  }
  object IO {
    def apply[A](a: =>A): IO[A] = new IO(Trampoline.delay(a))

    implicit val Monad: Monad[IO] with BindRec[IO] =
      new Monad[IO] with BindRec[IO] {
        def point[A](a: =>A): IO[A] = IO(a)
        def bind[A, B](fa: IO[A])(f: A => IO[B]): IO[B] =
          new IO(fa.tramp >>= (a => f(a).tramp))
        def tailrecM[A, B](f: A => IO[A \/ B])(a: A): IO[B] = ...
      }
  }

El intérprete, .unsafePerformIO(), ahora tiene un nombre intencionalmente terrorífico para desalentar su uso, con la excepción del punto de entrada de una aplicación.

Esta vez, no obtendremos un error por sobreflujo de la pila:

  scala> val hello = IO { println("hello") }
  scala> Apply[IO].forever(hello).unsafePerformIO()

  hello
  hello
  hello
  ...
  hello

El uso de un Trampoline típicamente introduce una regresión en el desempeño comparado a la implementación normal de referencia. Es Free en el sentido de que se genera de manera automática, no en el sentido literal.

7.4 Librería de transformadores de mónadas

Las transformadores de mónadas son estructuras de datos que envuelven un valor subyacente y proporcionan un efecto monádico.

Por ejemplo, en el capítulo 2 usamos OptionT para que pudiéramos usar F[Option[A]] en una comprehensión for como si se tratase de F[A]. Esto le dio a nuestro programa el efecto de un valor opcional. De manera alternativa, podemos conseguir el efcto de opcionalidad si tenemos una MonadPlus.

A este subconjunto de tipos de datos y extensiones a Monad con frecuencia se le conoce como una Librería de Transformadores de Mónadas (MTL, por sus siglas en inglés), como se resume enseguida. En esta sección, explicaremos cada uno de los transformadores, por qué razón son útiles, y cómo funcionan.

Efecto Equivalencia Transformador Typeclass
opcionalidad F[Maybe[A]] MaybeT MonadPlus
errores F[E \/ A] EitherT MonadError
un valor en tiempo de ejecución A => F[B] ReaderT MonadReader
journal / multi tarea F[(W, A)] WriterT MonadTell
estado en cambio S => F[(S, A)] StateT MonadState
mantén la calma y continúa F[E \&/ A] TheseT  
control de flujo (A => F[B]) => F[B] ContT  

7.4.1 MonadTrans

Cada transformador tiene la forma general T[F[_], A], proporcionando al menos una instancia de Monad y Hoist (y por lo tanto de MonadTrans):

  @typeclass trait MonadTrans[T[_[_], _]] {
    def liftM[F[_]: Monad, A](a: F[A]): T[F, A]
  }

  @typeclass trait Hoist[F[_[_], _]] extends MonadTrans[F] {
    def hoist[M[_]: Monad, N[_]](f: M ~> N): F[M, ?] ~> F[N, ?]
  }

.liftM nos permite crear un transformador de mónadas si tenemos un F[A]. Por ejemplo, podemos crear un OptionT[IO, String] al invocar ` .liftM[OptionT] en una IO[String]`.

.hoist es la misma idea, pero para transformaciones naturales.

Generalmente, hay tres maneras de crear un transformador de mónadas:

  • A partir de la estructura equivalente, usando el constructor del transformador
  • A partir de un único valor A, usando .pure usando la sintaxis de Monad
  • A partir de F[A], usando .liftM usando la sintaxis de MonadTrans

Debido a la forma en la que funciona la inferencia de tipos en Scala, esto con frecuencia significa que un parámetro de tipo complejo debe escribirse de manera explícita. Como una forma de lidiar con el problema, los transformadores proporcionan constructores convenientes en su objeto compañero que los hacen más fáciles de usar.

7.4.2 MaybeT

OptionT, MaybeT y LazyOption tienen implementaciones similares, proporcionando opcionalidad a través de Option, Maybe y LazyOption, respectivamente. Nos enfocaremos en MaybeT para evitar la repetición.

  final case class MaybeT[F[_], A](run: F[Maybe[A]])
  object MaybeT {
    def just[F[_]: Applicative, A](v: =>A): MaybeT[F, A] =
      MaybeT(Maybe.just(v).pure[F])
    def empty[F[_]: Applicative, A]: MaybeT[F, A] =
      MaybeT(Maybe.empty.pure[F])
    ...
  }

proporcionando una MonadPlus

  implicit def monad[F[_]: Monad] = new MonadPlus[MaybeT[F, ?]] {
    def point[A](a: =>A): MaybeT[F, A] = MaybeT.just(a)
    def bind[A, B](fa: MaybeT[F, A])(f: A => MaybeT[F, B]): MaybeT[F, B] =
      MaybeT(fa.run >>= (_.cata(f(_).run, Maybe.empty.pure[F])))

    def empty[A]: MaybeT[F, A] = MaybeT.empty
    def plus[A](a: MaybeT[F, A], b: =>MaybeT[F, A]): MaybeT[F, A] = a orElse b
  }

Esta mónada se ve un poco complicada, pero simplemente está delegando todo a la Monad[F] y entonces envolviendo todo dentro de un MaybeT. Simplemente es código para cumplir con el trabajo.

Con esta mónada podemos escribir lógica que maneja la opcionalidad en el contexto de F[_], más bien que estar lidiando con Option o Maybe.

Por ejemplo, digamos que estamos interactuando con un sitio social para contar el número de estrellas que tiene el usuario, y empezamos con una cadena (String) que podría o no corresponder al usuario. Tenemos esta álgebra:

  trait Twitter[F[_]] {
    def getUser(name: String): F[Maybe[User]]
    def getStars(user: User): F[Int]
  }
  def T[F[_]](implicit t: Twitter[F]): Twitter[F] = t

Necesitamos invocar getUser seguido de getStars. Si usamos Monad como nuestro contexto, nuestra función es difícil porque tendremos que lidiar con el caso Empty:

  def stars[F[_]: Monad: Twitter](name: String): F[Maybe[Int]] = for {
    maybeUser  <- T.getUser(name)
    maybeStars <- maybeUser.traverse(T.getStars)
  } yield maybeStars

Sin embargo, si tenemos una MonadPlus como nuestro contexto, podemos poner Maybe dentro de F[_] usando .orEmpty, y olvidarnos del asunto:

  def stars[F[_]: MonadPlus: Twitter](name: String): F[Int] = for {
    user  <- T.getUser(name) >>= (_.orEmpty[F])
    stars <- T.getStars(user)
  } yield stars

Sin embargo, agregar un requerimiento de MonadPlus puede ocasionar problemas más adelante en el proceso, si el contexto no tiene una. La solución es, o cambiar el contexto del programa a MaybeT[F, ?] (elevando el contexto de Monad[F] a una MonadPlus), o para usar explícitamente MaybeT en el tipo de retorno, a costa de un poco de código adicional:

  def stars[F[_]: Monad: Twitter](name: String): MaybeT[F, Int] = for {
    user  <- MaybeT(T.getUser(name))
    stars <- T.getStars(user).liftM[MaybeT]
  } yield stars

La decisión de requerir una Monad más poderosa vs devolver un transformador es algo que cada equipo puede decidir por sí mismo basándose en los intérpretes que planee usar en sus programas.

7.4.3 EitherT

Un valor opcional es el caso especial de un valor que puede ser un error, pero no sabemos nada sobre el error. EitherT (y la variante perezosa LazyEitherT) nos permite usar cualquier tipo que deseemos como el valor del error, porporcionando información contextual sobre lo que pasó mal.

EitherT es un envoltorio sobre F[A \/ B]

  final case class EitherT[F[_], A, B](run: F[A \/ B])
  object EitherT {
    def either[F[_]: Applicative, A, B](d: A \/ B): EitherT[F, A, B] = ...
    def leftT[F[_]: Functor, A, B](fa: F[A]): EitherT[F, A, B] = ...
    def rightT[F[_]: Functor, A, B](fb: F[B]): EitherT[F, A, B] = ...
    def pureLeft[F[_]: Applicative, A, B](a: A): EitherT[F, A, B] = ...
    def pure[F[_]: Applicative, A, B](b: B): EitherT[F, A, B] = ...
    ...
  }

Monad es una MonadError

  @typeclass trait MonadError[F[_], E] extends Monad[F] {
    def raiseError[A](e: E): F[A]
    def handleError[A](fa: F[A])(f: E => F[A]): F[A]
  }

.raiseError y .handleError son descriptivos en sí mismos: el equivalente de lanzar (throw) y atrapar (catch) una excepción, respectivamente.

MonadError tiene sintaxis adicional para lidiar con problemas comunes:

  implicit final class MonadErrorOps[F[_], E, A](self: F[A])(implicit val F: MonadError[F, E])\
 {
    def attempt: F[E \/ A] = ...
    def recover(f: E => A): F[A] = ...
    def emap[B](f: A => E \/ B): F[B] = ...
  }

.attempt trae los errores dentro del valor, lo cual es útil para exponer los errores en los subsistemas como valores de primera clase.

.recover es para convertir un error en un valor en todos los casos, en oposición a .handleError que toma una F[A] y por lo tanto permite una recuperación parcial.

.emap, es para aplicar transformaciones que pueden fallar.

El MonadError para EitherT es:

  implicit def monad[F[_]: Monad, E] = new MonadError[EitherT[F, E, ?], E] {
    def monad[F[_]: Monad, E] = new MonadError[EitherT[F, E, ?], E] {
    def bind[A, B](fa: EitherT[F, E, A])
                  (f: A => EitherT[F, E, B])<