Do it with (free?) arrows!

Julien Richard-Foy

Typelevel Summit Copenhagen – June 3, 2017

http://julienrf.github.io/2017/arrows

Outline

Context
Applicative Functor
Monad
Arrow
Choice

1.1 Description vs interpretation

Description vs interpretation

Description: HTML document

<html>
  <head><title>This is not a title</title></head>
  <body/>
</html>

Description: arithmetic expression

1 + 1   // This is not an addition

Interpretations make sense out of descriptions

Description	Interpretations
HTML document	rendering
arithmetic expression	evaluation, simplification, pretty print
image	draw on screen, generate a file
API endpoint	client, server, documentation

Interpretations

Transform (optimize)
Evaluate
Generate (code, assets)

The essence of descriptions

“atoms” (1, "foo", point(1, 2))
operators (+, concat, move)

Data description

Records with fields
Sum types

Interpretations of data descriptions

serialization
deserialization
schema documentation
lenses
UI form
…

Let’s design a data description language

trait DataDescr {

  /** A description of data of type `A` */
  type Data[A]

  /** “atom” describing a record with one
    * field of type `String`
    */
  def field(name: String): Data[String]

}

Let’s try our `DataDescr` language

trait Program extends DataDescr {

  /**
    * A record with one field named “x”
    * and containing a `String` value
    */
  val x: Data[String] = field("x")

}

Let’s describe a `User` data type (1)

trait Program extends DataDescr {

  case class User(name: String, email: String)







}

Let’s describe a `User` data type (2)

trait Program extends DataDescr {

  case class User(name: String, email: String)

  val user: Data[User] = {


    ???
  }

}

Let’s describe a `User` data type (3)

trait Program extends DataDescr {

  case class User(name: String, email: String)

  val user: Data[User] = {
    val name  = field("name")

    ???
  }

}

Let’s describe a `User` data type (4)

trait Program extends DataDescr {

  case class User(name: String, email: String)

  val user: Data[User] = {
    val name  = field("name")
    val email = field("email")
    ???
  }

}

2 Applicative Functor

2.1 We need the power of applicative functors!

Let’s upgrade our language

import scalaz.Applicative

trait DataDescr {

  type Data[A]

  def field(name: String): Data[String]

  /** Pretend that `Data[_]` is an applicative functor */
  implicit val applicativeData: Applicative[Data]

}

Feel the power! (1)

import scalaz.syntax._

trait Program extends DataDescr {

  case class User(name: String, email: String)

  val user: Data[User] = {
    val name  = field("name")
    val email = field("email")
    (name tuple email) // Data[(String, String)]
  }

}

Feel the power! (2)

import scalaz.syntax._

trait Program extends DataDescr {

  case class User(name: String, email: String)

  val user: Data[User] = {
    val name  = field("name")
    val email = field("email")
    (name tuple email).map(User.tupled)
  }

}

Intuition of an applicative functor

val name: Data[String] = …
val email: Data[String] = …
val user: Data[User] = (name tuple email).map(User.tupled)

We can turn several records into a single record containing all of their fields

`Data[User]`?

But what is a Data[User]?
We don’t know yet! Data is still an abstract type
Interpreters will give Data a concrete meaning

`Decoder`

trait Decoder extends DataDescr {

  type Data[A] = Map[String, String] => Option[A]

  // … (implementation of `field` and `applicativeData`)
}

`Documentation`

trait Documentation extends DataDescr {

  type Data[A] = Record
  case class Record(fields: List[String])

  // … (implementation of `field` and `applicativeData`)
}

3.1 Sum types description

Is our language powerful enough to describe this data type?

sealed trait Shape
case class Circle(radius: String) extends Shape
case class Rectangle(width: String, height: String) extends Shape

val kvs =
  Map(
    "type" -> "Circle",
    "radius" -> "42"
  )

Attempt

sealed trait Shape
case class Circle(radius: String) extends Shape
case class Rectangle(width: String, height: String) extends Shape

val shape: Data[Shape] = {
  val tpe = field("type")
  val circle = field("radius").map(Circle)
  val rectangle =
    (field("width") tuple field("height")).map(Rectangle.tupled)
  ???
}

Monads to the rescue

import scalaz.Monad

trait DataDescr {

  type Data[A]

  def field(name: String): Data[String]

  /** Pretend that `Data[_]` is a monad */
  implicit val monadData: Monad[Data]

}

Feel the power of the monad!

val shapeData: Data[Shape] = {

  val circle: Data[Shape] = field("radius").map(Circle)
  val rectangle: Data[Shape] =
    (field("width") tuple field("height")).map(Rectangle.tupled)

  for {
    tpe   <- field("type")
    shape <- tpe match {
      case "Circle" => circle
      case "Rectangle" => rectangle
    }
  } yield shape
}

Intuition of a monad

