Functor and Applicative in Scala, in depth: map, mapN, validation, traverse and parallel effects

The problem each abstraction solves

Every type in this article has the shape F[A]: a value of type A inside some context F. The context may mean the value might be missing (Option), might be an error (Either), might be many values (List), or will be produced later by running a program (IO). The abstractions differ in how much they let you do with values while keeping them inside the context.

Functor answers: I have one F[A] and a plain function A => B; give me F[B]. The context is untouched: a None stays None, a three-element list stays three elements. Applicative answers: I have several independent F values and a function of several arguments; combine them, and let the context decide what combining means. It also gives pure, which puts a plain value into the context. Monad adds the ability for the next computation to depend on the previous result. Each step up is strictly more powerful, and each step up fits fewer types.

Functor: map, with laws

In Cats, Functor is a type class over a type constructor F[_] with one essential method, map. Writing code against Functor rather than a concrete type means one function works for every context:

import cats.Functor
import cats.syntax.all.*

// Works for Option, List, Either[E, *], IO, Future ... anything with a Functor instance.
def discounted[F[_]: Functor](prices: F[BigDecimal], pct: Int): F[BigDecimal] =
  prices.map(p => p * (100 - pct) / 100)

discounted(Option(BigDecimal(200)), 10)          // Some(180)
discounted(List(BigDecimal(10), BigDecimal(20)), 50) // List(5, 10)

// Functors compose: List of Option is still a Functor.
val nested = Functor[List].compose[Option]
nested.map(List(Some(1), None, Some(3)))(_ + 1)  // List(Some(2), None, Some(4))

Functor instances must obey two laws. Identity: fa.map(identity) == fa. Composition: fa.map(f).map(g) == fa.map(f andThen g). Together they say map changes values and never the structure: it cannot drop elements, reorder them, retry an effect or change an error. The composition law is also an optimisation licence: a library may fuse two maps into one pass.

The last line of the example shows a property Monads lack: Functors always compose. A List of Option is mapped through both layers without ceremony, and the same holds for Applicatives. Composing two arbitrary monads is not generally possible, which is why monad transformers such as OptionT exist.

Applicative: combining independent values

Suppose you have Option[String] for a name and Option[Int] for an age and want Option[User]. Functor cannot help, because map takes one argument. You need an operation that combines two contexts. Cats splits this into small pieces:

// Simplified shape of the Cats hierarchy (the real traits have more derived methods).
trait Functor[F[_]]:
  def map[A, B](fa: F[A])(f: A => B): F[B]

trait Semigroupal[F[_]]:
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]

trait Apply[F[_]] extends Functor[F], Semigroupal[F]:
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
  def map2[A, B, Z](fa: F[A], fb: F[B])(f: (A, B) => Z): F[Z] =
    map(product(fa, fb))((a, b) => f(a, b))

trait Applicative[F[_]] extends Apply[F]:
  def pure[A](a: A): F[A]

product pairs two contexts; ap applies a function inside a context to a value inside a context; map2 and its generalisation mapN are what you use day to day. With import cats.syntax.all.*, (nameOpt, ageOpt).mapN(User.apply) gives Some(user) when both are present and None otherwise. Each context defines combination: for List it is every pairing (a cartesian product); for IO it is run both and pair the results; for Validated it is keep the values or collect all errors.

The Applicative laws are more technical than the Functor laws, but they reduce to one intuition: pure adds no effect, and combining is associative, so (a, b, c).mapN means the same thing however the tuple is grouped internally. In practice you rely on them when refactoring a large mapN into smaller ones, and Cats ships property-based law tests in the cats-laws module so you can check your own instances.

The crucial point is what Applicative cannot do. In (fa, fb).mapN(f), fb is fixed before fa produces anything. Neither can look at the other's result. That limitation is exactly what lets an implementation evaluate them in parallel, or evaluate both even when one fails.

Worked example: validation that reports every error

A signup form has three fields. With Either and a for-comprehension, the user submits, sees "bad email", fixes it, submits, sees "age out of range", fixes it, and only then learns the country is unsupported. Each check is independent of the others, so this is an applicative problem, and Cats' Validated is the applicative for it:

import cats.data.{ValidatedNec, NonEmptyChain}
import cats.syntax.all.*

final case class Signup(email: String, age: Int, country: String)

type V[A] = ValidatedNec[String, A]

def email(s: String): V[String] =
  if s.contains("@") then s.validNec else s"bad email: $s".invalidNec

def age(n: Int): V[Int] =
  if n >= 18 && n <= 130 then n.validNec else s"age out of range: $n".invalidNec

def country(c: String): V[String] =
  if Set("IN", "US", "DE").contains(c) then c.validNec else s"unsupported country: $c".invalidNec

def signup(e: String, a: Int, c: String): V[Signup] =
  (email(e), age(a), country(c)).mapN(Signup.apply)

signup("ana@x.io", 30, "IN")
// Valid(Signup(ana@x.io,30,IN))

signup("ana-at-x", 12, "FR")
// Invalid(Chain(bad email: ana-at-x, age out of range: 12, unsupported country: FR))

ValidatedNec[E, A] is either Valid(a) or Invalid(errors), where the errors are a NonEmptyChain, a non-empty sequence with cheap appends. Its mapN runs every validator and, if any failed, concatenates all their errors. The result type proves at compile time that an invalid result carries at least one error.

