Alternative

Alternative extends Applicative with a MonoidK. Let’s stub out all the operations just to remind ourselves what that gets us.

import cats.{Applicative, MonoidK}

trait Alternative[F[_]] extends Applicative[F] with MonoidK[F] {
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]

  def pure[A](a: A): F[A]

  def empty[A]: F[A]

  def combineK[A](x: F[A], y: F[A]): F[A]
}

As you might recall, pure wraps values in the context; ap allows us to do calculations in the context; combineK allows us to combine, for any given type A, any two contextual values F[A]; and empty provides the identity element for the combine operation.

Like other type classes, Alternative instances must obey some laws, in addition to those otherwise applying to MonoidK and Applicative instances:

  • Right Absorption: Applying a contextual function F[A => B] to empty [A] should be empty [B].
    • ff ap F.empty[A] = F.empty[B].
  • Left Distributivity: Mapping over a combined element must be the combinations of the mapped elements.
    • (fa <+> fa2) map f = ((fa map f) <+> (fa2 map f)) where fa: F[A] and fb: F[B] and f: A => B.
  • Right Distributivity: Applying the combination of two functions must be the combination of their applications.
    • (ff <+> fg) ap fa = (ff ap fa) <+> (fg ap fa) where ff: F[A => B], fg: F[A => B], and fa: F[A].

These laws guarantee the compatibility of the otherwise possibly independent Applicative and MonoidK structures.

Vector as an Alternative

Let’s examine an instance to get a feel for things. A useful instance of Alternative is that for Vector.

The relevant imports:

import cats.Alternative
import cats.implicits._

And what we can do with them:

val empty = Alternative[Vector].empty[Int]
// empty: Vector[Int] = Vector()

val pureOfFive = 5.pure[Vector]
// pureOfFive: Vector[Int] = Vector(5)

val concatenated = 7.pure[Vector] <+> 8.pure[Vector]
// concatenated: Vector[Int] = Vector(7, 8)

val double: Int => Int = _ * 2
// double: Int => Int = $$Lambda$10745/1778609039@1aa9a844

val addFive: Int => Int = _ + 5
// addFive: Int => Int = $$Lambda$10746/1030428021@641446bc

val apForVectors = (double.pure[Vector] <+> addFive.pure[Vector]) ap concatenated
// apForVectors: Vector[Int] = Vector(14, 16, 12, 13)

Making choices with Alternative

Alternative Parsing

Suppose we have a simple parser library with an interface something like:

trait Decoder[A] {
  def decode(in: String): Either[Throwable, A]
}
object Decoder {
  def from[A](f: String => Either[Throwable, A]): Decoder[A] =
    new Decoder[A] {
      def decode(in: String) = f(in)
    }
}

Then, we can implement an Alternative instance for this type like so:

implicit val decoderAlternative = new Alternative[Decoder] {
  def pure[A](a: A) = Decoder.from(Function.const(Right(a)))

  def empty[A] = Decoder.from(Function.const(Left(new Error("No dice."))))

  def combineK[A](l: Decoder[A], r: Decoder[A]): Decoder[A] =
    new Decoder[A] {
      def decode(in: String) = l.decode(in).orElse(r.decode(in))
    }

  def ap[A, B](ff: Decoder[A => B])(fa: Decoder[A]): Decoder[B] =
    new Decoder[B] {
      def decode(in: String) = fa.decode(in) ap ff.decode(in)
    }
}

The addition of the Alternative methods allows us to prioritize multiple strategies, compensating for inconsistencies in the source data.

def parseInt(s: String): Either[Throwable, Int] = Either.catchNonFatal(s.toInt)
def parseIntFirstChar(s: String): Either[Throwable, Int] = Either.catchNonFatal(2 * Character.digit(s.charAt(0), 10))

// Try first parsing the whole, then just the first character.
val decoder: Decoder[Int] = Decoder.from(parseInt _) <+> Decoder.from(parseIntFirstChar _)

This decoder correctly attempts each strategy in turn, as you can see:

decoder.decode("555")
// res1: Either[Throwable,Int] = Right(555)

decoder.decode("5a")
// res2: Either[Throwable,Int] = Right(10)

Partitioning Results

Alternative gives us a notion of partitioning, as long as we also have a Monad available. This is what separate does.

The trick here is that the inner type constructor (essentially the replacement for Boolean as the target of our “predicate”) must have a Bifoldable available. A great example of a Bifoldable is Either, and another is Tuple2.

Let’s imagine that we’re trying to make a bunch of independent possibly failure-prone calls with a bunch of different Int inputs (say it’s the id of a resource), each returning Either[String, Int] where a left String is the code modeling the failure we’re given (say it’s the HTTP code returned by a remote API we’re calling), while right of an integer is the output of the calculation.

// Resource holder returns (Request, Status)
def requestResource(a: Int): Either[(Int, String), (Int, Long)] = {
  if (a % 4 == 0) Left((a, "Bad request"))
  else if (a % 3 == 0) Left((a, "Server error"))
  else Right((a, 200L))
}

We can use separate to pull apart the failures and successes zipped with the input, letting us log failures and proceed with successes intelligently. separate will pull the two different outcomes into different sides of a tuple.

val partitionedResults = 
  ((requestResource _).pure[Vector] ap Vector(5, 6, 7, 99, 1200, 8, 22)).separate
// partitionedResults: (Vector[(Int, String)], Vector[(Int, Long)]) = (Vector((6,Server error), (99,Server error), (1200,Bad request), (8,Bad request)),Vector((5,200), (7,200), (22,200)))

Alternatively (no pun intended), in a totally different version of the same idea, we can lean on the instance of Bitraverse for Tuple2 to try and partition cleanly the outcomes of two different calculations that each depend pairwise on the same input (maybe we have a primary key and we want to select both the remote id of the resources with that key, and those that are linked via the foreign key to the input key).

// Surprising regularity in this politico-geographical data model!
def getRegionAndDistrict(pkey: Int): (Int, Vector[Int]) = (5 * pkey, (double.pure[Vector] <+> addFive.pure[Vector]) ap pkey.pure[Vector])
// getRegionAndDistrict: (pkey: Int)(Int, Vector[Int])

val regionsWithDistricts = (getRegionAndDistrict _).pure[Vector] ap Vector(5, 6, 7, 97, 1200, 8, 25)
// regionsWithDistricts: Vector[(Int, Vector[Int])] = Vector((25,Vector(10, 10)), (30,Vector(12, 11)), (35,Vector(14, 12)), (485,Vector(194, 102)), (6000,Vector(2400, 1205)), (40,Vector(16, 13)), (125,Vector(50, 30)))

val regionIds = regionsWithDistricts.separate._1
// regionIds: Vector[Int] = Vector(25, 30, 35, 485, 6000, 40, 125)

val districtIds = regionsWithDistricts.separate._2.flatten
// districtIds: scala.collection.immutable.Vector[Int] = Vector(10, 10, 12, 11, 14, 12, 194, 102, 2400, 1205, 16, 13, 50, 30)