This post is about writing a single program that returns the stream representing any recursive sequence of order $k$, which $i$th term a[i] = f(a[i-1], a[i-2], ... a[i-k]), for all $k$, in Scala. It explains things very slowly: If the meaning of the previous sentence is already 100% clear to you, you can easily skip the next 2 paragraphs.

All the code in this post can be found as a gist here.

Recursive sequences and their order

Most first-year computer science questions aim at teaching students recursion. Hence, they involve a flurry of questions about defining recursive sequence of varied orders.

What’s a recursive sequence ? It’s a sequence whose value at any rank $n$ is defined by a function of the values at rank $(n-1) .. (n-k)$, and the initial values at ranks $1 … k$. $k$ is the order. For example, the $n$th term $S_n$ of a Syracuse sequence - a recursive sequence of order 1 - is given by:

• $S_n = S_{n-1}/2$ if n even
• $S_n = 3 S_{n-1} + 1$ if n odd

Of course, you have to choose an initial term to define the sequence properly, but a famous conjecture is precisely that for any initial term, a Syracuse sequence - i.e. a member of the class of sequences that verify this recurrence relation - converges towards the cycle (1,4,2).

Another example is the Fibonacci sequence, a recursive sequence of order 2:

• $F_n = F_{n-1}+F_{n-2}$ if n ≥ 2
• $F_1 = 1$
• $F_0 = 0$

Naturally, basic examples about recursion start with sequences of order one, and then move on to sequences of order two, usually with Fibonacci. The student is then asked to notice that the naive way of defining the Fibonacci sequence leads to a exponential number of calls, which allows the teacher to introduce notions such as e.g. memoization, or dynamic programming.

Generic recursive sequences, as streams

A short while later, the student realizes that for a fixed $k$, there is a generic way of computing the $n$th term of a recursive sequence of order $k$, in linear time. Here it is for $k = 2$ :

def recTwo[A](f : A ⇒ A ⇒ A) (x:A) (y:A) (n:Int) : A =
  n match {
    case 0 ⇒ x
    case 1 ⇒ y
    case _ ⇒ recTwo (f) (y) (f (x) (y)) (n-1)
  }

We abstract over the function and initial elements here: all you need to do to define the Fibonacci sequence is invoke recTwo ((x:Int) ⇒ (y:Int) ⇒ x + y)(0)(1). The crucial thing that makes the computation of the $n$th term linear is that you are shifting the whole sequence by one rank at each call, or, equivalently, saying that the nth term of the sequence with initial terms $(x,y)$ is the $(n-1)$th term of the sequence with the same recurrence relation $f$ and initial terms $(y, f(x,y))$. In effect, it’s a witty memoization trick that reuses the initial terms arguments passed to recTwo.

So far, so good. Now, it turns out that it’s not too difficult to reuse the same reasoning to upgrade this function to one returning the Stream of the elements of the recursive sequence. It even makes the whole business simpler, since we don’t have to deal with $n$:

import Stream._
def recStreamTwo[A](f : A ⇒ A ⇒ A) (x:A) (y:A):Stream[A] =
  x #:: recStreamTwo (f) (y) (f(x)(y))

Then to get the first 10 terms of the Fibonacci sequence:

  recStreamTwo ((x:Int) ⇒ (y:Int) ⇒ x + y)(0)(1) take 10 print

Easy, right ? In fact, you can even apply the pattern to a sequence of any order, and define:

def recStreamK [A](f : A ⇒ A ⇒ ... A)
                  (x1:A) ... (xk:A):Stream[A] =
  x1 #:: recStreamK (f) (x2) (x3)  ...  (xk) (f(x1,x2,..., xk))

Good. Now, it turns out that this pattern solves most of the first-year CS questions about defining recursive sequences of a given order. But we still have to write a slightly different function, with a slightly different number of parameters, every time the order $k$ changes.

Generalizing over the order

The problem

My question is : can we generalize over the order ? That is, can we write a single function that, for all $k$, allows us to generate the stream of elements $U_n$, given $a_1, … a_k$ and a function $f$ such that $U_n = f(U_{n-1}, U_{n-2}, … U_{n-k})$ ?

The instinctive answer is no, at least within the bounds of the type system, since the type of the argument f in recStreamK is fixed by the order of the recursive sequence, which is also the arity of the corresponding recurrence relation defined by f. The common perception would have it that to generalize over the recursive order we need:

• a macro language
• initial arguments passed as a list, or a stream
• type casts, or an equivalent way to bypass the type system
• dependent types
• …

All those solutions are interesting. In fact, some were proposed in a recent Stackoverflow.com question. I learnt a lot from that question, and upvoted accordingly.

