Example of simple validation with ValidationNel

This is a follow-up to my previous question:

Suppose I need to validate a data structure (e.g. XML, JSON, HttpRequest, etc.). I can define a validating function A => ValidationNel[String, B] and a wrapper class around it:

class Validate[A, B](run: A => ValidationNel[String, B]) {
  def apply(a: A) = run(a)
}

I add also methods andThen and andAlso to compose Validates:

def andThen[C](other: Validate[B, C]) = new Validate[A, C] {a =>
  this(a) flatMap (b => other(b))
}

def andAlso(other: Validate[A, B]) = new Validate[A, B] (a =>
  (this(a), other(a)) match {
     case ((Success(b), Success(b)) => Success(b)
     case (failure @ Failure(errors), Success(b)) => failure
     case (Success(b), failure @ Failure(errors)) => failure
     case (Failure(errors1), Failure(errors2)) => Failure(errors1 + errors2)
  }
)

Now I can validate a data structure as follows:

case class Header(...)
case class Payload(...)
case class Message(header: Header, payload: Payload)

val validateHeader: Validate[Header, Header] = ...

val validatePayload: Validate[Payload, Payload] = ...

type ValidateMessage = Validate[Message, Message]

val validateMessageHeader =
  new ValidateMessage(m => validateHeader(m.header); m)

val validateMessagePayload =
  new ValidateMessage(m => validatePayload(m.payload); m)

val validateMessage = validateMessageHeader andAlso validateMessagePayload

Does it make sense ? How would you suggest fix/improve it ?