# Either, Validated, and Parallel

When it comes to validating values, many people working with Scala will think of the Validated data type from the Cats library. Indeed, as the name says, it's very well suited for such kind of problems. In this post, I will explain why it might be not the best idea to use Validated directly and how you can achieve the same results with the Either data type from the standard library.

# Validated

As a small reminder, the Validated data type is defined as follows:

sealed abstract class Validated[+E, +A]
final case class Valid[+A](a: A)   extends Validated[Nothing, A]
final case class Invalid[+E](e: E) extends Validated[E, Nothing]

The Valid case represents a value that passed the validation, and the Invalid case contains an error. There is also a type alias

type ValidatedNec[+E, +A] = Validated[NonEmptyChain[E], A]

that allows to accumulate multiple errors (NonEmptyChain is a data structure that can never be empty and that supports efficient prepending and appending).

A useful property of Validated is that it has an instance of the Applicative type class which combines multiple validated values accumulating possible errors.

Let's start with a small example of input validation. Imagine we are building a car marketplace. When someone wants to sell a car, we check if the car make and model make sense, and also we want people to provide a meaningful description of the car. Using Validated, we can write the following code:

case class Make(name: String)
case class Model(name: String)
case class Description(text: String)
case class MakeModel(make: Make, model: Model)
case class Listing(makeModel: MakeModel, description: Description)

def validateMake(make: String): ValidatedNec[String, Make]
def validateModel(name: String): ValidatedNec[String, Model]
def validateDescription(text: String): ValidatedNec[String, Description]
def validateMakeModel(make: Make, model: Model): ValidatedNec[String, MakeModel]

def validateListing(makeName: String,
                    modelName: String,
                    descriptionText: String): ValidatedNec[String, Listing] = {
  val make        = validateMake(makeName)
  val model       = validateModel(modelName)
  val description = validateDescription(descriptionText)

  val makeModel = (make, model).tupled
    .andThen { case (make, model) => validateMakeModel(make, model) }

  (makeModel, description).mapN(Listing)
}

The Applicative instance for the Validated data type allows us to use tupled and mapN to combine validation results. When we call validateMakeModel we need something different though — we need to use already validated make and model. Luckily, there is an andThen method that does exactly this.

A slightly simplified signature of andThen is

def andThen[B](f: A => Validated[E, B]): Validated[E, B]

and it looks exactly as flatMap would look like. Unfortunately, andThen cannot be just renamed to flatMap. The latter is an operation from the Monad type class, and since cats.Monad extends cats.Applicative there is a law that defines how their operations must relate to each other. One of them says that Applicative operations must be equivalent to the same operations implemented using Monad operations. In the case of Validated this means that if there was an instance of the Monad type class, the Applicative operations wouldn't be able to accumulate errors.

# Either

So, when we write a function that returns Validated we, in fact, say that the callers of our function want to accumulate errors (through the Applicative instance) and if they need to chain computations they will have to do something special. This sounds like an arbitrary assumption — we might as well return Either that supports flatMap (through the Monad instance) and require special handling for the accumulating use case:

def validateMake(name: String): EitherNec[String, Make]
def validateModel(name: String): EitherNec[String, Model]
def validateDescription(text: String): EitherNec[String, Description]
def validateMakeModel(make: Make, model: Model): EitherNec[String, MakeModel]

def validate(makeName: String,
             modelName: String,
             descriptionText: String): EitherNec[String, Listing] = {
  val make        = validateMake(makeName)
  val model       = validateModel(modelName)
  val description = validateDescription(descriptionText)

  val makeModel = (make, model).parTupled
    .flatMap { case (make, model) => validateMakeModel(make, model) }

  (makeModel, description).parMapN(Listing)
}

As you can see, the code looks very similar to the version written with Validated: instead if ValidatedNec I used EitherNec which is a type alias for Either[NonEmptyChain[E], A], and instead of tupled and mapN I used parTupled and parMapN. Let's look at these two methods in more detail.

A naive implementation of an error-accumulation makeModel validation for Either could look like this:

val makeModel =
  (make.toValidated, model.toValidated).tupled.toEither
    .flatMap { case (make, model) => validateMakeModel(make, model) }

We convert Either to Validated, use .tupled as before to accumulate errors, and then convert the result back to Either.

If you check the implementation of the parTupled and parMapN functions you will see that they require a Parallel type class (or, more precisely, NonEmptyParallel which is a superclass of Parallel). Parallel establishes a relation between Monads that describe dependent computations, and Applicatives that describe independent computations:

trait Parallel[M[_]] {
  type F[_]

  def parallel:   M ~> F
  def sequential: F ~> M
}

where M[_] has to have an instance of Monad and F[_] an instance of Applicative. For example, an instance of Parallel for the Either data type uses Validated as an error-accumulating counterpart. With this knowledge we can rewrite the code that uses toValidated and toEither functions into a more generic form:

val P = Parallel[EitherNec[String, *]]

val makeModel =
  P.sequential((P.parallel(make), P.parallel(model)).tupled)
    .flatMap { case (make, model) => validateMakeModel(make, model) }

And that's exactly what parTupled does under the hood, so the final implementation is as simple as

val makeModel = (make, model).parTupled
  .flatMap { case (make, model) => validateMakeModel(make, model) }

# EitherT

The code using Validated and Either looked very similar so far. With Either we were able to limit ourselves to operations from various type classes, while with Validated we had to use a very specific andThen, but that might not look like a compelling reason to prefer one over another. Imagine, however, that we want to make our validation asynchronous. If we use Future to represent asynchronicity, our code can look like this:

def validateMake(name: String): Future[EitherNec[String, Make]]
def validateModel(name: String): Future[EitherNec[String, Model]]
def validateDescription(text: String): Future[EitherNec[String, Description]]
def validateMakeModel(make: Make,
                      model: Model): Future[EitherNec[String, MakeModel]]

def validate(makeName: String,
             modelName: String,
             descriptionText: String): Future[EitherNec[String, Listing]] = {
  val make        = EitherT(validateMake(makeName))
  val model       = EitherT(validateModel(modelName))
  val description = EitherT(validateDescription(descriptionText))

  val makeModel = (make, model).parTupled
    .flatMap { case (make, model) => EitherT(validateMakeModel(make, model)) }

  (makeModel, description).parMapN(Listing).value
}

We are now converting Future[EitherNec[E, A]] to EitherT[Future[_], NonEmptyChain[E], A] by calling EitherT.apply, but everything else stays the same as in the synchronous version. This works because EitherT[Future, NonEmptyChain[E], A] also has an instance of the Parallel type class. If you try to implement an asynchronous version using Future[ValidatedNec[E, A]], the code will be much more complex.

# Summary

Validation doesn't have to be a special case of error handling that requires a different Validated data type. You can just use Either, and then you don't need to decide for the callers whether they need error-accumulating behavior or not — the monadic flatMap will be available directly, and errors can be accumulated with the help of the Parallel type class.