Using continuations to reorder type inference, or, a lesson in literal program design

Consider the following definition for a chain of computations:

  1  sealed trait Chain[-A,+B]
  2  case class End[A]() extends Chain[A,A]
  3  trait Chaining[A,B] extends Chain[A,B] {
  4    type I
  5    val first: A => I
  6    val rest: Chain[I,B]
  7  }

It is much like the List type, except that there is a hidden (existential) dependency between adjacent elements.

The "nestedness" of the structure is chosen to be like the List type for a very specific reason: when you go to use a Chain, you will perform the first computation first, so it should be the least nested; the last computation should be the most nested.

List defines a right-associative :: operator for building. Let us define such an operator:

  8  sealed trait Chain[-A,+B] {
  9    def :->:[A2<:A,P](f: P => A2): Chain[P,B] = new Chaining[P,B] {
 10      type I = A
 11      val first = f
 12      val rest = Chain.this
 13    }
 14  }

But we see we have a type inference problem:

 15  // Note the type annotation needed for second stage.
 16  val pipeline = (
 17         { (i: Int) => i.toString }
 18    :->: { (s: String) => s ++ s }
 19    :->: End()
 20  )

We might be tempted to think that the problem arises with Scala insisting that infix operators be members -- this does seem to be a likely explanation, since :->: being a member means that Scala must deduce the type of the right-hand operand first, which is the opposite of the direction in which we would like type information to flow. But you will find that the following non-member function fairs no better:

 21  def c[A,B,C](f: A => B, rest: Chain[B,C]): Chain[A,C] = f :->: rest

But we can learn something from the areas where Scala's type inference does seem to work very well, namely chains of list operations, map, filter, grouBy, etc, where you almost never need to annotate types. The reason is that any stage of a list-operation chain is itself an "incomplete operation chain" (ie we are (potentially) not done the computation yet), which can be extended to another incomplete chain by way of the next map or filter.

So what we need is a representation of an "incomplete Chain".

The most obvious meaning of an "incomplete Chain" is "something that can be turned into a complete chain by providing the following steps".

Principle rule of functional programming design: when you can say plainly and succinctly what something "is", translate that sentence literally into code, and there is your design.

Do not use tricks, do not use fancy types: simply turn sentences into their most literal meaning.

(Analogously in imperative code, you are looking to say what something "does").

Let us apply the rule as literally as we can:

 22  trait ChainBuilder[A,B] { outer =>
 23    def build[C](rest: Chain[B,C]): Chain[A,C]
 24  }

Our "incomplete Chain" is, unsurprisingly, a kind of continuation, since a continuation is the most basic form of an incomplete computation.

We can then define the incremental building operations:

 25  trait ChainBuilder[A,B] { outer =>
 26    def build[C](rest: Chain[B,C]): Chain[A,C]
 27  
 28    def and[C](f: B => C) = new ChainBuilder[A,C] {
 29      def build[D](rest: Chain[C,D]) = outer.build(f :->: rest)
 30    }
 31    def done = build(End())
 32  }
 33  
 34  def start[A] = new ChainBuilder[A,A] {
 35    def build[B](rest: Chain[A,B]) = rest
 36  }

And now everything works:

 37  val pipeline3 = (start[Int]
 38    and { i => i.toString }
 39    and { s => s ++ s }).done

I feel there may be something more useful here than merely getting better type inference but I haven't yet figured out what.