Becoming really rich with C# is a great example of what's coming in the version of C# in Visual Studio 2010 and it makes it obvious that C# is leaving Java in the dust. That why I'm looking at scala.

As an excercise, I translated the c# version of the stdDev function into Scala, copying the imperative non-functional style in the original c# code

Imperative version of stddev

// 1 for 1 translation of imperative c# version

def stdDevImperative(): Double = {

var now = Dates.now()

val limit = now - 3.years

var rets = List[Double]()

while (now >= _start + 12.days && now >= limit) {

val ret = getReturn(now - 7.days, now);

val retd = ret.get // might throw Exception (same as c# code)

rets = rets ::: retd :: Nil

now = now - 7.days;

}

val mean = average(rets)

val variance = sum(rets.map(r => Math.pow(r - mean, 2))) / rets.length

val weeklyStdDev = Math.sqrt(variance)

return weeklyStdDev * Math.sqrt(40)

}

Couple of notes here. I'm using the joda time scala wrapper (import org.scala_tools.time.Imports._). The sum() and average() functions should be obvious. getReturn(now - 7.days, now) returns an Option[Double] of the increase in price in the last seven days as per the c# version.

If you are learning Scala, you can stop right here! The imperative version shown above is absolutely fine. What follows here is an intellectual exercise in using functional programming techniques to reorganize the algorithm so that it does not use vars. Many people would see this as a pointless exercise. It also turns out that there is a very simple solution to this exercise which is described in the follow up section at the end of the post. |

I wanted to convert my stdDevImperative to a functional style, getting rid of all those icky vars. So this was my first go:

Simple Recursive version of stddev

// simplistic recursive version of imperative c# version

def stdDevSimpleRecursive(): Double = {

var now = Dates.now()

val limit = now - 3.years

def getListOfReturns(d : DateTime) : List[Double] = {

if (d >= _start + 12.days && d >= limit)

getReturn(d - 7.days, d).get :: getListOfReturns(d - 7.days) // Not TCO

else

Nil

}

val rets = getListOfReturns(now)

val mean = average(rets)

val variance = sum(rets.map(r => Math.pow(r - mean, 2))) /rets.length

val weeklyStdDev = Math.sqrt(variance);

return weeklyStdDev * Math.sqrt(40);

}

No more vars, but its longer and the algorithm is less obvious than the imperative version. (At least for me). Also the compiler cannot perform "tail call optimisation". And so it munches stack.

Next step: allow the compiler to use "tail call optimisation".

TCO Recursive version of stddev

// recursive version allowing TCO and insert result at head of list

def stdDevTCORecursive(): Double = {

var now = Dates.now()

val limit = now - 3.years

def getListOfReturns(results: List[Double], d : DateTime) : List[Double] = {

if (d >= _start + 12.days && d >= limit) {

val newResults = getReturn(d - 7.days, d).get :: results // optimised to add to head not tail

getListOfReturns(newResults, d - 7.days) // TCO possible

} else

results

}

val rets = getListOfReturns(List(),now).reverse // reverse unnecessary for algorithm, but matches c# ordering

val mean = average(rets)

val variance = sum(rets.map(r => Math.pow(r - mean, 2))) /rets.length

val weeklyStdDev = Math.sqrt(variance);

return weeklyStdDev * Math.sqrt(40);

}

Well it works, but its getting uglier and the actual algorithm is being obscured. (Yeah I know, premature optimisation is the root of all evil. Yada. But TCO is pretty basic).

So I got to thinking if there was a better algoirthm and couldn't think of one. All the neat algorithms use a starting list/sequence and I couldn't see one. We are going back in time 7 days at a time, stoping when we get to the first date (_start) of the available price history or we have collected 3 years worth of returns. Hell, I liked the imperative algorithm. Maybe that will change with as my brain adapts to functional techniques. I though what I need is a way of factoring out the recursion into a "thing".

Enter the unfold function described nicely by David Pollak. I though that this might be the solution. So here goes:

Unfold version of stddev

// This unfold function should probably be built into a scala standard library somewhere

def unfold[T, R](init: T)(f: T => Option[(R, T)]): List[R] = f(init) match {

case None => Nil

case Some(r, v) => r :: unfold(v)(f)

}

def stdDevUnfold(): Double = {

val now = Dates.now()

val limit = now - 3.years

def getReturnOnDayAndNextDay(someDay: DateTime) : Option[(Double, DateTime)] = {

if (someDay < _start || someDay < limit) return None

val ret = getReturn(someDay - 7.days, someDay)

Some((ret.get, someDay - 7.days)) // might throw Exception (same as c# code)

}

val rets = unfold(now)(getReturnOnDayAndNextDay)

val mean = average(rets)

val variance = sum(rets.map(r => Math.pow(r - mean, 2)))

val weeklyStdDev = Math.sqrt(variance / rets.length);

return weeklyStdDev * Math.sqrt(40);

}

So the recursion is now out of my stdDev function but the code is even more obscure. The problem is that the unfold parameter function f() has two jobs to do. (1) manage a loop counter, (in this case the current date) and (2) return a value to be collected in the returned results.

