1 note &
Every single freshman CS question in ˜80 lines of Scala
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[i1], a[i2], ... a[ik])
, 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 firstyear 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 $(n1) .. (nk)$, 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_{n1}/2$ if n even
 $S_n = 3 S_{n1} + 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_{n1}+F_{n2}$ 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)) (n1)
}
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 $(n1)$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 firstyear 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_{n1}, U_{n2}, … U_{nk})$ ?
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 typesafe 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 fixedsized tuple of width k
is not an instance of a recursivelygenerated 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 Tuplek1
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 fixedwidth tuple type is crucial to what we are trying to do, so that we will temporarily forgo Scala’s native Tuple
s, and work with our very own tuples defined in the following manner:
 the singleton of type
T
is simplyT
.  for any tuple type
U
of a given widthk
, its successor, the tuple of widthk+1
, is the typePair [T,U]
(^{1})
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 ktuple argument
f : Pair[A,Pair[A, ... Pair[A,A]...]] ⇒ A
,  and a corresponding ktuple of initial elements
(a1,(a2,...(ak1,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 typesafe : if we receive a function taking k
arguments as above, but only k1
or k+1
initial elements, things should “break” at typechecking.
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 speciﬁc 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 implicitlypassed 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 oftoverlooked 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 higherorder function of arity k1
, the last argument of the recursive call can be made to depend only on the k1
arguments a2, ..., ak
. This is important, because it will let us define this as the return of some recursive function at order $(k1)$.
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 k1
:
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 typesafe: 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 nestedpairs 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 higherorder 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 rightassociative, the parentheses in the latter expression are optional.
Naturally, uncurrying is the reverse transformation, from the higherorder function to the function taking a pair. To do this with firstorder 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 arbitraryorder 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 javastyle 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 !

note we implicitly forget about heterogeneity, since we won’t need it for our particular application ↩