λ Tony's Blog λ

Funky Scala Bifunctor

Posted on February 14, 2009

A co-variant binary functor (aka bifunctor) is any type constructor with a kind * -> * -> * that can satisfy identity and composition when mapping on either type variable. A couple of examples of bifunctors in the Scala library are

  • Tuple2

  • Either

Note that Function1 is not a bifunctor, evident by the fact that it is contra-variant in its first type variable. It is notable that Tuple2 represents conjunction while Either represents the disjunction of two theorems under the Curry-Howard Isomorphism (Function1 represents implication`).

A bifunctor often combines the two possible mappings into a function called bimap with the signature (Scala-ish syntax):

F[A, B] => (A => C) => (B => D) => F[C, D]

Recall that identity and composition laws must satisfy in the implementation.

Consider now an implementation of bimap for both Tuple2 and Either:

trait Bifunctor[F[+_, +_]] {
  def bimap[A, B, C, D](fa: F[A, B], f: A => C, g: B => D): F[C, D]
}

object Bifunctor {
  implicit def Tuple2Bifunctor = new Bifunctor[Tuple2] {
    def bimap[A, B, C, D](fa: (A, B), f: A => C, g: B => D) =
      (f(fa._1), g(fa._2))
  }

  implicit def EitherBifunctor = new Bifunctor[Either] {
    def bimap[A, B, C, D](fa: Either[A, B], f: A => C, g: B => D) =
      fa match {
        case Left(a) => Left(f(a))
        case Right(b) => Right(g(b))
      }
  }
}

These implementations are quite easy to understand, but they are not so pretty to use. This is an unfortunate consequence of a number of factors about Scala, including:

  • Higher-kinds are never inferred

  • Functions cannot be used in infix position

In Scala, methods that end with a colon (:) can have their arguments swapped when not using dot notation. For example, the following two lines are equivalent:

obj.::(arg) 
arg :: obj

This is evident when using scala.List and the cons (::) method.

We might wrap up our Bifunctor implementation similarly and create some nice syntax for mapping on the bifunctor. For example, let us define three methods on any Bifunctor value:

  • <-: for mapping on one side

  • :-> for mapping on the other side

  • <-:-> for mapping on both sides

trait BifunctorW[F[+_, +_], A, B] {
  val value: F[A, B]
  val bifunctor: Bifunctor[F]

  def <-:->[C, D](f: A => C, g: B => D) = bifunctor.bimap(value, f, g)

  def <-:[C](f: A => C) = bifunctor.bimap(value, f, identity[B])

  def :->[D](g: B => D) = bifunctor.bimap(value, identity[A], g)
}

object BifunctorW {
  // a somewhat verbose but handy trick
  // for partially applying type variables.
  def bifunctor[F[+_, +_]] = new BifunctorApply[F] {
    def apply[A, B](v: F[A, B])(implicit b: Bifunctor[F]) =
        new BifunctorW[F, A, B] {
      val value = v
      val bifunctor = b
    }
  }

  trait BifunctorApply[F[+_, +_]] {
    def apply[A, B](v: F[A, B])(implicit b: Bifunctor[F]): BifunctorW[F, A, B]
  }

  implicit def Tuple2Bifunctor[A, B](v: (A, B)) =
    bifunctor[Tuple2](v)

  implicit def Either2Bifunctor[A, B](v: Either[A, B]) =
    bifunctor[Either](v)
}

So we’ve wrapped a value and its Bifunctor implementation. So how does it look when we use it? Like this!

object Main {
  def main(args: Array[String]) {
    import BifunctorW._

    val x: Either[Int, String] = Left(7)
    val y = ("hello", 42)

    val f = (n: Int) => n + 1
    val g = (s: String) => s.reverse
    val h = (s: String) => s.toUpperCase
    val i = (n: Int) => n * 2

   // Pretty neat eh?
    val p = f <-: x :-> g
    val q = h <-: y :-> i

    // $ scala Main
    // Left(8)
    // (HELLO,84)
    println(p)
    println(q)
  }
}

And I think that’s an elegant use of a sometimes baroque (when trying for advanced concepts) language :)