So I liked the idea of unfold because it hides the recursion, but not the multiple jobs that the function has to do. The obvious answer is to have more than one function argument: One function to get the next value for the iteration or terminate and another function that works out the result. Hang on a minute, that first function is doing two jobs: getting the next value and working out when to terminate. How about three functions? Hey wait while we're there...

This is what I see in my head as the clearest way of defining the algorithm in a sort of java/pseudocode

// Java like pseudocode

ArrayList a = new ArrayList();

for (DateTime d = today(); d > firstDateForWhichPriceIsAvaialble && d > today - 3.years; d = d - 7.days) {

a.append(getReturn(d, d-7.days));

}

Final version of stddev with forloop

The challenge was to come up with something completely stateless of course. After many iterations (ha ha) this is what I have ended up with as my new stdDev method:

def stdDevForLoop(): Double = {

val today = Dates.now()

val limit = today - 3.years

val rets =

forloop(today)(d => d >= _start && d >= limit)(d => d - 7.days) {

day =>

val ret = getReturn(day - 7.days, day)

ret.get // might throw Exception (same as c# code)

}

val mean = average(rets)

val variance = sum(rets.map(r => Math.pow(r - mean, 2))) / rets.length

val weeklyStdDev = Math.sqrt(variance);

return weeklyStdDev * Math.sqrt(40);

}

I was pretty happy with the result, which, to my non-functional brain, expresses the algorithm (slightly) more clearly than the original imperative algorithm but without using any vars. The recursion is neatly tucked away in the forloop method. The definition of forloop is shown at the end.

The icing on the cake: break and continue

I realised that c style break and continue would be relatively easy to implement copying the techniques used in breakable. As ever the devil is in the detail: as the forloop body yields a value that is collected in the list of results, I added a breakWith 'keyword' too so that you can return a last value when you break. So the following becomes possible:

def stdDevForLoopBreakAndContinue(): Double = {

val today = Dates.now()

val limit = today - 3.years

val rets = forloop(today)(d => d >= _start && d >= limit)(d => d - 7.days) {

day =>

val ret = getReturn(day - 7.days, day)

if (day == blackFriday1981) continue

if (day == blackWednesday1973) breakWith(0d) // or just plain break, if no final value required

ret.get // might throw Exception (same as c# code)

}

val mean = average(rets)

val variance = sum(rets.map(r => Math.pow(r - mean, 2))) / rets.length

val weeklyStdDev = Math.sqrt(variance);

return weeklyStdDev * Math.sqrt(40);

}

What's missing?

- Multiple loop counters. Of course you can do this by using a Tuple as the loop counter containing as many 'embedded' loop counters as you need, but this gets Lispy with the brackets. Maybe there is a nicer way.

trait ForLoops

{

def forloop[T, R]

(init: T)

(cond: T => Boolean)

(next: T => T)

(body: T => R)

: List[R] =

{

def _forloop(currentResults: List[R])(loopcounter: T) : List[R] = {

if (cond(loopcounter)) {

// Get the newResults by appending the result of the body() function on the current loopcounter

val newResults = try {

// normal case: body() returns something based on loopcounter

val bodyResult = body(loopcounter)

bodyResult match {

// if the body has no return value (Unit) then don't bother appending to the newResults

case _:Unit => currentResults

// if the body has a return value then append to the newResults

case _ => bodyResult :: currentResults

}

} catch {

case ex: ContinueException => currentResults // don't add to the currentResults

case ex: BreakException => return currentResults // exit loop so return currentResults

case BreakWithException(v) => return v.asInstanceOf[R] :: currentResults

}

// This can be tail call optimized

// Recursive call to loop with the next value of the loop counter

_forloop(newResults)(next(loopcounter))

} else {

// loop has terminated so return results

currentResults

}

}

// Seed the _forloop currentResults with an empty list and the first value (init) of the loopcounter

_forloop(List())(init).reverse

}

// Copied break and continue technique from "breakable" in Scala 2.8

def continue = throw continueException

def break = throw breakException

def breakWith(v:Any) = throw new BreakWithException(v)

private class ContinueException extends RuntimeException

private val continueException = new ContinueException

private class BreakException extends RuntimeException

private val breakException = new BreakException

private case class BreakWithException(v:Any) extends RuntimeException {

override def fillInStackTrace():Throwable = {

// this is a performance optimisation. the actual stack trace is not required.

return null;

}

}

}

Follow up: An implementation using Iterator.iterate:

In the next couple of posts (in the future) I look at various alternatives to the forloop function that I have described above and got some very helpful comments from various people. The simplest (and built-in) solution that I found was using the new Iterator.iterate method in Scala 2.8pre along with takeWhile and map. Also, a very neat alternative to Iterator.iterate is to use define an iterate method that uses lazy Stream.

def stdDevIteratorIterate(): Double = {

val today = Dates.now()

val limit = today - 3.years

val dates = Iterator.iterate(today)(_ - 7.days) takeWhile (d => d >= _start && d >= limit) toList

val rets = dates.map(d => getReturn(d - 7.days, d).get)

val mean = rets.average

val variance = rets.map(r => Math.pow(r - mean, 2)).average

val weeklyStdDev = Math.sqrt(variance);

return weeklyStdDev * Math.sqrt(40);

}