Type classes, category theory, and Scala

December 08, 2012

This is a light reference for Scala implementations of some commonly used aspects of category theory, and will grow over time as I encounter useful ways to apply it.

Functor

A functor lifts a function of type A => B to a function of type F[A] => F[B]

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

The unary function functor

The unary function functor is used to compose a bunch of unary functions together, like Scala's andThen function.

class Fn1Functor[A, B](g: A => B) extends Functor[B, ({type λ[α] = A => α})#λ] {
  override def map[C](f: B => C): (A => C) = a => f(g(a))
}

Example: the function fn1FunctorEx below has the form x => ((x + 1) * 2) - 3

implicit def fn1Functor[A, B](g: A => B) = new Fn1Functor(g)

val fn1FunctorEx: Int => Int =
  { x: Int => x + 1 } map { x: Int => x * 2 } map { x: Int => x - 3 }

val x = fn1FunctorEx(5) // x = ((5 + 1) * 2) - 3 = 9

Applicative

An applicative builds upon a functor with a way to apply an already-lifted function of type F[A => B] as a function of type F[A] => F[B]

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

The unary function applicative functor

class Fn1Applicative[A, B](g: A => B) extends Fn1Functor[A, B](g)
                                         with Applicative[B, ({type λ[α] = A => α})#λ] {
  override def ap[C](f: A => B => C): (A => C) = a => f(a)(g(a))
}

Example:

implicit def fn1Applicative[A, B](g: A => B) = new Fn1Applicative(g)
val fn1ApplicativeDemo: Int => Int =
  { x: Int => x + 1 } ap { x: Int => y: Int => x * (y + 3) }
val x = fn1ApplicativeDemo(5) // x = 5 * ((5 + 1) + 3) = 45

The optional value applicative functor

The optional value applicative functor can be used to pass potentially unknown arguments to a function.

class OptionApplicative[A](a: A) extends Applicative[A, Option] {
  override def map[B](f: A => B): Option[B] = Option(f(a))
  override def ap[B](f: Option[A => B]): Option[B] = f.map(_(a))
}

Example: the function add3 takes three integers that might be null, which Scala interprets as zero, and sums them.

implicit def optionApplicative[A](a: A) = new OptionApplicative(a)
val add3: Int => Int => Int => Int = x => y => z => x + y + z

val optionApplicativeDemo1 = 1 ap (2 ap (3 map add3)) // Some(6)

val nope: Int = null.asInstanceOf[Int]
val optionApplicativeDemo2 = 1 ap (nope ap (3 map add3)) // Some(4)

The either applicative functor (aka Validation)

The either applicative functor can be used to pass potentially invalid arguments to a function, accumulating invalid arguments along the way. This is also known as Validation, and is useful when arguments to a function must first be parsed.

trait Semigroup[A] {
  def append(a: A): A
}

class ListSemigroup[A](as: List[A]) extends Semigroup[List[A]] {
  override def append(as2: List[A]) = as ++ as2
}

class EitherApplicative[B, A](x: Either[B, A])(implicit bs: B => Semigroup[B])
  extends Applicative[A, ({type λ[α] = Either[B, α]})#λ] {
  override def map[C](f: A => C): Either[B, C] = x match {
    case Right(a) => Right(f(a))
    case Left(b)  => Left(b)
  }
  override def ap[C](f: Either[B, A => C]): Either[B, C] = x match {
    case Right(a) => f match {
      case Right(ac) => Right(ac(a))
      case Left(b)   => Left(b)
    }
    case Left(b) => f match {
      case Right(_) => Left(b)
      case Left(b2) => Left(bs(b) append b2)
    }
  }
}

Example: the function add4 takes four integers that have been parsed from strings, and sums them.

implicit def listS[A](as: List[A]) = new ListSemigroup(as)
implicit def eitherA[A, B](x: Either[B, A])(implicit bs: B => Semigroup[B]) = new EitherApplicative(x)
import EitherApplicative._

val add4: Int => Int => Int => Int => Int = w => x => y => z => w + x + y + z

def parse(x: String): Either[List[String], Int] = try {
  Right(x.toInt)
} catch {
  case _ => Left(List("'" + x + "' is not an integer"))
}

val rightApplicativeDemo1 = parse("1") ap (parse("2") ap (parse("3") ap (parse("4") map add4)))
  // rightApplicativeDemo1 = Right(10)

val leftApplicativeDemo1 = parse("1") ap (parse("nooo") ap (parse("3") ap (parse("fourve") map add4)))
  // leftApplicativeDemo1 = Left(List('nooo' is not an integer, 'fourve' is not an integer))

This syntax can be cleaned up a bit with <%> and <*> functions to apply map and ap as infix operators.

