Pages

09 December 2011

Pragmatic IO - part 3

A follow-up to my previous posts about IO.

Why types and laws matter

It's embarrassing to write post after post only to find out I keep being wrong :-). While the technique I described in my last post (using StreamT) works ok, I actually don't have to use it. The traverse technique explained in EIP works perfectly, provided that:

  • we write a proper Traverse instance using foldLeft (as explained in the first part of this post)

  • we trampoline the State to avoid Stack overflows due to a long chain of flatMaps during the traversal

  • we use the right types!

Get the types right

That's the point I want to insist on today. Last evening I read the revisited WordCount example in Scalaz-seven which is like the canonical example of using the EIP ideas. Two words in the comments struck my mind: "compose" and "fuse". Indeed, one very important thing about EIP is the ability to compose Applicatives so that their actions should "fuse" during a traversal. As if they were executed in the same "for" loop!

So, when I wrote in my previous post that I needed to traverse the stream of lines several times to get the results, something had to be wrong somewhere. The types were wrong!

  1. instead of traversing with State[S, *] where * =:= IO[B], I should traverse with State[S, IO[*]]
  2. what I get back is a State[S, IO[Seq[B]]], instead of a State[S, Seq[IO[B]]
  3. this matters because passing in an initial state then returns IO[Seq[B]] instead of Seq[IO[B]]

Exactly what I want, without having to sequence anything.

Use the laws

Not only I get what I want, but also it is conceptually right as the result of an important traverse law:

  traverse(f compose g) == traverse(f) compose traverse(g)

That "fusion" law guarantees that composing 2 effects can be fused, and executed in only one traversal. It's worth instantiating f and g to make that more concrete:

  // what to do with the line and line number
  def importLine(i: Int, l: String): (Int, IO[Unit]) =
    (i, storeLine(l) >>= println("imported line "+i))

  // `g` keeps track of the line number
  val g : String => State[Int, String] =
    (s: String) => state((i: Int) => (i+1, s))

  // `f` takes the current line/line number and do the import/reporting
  val f : State[Int, String] => State[Int, IO[Unit]] =
    st => state((i: Int) => importLine(st(i)))

  // `f compose g` fuses both actions
  val f_g: String => State[Int, IO[Unit]] = f compose g

I'm really glad that I was able to converge on established principles. Why couldn't I see this earlier?

Scala and Scalaz-seven might help

In retrospect, I remember what led me astray. When I realized that I had to use a State transformer with a Trampoline, I just got scared by the Applicative instance I had to provide. Its type is:

  /**
   * Here we want M1 to `Trampoline` and M2 to be `IO`
   */
  implicit def StateTMApplicative[M1[_]: Monad, S, M2[_] : Applicative] =
    Applicative.applicative[({type l[a] = StateT[M1, S, M2[a]]})#l]

I also need some Pure and Apply instances in scope:

  implicit def StateTMApply[M1[_]: Monad, S, M2[_] : Applicative] =
    new Apply[({type l[a]=StateT[M1, S, M2[a]]})#l] {
      def apply[A, B](f: StateT[M1, S, M2[A => B]], a: StateT[M1, S, M2[A]]) =
        f.flatMap(ff => a.map(aa => aa <*> ff))
    }

  implicit def StateTMPure[M1[_] : Pure, S, M2[_] : Pure] =
    new Pure[({type l[a]=StateT[M1, S, M2[a]]})#l] {
      def pure[A](a: => A) = stateT((s: S) => (s, a.pure[M2]).pure[M1])
    }

Once it's written, it may not seem so hard but I got very confused trying to get there. How can it be made easier? First, we could have better type annotations for partial type application, like:

  // notice the * instead of the "type l" trick
  implicit def StateTMApplicative[M1[_]: Monad, S, M2[_] : Applicative] =
    Applicative.applicative[StateT[M1, S, M2[*]]]

  implicit def StateTMApply[M1[_]: Monad, S, M2[_] : Applicative] =
    new Apply[StateT[M1, S, M2[*]]] {
      def apply[A, B](f: StateT[M1, S, M2[A => B]], a: StateT[M1, S, M2[A]]) =
        f.flatMap(ff => a.map(aa => aa <*> ff))
    }

  implicit def StateTMPure[M1[_] : Pure, S, M2[_] : Pure] =
    new Pure[StateT[M1, S, M2[*]]] {
      def pure[A](a: => A) = stateT((s: S) => (s, a.pure[M2]).pure[M1])
    }

And with a better type inference, the first definition could be even be (we can always dream :-)):

  implicit def StateTMApplicative[M1[_]: Monad, S, M2[_] : Applicative]:
    Applicative[StateT[M1, S, M2[*]]] = Applicative.applicative

Which means that it may even be removed, just import Applicative.applicative!

Actually Scalaz-seven might help by:

  • providing those instances out-of-the box

  • even better, provide combinators to create those instances easily. That's what the compose method does

  • give even better type inference. Look at the traverseU method here, no type annotations Ma!

Now that the fundamentals are working ok for my application, I can go back to adding features, yay!

No comments: