Syntactic sugar for step-by-step annotated functions in pointfree style

01.README.md

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 (almost) pointfree "one-liner":

lazy val loop: M[Base[A]] => W[Base[B]] = {
  val trans: M[A] => W[B] = ma => loop(ma >>= g) cobind f
  (kg[A] _) andThen (_ map trans) andThen kf[B]
}

In particular, notice how we need to introduce the auxiliary definition trans and refrain from fully using pointfree style in order to assist type inference.

02.annotations.scala

// 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
}

post.yml

layout: post
title: "Pointfree, fully annotated"
date: 2017-02-20 23:44
comments: false
categories:
- functional programming
- scala

Nice trick! 👍

this is awesome. In a broadly similar vein, at $work we have:

  implicit class ThrushOpsImpl[A](x: A) {
    def $[Z](rhs: A => Z): Z = rhs(x)
  }
  implicit class ThrushOpsImp2l[A,B](x: (A, B)) {
    def $[Z](rhs: (A, B) => Z): Z = rhs(x._1, x._2)
  }
//etc...

(only with macros to elide the object creation+extra function calls).

I'd never noticed that we get largely the same syntax for free from this:

  val f = (_: Int) $
          [Int] {_ + 1} $
          [(String, String)] {i => (i.toString, (i+2).toString)} $$
          [List[Int]] { _.size :: _.size :: Nil}

@AlecZorab Nice to see that people actually use this trick :)

Regarding overhead of object creation and function calls I thought about using a combination of the miniboxing plugin and @inline annotation to address this overhead, but macros are a indeed a simpler solution there (never thought I would put these words into my mouth...).

The macro is especially simple if you use typelevel/machinist - it just becomes

  implicit class ThrushOpsImpl[A](x: A) {
    def $[Z](rhs: A => Z): Z = macro ThrushSyntax.flip[A => Z, Z] //flip comes straight from machinist
  }

  implicit class ThrushTuple2[A, B](val a: (A, B)) {
    final def $$[Z](rhs: (A, B) => Z): Z = macro ThrushSyntax.flipN[(A, B) => Z, Z]
  }

  def flipN[A: c.WeakTypeTag, Z](c: whitebox.Context)(rhs: c.Expr[A]): c.Expr[Z] = {
    import c.universe._
    //A has N + 1 type args
    val n = weakTypeOf[A].typeArgs.length - 1
    val lhs = unpackWithoutEv(c)
    val prjs = (1 to n) map (i => q"$lhs.${TermName(s"_$i")}")
    c.Expr[Z](q"$rhs.${findMethodName(c)}(..$prjs)")
  }