b-studios

Pointfree, Fully Annotated

When defining complex functions in pointfree style, I often find myself switching to pointful style. Sometimes, I even convert to ANF and annotate the types to understand the steps.

After completing the function definition, I often convert back to pointfree style for conciseness. End of the story: To understand it again a couple of weeks later, I start expanding to annotated pointful again.

The small 10-lines library at the end of this post allows to define pointfree functions with intermediate type annotations.

Credits: Agda and EqReasoning for syntactical inspiration.

Simple Example

val f: Int => List[Int] =
  begin [ Int ]
    [ Int ]       { _ + 1 }
    [ String ]    { _.toString }
    [ List[Int] ] { n => List(n.size) }

basically this is just syntactic sugar for the (almost equally verbose / concise):

val f: Int => List[Int] =
  ( identity[ Int ] _ )
    .andThen[ Int ]       { _ + 1 }
    .andThen[ String ]    { _.toString }
    .andThen[ List[Int] ] { n => List(n.size) }

The latter only uses functions from the Scala Predef and thus requires no “library”. Still, I have never encountered this style of writing annotated pointfree programs in the wild.

Realistic Example

You can safely ignore the details of this example, it is just to show the syntax.

lazy val loop: M[Base[A]] => W[Base[B]] = {
  val trans: M[A] => W[B] = begin [ M[A] ]
    [ M[Base[A]] ] { Monad[M].bind(_)(g) }
    [ W[Base[B]] ] { loop }
    [ W[B] ]       { Comonad[W].cobind(_)(f) }

  begin [ M[Base[A]] ]
    [ Base[M[A]] ] { kg[A] }
    [ Base[W[B]] ] { BF.map(_)(trans) }
    [ W[Base[B]] ] { kf[B] }
}

Compare with the type-annotated (almost ANF) pointful version:

lazy val loop: M[Base[A]] => W[Base[B]] = { t =>
  val trans: M[A] => W[B] = { (ma : M[A]) =>
    val mfa: M[Base[A]] = Monad[M].bind(ma) { a =>
      g(a) : M[Base[A]]
    }
    val wfb: W[Base[B]] = loop(mfa)
    Comonad[W].cobind(wfb) { (wb: W[Base[B]]) =>
      f(wb) : B
    }
  }

  val fma: Base[M[A]] = kg(t)
  val fwb: Base[W[B]] = BF.map(fma)(trans)
  val wfb: W[Base[B]] = kf(fwb)
  wfb
}

And the pointfree “one-liner”:

lazy val loop: M[Base[A]] => W[Base[B]] =
  (kg[A] _) andThen (BF.map[M[A], W[B]](_) {
    loop compose[M[A]] (Monad[M].bind(_)(g)) andThen (Comonad[W].cobind(_)(f))
  }) andThen (kf[B] _)

In particular, notice that we use compose[M[A] and andThen in a mixed way to satisfy Scala’s type inference. This is not necessary in the first version.

// The full library:
object typeannotation {
  // Typeannotations are functions with annotated function composition
  class :->:[S, T](val impl: S => T) {
    def apply[R](f: T => R): S :->: R = new :->:(f compose impl)
  }

  def begin[T]: T :->: T = new :->:(identity)
  implicit def taToFun[S, T](ta: S :->: T): S => T = ta.impl
}

Note: This post is automatically generated from a github gist. You may want to checkout the original sources and consider commenting there.