Compare the same code with Either:

// The same three checks with Either stop at the first failure.
def emailE(s: String): Either[String, String] = email(s).toEither.leftMap(_.head)
def ageE(n: Int): Either[String, Int]         = age(n).toEither.leftMap(_.head)
def countryE(c: String): Either[String, String] = country(c).toEither.leftMap(_.head)

(emailE("ana-at-x"), ageE(12), countryE("FR")).mapN(Signup.apply)
// Left(bad email: ana-at-x)   -- one error, because Either's Applicative is derived from its Monad

// Validated has no flatMap; for a dependent check, switch explicitly.
email("ana@x.io").andThen(e => if e.endsWith(".io") then e.validNec else "need .io".invalidNec)

Either also has mapN, but its Applicative is derived from its Monad, so it must agree with flatMap and stop at the first Left. Validated deliberately has no flatMap. That is not an omission: a lawful monad for Validated would have to short-circuit and so could not accumulate. For the occasional dependent check, andThen sequences one validation after another, and converting with .toEither and .toValidated moves between the two worlds. A common shape is: validate independent fields with Validated, combine with mapN, convert to Either, then continue with dependent steps in a for-comprehension.

traverse: the payoff of Applicative

Turning a List[A] into an F[List[B]] with a function A => F[B] is so common that it has a name. traverse walks the structure and combines the results with the Applicative of F, so the behaviour comes for free from the instance:

import cats.effect.IO
import cats.syntax.all.*

final case class Row(raw: String)

def parse(r: Row): V[Int] =
  r.raw.toIntOption.toValidNec(s"not a number: ${r.raw}")

val rows = List(Row("4"), Row("x"), Row("9"), Row("y"))
rows.traverse(parse)
// Invalid(Chain(not a number: x, not a number: y))   -- every bad row reported

def fetchPrice(sku: String): IO[BigDecimal] = ???

// Sequential: one request after another.
val seq: IO[List[BigDecimal]] = List("a", "b", "c").traverse(fetchPrice)

// Parallel: same shape, uses the Parallel instance for IO.
val par: IO[List[BigDecimal]] = List("a", "b", "c").parTraverse(fetchPrice)

// Independent effects combined in parallel.
val quote: IO[(BigDecimal, BigDecimal)] = (fetchPrice("a"), fetchPrice("b")).parTupled

With V, traverse reports every bad row; with Option it gives None if any element fails; with IO it runs the effects and collects the results. sequence is traverse with the identity function: List[IO[A]] to IO[List[A]]. The traversed structure needs a Traverse instance, which List, Vector, Option, Either, Map values and others have.

Notice that traverse requires only an Applicative. Because the elements are independent, it never needs flatMap. That is why it works for Validated, which is not a monad, and why it can be parallel.

Parallel: same shape, concurrent execution

For IO, the Applicative derived from its Monad runs effects one after another, because it must agree with flatMap. Cats separates the parallel version into the Parallel type class, which pairs a monad with an applicative that may run effects concurrently. The par operators, parMapN, parTupled and parTraverse, use it.

The same mechanism links Either to Validated: (e1, e2, e3).parMapN(f) on Either values with a semigroup error type accumulates errors, because Either's Parallel instance goes through Validated. One rule covers both: mapN follows the monad, parMapN follows the parallel applicative.

Unbounded parallelism needs care. parTraverse over 10,000 elements starts 10,000 fibers and 10,000 HTTP requests. Cats Effect provides parTraverseN(n) to bound concurrency; use it whenever the collection size is not small and fixed. How fibers are scheduled and cancelled is covered in the Cats Effect runtime. Also remember that in a parallel combination, when one effect fails, Cats Effect cancels the others, so effects must be safe to interrupt.

Composition and when to ask for less

Applicatives compose. Given Future[Option[A]] values, Nested wraps them so a single mapN goes through both layers, and Applicative[Future].compose[Option] builds the combined instance directly. If you only need to combine independent nested values, this avoids a transformer entirely. If later steps depend on earlier results, you need the monadic tools in Scala monads.

The general guidance is to ask for the least powerful type class your function needs. A function with F[_]: Applicative in its signature accepts every monad and also Validated, parallel applicatives and composed applicatives. It also documents that its steps are independent, which a reader and a reviewer can rely on. This is the style that tagless final programs use: algebras parameterised on F[_] with the smallest constraint that compiles.

Failure modes

The last row matters. A Future starts when it is created, so (f1, f2).mapN on two already-created futures is parallel no matter which combinator you use, and retrying one means creating it again. Lazy effect types such as IO make the sequential-or-parallel choice explicit, which is one reason effect libraries are preferred for new code.

What to do next

1. Find one form or request validator that returns Either and rewrite it with ValidatedNec and mapN; show users every error at once.
2. Search your code for for-comprehensions whose steps do not use earlier results; replace them with mapN, or parMapN for IO.
3. Replace manual loops that build lists of results inside effects with traverse, and bound any parTraverse with parTraverseN.
4. Lower constraints on generic functions from Monad to Applicative or Functor where they compile.
5. For any custom type-class instance, add the cats-laws tests to your test suite.