This is a pretty tough question - I also read these posts and wondered what the terrifying Scala implementation would look like, but I never tried it. So I'm going to answer in detail, but please note that the following is extremely incompatible (Saturday morning) and does not necessarily represent the cleanest way to do this in Scala.
It's probably best to start by defining some types from the first message in the series :
import scala.language.higherKinds import scalaz._, Scalaz._ case class Const[M, A](mo: M) sealed trait Sum[F[_], G[_], A] object Sum { def inL[F[_], G[_], A](l: F[A]): Sum[F, G, A] = InL(l) def inR[F[_], G[_], A](r: G[A]): Sum[F, G, A] = InR(r) } case class InL[F[_], G[_], A](l: F[A]) extends Sum[F, G, A] case class InR[F[_], G[_], A](r: G[A]) extends Sum[F, G, A]
And a couple from the blog itself :
case class Embed[F[_], A](out: A) case class ProductF[F[_[_], _], G[_[_], _], B[_], A](f: F[B, A], g: G[B, A])
If you have worked above, you should have an idea of what FixF should look FixF :
case class FixF[F[f[_], _], A](out: F[({ type L[x] = FixF[F, x] })#L, A])
It turns out this is a little too strict, so instead we will use the following:
class FixF[F[f[_], _], A](v: => F[({ type L[x] = FixF[F, x] })#L, A]) { lazy val out = v override def toString = s"FixF($out)" }
Now suppose we want to implement lists as “a fixed second-order point of polynomial functors,” as in a blog. We can start by defining some useful aliases:
type UnitConst[x] = Const[Unit, x] type UnitConstOr[F[_], x] = Sum[UnitConst, F, x] type EmbedXUnitConstOr[F[_], x] = ProductF[Embed, UnitConstOr, F, x] type MyList[x] = FixF[EmbedXUnitConstOr, x]
And now we can determine the Scala version of the examples from the message:
val foo: MyList[String] = new FixF[EmbedXUnitConstOr, String]( ProductF[Embed, UnitConstOr, MyList, String]( Embed("foo"), Sum.inL[UnitConst, MyList, String](Const()) ) ) val baz: MyList[String] = new FixF[EmbedXUnitConstOr, String]( ProductF[Embed, UnitConstOr, MyList, String]( Embed("baz"), Sum.inL[UnitConst, MyList, String](Const()) ) ) val bar: MyList[String] = new FixF[EmbedXUnitConstOr, String]( ProductF[Embed, UnitConstOr, MyList, String]( Embed("bar"), Sum.inR[UnitConst, MyList, String](baz) ) )
This looks the way we expected, given the Haskell implementation:
scala> println(foo) FixF(ProductF(Embed(foo),InL(Const(())))) scala> println(bar) FixF(ProductF(Embed(bar),InR(FixF(ProductF(Embed(baz),InL(Const(())))))))
Now we need instances of the type class. Most of them are pretty simple:
implicit def applicativeConst[M: Monoid]: Applicative[ ({ type L[x] = Const[M, x] })#L ] = new Applicative[({ type L[x] = Const[M, x] })#L] { def point[A](a: => A): Const[M, A] = Const(mzero[M]) def ap[A, B](fa: => Const[M, A])(f: => Const[M, A => B]): Const[M, B] = Const(f.mo |+| fa.mo) } implicit def applicativeEmbed[F[_]]: Applicative[ ({ type L[x] = Embed[F, x] })#L ] = new Applicative[({ type L[x] = Embed[F, x] })#L] { def point[A](a: => A): Embed[F, A] = Embed(a) def ap[A, B](fa: => Embed[F, A])(f: => Embed[F, A => B]): Embed[F, B] = Embed(f.out(fa.out)) } implicit def applicativeProductF[F[_[_], _], G[_[_], _], B[_]](implicit fba: Applicative[({ type L[x] = F[B, x] })#L], gba: Applicative[({ type L[x] = G[B, x] })#L] ): Applicative[({ type L[x] = ProductF[F, G, B, x] })#L] = new Applicative[({ type L[x] = ProductF[F, G, B, x] })#L] { def point[A](a: => A): ProductF[F, G, B, A] = ProductF(fba.point(a), gba.point(a)) def ap[A, C](fa: => ProductF[F, G, B, A])( f: => ProductF[F, G, B, A => C] ): ProductF[F, G, B, C] = ProductF(fba.ap(fa.f)(ff), gba.ap(fa.g)(fg)) }
Including the applicative instance for FixF itself:
implicit def applicativeFixF[F[_[_], _]](implicit ffa: Applicative[({ type L[x] = F[({ type M[y] = FixF[F, y] })#M, x] })#L] ): Applicative[({ type L[x] = FixF[F, x] })#L] = new Applicative[({ type L[x] = FixF[F, x] })#L] { def point[A](a: => A): FixF[F, A] = new FixF(ffa.pure(a)) def ap[A, B](fa: => FixF[F, A])(f: => FixF[F, A => B]): FixF[F, B] = new FixF(ffa.ap(fa.out)(f.out)) }
We will also define a terminal transformation:
implicit def terminal[F[_], M: Monoid]: F ~> ({ type L[x] = Const[M, x] })#L = new (F ~> ({ type L[x] = Const[M, x] })#L) { def apply[A](fa: F[A]): Const[M, A] = Const(mzero[M]) }
But now we have a problem. We really need extra laziness, so we cheat a little:
def applicativeSum[F[_], G[_]]( fa: Applicative[F], ga: => Applicative[G], nt: G ~> F ): Applicative[({ type L[x] = Sum[F, G, x] })#L] = new Applicative[({ type L[x] = Sum[F, G, x] })#L] { def point[A](a: => A): Sum[F, G, A] = InR(ga.point(a)) def ap[A, B](x: => Sum[F, G, A])(f: => Sum[F, G, A => B]): Sum[F, G, B] = (x, f) match { case (InL(v), InL(f)) => InL(fa.ap(v)(f)) case (InR(v), InR(f)) => InR(ga.ap(v)(f)) case (InR(v), InL(f)) => InL(fa.ap(nt(v))(f)) case (InL(v), InR(f)) => InL(fa.ap(v)(nt(f))) } } implicit def myListApplicative: Applicative[MyList] = applicativeFixF[EmbedXUnitConstOr]( applicativeProductF[Embed, UnitConstOr, MyList]( applicativeEmbed[MyList], applicativeSum[UnitConst, MyList]( applicativeConst[Unit], myListApplicative, terminal[MyList, Unit] ) ) )
Maybe there is a way to make it work with Scalaz 7 encoding applications without hacking, but if there is, I do not want to spend Saturday to figure it out.
So, this sucks, but at least now we can check our work:
scala> println((foo |@| bar)(_ ++ _)) FixF(ProductF(Embed(foobar),InL(Const(()))))
This is exactly what we wanted.