Questions about \/ and Validation

scalaz.scala

// Questions about \/ and Validation
object scalaz {

/*
This explanation might help. This is a compilable source file with revisions 
available at https://gist.github.com/tonymorris/8263051

Fact: All monads are applicative functors. As has been seen we can witness the
`Applicative` that arises from the `Monad` primitives. Let's illustrate this:

*/

trait Applicative[F[_]] {
  def pure[A](a: A): F[A]
  def ap[A, B](f: F[A => B], a: F[A]): F[B]
}

trait Monad[F[_]] extends Applicative[F] {
  def unit[A](a: A): F[A]
  def bind[A, B](f: A => F[B], a: F[A]): F[B]

  override def pure[A](a: A): F[A] =
    unit(a)
  override def ap[A, B](f: F[A => B], a: F[A]): F[B] =
    bind((ff: A => B) => bind((aa: A) => pure(ff(aa)), a), f)
}

/*
We see that the Applicative primitives `ap` and `pure` are derived from the
monad primitives, `bind` and `unit`. This applicative functor that arises is 
guaranteed to be lawful. Ergo, we can confidently say, "all monads are 
applicative."

However, not all applicative functors are monads. Some are, but not all. This
discussion centres around two different applicative functors. One of those gives
rise to a monad, while the other doesn't. Furthermore, one of the applicative
functors (the one that is not a monad) requires a constraint on the functor
itself.

That constraint is called a semigroup and is closed binary operation that is
associative.
*/

trait Semigroup[A] {
  def op(a1: A, a2: A): A
}

/*
Let's look at these two applicative functors by first using `scala.Either`
*/

// From hereon, we will call this "the \/ applicative"
def Applicative_\/[X]: Applicative[({type λ[α]=X Either α})#λ] =
  new Applicative[({type λ[α]=X Either α})#λ] {
    def pure[A](a: A) =
      Right(a)
    def ap[A, B](f: X Either (A => B), a: X Either A) =
      for {
        ff <- f.right
        aa <- a.right
      } yield ff(aa)
}

// From hereon, we will call this "the Validation applicative"
// Note the Semigroup constraint, which is required.
def Applicative_Validation[X](s: Semigroup[X]): Applicative[({type λ[α]=X Either α})#λ] =
  new Applicative[({type λ[α]=X Either α})#λ] {
    def pure[A](a: A) =
      Right(a)
    def ap[A, B](f: X Either (A => B), a: X Either A) =
      f match {
        case Left(x1) => 
          a match {
            case Left(x2) => 
              Left(s.op(x1, x2))
            case Right(_) =>
              Left(x1)
          }
        case Right(ff) =>
          a match {
            case Left(x2) => 
              Left(x2)
            case Right(aa) =>
              Right(ff(aa))
          }
      }
}

/*
OK, so that was a bit of a mouthful. Bladdy Scala.

It is important to observe that we could have written the \/ applicative by
implementing the Monad trait and automatically inheriting the behaviour that
was written out.

Like so:
*/
def Monad_\/[X]: Monad[({type λ[α]=X Either α})#λ] =
  new Monad[({type λ[α]=X Either α})#λ] {
    def unit[A](a: A) =
      Right(a)
    def bind[A, B](f: A => X Either B, a: X Either A) =
      a.right flatMap f
}

/*
Before going further, convince yourself that `Monad_\/#ap` and
`Applicative_\/#ap` both exhibit exactly the same behaviour. They are the same 
function.

OK, so what about `Applicative_Validation`? Can we just implement the `Monad`
trait instead?

No. This is not possible. What we have here is an applicative functor without a
corresponding monad.

In summary, we have two applicative functors, one of which has a corresponding
monad, while the other doesn't.
*/

/*
OK, how would we exploit all of these lovely libraries in
practice? It might be argued, let's implement all the different types of
behaviour in a single data type like so:
*/

case class Or[A, B](run: A Either B) {
  // the \/ monad
  def flatMap[X](f: B => A Or X): A Or X =  
    Or(run.right.flatMap(f(_).run))

  // the \/ applicative
  def ap_\/[X](f: A Or (B => X)): A Or X =
    Or(
        for {
          ff <- f.run.right
          aa <- run.right
        } yield ff(aa)
    )

  // the validation applicative
  def ap_Validation[X](f: A Or (B => X))(implicit s: Semigroup[A]): A Or X =
    Or(
        f.run match {
          case Left(x1) => 
            run match {
              case Left(x2) => 
                Left(s.op(x1, x2))
              case Right(_) =>
                Left(x1)
            }
          case Right(ff) =>
            run match {
              case Left(x2) => 
                Left(x2)
              case Right(aa) =>
                Right(ff(aa))
            }
      }
    )
}

/*
OK, so we have a data type that has all the different possibilities. We may or
may not accumulate errors using an applicative operation or we might using the
only possible monad instance with `flatMap`. We are done!

Not so fast. This has a problem. Actually, it has a *huge* problem.

Let's go back to basics for a minute. What is the entire point of generalising
to `Applicative` or `Monad`? Why have such interfaces to begin with? The answer
is the same reason we write interfaces all the time as responsible programmers:
to abstract the commonalities to give rise to operations common across both.

OK, what is one such operation that arises with the interfaces we are discussing
here? Here is one of a possible many:
*/
def sequence[F[_], A](x: List[F[A]])(implicit F: Applicative[F]): F[List[A]] =
  x.foldRight[F[List[A]]](F.pure(Nil))((a, b) =>
      F.ap(F.ap(F.pure((a: A) => (as: List[A]) => a :: as), a), b))

/*
Right, so if we have a list of F[A] we can turn it into a F of list of A, as
long as we have an Applicative for F. This means we could take a list through
either the \/ applicative or the validation applicative and get very different 
results. 

So which applicative instance should we implement for `Or`? We are stuck, we
have to pick one! OK, let's pick the \/ applicative implementation, which has no
accumulation and a corresponding monad.
*/
implicit def Monad_Or[X]: Monad[({type λ[α]=X Or α})#λ] =
  new Monad[({type λ[α]=X Or α})#λ] {
    def unit[A](a: A) =
      Or(Right(a))
    def bind[A, B](f: A => X Or B, a: X Or A) =
      a flatMap f
}

/*
Great, now we can use `sequence` with our new (derived) applicative functor.

(Please excuse that ugly annotation to help out the inferencer).
*/
val list = 
  List(Left(List(7)), Left(List(8)), Right("abc"), Right("def"))

def hithere =  
  sequence[({type λ[α]=List[Int] Or α})#λ, String](
    list map (Or(_))
  )

/*
OK, but what if we want to sequence a list of Or values, accumulating with our
other applicative functor?

We are completely boned, that's what.

Just kidding, we write a new data type that is isomorphic to `Or` and provides
the appropriate Applicative instance (but not a Monad instance).

Let's call it ... oh I don't know ... hmm how about Validation?
*/
case class Validation[A, B](run: A Either B)

implicit def Applicative_Validation_for_realz[X](implicit s: Semigroup[X]): Applicative[({type λ[α]=X Validation α})#λ] =
  new Applicative[({type λ[α]=X Validation α})#λ] {
    def pure[A](a: A) =
      Validation(Right(a))
    def ap[A, B](f: X Validation (A => B), a: X Validation A) =
      Validation(
        f.run match {
          case Left(x1) => 
            a.run match {
              case Left(x2) => 
                Left(s.op(x1, x2))
              case Right(_) =>
                Left(x1)
            }
          case Right(ff) =>
            a.run match {
              case Left(x2) => 
                Left(x2)
              case Right(aa) =>
                Right(ff(aa))
            }
          }
      )
}

/*
Now we have the best of both worlds. We can sequence with our earlier 
applicative or with the accumulating applicative. We'll just need a `Semigroup`
for whatever we are accumulating. Easy enough:
*/
implicit def ListSemigroup[A]: Semigroup[List[A]] =
  new Semigroup[List[A]] {
    def op(a1: List[A], a2: List[A]) =
      a1 ::: a2
  }

/*
And now we can sequence in our other applicative functor:
*/
def hithereagain =  
  sequence[({type λ[α]=List[Int] Validation α})#λ, String](
    list map (Validation(_))
  )

/*
Great, now we truly do have the best of all worlds. Our strategy applies to the
entire monad and applicative library, not just sequence. This is the practical 
point of monads and applicative functors after all!

We have two data types, `Or` and `Validation`, each denoting the different types
of applicative functor behaviour and one of which has a corresponding monad. It 
is important to know why you are using one or the other. They do not exist in
redundancy. Nobody thought, "let's write two data types that overlap!" No no,
repeating useless library code is for ... well ... it's very much not in the
scalaz handbook.

There is a very important difference between these two data types. If you want
accumulation, you use `Validation`. If you do not want accumulation, you use
`Or`. If it makes no difference, pick either and choose wisely.

As for naming, `Or` is actually called `\/` in scalaz. I am so pleased that this
discussion started off in the degenerate pits of the merits of identifier names
and has managed to crawl out to a world of utility. Let's keep it that way!
*/

def main(args: Array[String]) {
  println(hithere)
  println(hithereagain)
}

}