But in Scala, we don’t necessarily need to resort to that. It turns out that with Scala’s overlapping implicits, we can define a single constructor that will automatically generate the appropriate stream for any order.

In a type-safe manner.

Here’s how.

A small proviso

More exactly, “here’s how” with a temporary proviso on tuples (that we will remove at the end): in Scala, the usual fixed-sized tuple of width k is not an instance of a recursively-generated type built from nested pairs, it is a bespoke constant type Tuplek (for a fixed k between 2 and 22), with little structural relation to Tuplek-1 or Tuplek+1. In particular, there is no recursive relation that allows me to consider something structurally akin to a function of type Tuplek ⇒ Tuplek+1 for any given k. As we will see, having some sort of recursive structure recognizable within some fixed-width tuple type is crucial to what we are trying to do, so that we will temporarily forgo Scala’s native Tuples, and work with our very own tuples defined in the following manner:

• the singleton of type T is simply T.
• for any tuple type U of a given width k, its successor, the tuple of width k+1, is the type Pair [T,U](¹)

Forget everything you know about Scala’s Tuple5 for a minute: when we think (1,2,3,4,5), what we are really going to write is (1,(2,(3,(4,5)))). The same goes for Tuple2 ...Tuple22. In a later, separate step, we will come back to how to apply this to regular arguments.

So, let’s recapitulate: we want a generic function that given two arguments:

• a function taking any k-tuple argument f : Pair[A,Pair[A, ... Pair[A,A]...]] ⇒ A,
• and a corresponding k-tuple of initial elements (a1,(a2,...(ak-1,ak)...)),

returns the Stream[A] consisting of the recursive sequence of order k defined by the recurrence relation given by f and the initial elements a1, ... ak.

We want that single program to work for any k, but we want to be type-safe : if we receive a function taking k arguments as above, but only k-1 or k+1 initial elements, things should “break” at type-checking.

Overlapping implicits

As per Fighting Bit Rot With Types:

The foundations of Scala’s implicits are quite simple. A method’s last argument list may be marked as implicit. If such an implicit argument list is omitted at a call site, the compiler will, for each missing implicit argument, search for the implicit value with the most specific type that conforms to the type of that argument. For a value to be eligible, it must have been marked with the implicit keyword, and it must be in the implicit scope at the call site.

As it turns out, those implicit arguments form implicitly-passed dictionaries, and can carry transitive constraints: a method can define an implicit (with the implicit prefix keyword), and itself require implicit arguments - ensuring the propagation of constraints. These two mechanisms:

• automatic instantiation
• constraint propagation

make Scala’s implicits a flavor of type classes. The feature we are going to be mostly interested in is the oft-overlooked overlap resolution between implicits: when two implicits are in scope, Scala follows the overloading resolution rules (Scala ref §6.26.3), and considers the lowest subclass in the subtyping lattice. Which means that if we want to direct implicit instance resolution, we can simply define the alternatives to be tried first in subtypes, and the fallback cases in supertypes. There are examples in several papers.

Recursive Implicits

Let’s consider the stream equation at rank $k$ as we have outlined it in the pattern above:

def recStreamK [A](f : A ⇒ A ⇒ ... A)
                  (x1:A) ... (xk:A):Stream[A] =
  x1 #:: recStreamK (f) (x2) (x3)  ...  (xk) (f(x1)(x2) ... (xk))

If you consider $f(a1)$ as a higher-order function of arity k-1, the last argument of the recursive call can be made to depend only on the k-1 arguments a2, ..., ak. This is important, because it will let us define this as the return of some recursive function at order $(k-1)$.

Thus we want to define an intermediary function:

prod (f) (a1, ..., ak) = (a1, ..., ak, f(a1, ..., ak))

This lets us define the stream rstream f taking a tuple of width k recursively as a function of some prod (f(a1)) taking a tuple of rank k-1:

rstream (f) (a1, ..., ak) = a1 #:: rstream f (a2, ..., ak,
                                           f(a1, ..., ak))
                          = a1 #:: rstream f (prod (f(a1))
                                             (a2, ... ak))

The next stage involves defining an implicit trait that defines methods rstream and prod for every tuple, by recognizing the Pair-directed structure of the recursive function’s argument. Since we have a recursive, structural type of tuple, this just involves a relatively simple manipulation:

trait RecStream [S,Base] {
  def prod : (S ⇒ Base) ⇒ S ⇒ Pair[Base, S]
  def rstream : (S ⇒ Base) ⇒ S ⇒ Stream[Base]
}

class RecStreamDefault {
  implicit def ZeroRS[S] = new RecStream[S,S] {
    def prod = xs ⇒ ss ⇒ (ss, xs (ss))
    def rstream = xs ⇒ ss ⇒ ss #:: rstream (xs) (xs(ss))
  }

}