object EitherApplicative {
  val lifter = new Applicative.Lifter[({type λ[α] = Either[List[Any], α]})#λ]
  implicit def functee[A, B](g: A => B) = new lifter.Functee(g)
  implicit def applicatee[A, B](f: Either[List[Any], A => B]) = new lifter.Applicatee(f)
}

object Applicative {
  class Lifter[F[_]] {
    class Functee[A, B](g: A => B) {
      def <%>(f: Functor[A, F]) = f map g
    }
    class Applicatee[A, B](f: F[A => B]) {
      def <*>(a: Applicative[A, F]) = a ap f
    }
  }
}

val rightApplicativeDemo2 = add4 <%> parse("1") <*> parse("2") <*> parse("3") <*> parse("4")
  // rightApplicativeDemo2 = Right(10)

val leftApplicativeDemo2 = add4 <%> parse("1") <*> parse("nooo") <*> parse("3") <*> parse("fourve")
  // leftApplicativeDemo2 = Left(List('fourve' is not an integer, 'nooo' is not an integer))

Monad

A monad builds upon an applicative by adding a way to "tilt" an inter-category function of type A => F[B] and apply it as a function of type F[A] => F[B]

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

The unary function monad (aka the Reader monad)

The unary function monad is used to pass a single external value into a bunch of functions that depend on it. This is also known as the Reader monad, and is a way to implement dependency injection.

class Fn1Monad[A, B](g: A => B) extends Fn1Applicative[A, B](g)
                                   with Monad[B, ({type λ[α] = A => α})#λ] {
  override def flatMap[C](f: B => (A => C)): (A => C) = a => f(g(a))(a)
}

Example: the function fn1MonadEx1 below has the form x => (x + 1) * x

implicit def fn1Monad[A, B](g: A => B) = new Fn1Monad(g)

val fn1MonadEx1: Int => Int =
  { x: Int => x + 1 } flatMap { x: Int => y: Int => x * (y + 3) }

val x = fn1MonadEx1(5) // x = (5 + 1) * (5 + 3) = 48

Example: like fn1MonadEx1 above, the function fn1MonadEx2 below has the form x => (x + 1) * x

implicit def fn1Monad[A, B](g: A => B) = new Fn1Monad(g)

val fn1MonadEx2: Int => Int =
  for {
    a <- { x: Int => x + 1 }
    b <- { x: Int => y: Int => x * y } apply a
  } yield b

val x = fn1MonadEx2(5) // x = (5 + 1) * (5 + 3) = 48

The state monad

The state monad is used to pass a modifiable context from one function invocation to the next.

class StateMonad[S, A](g: S => (A, S)) extends Monad[A, ({type λ[α] = S => (α, S)})#λ] {
  override def map[B](f: A => B): (S => (B, S)) =
    state => {
      val (a, state1) = g(state)
      (f(a), state1)
    }
  def ap[B](f: S => (A => B, S)): (S => (B, S)) =
    state => {
      val (a, state1) = g(state)
      val (atob, state2) = f(state1)
      (atob(a), state2)
    }
  override def flatMap[B](f: A => (S => (B, S))): (S => (B, S)) =
    state => {
      val (a, state1) = g(state)
      f(a)(state1)
    }
}

Example: logging to an in-memory list of messages

implicit def stateMonad[S, A](g: S => (A, S)) = new StateMonad(g)

val f1: List[String] => (Int, List[String]) = log => (1, "f1" :: log)
val f2: Int => List[String] => (Int, List[String]) = x => log => (x + 1, "f2" :: log)

val f3: List[String] => (Int, List[String]) = for {
  a <- f1
  b <- f2(a)
} yield b

val (x, log) = f3(Nil) // (x, log) = (2, List("f2", "f1"))

Example: explicitly setting and getting state

def set[S](s: S): StateMonad[S, S] = new StateMonad(_ => (s, s))
def get[S]: StateMonad[S, S] = new StateMonad(s => (s, s))

implicit def stateMonad[S, A](g: S => (A, S)) = new StateMonad(g)

val f1: List[String] => (Int, List[String]) = log => (1, "f1" :: log)
val f2: Int => List[String] => (Int, List[String]) = x => log => (x + 1, "f2" :: log)

val f3: List[String] => (Int, List[String]) = for {
  _ <- set(List("foo", "bar"))
  a <- f1
  s <- get[List[String]]
  _  = println("sneaky peek at the state: " + s)
  b <- f2(a)
} yield b
  // printed to stdout: "sneaky peek at the state: List(f1, foo, bar)"

val (x, log) = f3(List("this state will be replaced"))
  // (x, log) = (2, List(f2, f1, foo, bar))

Example: logging to a mutable log

We can cheat a little bit and implement a log that does something other than simply collecting log messages in memory.

trait Log { def append(level: String, message: String): Log }
class StdoutLog extends Log {
  def append(level: String, message: String) = {
    println("[" + level + "] " + message)
    this
  }
}

implicit def stateMonad[S, A](g: S => (A, S)) = new StateMonad(g)

val f1: Log => (Int, Log) = log => (1, log.append("info", "f1"))
val f2: Int => Log => (Int, Log) = x => log => (x + 1, log.append("info", "f2"))

val f3: Log => (Int, Log) = for {
  a <- f1
  b <- f2(a)
} yield b

val (x, log) = f3(new StdoutLog) // x = 2, log has printed two `info` messages to stdout

Arrow

Arrows can be a useful generalization for "assembly line" computation.

class Arrow[A, B](f: A => B) {
  def arr: A => B = f
  def >>>[C](g: B => C): A => C = (a: A) => g(f(a))
  def first[C]: Tuple2[A, C] => Tuple2[B, C] = ac => (f(ac._1), ac._2)
  def second[C]: Tuple2[C, A] => Tuple2[C, B] = ca => first(ca.swap).swap
  def ***[C,D](g: C => D): Tuple2[A, C] => Tuple2[B, D] = ac => (f(ac._1), g(ac._2))
  def &&&[C](g: A => C): A => Tuple2[B, C] = a => ***(g)((a,a))
}

Example: parallel addition

implicit def arrow[A, B](g: A => B): Arrow[A, B] = new Arrow(g)

val show: Tuple2[Int, Int] => String = x => "(" + x._1 + ", " + x._2 + ")"
val add: Int => Int => Int = x => y => x + y

val fn1ArrowDemo = (add(3) *** add(5)) >>> (add(7) *** add(11)) >>> show >>> println
  // fn1ArrowDemo = (x, y) => ((x + 3 + 7), (y + 5 + 11))

fn1ArrowDemo((1, 2))
  // prints (11, 18) to stdout