Cats Core, Part 6: NonEmptyChain or NonEmptyList for Validation Errors

In Part 1 I collected form errors in a Validated[List[String], A] and noted in passing that a list can technically be empty. The invalid branches always supplied a message, but nothing in the type said so.

This week I started a small Play 3 todo app: Scala 2.13.18, cats-core 2.13.0, and MongoDB behind a cake-pattern repository. I reached for ValidatedNec instead. The first compile failed on a line I expected to be trivial. This post covers what the Nec is, why the compiler refused that line, and when I would use NonEmptyList instead.

The validation in the todo app

A POST /todos body goes through Play JSON first, which only checks the shape: is there a title, and is it a string? {"title": " "} passes that check. The business rules live in a separate object with no Play imports:

package wiring.validation

import cats.data.ValidatedNec
import cats.syntax.all._

sealed trait TodoError { def message: String }

object TodoError {
  case object TitleBlank extends TodoError { val message = "title must not be blank" }
  final case class TitleTooLong(max: Int) extends TodoError { def message = s"title must be at most $max characters" }
}

object TodoValidation {
  import TodoError._

  type ValidationResult[A] = ValidatedNec[TodoError, A]

  val MaxTitleLength = 100

  def validateTitle(raw: String): ValidationResult[String] = {
    val title = raw.trim
    if (title.isEmpty) TitleBlank.invalidNec
    else if (title.length > MaxTitleLength) TitleTooLong(MaxTitleLength).invalidNec
    else title.validNec
  }
}

On success it returns the trimmed title, so the controller saves the cleaned value rather than the raw input.

What Nec stands for

Nec is short for NonEmptyChain. The cats Validated documentation states the alias directly: ValidatedNec[E, A] is Validated[NonEmptyChain[E], A], and a NonEmptyChain “statically guarantees we have at least one value.”

That removes the caveat from Part 1. An Invalid with no reason cannot be built. Building a chain from a collection that might be empty returns an Option, so the empty case has to be handled before an Invalid exists:

NonEmptyChain.fromSeq(Seq.empty[String])   // None
NonEmptyList.fromList(List.empty[String])  // None

The compile error that started this

My first version of the controller turned the errors into a JSON array like this:

errors => Future.successful(BadRequest(Json.obj("errors" -> errors.toList.map(_.message))))

Play reported the compile error in the browser:

value toList is not a member of cats.data.NonEmptyChain[wiring.validation.TodoError]

The same call had compiled in a scratch test a few minutes earlier. The only difference was that the test file imported cats.syntax.all._ and the controller did not.

NonEmptyChain is not a class with its own methods. Cats encodes it as a newtype over Chain: a type with a compile-time tag and no wrapper object at runtime. When I printed NonEmptyChain("a", "b").getClass.getName, it returned cats.data.Chain$Append. The methods you can call come from NonEmptyChainOps, which the compiler finds without an import, plus typeclass syntax such as Foldable, which needs one. In cats 2.13.0, toList is in the second group.

I fixed it without adding an import. I convert to a Chain first, which has its own toList:

TodoValidation.validateTitle(payload.title).fold(
  errors => Future.successful(BadRequest(Json.obj("errors" -> errors.toChain.toList.map(_.message)))),
  title => {
    val todo = Todo(TodoId.generate, title, done = false)
    todoRepository.save(todo).map(_ => Created(Json.toJson(todo)))
  }
)

Why a chain rather than a list

When mapN meets two Invalid values, it combines their error containers with the container’s Semigroup. That is the rule from Part 2. For NonEmptyList, that means list concatenation, which copies the left-hand list. The cats Chain documentation describes Chain as supporting “constant O(1) time append, prepend and concat”. It also warns that accumulating through a List while traversing ends in O(n²).

For a form with two fields, neither cost is measurable. The difference starts to matter when I traverse a large batch, for example validating every row of an import, because then appending happens many times.

The same check with NonEmptyList

Switching to Nel only changes the suffixes. I ran both versions with a blank title and an out-of-range priority:

val a: ValidatedNec[String, Int] = "title must not be blank".invalidNec
val b: ValidatedNec[String, Int] = "priority out of range".invalidNec
(a, b).mapN(_ + _)
// Invalid(Chain(title must not be blank, priority out of range))

val c: ValidatedNel[String, Int] = "title must not be blank".invalidNel
val d: ValidatedNel[String, Int] = "priority out of range".invalidNel
(c, d).mapN(_ + _)
// Invalid(NonEmptyList(title must not be blank, priority out of range))

Both keep the errors in the same order; only the container differs. NonEmptyList is an ordinary case class with a head and a tail, so toList works without imports and you can pattern-match on it. If the code around the validation already produces or expects a NonEmptyList, using Nel avoids converting back and forth.

Converting, and the trap I hit

While checking how to go from one to the other, I tried toValidatedNel first. It compiles, but it does something different from what the name suggests:

toValidatedNel is defined on any Validated[E, A]. It puts E into a single-element NonEmptyList. When E is already a chain, the result is a list holding one chain. The type shows it: ValidatedNel[NonEmptyChain[String], Int]. The conversion I wanted is leftMap(_.toNonEmptyList).

Which one I keep

In this app the errors stay in a NonEmptyChain for the whole validation step and become a plain List only at the HTTP boundary, in one toChain.toList. TodoValidation has no Play dependency, so I can test it with a plain AnyFunSuite. I would use Nel when an API on either side already speaks NonEmptyList, or when I want to pattern-match on the first error.

The next step in the app is a second field, priority. That is where (validateTitle(...), validatePriority(...)).mapN(...) returns both errors in one response.

What I verified

• Versions: Play 3.0.12, Scala 2.13.18, sbt 1.12.15, cats-core 2.13.0, Java 21.
• errors.toList on a NonEmptyChain without cats.syntax.all._ fails to compile with the message quoted above. It compiles with the import.
• A runtime probe printed cats.data.Chain$Append for a NonEmptyChain and cats.data.NonEmptyList for a NonEmptyList. fromSeq and fromList on empty input both returned None.
• The mapN and conversion outputs above are printed results, not hand-written.
• Against the running app: a blank title returned 400 {"errors":["title must not be blank"]}, a 101-character title returned the length error, " buy milk " returned 201 with the title stored as "buy milk", and a body without title was rejected by Play JSON before validation ran.