Why does maxBy return only single item?

Question

Following up this question I wonder why maxBy of Traversable[T] returns a single value T instead of a sequence of T (list or similar). It looks like a pretty common case. For example (from the previous question):

For the list of students with their grades

List(Student("Mike", "A"), Student("Pete", "B"), Student("Paul", A))"

I want to get

List(Student("Mike", "A"), Student("Paul", A))

Does anybody know about any standard implementation of maxBy, which returns a sequence of found items?

Answer 1

There is no single command. The shortest I know of--which will group everything not just the maximum value as an intermediate--is

xs.groupBy(f).maxBy(_._1)._2

For greater efficiency, folds are good general-purpose tools for finding sums and maxima and various similar things. Basically, any time you need to run over your collection while accumulating some answer, use a fold. In this case,

(xs.head /: xs.tail) {
  (biggest, next) => if (f(biggest) < f(next)) next else biggest
}

will perform maxBy(f) if you don't mind re-evaluating the function twice for each element, while

((xs.head, f(xs.head)) /: xs.tail) {
  case (scored, next) =>
    val nextscore = f(next)
    if (scored._2 < nextscore) (next, nextscore)
    else scored
}._1

will do it with only one evaluation per element. If you want to keep a sequence, you can modify this to

(Seq(xs.head) /: xs.tail) {
  (bigs, next) =>
    if (f(bigs.head) > f(next)) bigs
    else if (f(bigs.head) < f(next)) Seq(next)
    else bigs :+ next
}

to keep the list (the corresponding single-evaluation form is left as an exercise to the reader).

Finally, even the near-maximum efficiency version isn't all that hard to manage, if you're willing to use a few mutable variables (hopefully well-hidden in a code block like I have here)

val result = {
  var bigs = xs.take(0).toList
  var bestSoFar = f(xs.head)
  xs.foreach{ x =>
    if (bigs.isEmpty) bigs = x :: bigs
    else {
      val fx = f(x)
      if (fx > bestSoFar) {
        bestSoFar = fx
        bigs = List(x)
      }
      else if (fx == bestSoFar) bigs = x :: bigs
    }
  }
  bigs
}

(this will return in reverse order, incidentally).

Answer 2

If you have

case class Student(name: String, grade: String)
val students = List(Student("Mike", "A"), Student("Pete", "B"), Student("Paul", "A"))

then this is a pretty simple O(N) solution, which doesn't involve building any intermediate lists:

val bestGrade = students.minBy(_.grade).grade
students.filter(_.grade == bestGrade)    //List(Student(Mike,A), Student(Paul,A))

We use minBy here because of the ordering of Strings.

As a method:

def multiMinBy[A,B](xs: Traversable[A])(f: A => B)(implicit ord: Ordering[B]) = {
  val minVal = f(xs minBy f)
  xs filter (f(_) == minVal)
}

scala> multiMinBy(students)(_.grade)
res26: Traversable[Student] = List(Student(Mike,A), Student(Paul,A))