Scala: Sorting a list while keeping the position of placeholders

Question

The problem I'm facing is sorting a List of Double values in Scala also containing some kind of placeholder values (Double.NaN in the example below. However, these can be set as required for the sorting to work.), which should keep their position after sorting.

Input:

val placeholder = Double.NaN
List(placeholder, 5.0, 2.0, placeholder, 4.0, 3.0, placeholder)

Output:

List(placeholder, 2.0, 3.0, placeholder, 4.0, 5.0, placeholder)

How can I sort Double values in a list without altering the position of placeholder values? I'm searching for a solution to work with Scala 2, specifically 2.12

Thanks for your help!

Answer 1

One way is to sort the list and insert back the placeholders at right position.

This is not optimal, optimisation left to the reader as an exercise, but here's the idea:

val placeholder = Double.NaN
val list = List(placeholder, 5.0, 2.0, placeholder, 4.0, 3.0, placeholder)

val sorted = list.filterNot(_.isNaN).sorted

def insertSorted(in: List[Double], sorted: List[Double]): List[Double] = {
  in match {
    case Nil => Nil
    case head :: tail => 
      if (head.isNaN)
        placeholder :: insertSorted(tail, sorted)
      else
        sorted.head :: insertSorted(tail, sorted.tail)
  }
}

insertSorted(list, sorted)
// List(NaN, 2.0, 3.0, NaN, 4.0, 5.0, NaN)

This only works with NaN as placeholder. If using another value (like -1), regular comparison should be used.

Also, as raised in the comments, comparison on doubles can lead to surprises, use with caution.

Answer 2

foldRight is stack safety

def sort(in: List[Double]): List[Double] = {
    val sortedIn = in.filterNot(_.isNaN).sorted.reverse
    val (result, _) = in.foldRight((List.empty[Double], sortedIn)) {
        case (n, (result, list)) =>
            if (n.isNaN) (placeholder :: result, list)
            else (list.head :: result, list.tail)
    }
    result
}

Answer 3

This solution could also be written as a fold:

  def sort(list: List[Double]): List[Double] = {
    val (sorted, _) = list
      .foldLeft((List.empty[Double], list.sorted)) { case ((result, sortedInput), n) =>
        if (n.isNaN) (result :+ placeholder, sortedInput)
        else (result :+ sortedInput.head, sortedInput.tail)
      }
    sorted
  }

Again not optimal, but possibly the most straightforward if performance is not a high priority.