# Counting inversions

I'm trying to implement an inversion counting routine in Scala in a functional way (I don't want to port Java solution) but have real troubles with it. The sorting routine works fine but adding the code to count inversions leads to stack overflow error. Here's the code in question:

  object FuncSort
def streamMerge(l: Stream[Int], r: Stream[Int]) : Stream[Int] = {
(l, r) match {
case (x#::xs, Empty) => l
case (Empty, y#::ys) => r
case (x#::xs, y#::ys) => if(x < y) x#::streamMerge(xs, r) else y#::streamMerge(l, ys)
}
}

// This function works albeit slow
def streamSort(xs: Stream[Int]) : Stream[Int] = {
if(xs.lengthCompare(1) <= 0) xs
else {
val m = xs.length / 2
val (l, r) = xs.splitAt(m)
streamMerge(streamSort(l), streamSort(r))
}
}

// This one fails with StackOverflowError
def mergeAndCount(l: Stream[Int], r: Stream[Int]) : (Long, Stream[Int]) = {
(l, r) match {
case (x#::xs, Empty) => (0, l)
case (Empty, y#::ys) => (0, r)
case (x#::xs, y#::ys) => if(x < y) {
lazy val (i, s) = mergeAndCount(xs, r)
(i, x#::s)
} else {
lazy val (i, s) = mergeAndCount(l, ys)
(i + l.length, y#::s)
}
}
}
}


The recursive calls to mergeAndCount are not in tail position, so the Scala compiler can not use tail optimisation and the stack grows till it overflows its alloted space. The lazy modifier in lazy val (i, s) is doing you no good at all, by the way.

Scala can only do tail optimisation if the recursive call to mergeAndCount is the last expression to be called and even then only if the value returned is not modified in anyway but simply passed straight back, all the way to the first recursive call to mergeAndCount.

To fix this, you could add a local helper function inside mergeAndCount, which takes as parameters not only the two streams but also the state you need to carry forward. It would look something like this..

def mergeAndCount(left: Stream[Int], right: Stream[Int]) = {
def mac(l: Stream[Int], r: Stream[Int], m: Stream[Int], count: Long): (Long, Stream[Int]) = (l, r) match {
case (x #:: xs, Empty) => (count, merge append l)
case (Empty, y #:: ys) => (count, merge append r)
case (x #:: xs, y #:: ys) if x < y => mac(xs, r, x #:: m, count + 1)
case (x #:: xs, y #:: ys) => mac(l, ys, y #:: m, count + 1)
}
mac(left, right, Stream.empty, 0)
}


I may not have understood how the count is supposed to work, but I think the general idea is clear. Note how I split your final case statement into two by turning the if condition into a guard - it's tidier, I think. Note also that if an entire function is one big pattern match, you don't have to wrap the match in braces.

streamMerge(streamSort(l), streamSort(r))

• Then how does the streamMerge method work with large streams? It's not tail-recursive. – synapse Sep 24 '13 at 5:54
• @synapse Streams use thunks and lazy evaluation to return as quickly as possible. StreamMerge is mathematically recursive but it isn't actually recursive in the generated code; there is only ever one call to StreamMerge happening at once. – itsbruce Sep 24 '13 at 7:47
• What makes StreamSort slow is the calls to lengthCompare and length, because they force realisation of the entire stream. There are ways to work around this. Don't have time to go into them now but can find some time tonight. – itsbruce Sep 24 '13 at 7:55