Can do all the things an applicative functor can do
Can describe a type according to the actual value of another type

`Decoder`

trait Decoder extends DataDescr {

  type Data[A] = Map[String, String] => Option[A]

  // … (implementation of `monadData`)

}

`Documentation`

trait Documentation extends DataDescr {

  type Data[A] = Record
  case class Record(fields: List[String])

  val monadData: Monad[Data] = ???





}

`Documentation`

trait Documentation extends DataDescr {

  type Data[A] = Record
  case class Record(fields: List[String])

  val monadData: Monad[Data] =
    new Monad[Data] {
      def point[A](x: A): Data[A] = ???
      def bind[A, B](fa: Data[A])(f: A => Data[B]): Data[B] = ???
    }

}

`Documentation`

trait Documentation extends DataDescr {

  type Data[A] = Record
  case class Record(fields: List[String])

  val monadData: Monad[Data] =
    new Monad[Data] {
      def point[A](x: A): Record = ???
      def bind[A, B](fa: Record)(f: A => Record): Record = ???
    }

}

`Documentation`

trait Documentation extends DataDescr {

  type Data[A] = Record
  case class Record(fields: List[String])

  val monadData: Monad[Data] =
    new Monad[Data] {
      def point[A](x: A): Record = Record(Nil)
      def bind[A, B](fa: Record)(f: A => Record): Record = ???
    }

}

`Documentation`

trait Documentation extends DataDescr {

  type Data[A] = Record
  case class Record(fields: List[String])

  val monadData: Monad[Data] =
    new Monad[Data] {
      def point[A](x: A): Record = Record(Nil)
      def bind[A, B](fa: Record)(f: A => Record): Record = fa
    }

}

`Documentation`

Where are the record fields???

Monads: summary

User point of view
- greater power: describe a data type based on the information contained in another data type’s instance
Interpreter point of view
- too much power: we can not anymore give a useful Documentation implementation…
Can we find a better compromise?

Let’s make our `Data` an arrow

trait DataDescr {

  /** Description of a data type */
  type Data[In, Out]
  /** Raw format of data */
  type Raw

  /** Describes a record with one field */
  def field(name: String): Data[Raw, String]

  /** Pretend that `Data[_, _]` is an arrow */
  implicit val arrowData: Arrow[Data]

}

4.1 Describing data types with arrows

Record types

import scalaz.syntax.all._

trait Program exends DataDescr {
  import arrowData._

  case class User(name: String, email: String)

  def userData: Data[Raw, User] = {
    val name  = field("name")
    val email = field("email")
    (name &&& email) // Data[Raw, (String, String)]
  }

}

Record types

import scalaz.syntax.all._

trait Program exends DataDescr {
  import arrowData._

  case class User(name: String, email: String)

  def userData: Data[Raw, User] = {
    val name  = field("name")
    val email = field("email")
    (name &&& email) >>> arr(User.tupled)
  }

}

Intuition of an arrow

combine processing steps, sequentially (>>>) or in parallel (&&&)

Sum types

sealed trait Shape
case class Circle(radius: String) extends Shape
case class Rectangle(width: String, height: String) extends Shape

val shapeDecoder: Data[Raw, Shape] = {

  val circle: Data[Raw, Shape] = field("radius") >>> arr(Circle)

  val rectangle: Data[Raw, Shape] =
    (field("width") &&& field("height")) >>> arr(Rectangle.tupled)

  val tpe = field("type")
  ???
}

Sum types

We still miss some power…

Add the power of making choices

trait DataDescr {

  /** Pretend that `Data[_, _]` is an arrow with choice */
  implicit val arrowChoiceData: Arrow[Data] with Choice[Data]

}

Can we now describe sum types?

