Friday, September 13, 2013

A realistic use case for applicative functors

But why would you do that??

Say you have a collection of document IDs and you are going to retrieve
the documents from the database. Not right away, but someday. You are
writing a function that defines the operation of retrieving a sequence
of documents.

So there's such a thing as an DbTask, which says "If you give me a
database, I can do something with it." In our case we wind up with an
DbTask[Seq[Document]], which says, "If you give me a database, I can
give you this collection of documents you want."

If you're wondering why we would abstract the decision of "what to do
with a database" from actually doing stuff with a database, check out
Runar's presentation about purely functional I/O.

Now you want a DbTask that retrieves a whole sequence of documents, based on a sequence of IDs. Can we build this without writing anything new in the DbTask classes?

    def retrieveAll: Seq[DocId] => DbTask[Seq[Document]] = ???

How do we implement it? Say we have a primitive operation for retrieving
one document.

    def retrieveOne: DocId => DbTask[Document] = // already implemented by someone else

If we can retrieve one, we can retrieve them all! Let's do that:

    (docIds : Seq[DocId]) => docIds map retrieveOne

That doesn't give us quite what we want. We turned each DocId into a
retrieval DbTask[Document], so we have a sequence of single
operations.

    Seq[DocId] => Seq[DbTask[Document]]

How do we turn that inside out, to get to a DbTask[Seq[Document]]?

To construct a sequence inside an DbTask out of a bunch of
DbTasks, we'll use these pieces:
  • each DbTask[Document]
  • an empty sequence, Seq()
  • a way to add a document into a sequence, which is the +: (prepend) method on Seq.
  • a way to put each of these last two into a DbTask. It's sort of a factory method.[1]
        DbTask(x: X) => DbTask[X]
  • a way to plug things together within DbTasks. Call this apply. It's a method on DbTask that takes a wrapped function (microwave in a tortilla) and spits out a wrapped result (hot food in a tortilla).
    DbTask[X] { ...
       def apply(f: DbTask[X => Y]) : DbTask[Y]
    }

We have the first three easily enough. The last two together form the
qualifying characteristics for an applicative functor. Applicative
functors let us plug the things inside them together, like building a
ship in a bottle.

Let's use these five pieces to turn our DbTask[Seq[_]] into a
Seq[DbTask[_]]. Fold up the sequence of DbTasks, starting
with a DbTask containing an empty sequence, and then prepending each
item into the sequence, all within the DbTask.

  def turnInsideOut[X]: Seq[DbTask[X]] => DbTask[Seq[X]] = 
  { seqOfOps =>
      val wrappedEmptyDbTask[Seq[X]] = DbTask of Seq.empty[X]
      def wrappedPrependDbTask of((b: Seq[X])=>(a:X)=> a +: b)

      seqOfOps.foldRight(wrappedEmpty){(e, soFar) =>
           e apply (soFar apply wrappedPrepend)}
  }

Note that prepend needs two arguments, and they're applied one at
a time. All of the operations take place within the bottle.

    def retrieveAll = { ids =>
       turnInsideOut( ids map DbTask.retrieveOne)
    }

The code for this example is on github. I'm not sure it's good, so I put it on the internet and you all can correct me.

The point is: applicative functors let you build up what you
want to do, within a context. Think of the context as a bottle, or a
tortilla, whatever you like. In this example, the purpose of that
context is to hold operations on a database for later execution.



The example assembles singles into a sequence. The same ideas can
assemble them into tuples, arrays, etc. Libraries like scalaz abstract
the turnInsideOut functionality so you don't have to write it yourself.

Applicative functors are one small functional recipe for building things that combine in many ways. Look for more of these on this blog in the future.

------------
[1] FP people call this X => O[X] "pure" or "return".

No comments:

Post a Comment