Rewriting imperative for loop to declarative style in Scala

Question

How do I rewrite the following loop (pattern) into Scala, either using built-in higher order functions or tail recursion?

This the example of an iteration pattern where you do a computation (comparison, for example) of two list elements, but only if the second one comes after first one in the original input. Note that the +1 step is used here, but in general, it could be +n.

public List<U> mapNext(List<T> list) {
    List<U> results = new ArrayList();

    for (i = 0; i < list.size - 1; i++) {
        for (j = i + 1; j < list.size; j++) {
            results.add(doSomething(list[i], list[j]))
        }
    }

    return results;
}

So far, I've come up with this in Scala:

def mapNext[T, U](list: List[T])(f: (T, T) => U): List[U] = {
  @scala.annotation.tailrec
  def loop(ix: List[T], jx: List[T], res: List[U]): List[U] = (ix, jx) match {
    case (_ :: _ :: is, Nil) => loop(ix, ix.tail, res)
    case (i :: _ :: is, j :: Nil) => loop(ix.tail, Nil, f(i, j) :: res)
    case (i :: _ :: is, j :: js) => loop(ix, js, f(i, j) :: res)
    case _ => res
  }

  loop(list, Nil, Nil).reverse
}

Edit: To all contributors, I only wish I could accept every answer as solution :)

Answer 1

Comeback Attempt:

After deleting my first attempt to give an answer I put some more thought into it and came up with another, at least shorter solution.

def mapNext[T, U](list: List[T])(f: (T, T) => U): List[U] = {
  @tailrec
  def loop(in: List[T], out: List[U]): List[U] = in match {
    case Nil          => out
    case head :: tail => loop(tail, out ::: tail.map { f(head, _) } )
  }

  loop(list, Nil)
}

I would also like to recommend the enrich my library pattern for adding the mapNext function to the List api (or with some adjustments to any other collection).

object collection {
  object Implicits {
    implicit class RichList[A](private val underlying: List[A]) extends AnyVal {
      def mapNext[U](f: (A, A) => U): List[U] = {
        @tailrec
        def loop(in: List[A], out: List[U]): List[U] = in match {
          case Nil          => out
          case head :: tail => loop(tail, out ::: tail.map { f(head, _) } )
        }

        loop(underlying, Nil)
      }
    }
  }
}

Then you can use the function like:

list.mapNext(doSomething)

Again, there is a downside, as concatenating lists is relatively expensive. However, variable assignemends inside for comprehensions can be quite inefficient, too (as this improvement task for dotty Scala Wart: Convoluted de-sugaring of for-comprehensions suggests).

UPDATE

Now that I'm into this, I simply cannot let go :(

Concerning 'Note that the +1 step is used here, but in general, it could be +n.'

I extended my proposal with some parameters to cover more situations:

object collection {
  object Implicits {
    implicit class RichList[A](private val underlying: List[A]) extends AnyVal {
      def mapNext[U](f: (A, A) => U): List[U] = {
        @tailrec
        def loop(in: List[A], out: List[U]): List[U] = in match {
          case Nil          => out
          case head :: tail => loop(tail, out ::: tail.map { f(head, _) } )
        }

        loop(underlying, Nil)
      }

      def mapEvery[U](step: Int)(f: A => U) = {
        @tailrec
        def loop(in: List[A], out: List[U]): List[U] = {
          in match {
            case Nil => out.reverse
            case head :: tail => loop(tail.drop(step), f(head) :: out)
          }
        }

        loop(underlying, Nil)
      }
      def mapDrop[U](drop1: Int, drop2: Int, step: Int)(f: (A, A) => U): List[U] = {
        @tailrec
        def loop(in: List[A], out: List[U]): List[U] = in match {
          case Nil          => out
          case head :: tail =>
            loop(tail.drop(drop1), out ::: tail.drop(drop2).mapEvery(step) { f(head, _) } )
        }

        loop(underlying, Nil)
      }
    }
  }
}