Skip to content

Instantly share code, notes, and snippets.

@sadache
Created September 5, 2012 22:14
Show Gist options
  • Save sadache/3646092 to your computer and use it in GitHub Desktop.
Save sadache/3646092 to your computer and use it in GitHub Desktop.
Applicatives are too restrictive, breaking Applicatives and introducing Functional Builders

This post aims to document a practical design implementation we came up with when designing some APIs in Scala. Of course the concept is not Scala specific and applies to other functional languages.

If you don't want to go into the full introduction, this post talks about how Applicatives are too restrictive and breaking them into two independent components can be interesting for Contravariant and Invariant Functors. Jump to implementation attached.

We are taking JSON serialization/deserialization as a motivating example.

JsValue is the name of the type that represents the JSON AST. What we need is to be able to read a JsValue and produce an A:

trait Reads[A]{

  def reads(json:JsValue):JsResult[A]

}

Implementing Reads interface provides a way to deserialize a JSON value into an A (and here giving you an opportunity to fail with JsError which is a valid JsResult).

Writing JSON we have its dual:

trait Writes[A]{

  def writes(a:A):JsValue

}

Implementing Writes provides a way to write JSON for a type A.

We have also a type that represents both, being able to read and write a JSON for an A type:

trait Format[A] extends Reads[A] with Writes[A]

Reads happens to be a monad, which is interesting but we are not going to talk about this much more. What we are interested in is having a simple way of combining JSON serializers, meaning if we have

val readAge: Reads[Int]
val readName: Reads[String]

it could be very interesting to have a Reads[(Int,String)] or even better, a Reads[User] having for instance case class User(age:Int, name:String)

This is actually quite easy to achieve with Applicative Functors. To simplify, Applicative Functors are Functors (having the map or fmap function implemented) together with the Applicative part which adds the power we need to achieve the combination we want to do. Explaining Applicative Functors is out of scope and there is a lot of material on the web explaining these.

val readUser: Reads[User] = readAge.and(readName).apply(User)

// or using symbolic methods:

val readUser: Reads[User] = (readAge ~ readName).apply(User)

This composition simply means that if we have two readers of two different types, they could read from the same JSON and provide two values which I can pack into another type (User here).

Now that we solved our problem of combining the Reads with Applicative Functors, wouldn't it be even more interesting if we could combine similarly the Writes? Having:

val writeAge: Writes[Int]
val writeName: Writes[String]

then we could have a Writes[User], or can we?

Almost. If we have two writers (capable of writing two different JsValue from two different types, Int and String here) then we end up with two JsValues, and there is no way of merging these into one, except if they are both JsObjects.

Let's do a new type that only writes JsObject

trait OWrites[A] extends Writes[A]{

  def writes(a:A):JsObject

}

Now it makes sense to have one writer out of our two writes above ( writeAge, writeName) by simply merging the resulting objects. So logically it makes sense, except that we can't use our Applicative based builder since an OWrites is not a Functor at all!

Actually our OWrite is, naturally, the dual of a Functor, a CoFunctor (or Contravariant). Put simply, this means that to change the A type to B in OWrites we should provide a function backwards from B => A. This makes a lot of sense since if we know how to write an A and we know how to transform a B to A then we can write a B. Instead of fmap we got a contramap

def contramap[B](B => A):OWrite[B]

So or status here, we know how to transform the type of OWrites, we know how to merge two OWrites but all of that doesn't help us to use the builder which based on an Applicative Functor.

What if we split our problem into two components. Let's introduce a new type that we call FunctionalCanBuild:

trait FunctionalCanBuild[M[_]]{

  def apply[A,B](ma:M[A],mb:M[B]):M[(A,B)]

}

Meaning for a given container M, we can some how compose two instances into one with the tuple of the type parameters. So for Reads it will be:

val fpReads = new FunctionalCanBuild[Reads]{

  // read the same value using the two readers and return a tuple
  def apply[A,B](ra:Reads[A],rb:Reads[B]):Reads[(A,B)] = ...

}

and for the OWrites it will make:

val fpOwrites = new FunctionalCanBuild[OWrites]{

  //write two objects using the two writers and merge the two resulting JsObjects
  def apply[A,B](oa:OWrites[A],ob:OWrites[B]):OWrites[(A,B)] = ...

}

But that gets us only half way through what we want to achieve. What we want is actually a Reads and OWrites of User and not tuple of Int, String.

