1
\$\begingroup\$

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)
      }
    }
  }
}
\$\endgroup\$
1
\$\begingroup\$

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.

To be fair, nothing about

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

is in tail position either, but because all 3 functions return only a stream, you get away with it.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Then how does the streamMerge method work with large streams? It's not tail-recursive. \$\endgroup\$ – synapse Sep 24 '13 at 5:54
  • \$\begingroup\$ Well, that's exactly what I'm asking about. Inversion counter introduces strict evaluation into sorting routine so I'm looking for a way to lazily evaluate it. \$\endgroup\$ – synapse Sep 24 '13 at 7:45
  • \$\begingroup\$ @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. \$\endgroup\$ – itsbruce Sep 24 '13 at 7:47
  • \$\begingroup\$ Oop, edited my comment so things are out of sequence. @synapse, your original question talks about the stack overflow problem and nothing else - the code comments happen to mention the slow performance of the sort, but you only made that the focus of your question in the comment you just made here. \$\endgroup\$ – itsbruce Sep 24 '13 at 7:49
  • \$\begingroup\$ 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. \$\endgroup\$ – itsbruce Sep 24 '13 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.