Off by one with sliding?

Question

One of the advantages of not handling collections through indices is to avoid off-by-one errors. That's certainly not the only advantage, but it is one of them.

Now, I often use sliding in some algorithms in Scala, but I feel that it usually results in something very similar to the off-by-one errors, because a sliding of m elements in a collection of size n has size n - m + 1 elements. Or, more trivially, list sliding 2 is one element shorter than list.

The feeling I get is that there's a missing abstraction in this pattern, something that would be part sliding, part something more -- like foldLeft is to reduceLeft. I can't think of what that might be, however. Can anyone help me find enlightenment here?

UPDATE

Since people are not clear one what I'm talking, let's consider this case. I want to capitalize a string. Basically, every letter that is not preceded by a letter should be upper case, and all other letters should be lower case. Using sliding, I have to special case either the first or the last letter. For example:

def capitalize(s: String) = s(0).toUpper +: s.toSeq.sliding(2).map {
  case Seq(c1, c2) if c2.isLetter => if (c1.isLetter) c2.toLower else c2.toUpper
  case Seq(_, x) => x
}.mkString

Answer 1

I realize this is an old question but I just had a similar problem and I wanted to solve it without having to append or prepend anything, and where it would handle the last elements of the sequence in a seamless manner. The approach I came up with is a slidingFoldLeft. You have to handle the first element as a special case (like some others mentioned, for capitalize, it is a special case), but for the end of the sequence you can just handle it like other cases. Here is the implementation and some silly examples:

def slidingFoldLeft[A, B] (seq: Seq[A], window: Int)(acc: B)(
    f: (B, Seq[A]) => B): B = {
  if (window > 0) {
    val iter = seq.sliding(window)
    iter.foldLeft(acc){
      // Operate normally
      case (acc, next) if iter.hasNext => f(acc, next)
      // It's at the last <window> elements of the seq, handle current case and 
      // call recursively with smaller window
      case (acc, next) =>
        slidingFoldLeft(next.tail, window - 1)(f(acc, next))(f)
    }
  } else acc
}

def capitalizeAndQuestionIncredulously(s: String) =
  slidingFoldLeft(s.toSeq, 2)("" + s(0).toUpper) {
    // Normal iteration
    case (acc, Seq(c1, c2)) if c1.isLetter && c2.isLetter => acc + c2.toLower
    case (acc, Seq(_, c2))  if c2.isLetter                => acc + c2.toUpper
    case (acc, Seq(_, c2))                                => acc + c2
    // Last element of string
    case (acc, Seq(c)) => acc + "?!"
  }

def capitalizeAndInterruptAndQuestionIncredulously(s: String) =
  slidingFoldLeft(s.toSeq, 3)("" + s(0).toUpper) {
    // Normal iteration
    case (acc, Seq(c1, c2, _)) if c1.isLetter && c2.isLetter => acc + c2.toLower
    case (acc, Seq(_, c2, _))  if c2.isLetter                => acc + c2.toUpper
    case (acc, Seq(_, c2, _))                                => acc + c2
    // Last two elements of string
    case (acc, Seq(c1, c2)) => acc + " (commercial break) " + c2
    // Last element of string
    case (acc, Seq(c)) => acc + "?!"
  }

println(capitalizeAndQuestionIncredulously("hello my name is mAtthew"))
println(capitalizeAndInterruptAndQuestionIncredulously("hello my name is mAtthew"))

And the output:

Hello My Name Is Matthew?!
Hello My Name Is Matthe (commercial break) w?!