-
-
Save bvenners/8273112 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Questions about \/ and Validation | |
| object scalaz { | |
| /* | |
| Thanks for the great explanation, Tony. This explanation as well as the answers | |
| that came back from Runar and Mark nudged my thinking in a different direction. | |
| The feeling I get is that there's a monad inside of Validation trying to get out. | |
| It looks like Validation would be monadic just from its shape, and users seem to | |
| want to use them in for expressions. I now see that a Validation monad would need | |
| to have an applicative personality that is consistent with monad, and I think it | |
| could be done by offering a lower priority Monad instance for Validation (complete | |
| with the default, inherited Applicative behavior that short-circuits on the first | |
| error) as well as a higher priority Applicative instance that accumulates errors. | |
| That way if a method abstracts over Monad, you could pass a Validation to it, but | |
| it would short-circuit if they sequenced it or did anything else that accessed | |
| its Applicative nature. If a method abstracts over Applicative, you could (as you can | |
| now) pass a Validation to it, and it would accumulate. | |
| The reason you might not want to do that is it may be more confusing than any | |
| benefit it provides. It might be simpler for user if there's one type, \/, that | |
| is a monad with consistent applicative behavior and similar type Validation that | |
| is not a monad (including not having a flatMap method so it can't be used monadically | |
| in a for expression) and has an applicative that accumulates. | |
| The reason this works for Or, I think, is that Or isn't tied into scalaz-like type | |
| classes. It is just a functional/OO design that has an API that allows it to | |
| be treated monadically, and another API when the bad type is an Every that allows | |
| accumulation. | |
| But just for fun, I decided to try it and I got it to work. It was a bit tricky to | |
| get the Scala compiler to understand the implicit priorities I wanted. I improved | |
| my understanding of how that works in the process, and will explain that below. | |
| This is a compilable source file with revisions | |
| available at https://gist.github.com/bvenners/8273112 | |
| That's a fork of Tony's gist. I have removed his comments and replaced | |
| them with my own. | |
| */ | |
| /* | |
| All of the code until my next comment is unchanged from Tony's original gist, except | |
| with Tony's comments removed. | |
| */ | |
| 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) | |
| } | |
| trait Semigroup[A] { | |
| def op(a1: A, a2: A): A | |
| } | |
| 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) | |
| } | |
| 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)) | |
| } | |
| } | |
| } | |
| 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 | |
| } | |
| 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)) | |
| } | |
| } | |
| ) | |
| } | |
| 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)) | |
| 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 | |
| } | |
| val list = | |
| List(Left(List(7)), Left(List(8)), Right("abc"), Right("def")) | |
| def hithere = | |
| sequence[({type λ[α]=List[Int] Or α})#λ, String]( | |
| list map (Or(_)) | |
| ) | |
| case class Validation[A, B](run: A Either B) { | |
| def flatMap[X](f: B => A Validation X): A Validation X = | |
| Validation(run.right.flatMap(f(_).run)) | |
| } | |
| /* | |
| Here's where the code first departs from Tony's original. I actually | |
| define a Monad instance for Validation, but I put it in a trait. | |
| Note that as a Monad, Validation requires no Semigroup constraint. | |
| */ | |
| trait MonadicValidation { | |
| implicit def Monad_Validation[X]: Monad[({type λ[α]=X Validation α})#λ] = | |
| new Monad[({type λ[α]=X Validation α})#λ] { | |
| def unit[A](a: A) = | |
| Validation(Right(a)) | |
| def bind[A, B](f: A => X Validation B, a: X Validation A) = | |
| a flatMap f | |
| } | |
| } | |
| /* | |
| I then put Tony's method unchanged providing the accumulating Applicative for | |
| Validation in Validation's companion object, and made that extend the trait | |
| that holds the implicit providing the monad instance for Validation. Here is | |
| where I ran into an unexpected ambiguous implicit compiler error. I didn't fully | |
| understand the point system that the compiler uses to select implicits. Turns out you | |
| get points for being more specific as well as points for being in subtypes, and | |
| these points are added together. | |
| Monad is more specific than Applicative because Monad is a subtype of | |
| Appicative. So if placed in the same trait Monad_Validation scores one | |
| more point than Applicative_Validation_for_realz when the compiler is looking | |
| for an Applicative. The compiler then awards Applicative_Validation_for_realz a point | |
| for being in a sub-object, and that evens the score, so the compile fails with an | |
| ambiguity error. What I ended up doing to solve it is making this clunky subtrait | |
| of Applicative, MoreSpecificApplicative, that does nothing more than cause the compiler | |
| to give it a point for being more specific. That evens that score, so the compiler will | |
| pick the accumulating one if X is a Semigroup and an Applicative is asked for, because | |
| it is declared in a subobject. | |
| */ | |
| object Validation extends MonadicValidation { | |
| trait MoreSpecificApplicative[F[_]] extends Applicative[F] | |
| implicit def Applicative_Validation_for_realz[X](implicit s: Semigroup[X]): MoreSpecificApplicative[({type λ[α]=X Validation α})#λ] = | |
| new MoreSpecificApplicative[({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)) | |
| } | |
| } | |
| ) | |
| } | |
| } | |
| implicit def ListSemigroup[A]: Semigroup[List[A]] = | |
| new Semigroup[List[A]] { | |
| def op(a1: List[A], a2: List[A]) = | |
| a1 ::: a2 | |
| } | |
| /* | |
| This works the same as before: the compiler picks the higher priority | |
| impicit and you get accumulation. The result is: Validation(Left(List(7, 8))) | |
| */ | |
| def hithereagain = | |
| sequence[({type λ[α]=List[Int] Validation α})#λ, String]( | |
| list map (Validation(_)) | |
| ) | |
| /* | |
| To demonstrate what happens when a Validation is treated as a monad, I made | |
| this sequenceAsMonad method. It is the exact same implementation as Tony's | |
| original sequence, but it requires a Monad instead of an Applicative. | |
| */ | |
| def sequenceAsMonad[F[_], A](x: List[F[A]])(implicit F: Monad[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)) | |
| /* | |
| When I call this method, it passes in the Monad instance, and uses the | |
| Applicative inherited by monad, so it short-circuits. The result is: Validation(Left(List(7))) | |
| */ | |
| def hithereyetagain = | |
| sequenceAsMonad[({type λ[α]=List[Int] Validation α})#λ, String]( | |
| list map (Validation(_)) | |
| ) | |
| /* | |
| One way this makes Validation more general (and possibly also more confusing for users) | |
| is that it will still work when an Applicative is asked for but the Left type is not | |
| a Semigroup. In this case, the higher priority Applicative_Validation_for_realz does | |
| not apply at all, because X is not a Semigroup, so it picks the Monad one, which | |
| doesn't accumulate. Although Vector is a semigroup in essence, it isn't one here because | |
| we haven't defined a Semigroup instance for Vector. So a Vector will work to demonstrate: | |
| */ | |
| val listOfNonSemigroups = | |
| List(Left(Vector(7)), Left(Vector(8)), Right("abc"), Right("def")) | |
| /* | |
| Even though we are passing a Validation to a method that abstracts | |
| over Applicative, because no Semigroup is available for Vector, it | |
| picks the Applicative that makes sense more generally, which is the | |
| one supplied by Monad. This results in: Validation(Left(Vector(7))) | |
| */ | |
| def hithereonelasttime = | |
| sequence[({type λ[α]=Vector[Int] Validation α})#λ, String]( | |
| listOfNonSemigroups map (Validation(_)) | |
| ) | |
| /* | |
| This prints: | |
| Or(Left(List(7))) | |
| Validation(Left(List(7, 8))) | |
| Validation(Left(List(7))) | |
| Validation(Left(Vector(7))) | |
| */ | |
| def main(args: Array[String]) { | |
| println(hithere) | |
| println(hithereagain) | |
| println(hithereyetagain) | |
| println(hithereonelasttime) | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment