Min value of Integer List when it can be empty in scala

Question

I am trying to find min value of integer list also when it can be empty.

scala> val minValue:Int = List() match {
     |   case Nil => -1
     |   case xs  => xs.min
     | }
<console>:9: error: diverging implicit expansion for type Ordering[B]
starting with method Tuple9 in object Ordering
     case xs => xs.min

though it worked well not non empty list.

scala> val minValue = List(1,2) match {
     |   case Nil => -1
     |   case xs  => xs.min
     | }
minValue: Int = 1

How do I find min with out sorting as one way I could think of is sort and get head with getOrElse defaultValue.

Answer 1

The problem is that the typechecker doesn't know what type to use for List(). If you specifically annotate the empty list with a type it should work just fine:

val minValue:Int = List.empty[Int] match { // ...

After discussing with @senia I realized you're probably using -1 as a "hack" to say "no minimum" rather than as an actual value. If that's the case, then using the Option type in Scala might be more clear, as you can return the Some variant for actual results and the None variant in the case of an empty list. Scala sequences actually already have a nice method for doing this for you:

scala> List.empty[Int].reduceLeftOption(_ min _)
res0: Option[Int] = None

scala> List(5, 2, 1, 3, 4).reduceLeftOption(_ min _)
res1: Option[Int] = Some(1)

Answer 2

Your implementation is correct, but you have an incorrect test case: you are using List[Nothing] instead of List[Int], try this:

List[Int]() match {
  case Nil => -1;
  case xs => xs.min;
}

// -1

You could add safe methods to all collections:

import scala.collection.GenTraversableOnce

implicit class MinMaxOpt[T](val l: GenTraversableOnce[T]) extends AnyVal {
  def minOpt(implicit o: Ordering[T]) = if (l.isEmpty) None else Some(l.min)
  def minOrElse[T2 >: T](default: T2)(implicit o: Ordering[T]) = minOpt getOrElse default

  def maxOpt(implicit o: Ordering[T]) = if (l.isEmpty) None else Some(l.max)
  def maxOrElse[T2 >: T](default: T2)(implicit o: Ordering[T]) = maxOpt getOrElse default
}

List(1, 2).minOpt
// Some(1)

List[Int]().minOrElse(-1)
// -1

Answer 3

See the full signature of List.min in ScalaDoc.

def min[B >: A](implicit cmp: Ordering[B]): A

You see, if you use List() without any type hint, it will become List[Nothing] type, then the compiler cannot find what to use in the place of cmp, which must be type of Ordering[B] where B >: Nothing (B is a supertype of Nothing. There are too many such type, - Nothing is a subtype of every other type - so it cannot determine what to use).