For the Reads[(Int,String)] we can solve this problem easily using the fmap function of Functor. But even for OWrites[(Int,String)] it is easy, OWrites is a CoFunctor (or ContraVariant) and we can use contramap to get back from (Int,String) to User.

So it seems that separating the problem into two sub problems is working for us. But what about format? Format is not a Functor and a Contra, it is actually Invariant. This means that it need functions in both directions, A => B and B => A to transform the A type to B.

Like the OWrites we will use OFormat:

trait OFormat[A] extends OWrites[A] with Reads[A]

Now we can implement FunctionalCanBuild[OFormat] :

val fbf: FunctionalCanBuild[OFormat] = new FunctionalCanBuild[OFormat]{

  // merge reads and writes
  def apply[A,B](fa: OFormat[A], fb: OFormat[B]): OFormat[(A,B)] = ...

}

and once we have the OFormat[(Int,String)] we can transform it to a User by using inmap and passing (Int,String) => User and User => (Int,String).

This led us to an API that is capable of building compositions for Functors (Reads), CoFunctors (Writes) and Invariant (Format). Using the FunctionBuilder type class and the correct Variance we can offer a nice unified API for composing different abstractions.

Bottom Line: By breaking Applicatives into two independent components (FunctionalCanBuild and Variance we could use them for more than Functors, ie Covariant and Invariant Functors.

ps: FunctionalCanBuild[M[_]] may look like a monoid but it is not exactly one.

ps2: This is a work I did together with @mandubian and other Zenexity guys

ps3: The Format,Reads and Writes approach is copied and adapted from @debasishg on sjson

ps4: This work is integrated into Play's included JSON library

class FunctorOps[M[_],A](ma:M[A])(implicit fu:Functor[M]){
def fmap[B](f: A => B):M[B] = fu.fmap(ma,f)
}
class ApplicativeOps[M[_],A](ma:M[A])(implicit a:Applicative[M]){
def ~>[B](mb: M[B]):M[B] = a(a(a.pure((_:A) => (b:B) => b), ma),mb)
def andThen[B](mb: M[B]):M[B] = ~>(mb)
def <~[B](mb: M[B]):M[A] = a(a(a.pure((a:A) => (_:B) => a), ma),mb)
def provided[B](mb: M[B]):M[A] = <~(mb)
def <~>[B,C](mb: M[B])(implicit witness: <:<[A,B => C]):M[C] = apply(mb)
def apply[B,C](mb: M[B])(implicit witness: <:<[A,B => C]):M[C] = a(a.map(ma,witness),mb)
}
class FunctionalBuilderOps[M[_],A](ma:M[A])(implicit fcb:FunctionalCanBuild[M]){
def ~[B](mb:M[B]):FunctionalBuilder[M]#CanBuild2[A,B] = {
val b = new FunctionalBuilder(fcb)
new b.CanBuild2(ma,mb)
}
def and[B](mb:M[B]):FunctionalBuilder[M]#CanBuild2[A,B] = this.~(mb)
}
trait Applicative[M[_]]{
def pure[A](a:A):M[A]
def map[A,B](m:M[A], f: A => B):M[B]
def apply[A,B](mf:M[A => B], ma:M[A]):M[B]
}
class AlternativeOps[M[_],A](alt1:M[A])(implicit a:Alternative[M]){
def |[B >: A](alt2 :M[B]):M[B] = a.|(alt1,alt2)
def or[B >: A](alt2 :M[B]):M[B] = |(alt2)
}
trait Alternative[M[_]]{
def app:Applicative[M]
def |[A,B >: A](alt1: M[A], alt2 :M[B]):M[B]
def empty:M[Nothing]
//def some[A](m:M[A]):M[List[A]]
//def many[A](m:M[A]):M[List[A]]
}
trait FunctionalCanBuild[M[_]]{
def apply[A,B](ma:M[A], mb:M[B]):M[A ~ B]
}
trait Variant[M[_]]
trait Functor[M[_]] extends Variant[M]{
def fmap[A,B](m:M[A], f: A => B): M[B]
}
trait InvariantFunctor[M[_]] extends Variant[M]{
def inmap[A,B](m:M[A], f1: A => B, f2: B => A):M[B]
}
trait ContravariantFunctor[M[_]] extends Variant[M]{
def contramap[A,B](m:M[A], f1: B => A):M[B]
}
case class ~[A,B](_1:A,_2:B)
class FunctionalBuilder[M[_]](canBuild:FunctionalCanBuild[M]){
class CanBuild2[A1,A2](m1:M[A1], m2:M[A2]){
def ~[A3](m3:M[A3]) = new CanBuild3(canBuild(m1, m2), m3)
def and[A3](m3:M[A3]) = this.~(m3)
def apply[B](f: (A1,A2) => B)(implicit fu: Functor[M]): M[B] =
fu.fmap[A1 ~ A2, B](canBuild(m1, m2), {case a1 ~ a2 => f(a1, a2)} )
def apply[B](f: B => (A1,A2))(implicit fu: ContravariantFunctor[M]): M[B] =
fu.contramap(canBuild(m1, m2), (b: B) => { val (a1, a2) = f(b); new ~(a1, a2)})
def apply[B](f1: (A1,A2) => B, f2: B => (A1,A2))(implicit fu: InvariantFunctor[M]): M[B] =
fu.inmap[A1 ~ A2, B](
canBuild(m1, m2), {case a1 ~ a2 => f1(a1, a2)},
(b:B) => { val (a1, a2) = f2(b); new ~(a1, a2)}
)
def join[A >: A1](implicit witness1: <:<[A, A1], witness2: <:<[A, A2], fu: ContravariantFunctor[M]): M[A] =
apply[A]( (a: A) => (a: A1, a: A2) )(fu)
def tupled(implicit v:Variant[M]): M[(A1, A2)] = v match {
case fu: Functor[M] => apply{ (a1: A1, a2: A2) => (a1, a2) }(fu)
case fu: ContravariantFunctor[M] => apply[(A1, A2)]{ (a: (A1, A2)) => (a._1, a._2) }(fu)
case fu: InvariantFunctor[M] => apply[(A1, A2)]({ (a1: A1, a2: A2) => (a1, a2) }, { (a: (A1, A2)) => (a._1, a._2) })(fu)
}
}
class CanBuild3[A1,A2,A3](m1:M[A1 ~ A2], m2:M[A3]){
def ~[A4](m3:M[A4]) = new CanBuild4(canBuild(m1, m2), m3)
def and[A3](m3:M[A3]) = this.~(m3)
def apply[B](f: (A1,A2,A3) => B)(implicit fu:Functor[M]):M[B] = /*null.asInstanceOf[M[B]]*/
fu.fmap[A1 ~ A2 ~ A3, B](canBuild(m1, m2), { case a1 ~ a2 ~ a3 => f(a1, a2, a3) })
def apply[B](f: B => (A1,A2,A3))(implicit fu:ContravariantFunctor[M]):M[B] = /*null.asInstanceOf[M[B]]*/
fu.contramap(canBuild(m1, m2), (b: B) => { val (a1, a2, a3) = f(b); new ~(new ~(a1, a2), a3)})
def apply[B](f1: (A1,A2,A3) => B, f2: B => (A1,A2,A3))(implicit fu:InvariantFunctor[M]):M[B] = /*null.asInstanceOf[M[B]]*/
fu.inmap[A1 ~ A2 ~ A3, B](
canBuild(m1, m2), {case a1 ~ a2 ~ a3 => f1(a1, a2, a3)},
(b:B) => { val (a1, a2, a3) = f2(b); new ~(new ~(a1, a2), a3) }
)
def join[A >: A1](implicit witness1: <:<[A, A1], witness2: <:<[A, A2], witness3: <:<[A, A3], fu: ContravariantFunctor[M]): M[A] =
apply[A]( (a: A) => (a: A1, a: A2, a: A3) )(fu)
def tupled(implicit v:Variant[M]): M[(A1, A2, A3)] = v match {
case fu: Functor[M] => apply{ (a1: A1, a2: A2, a3: A3) => (a1, a2, a3) }(fu)
case fu: ContravariantFunctor[M] => apply[(A1, A2, A3)]{ (a: (A1, A2, A3)) => (a._1, a._2, a._3) }(fu)
case fu: InvariantFunctor[M] => apply[(A1, A2, A3)]({ (a1: A1, a2: A2, a3: A3) => (a1, a2, a3) }, { (a: (A1, A2, A3)) => (a._1, a._2, a._3) })(fu)
}
}
class CanBuild4[A1,A2,A3,A4](m1:M[A1 ~ A2 ~ A3], m2:M[A4]){
def ~[A5](m3:M[A5]) = new CanBuild5(canBuild(m1,m2),m3)
def and[A5](m3:M[A5]) = this.~(m3)
def apply[B](f: (A1,A2,A3,A4) => B)(implicit fu:Functor[M]):M[B] =
fu.fmap[A1 ~ A2 ~ A3 ~ A4, B](canBuild(m1, m2), { case a1 ~ a2 ~ a3 ~ a4 => f(a1, a2, a3, a4) })
def apply[B](f: B => (A1,A2,A3, A4))(implicit fu:ContravariantFunctor[M]):M[B] =
fu.contramap(canBuild(m1, m2), (b: B) => { val (a1, a2, a3, a4) = f(b); new ~(new ~(new ~(a1, a2), a3), a4)})
def apply[B](f1: (A1,A2,A3,A4) => B, f2: B => (A1,A2,A3,A4))(implicit fu:InvariantFunctor[M]):M[B] =
fu.inmap[A1 ~ A2 ~ A3 ~ A4, B](
canBuild(m1, m2), {case a1 ~ a2 ~ a3 ~ a4 => f1(a1, a2, a3, a4)},
(b:B) => { val (a1, a2, a3, a4) = f2(b); new ~(new ~(new ~(a1, a2), a3), a4) }
)
def join[A >: A1](implicit witness1: <:<[A, A1], witness2: <:<[A, A2], witness3: <:<[A, A3], witness4: <:<[A, A4], fu: ContravariantFunctor[M]): M[A] =
apply[A]( (a: A) => (a: A1, a: A2, a: A3, a: A4) )(fu)
def tupled(implicit v:Variant[M]): M[(A1, A2, A3, A4)] = v match {
case fu: Functor[M] => apply{ (a1: A1, a2: A2, a3: A3, a4: A4) => (a1, a2, a3, a4) }(fu)
case fu: ContravariantFunctor[M] => apply[(A1, A2, A3, A4)]{ (a: (A1, A2, A3, A4)) => (a._1, a._2, a._3, a._4) }(fu)
case fu: InvariantFunctor[M] => apply[(A1, A2, A3, A4)]({ (a1: A1, a2: A2, a3: A3, a4: A4) => (a1, a2, a3, a4) }, { (a: (A1, A2, A3, A4)) => (a._1, a._2, a._3, a._4) })(fu)
}
}
class CanBuild5[A1,A2,A3,A4,A5](m1:M[A1 ~ A2 ~ A3 ~ A4], m2:M[A5]){
}
}
object `package` {
implicit def toAlternativeOps[M[_],A](a:M[A])(implicit app:Alternative[M]):AlternativeOps[M,A] = new AlternativeOps(a)
implicit def toApplicativeOps[M[_],A](a:M[A])(implicit app:Applicative[M]):ApplicativeOps[M,A] = new ApplicativeOps(a)
implicit def toFunctionalBuilderOps[M[_],A](a:M[A])(implicit fcb:FunctionalCanBuild[M]) = new FunctionalBuilderOps[M,A](a)(fcb)
implicit def functionalCanBuildApplicative[M[_]](implicit app:Applicative[M]):FunctionalCanBuild[M] = new FunctionalCanBuild[M] {
def apply[A,B](a: M[A], b:M[B]):M[A~B] = app.apply(app.map[A, B => A ~ B](a, a => ((b:B) => new ~(a,b))),b)
}
implicit def functorOption:Functor[Option] = new Functor[Option] {
def fmap[A,B](a:Option[A], f: A => B):Option[B] = a.map(f)
}
implicit def applicativeOption:Applicative[Option] = new Applicative[Option]{
def pure[A](a:A):Option[A] = Some(a)
def map[A,B](m:Option[A], f: A => B):Option[B] = m.map(f)
def apply[A,B](mf:Option[A => B], ma: Option[A]):Option[B] = mf.flatMap(f => ma.map(f))
}
}
val userReads = {
(Reads.at(JsPath \ "name")(minLength[String](5)) and
Reads.at(JsPath \ "age")(min(40))) apply (User)
}
val userWrites = {
(Writes.at[String](JsPath \ "name") and
Writes.at[Int](JsPath \ "age")) apply (unlift(User.unapply))
}
val userFormats = {
(Format.at(JsPath \ "name")(Format(minLength[String](5), of[String])) and
Format.at(JsPath \ "age")(Format(min(40), of[Int])))(User, unlift(User.unapply))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment