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 point-free style for conciseness. End of the story: To understand it again a couple of weeks later, I start expanding to annotated pointful again.

This small 10-lines library allows to define point-free 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.

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.

Comments