Printer combinators. The duality of parsing

printer-combinators.org

Printing combinators

In the same way parsing combinators pave the way for doing parsing in a functional way, printing combinators do the same for printing.

Parsing combinators

But, what does parsing combinators mean?

Parsing combinators

What’s a parser

type Parser[A] = String => A

Parsing combinators

And what does parsing combinators mean? Parsing combinators allow us to combine small parsers into bigger ones:

/* parse & match */
def string(s: String): Parser[String]
/* parse & match `n` elements from the input as a String */
def take(n: Int): Parser[String]
/* match chars from the input until they don't satisfy f */
def takeWhile(f: Char => Boolean): Parser[String]
/* match & return the rest of the input */
def takeRest: Parser[String]

Typeclasses for parsing

There are some particular typeclasses we use for combining parsers:

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

// applicative allows us to combine fa: F[A] and fb: F[B] into F[(A, B)] with <*>
sealed trait Applicative[F[_]] extends Functor[F]{
  def pure[A](a: A): F[A]
  def ap[A, B](fab: F[A => B])(fa: F[A]): F[B]
}

// alternative allows us to combine fa:  F[A] and F[B] into F[A \/ B] with <|>
sealed trait Alternative[F[_]] extends Applicative[F] {
  def combine[A]:(fa: F[A])(fa2: F[A]): F[A]
}

Combining parsers

Since we have an instance of Parser[A] for Applicative and Alternative, we can use it’s operations for combining parsers:

/**
Pepe Garcia
pepe@pepegar.com

or

Pepe Garcia
898393202
*/
sealed trait Contact
object Contact {
  case class Email(name: String, domain: String) extends Contact
  case class Telephone(num: String) extends Contact
}
case class User(name: String, contact: Contact)

val parseEmail: Parser[Email] =
  ((takeWhile(_ != "@") <* const("\n")) <*> takeRest).map(Email)

val parseTelephone: Parser[Telephone] =
  takeRest.map(Telephone)

val parseContact: Parser[Contact] =
  parseEmail <|> parseTelephone

(takeWhile(_ != "\n") <* const("\n") <*> parseContact).map(User)

The duality of parsing

We know that parsing is for consuming strings and producing values, but what’s its dual?

Printing

the dual of a Parser is a Printer, a datatype which, given a value, provides its string representation.

case class Printer(print: A => String)

Printing combinators

def const(str: String): Printer[Unit] =
  Printer(Function.const(str))

def space = const(" ")

def newLine = const("\n")

val string: Printer[String] = Printer(identity)

def optional[A](p: Printer[A]): Printer[Option[A]] =
  Printer(_.fold("")(p.print))

def mkList[A](p: Printer[A], sep: String): Printer[List[A]] =
  Printer({
    case Nil => ""
    case xs  => xs.map(p.print).mkString(sep)
  })

The duality of parsing combinators

We used Applicative and Alternative for combining parsers but… how do we combine printers?

Typeclasses for printing

There are some typeclasses that we can use for printing:

trait Contravariant[F[_]] {
  def contramap[A, B](f: A => B)(fb: F[B]): F[A]
}

/* Divisible allows us to combine `fa: F[A]` and `fb: F[B]` into `F[C]` by `fa >*< fb`*/
trait Divisible[F[_]] extends Contravariant[F] {
  def divide[A, B, C](fa: F[A], fb: F[B])(cab: C => (A, B)): F[C]
  def conquer[A]: F[A]
}

/* Divisible allows us to combine `fa: F[A]` and `fb: F[B]` into `F[C]` by `fa >|< fb`*/
trait Decidable[F[_]] extends Divisible[F] {
  def choose[A, B, C](fa: F[A], fb: F[B])(cab: C => Either[A, B]): F[C]
}

Combining printers

Imagine the same case:

sealed trait Contact
object Contact {
  case class Email(name: String, domain: String) extends Contact
  case class Telephone(num: String) extends Contact
}
case class User(name: String, contact: Contact)

val printEmail: Printer[Email] =
  (string >* const("@") >*< string).contramap(Email)
val printTelephone: Printer[Telephone] =
  string.contramap(Telephone)
val printContact: Printer[Contact] =
  printEmail >|< printTelephone
val printUser: Printer[User] =
  (string >* const("\n") >*< printContact).contramap(User)