Validation for Free in Scala

Due to the complexity of business data, much effort has been spent on data validation. In Scala, using applicatives to build validation was proposed and is widely considered an effective approach. Inspired by ideas both from applicative validation and free monad, in this article, we introduce a monadic validation framework that builds validations “for free.” We will discuss this approach further and show the implementation through example code.

We will not elaborate on how free monad and applicatives validation work in Scala. To understand the concept of free Monads, please refer to this and this. Additionally, to understand how validation is modeled using applicative functors, please refer to this and this. A generic free monad implementation can be found here. We will only focus on how validation can be modeled as a free monad, and the benefits it brings.

Validation in Scala

Validation can be found in different forms when error(s) are detected. Validation can return immediately when the first error (or exception) has been encountered; the validation result may or may not contain the validation error or exception message. This scenario is called fast failing validation, in which the validation does not validate all the business rules and only zero or one message is returned, and the process shall be cut short upon first error. This simple form of validation is sometimes considered insufficient, as a full validation is not carried out with accumulated errors. In reality, it is widely used in application development. Monadic entities in Scala, such as Option, Try, and Either, are very handy to use.

Validating all the business rules, and accumulating errors, is very different from fast failing validation. Applicative functors are proposed, and they have effectively solved accumulation problems. Popular Scala libraries, such scalaz and Cats, all provide applicatives validation support. Readers can refer to the scalaz.Validation API and cats.data.Validated API for more details.

However, many projects written in Scala do not use either of these libraries for various reasons, and the Scala language does not have native support of applicative for-comprehensions. Therefore, a native validation approach without leaning on any third-party libraries is very appealing.

The validation problem is very similar to the problems that free monads can solve — modeling a series of validators as a workflow in a for-comprehension and executing them in an interpreter. Free monads provide a powerful way to lift the validators into monads implicitly (for free). Therefore, the problem we need to solve is to re-model our interpreter to carry on the execution while errors or exceptions are encountered. The interpreter shall have the ability to guarantee the execution of each validator, and all the validation messages shall be returned to the call site.

The Validators and Free Monads

In our approach, validation is a monadic composition of validator executions; each validator represents validation of each business rule, composed by a for-comprehension. This is where a free monad can help — the validator can be lifted to a monad implicitly “for free”. This allows our validation to enjoy all the benefits that a free monad can offer — stack free and natural transformation.

First, we discuss the fast failing validation framework and its limitations.

Suppose we need to validate a person’s name and age before saving the person to the database:

case class Person(name: String, age: Int){
  def validateName= if (name.isEmpty) None else Some("Success")
  def validateAge = if (age < 18) None else Some("Success")
}

def save(person: Person): Boolean = {
  println(s"save ${person.name} at age ${person.age}")
  true
}

val person = Person("Michael", 20)
for {
  _ <- person.validateName
  _ <- person.validateAge
} yield save(person)

There are two limitations in the above encoding:

1. Validation does not carry the validation error to the call site, a None is returned when error is encountered

2. Validation stops short upon a None. For comprehension desugars the above code into a chain of flatMap followed by a map:

person.validateName    
.flatMap((_: String) =>person.validateAge.map((_: String) => save(person)))

If name is blank, validateName returns None, the process stops short, and validateAge will not be executed - this is fast failing validation.

In our approach, we model our validators to conform to a simple trait:

sealed trait Validator[A] {
  def validate: Option[Error]
  def unbox: A
}

Each validator implements its own validation rule:

case class NameValidator(name: String) extends Validator[String] {
  def validate = if (name.isEmpty) Option(NameError) else None
  def unbox: String = name
}

case class AgeValidator(age: Int) extends Validator[Int] {
  def validate = if (age >= 18) None else Some(AgeError)
  def unbox: Int = age
}

Notice the followings in this implementation:

• A validator is a container of the data to be validated, coupled with its validation rule. An "unbox" function is provided to allow obtaining the data from the validator, this is important in the implementation that will be discussed later;
• Instead of returning None upon error, our validator returns Some[Error] upon errors, None without error. This allows us to carry the error messages back to the call site.
     

Validators are lifted to monads implicitly, exactly as in free monad:

implicit def liftF[F[_], A](fa: F[A]): Free[F, A] = FlatMap(fa, Return.apply)

Where free monads are standard in the form of:

sealed trait Free[F[_], A] {
    def flatMap[B](f: A => Free[F, B]): Free[F, B] = this match {
      case Return(a) => f(a)
      case FlatMap(sub, cont) => FlatMap(sub, cont andThen (_ flatMap f))
    }

    def map[B](f: A => B): Free[F, B] = flatMap(a => Return(f(a)))
}
final case class Return[F[_], A](a: A) extends Free[F, A]
case class FlatMap[F[_], I, A](sub: F[I], cont: I => Free[F, A]) extends Free[F, A]

The interpreter executes the validators accordingly:

val interpreter = new Executor[Validator] {
  override def exec[A](fa: Validator[A]) = fa.validate
  override def unbox[A](fa: Validator[A]) = fa.unbox
}

def validate[F[_], A](prg: Free[F, A], interpreter: Executor[F]): List[Error] = {
  def go(errorList: List[Option[Error]], prg: Free[F, A]): List[Option[Error]]= 
prg match {
       case Return(a) => errorList
       case FlatMap(sub, cont) => go(interpreter.exec(sub) :: errorList, 
cont(interpreter.unbox(sub)))
  }
  go(List.empty[Option[Error]], prg).flatten
}

The interpreter is the glue between the data, the error, the data validators, and the free monads. Notice three important detailed differences between this interpreter and the interpreter in the free monad:

• The interpreter provides an unbox function; it is used in a "no-error" case. When a None type is returned, unbox is used to find the data being validated in a type-safe way. To continue the validation process, unbox, in turn, uses the unbox function provided by the validator to obtain the data being validated.
• Unlike the interpreter in a free monad, the continuation of the process is through monadic operations and may cut short upon None:

executor.exec(sub).flatMap(x => validateAndRun(cont(x), executor))

In our validation interpreter, the continuation of the process is guaranteed by following the validators until the last validator is executed, as the sequential execution is taken out of flatMap, but still, it maintains the tail-recursion position so that the validation process is stack-free.

• A list is returned that contains the validation error messages from each validator, if it exists.

The Validation Composition

Just as the workflow is modeled in free monads, the validation flow is modeled through for-comprehension. For instance, we will call save(person) if name validation and age validation all pass. Otherwise, we print out the accumulated errors:

val validation = for {
  _ <- NameValidator(person.name)
  _ <- AgeValidator(person.age)
} yield ()


validate(validation, interpreter) match {
  case Nil => save(person)
  case errors => errors foreach println
}

The implementation can be found at Validation For Free.

Conclusion

A free monad is a construction that allows you to build a monad from any Functor. Like other monads, it is a pure way to represent and manipulate computations.

In particular, free monads provide a practical way to:

• Represent stateful computations as data, and run them
• Run recursive computations in a stack-safe way
• Build an embedded DSL (domain-specific language)
• Retarget a computation to another interpreter using natural transformations

(The above is bullet points are taken from typelevel)

According to Leif Battermann:

 "Applicatives allow us to compose independent operations and evaluate each one. Even if an intermediate evaluation fails. This allows us to collect error messages instead of returning only the first error that occurred."

In this article, we introduced an approach that gives you the best of both worlds – a validation framework as a free monad without applicative. Hope you enjoyed this short demonstration!