Min and Max

Min[T] and Max[T] are data structures that keep track of, respectively, the minimum and maximum instances of T that you’ve seen. First[T] works for any type T with an Ordering[T] instance:

import com.twitter.algebird._
// import com.twitter.algebird._

Min(3) + Min(2) + Min(1)
// res0: com.twitter.algebird.Min[Int] = Min(1)

Min("a") + Min("aaa") + Min("ccccc") // by length
// res1: com.twitter.algebird.Min[String] = Min(a)

As does Max[T]:

Max(3) + Max(2) + Max(1)
// res2: com.twitter.algebird.Max[Int] = Max(3)

Max("a") + Max("aaa") + Max("ccccc") // by length
// res3: com.twitter.algebird.Max[String] = Max(ccccc)

Algebraic Properties

Min[T] and Max[T] are both commutative semigroups. For Min[T], the + function keeps the input with the minimum wrapped instance of T, while Max[T]’s + implementation keeps the maximum input. For example, for Min[T]:

val min1 = Min(1) + Min(100) == Min(1)
// min1: Boolean = true

val min2 = Min(100) + Min(1) == Min(1)
// min2: Boolean = true

assert(min1 && min2)

And for Max[T]:

val max1 = Max(1) + Max(100) == Max(100)
// max1: Boolean = true

val max2 = Max(100) + Max(1) == Max(100)
// max2: Boolean = true

assert(max1 && max2)

Min[T] forms a monoid on numeric types with an upper bound, like Int and Float:

Monoid.zero[Min[Int]]
// res6: com.twitter.algebird.Min[Int] = Min(2147483647)

Monoid.zero[Min[Float]]
// res7: com.twitter.algebird.Min[Float] = Min(3.4028235E38)

Since all instances of T will be less than or equal to the upper bound.

Max[T] forms a monoid on types with a lower bound. This includes the numeric types as well as collections like List[T] and String. The monoid instance for these containers compares each T element-wise, with the additional notion that “shorter” sequences are smaller. This allows us to use the empty collection as a lower bound.

Monoid.zero[Max[Int]]
// res8: com.twitter.algebird.Max[Int] = Max(-2147483648)

Monoid.zero[Max[Float]]
// res9: com.twitter.algebird.Max[Float] = Max(-3.4028235E38)

Monoid.zero[String]
// res10: String = ""

Usage Examples

Let’s have a popularity contest on Twitter. The user with the most followers wins! (We’ve borrowed this example with thanks from Michael Noll’s excellent algebird tutorial, Of Algebirds, Monoids, Monads, and Other Bestiary for Large-Scale Data Analytics). First, let’s write a data structure to represent a pair of username and the user’s number of followers:

case class TwitterUser(val name: String, val numFollowers: Int) extends Ordered[TwitterUser] {
  def compare(that: TwitterUser): Int = {
    val c = this.numFollowers - that.numFollowers
    if (c == 0) this.name.compareTo(that.name) else c
  }
}
// defined class TwitterUser

Now let’s create a bunch of TwitterUser instances.

val barackobama = TwitterUser("BarackObama", 40267391)
// barackobama: TwitterUser = TwitterUser(BarackObama,40267391)

val katyperry = TwitterUser("katyperry", 48013573)
// katyperry: TwitterUser = TwitterUser(katyperry,48013573)

val ladygaga = TwitterUser("ladygaga", 40756470)
// ladygaga: TwitterUser = TwitterUser(ladygaga,40756470)

val miguno = TwitterUser("miguno", 731) // I participate, too.  Olympic spirit!
// miguno: TwitterUser = TwitterUser(miguno,731)

val taylorswift = TwitterUser("taylorswift13", 37125055)
// taylorswift: TwitterUser = TwitterUser(taylorswift13,37125055)

Who’s the winner? Since TwitterUser defines an Ordering by extending Ordered, we can find the winner by wrapping each user in Max and combining all of the Max[TwitterUser] instances with +:

val winner: Max[TwitterUser] = Max(barackobama) + Max(katyperry) + Max(ladygaga) + Max(miguno) + Max(taylorswift)
// winner: com.twitter.algebird.Max[TwitterUser] = Max(TwitterUser(katyperry,48013573))

assert(katyperry == winner.get)

A similar trick with Min[TwitterUser] gives us the loser:

val loser: Min[TwitterUser] = Min(barackobama) + Min(katyperry) + Min(ladygaga) + Min(miguno) + Min(taylorswift)
// loser: com.twitter.algebird.Min[TwitterUser] = Min(TwitterUser(miguno,731))

assert(miguno == loser.get)

So sad.

Min[T] and Max[T] are related to First[T] and Last[T]. All four of these data structures wrap up instances of another type T to make them combine in a different way. Min[T] and Max[T] force their combination to depend on the ordering of the type T. First[T] and Last[T] force them to combine based on the order that they’re seen in a stream.

See the docs on First and Last for more information.

Documentation Help

We’d love your help fleshing out this documentation! You can edit this page in your browser by clicking this link.