val shapeDecoder: Data[Raw, Shape] = {
  import arrowChoiceData._

  val circle: Data[Raw, Shape] = …
  val rectangle: Data[Raw, Shape] = …

  val tpe: Data[Raw, Unit \/ Unit] =
    field("type") >>> arr((_: String) match {
      case "Circle"    => ().left
      case "Rectangle" => ().right
    }

  tpe.withFst >>> (circle ||| rectangle)
}

Intuition of choice

fan in: merge alternative branches

Can we also implement a (useful) documentation interpreter?

`Documentation`

trait Documentation extends DataDescr {

  type Data[A, B] = ???
  type Raw = ???

  implicit val arrowChoiceData: Arrow[Data] with Choice[Data] = ???

}

`Documentation`

trait Documentation extends DataDescr {

  type Data[A, B] = ???
  type Raw = Nothing

  implicit val arrowChoiceData: Arrow[Data] with Choice[Data] = ???

}

`Documentation`

trait Documentation extends DataDescr {

  type Data[A, B] = ???
  type Raw = Nothing


  case class Record(fields: List[String])


  implicit val arrowChoiceData: Arrow[Data] with Choice[Data] = ???

}

`Documentation`

trait Documentation extends DataDescr {

  type Data[A, B] = ???
  type Raw = Nothing

  sealed trait Adt
  case class Record(fields: List[String]) extends Adt
  case class CoProd(alternatives: List[Record]) extends Adt

  implicit val arrowChoiceData: Arrow[Data] with Choice[Data] = ???

}

`Documentation`

trait Documentation extends DataDescr {

  type Data[A, B] = Adt
  type Raw = Nothing

  sealed trait Adt
  case class Record(fields: List[String]) extends Adt
  case class CoProd(alternatives: List[Record]) extends Adt

  implicit val arrowChoiceData: Arrow[Data] with Choice[Data] = ???

}

`Documentation`

sealed trait Adt
case class Record(fields: List[String]) extends Adt
case class CoProd(alternatives: List[Record]) extends Adt

implicit val arrowChoiceData: Arrow[Data] with Choice[Data] =
  new Arrow[Data] with Choice[Data] {
    // …
  }

`Documentation`

sealed trait Adt
case class Record(fields: List[String]) extends Adt
case class CoProd(alternatives: List[Record]) extends Adt

implicit val arrowChoiceData: Arrow[Data] with Choice[Data] =
  new Arrow[Data] with Choice[Data] {

    def compose[A, B, C](f: Data[B, C], g: Data[A, B]): Data[A, C] = ???

    // …
  }

`Documentation`

sealed trait Adt
case class Record(fields: List[String]) extends Adt
case class CoProd(alternatives: List[Record]) extends Adt

implicit val arrowChoiceData: Arrow[Data] with Choice[Data] =
  new Arrow[Data] with Choice[Data] {

    def compose[A, B, C](f: Adt, g: Adt): Adt = ???

    // …
  }

`Documentation`

sealed trait Adt
case class Record(fields: List[String]) extends Adt
case class CoProd(alternatives: List[Record]) extends Adt

implicit val arrowChoiceData: Arrow[Data] with Choice[Data] =
  new Arrow[Data] with Choice[Data] {

    def compose[A, B, C](f: Adt, g: Adt): Adt =
      (f, g) match {
        case (Record(fs1), Record(fs2)) => Record(fs1 ++ fs2)
      }

    // …
  }

`Documentation`

sealed trait Adt
case class Record(fields: List[String]) extends Adt
case class CoProd(alternatives: List[Record]) extends Adt

implicit val arrowChoiceData: Arrow[Data] with Choice[Data] =
  new Arrow[Data] with Choice[Data] {

    def compose[A, B, C](f: Adt, g: Adt): Adt =
      (f, g) match {
        case (Record(fs1), Record(fs2)) => Record(fs1 ++ fs2)
        case (CoProd(as1), CoProd(as2)) => CoProd(as1 ++ as2)
      }

    // …
  }

`Documentation`

sealed trait Adt
case class Record(fields: List[String]) extends Adt
case class CoProd(alternatives: List[Record]) extends Adt

implicit val arrowChoiceData: Arrow[Data] with Choice[Data] =
  new Arrow[Data] with Choice[Data] {

    def compose[A, B, C](f: Adt, g: Adt): Adt =
      (f, g) match {
        case (Record(fs1), Record(fs2)) => Record(fs1 ++ fs2)
        case (CoProd(as1), CoProd(as2)) => CoProd(as1 ++ as2)
        case (Record(fs1), CoProd(as2)) => CoProd(as2.map(r => Fields(r.fields ++ fs1)))
        case (CoProd(as1), Record(fs2)) => coProd(as1.map(r => Fields(r.fields ++ fs2)))
      }

    // …
  }

`Documentation`

sealed trait Adt
case class Record(fields: List[String]) extends Adt
case class CoProd(alternatives: List[Record]) extends Adt

implicit val arrowChoiceData: Arrow[Data] with Choice[Data] =
  new Arrow[Data] with Choice[Data] {

    def choice[A, B, C](f: Data[A, C], g: Data[B, C]): Data[A \/ B, C] = ???

    // …
  }

`Documentation`

sealed trait Adt
case class Record(fields: List[String]) extends Adt
case class CoProd(alternatives: List[Record]) extends Adt

implicit val arrowChoiceData: Arrow[Data] with Choice[Data] =
  new Arrow[Data] with Choice[Data] {

    def choice[A, B, C](f: Adt, g: Adt): Adt = ???

    // …
  }

`Documentation`

sealed trait Adt
case class Record(fields: List[String]) extends Adt
case class CoProd(alternatives: List[Record]) extends Adt

implicit val arrowChoiceData: Arrow[Data] with Choice[Data] =
  new Arrow[Data] with Choice[Data] {

    def choice[A, B, C](f: Adt, g: Adt): Adt =
      (f, g) match {
        case (r1: Record,  r2: Record)  => CoProd(r1 :: r2 :: Nil)
      }

    // …
  }

`Documentation`

sealed trait Adt
case class Record(fields: List[String]) extends Adt
case class CoProd(alternatives: List[Record]) extends Adt

implicit val arrowChoiceData: Arrow[Data] with Choice[Data] =
  new Arrow[Data] with Choice[Data] {

    def choice[A, B, C](f: Adt, g: Adt): Adt =
      (f, g) match {
        case (r1: Record,  r2: Record)  => CoProd(r1 :: r2 :: Nil)
        case (CoProd(as1), CoProd(as2)) => CoProd(as1 ++ as2)
      }

    // …
  }

`Documentation`

sealed trait Adt
case class Record(fields: List[String]) extends Adt
case class CoProd(alternatives: List[Record]) extends Adt

implicit val arrowChoiceData: Arrow[Data] with Choice[Data] =
  new Arrow[Data] with Choice[Data] {

    def choice[A, B, C](f: Adt, g: Adt): Adt =
      (f, g) match {
        case (r1: Record,  r2: Record)  => CoProd(r1 :: r2 :: Nil)
        case (CoProd(as1), CoProd(as2)) => CoProd(as1 ++ as2)
        case (r1: Record,  CoProd(as2)) => CoProd(r1 :: as2)
      }

    // …
  }

`Documentation`

sealed trait Adt
case class Record(fields: List[String]) extends Adt
case class CoProd(alternatives: List[Record]) extends Adt

implicit val arrowChoiceData: Arrow[Data] with Choice[Data] =
  new Arrow[Data] with Choice[Data] {

    def choice[A, B, C](f: Adt, g: Adt): Adt =
      (f, g) match {
        case (r1: Record,  r2: Record)  => CoProd(r1 :: r2 :: Nil)
        case (CoProd(as1), CoProd(as2)) => CoProd(as1 ++ as2)
        case (r1: Record,  CoProd(as2)) => CoProd(r1 :: as2)
        case (CoProd(as1), r2: Record)  => CoProd(r2 :: as1)
      }

    // …
  }

Arrows and choice: summary

Arrows (with choice), like monads, provide enough expressive power to describe record types and sum types
Like applicative functors, they support a (useful) documentation interpreter

Arrows are relevant for…

Business rules
Pipelines of data transformations
FRP (e.g. yampa)

Summary

We compared the expressive power of the operations provided by three notions of computation (applicative functors, arrows and monads)
We observed that when we increase the expressive power for users, at the same time we decrease our ability to give useful meanings to their code
- See also “Constraints liberate, liberties constrain”, Rúnar Bjarnason, 2015 [video]
Arrows (with choice) provide a compromise between applicative functors and monads
- Users benefit from more expressive power than with applicative functors
- Interpreters are less constrained than with monads

Do it with (free?) arrows!

Outline

1 Context

1.1 Description vs interpretation

Description vs interpretation

Description: HTML document

Description: arithmetic expression

Interpretations make sense out of descriptions

Interpretations

The essence of descriptions

1.2 Domain: data

Data description

Interpretations of data descriptions

Let’s design a data description language

Let’s try our DataDescr language

Let’s describe a User data type (1)

Let’s describe a User data type (2)

Let’s describe a User data type (3)

Let’s describe a User data type (4)

2 Applicative Functor

2.1 We need the power of applicative functors!

Let’s upgrade our language

Feel the power! (1)

Feel the power! (2)

Intuition of an applicative functor

Data[User]?

2.2 Interpreters

Decoder

Documentation

3 Monad

3.1 Sum types description

Is our language powerful enough to describe this data type?

Attempt

Monads to the rescue

Feel the power of the monad!

Intuition of a monad

3.2 Interpreters

Decoder

Documentation

Documentation

Documentation

Documentation

Documentation

Documentation

Monads: summary

4 Arrow

Let’s make our Data an arrow

4.1 Describing data types with arrows

Record types

Record types

Record types

Intuition of an arrow

Sum types

Sum types

5 Choice

Add the power of making choices

Can we now describe sum types?

shapeDecoder

Intuition of choice

Can we also implement a (useful) documentation interpreter?

Documentation

Documentation

Documentation

Documentation

Documentation

Documentation

Documentation

Documentation

Documentation

Documentation

Documentation

Documentation

Documentation

Documentation

Documentation

Documentation

Documentation

Arrows and choice: summary

Arrows are relevant for…

6 Summary

Let’s try our `DataDescr` language

Let’s describe a `User` data type (1)

Let’s describe a `User` data type (2)

Let’s describe a `User` data type (3)

Let’s describe a `User` data type (4)

`Data[User]`?

`Decoder`

`Documentation`

`Decoder`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

Let’s make our `Data` an arrow

`shapeDecoder`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`

`Documentation`