4

Scenario:

val col: IndexedSeq[Array[Char]] = for (i <- 1 to n) yield {
   val x = for (j <- 1 to m) yield 'x'
   x.toArray
}

This is a fairly simple char matrix. toArray used to allow updating.

  var west = last.x - 1
  while (west >= 0 && arr(last.y)(west) == '.') {
      arr(last.y)(west) = ch;
      west -= 1;
  }

This is updating all . to ch until a non-dot char is found.

Generically, update until stop condition is met, unknown number of steps.

What is the idiomatic equivalent of it?

Conclusion

It's doable, but the trade-off isn't worth it, a lot of performance is lost to expressive syntax when the collection allows updating.

flavian
  • 28,161
  • 11
  • 65
  • 105

2 Answers2

3

Your wish for a "cleaner, more idiomatic" solution is of course a little fuzzy, because it leaves a lot of room for subjectivity. In general, I'd consider a tail-recursive updating routine more idiomatic, but it might not be "cleaner" if you're more familiar with a non-functional programming style. I came up with this:

@tailrec
def update(arr:List[Char], replace:Char, replacement:Char, result:List[Char] = Nil):List[Char] = arr match {
    case `replace` :: tail =>
        update(tail, replace, replacement, replacement :: result)
    case _ => result.reverse ::: arr
}

This takes one of the inner sequences (assuming a List for easier pattern matching, since Arrays are trivially convertible to lists), and replaces the replace char with the replacement recursively.

You can then use map to update the outer sequence, like so:

col.map { x => update(x, '.', ch) }

Another more reusable alternative is writing your own mapUntil, or using one which is implemented in a supplemental library (Scalaz probably has something like it). The one I came up with looks like this:

def mapUntil[T](input:List[T])(f:(T => Option[T])) = {
    @tailrec
    def inner(xs:List[T], result:List[T]):List[T] = xs match {
        case Nil => Nil
        case head :: tail => f(head) match {
            case None => (head :: result).reverse ::: tail
            case Some(x) => inner(tail, x :: result)
        }
    }

    inner(input, Nil)
}

It does the same as a regular map invocation, except that it stops as soon as the passed function returns None, e.g.

mapUntil(List(1,2,3,4)) {
    case x if x >= 3 => None
    case x => Some(x-1)
}

Will result in

List[Int] = List(0, 1, 3, 4)

If you want to look at Scalaz, this answer might be a good place to start.

Community
  • 1
  • 1
fresskoma
  • 25,481
  • 10
  • 85
  • 128
  • Please note that I wrote up the `mapUntil` implementation just now and it might very well contain a hidden "gift" (read: bug). If you're planning on using it in production, I'd definitely whip up a couple of unit tests for it ;) – fresskoma Oct 29 '13 at 13:26
  • I have no idea what to make of your last comment. Could you clarify? I'd be interested in some concrete data on how much slower `mapUntil` actually is, and why you'd want to use `update` on a list. – fresskoma Oct 29 '13 at 13:43
2

x3ro's answer is the right answer, esp. if you care about performance or are going to be using this operation in multiple places. I would like to add simple solution using only what you find in the collections API:

col.map { a =>
  val (l, r) = a.span(_ == '.')
  l.map {
    case '.' => ch
    case x => x
  } ++ r
}
wingedsubmariner
  • 13,350
  • 1
  • 27
  • 52