object RecStream extends RecStreamDefault {
  def apply[S,B](f:S ⇒ B)
    (implicit rs:RecStream[S,B]):S ⇒ Stream[B] =
    rs.rstream(f)

  implicit def SuccRS[R,B] (implicit rs:RecStream[R,B]) =
    new RecStream[Pair[B,R],B] {
      def prod = f ⇒ a ⇒
        (a._1, rs.prod (y ⇒ f (a._1,y)) (a._2))
      def rstream = f ⇒ a ⇒
        a._1 #:: rstream (f) (rs.prod (y ⇒ f (a._1,y)) (a._2))
    }

}

This is the core of the trick: we already have something that works for any k, and returns the appropriate recursive stream. Here are examples for orders 1 and 2:

def increaser : Int ⇒ Stream[Int] =
  RecStream((x:Int) ⇒ x + 1)

def fibonacci : Pair[Int,Int] ⇒ Stream [Int] =
  RecStream(x ⇒ x._1 + x._2)

fibonacci(0,1).take(10).print
increaser(0).take(10).print

We are type-safe: if we attempt to write fibonacci(0).take(10), we get:

recstream.scala:104: error: type mismatch;
 found   : Int(0)
 required: (Int, Int)
    fibonacci(0).take(10)
              ^
one error found

The only problem is the fact that if we really want to extend this to some k ≥ 3, then we can’t use a function such as (x:Int) ⇒ (y:Int) ⇒ (z:Int) ⇒ x + y + z. We have to shape it according to our bespoke nested-pairs tuple type, and write the painful x ⇒ x._1 + x._2._1 + x._2._2. Can’t we solve that problem too, and use regular curried functions to solve our problem ?

Currying and Uncurrying

Currying is a fancy name for transforming a function that takes a pair as an argument, of type $A × B → C$ into a higher-order function that takes a single argument, and returns the function that takes the second argument before returning a result computed with both. That latter function has of course the type $A → (B → C)$. Since arrows are right-associative, the parentheses in the latter expression are optional.

Naturally, uncurrying is the reverse transformation, from the higher-order function to the function taking a pair. To do this with first-order types, you just have to write the following couple of functions:

def curry [A,B,C](f:Pair[A,B] ⇒ C) =
  (x:A) ⇒ (y:B) ⇒ f (x,y)
def uncurry [A,B,C](f: A ⇒ B ⇒ C) =
  (x:Pair[A,B]) ⇒ f (x._1) (x._2)

Now, this is all well and good if you are dealing with ground types, but what if you are dealing, as we are, with nested pairs ? How do we apply the transformation recursively to our tuples ?

We can resort in fact to the same trick of using prioritized implicits! In fact, leaving to Scala to thread the construction of implicit curryfication functions through the unification process involved in typeinference. Here is the code for recursive curryfication using prioritized overlapping implicits:

trait Curried[S,R] {
  type Fun
  def curry : (S ⇒ R) ⇒ Fun
}

class CurriedDefault {
  implicit def ZeroC[S,R] = new Curried[S,R]{
    type Fun = S ⇒ R
    def curry = f ⇒ f
  }
}

object Curried extends CurriedDefault{
  def apply[S,R] (f:S ⇒ R) (implicit c:Curried[S,R]) : c.Fun =
    c.curry(f)

  implicit def SuccC[T,S,R] (implicit c:Curried[S,R]) =
    new Curried[Pair[T,S],R] {
      type Fun = T ⇒ c.Fun
      def curry = f ⇒ x ⇒ c.curry(y ⇒ f(x,y))
    }
}

I leave the code for recursive uncurryfication to the reader as an exercise. In fact, after looking for it by herself if it suits her, said reader can find the solution as a gist here (along with all the code presented in this post).

Once this is defined, the definition of our generic recursive arbitrary-order streams is a breeze:

def sumthree (x:Int)(y:Int)(z:Int) = x+y+z
def sumthreestream = Curried(RecStream(Uncurried(sumthree _)))

The client function call is (using java-style syntax to emphasize that I am passing arguments one by one) :

sumthreestream(0)(0)(1).take(10).print

Not convinced about the type yet ? Compiling this with -Xprint:typer yields:

def sumthreestream: Int => Int => Int => Stream[Int]

Isn’t Scala wonderful ?

Further work

I suspect several improvements are possible using prioritized implicits are still possible, including:

• avoiding our ugly kludge using nested pair types entirely
• streamlining the use of curryfication and uncurryfication using views
• …

Don’t hesitate to suggest improvements in comments !